C++ Set、Map容器基础语法指南

C++ Set、Map容器基础语法指南

Set:

set 是 STL 中的有序关联容器，底层采用红黑树实现，存储 唯一键值 并按 严格弱序规则自动排序，查找时间复杂度为 O(log n)，存储不重复元素，且元素值不可修改（因会破坏红黑树结构）。

• 构造方式

• 元素插入：

// 方式1：插入值（返回pair<iterator, bool>）
auto [iter, success] = s.insert(42);

// 方式2：构造元素（C++11起）
s.emplace("hello");  // 避免临时对象构造

// 方式3：插入范围
vector<int> vec{7, 2, 9};
s.insert(vec.begin(), vec.end());

• 元素访问：

// 方式1：迭代器遍历
for(auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
}

// 方式2：范围查询
auto lower = s.lower_bound(20);  // 首个 >=20 的元素
auto upper = s.upper_bound(50);   // 首个 >50 的元素
for(auto it=lower; it!=upper; ++it) {
    // 处理[20,50]区间元素
}
// 找首个 >=20 的元素
auto lower = s.lower_bound(20);  

// 找首个 >20 的元素  
auto upper = s.upper_bound(20);  

• 元素删除：

// 方式1：按值删除（返回删除数量）
size_t count = s.erase(42);

// 方式2：按迭代器删除
auto it = s.find(30);
if(it != s.end()) s.erase(it);

// 方式3：按范围删除
s.erase(s.lower_bound(10), s.upper_bound(20));

Multiset:

multiset 是 STL 中的有序关联容器，允许 重复元素存储，底层采用红黑树实现，保持元素按严格弱序规则自动排序，查找时间复杂度为 O(log n)。

• 构造方式

// 默认构造（升序）
multiset<string> ms1;  // 等同于 multiset<int, less<int>> ms1;

// 初始化列表构造（允许重复）
multiset<char> ms2{'a', 'a', 'b'};  // 存储 a,a,b

// 自定义排序规则（降序）
multiset<int, greater<int>> ms3;

// 迭代器范围构造
vector<int> vec{5,3,5,2};
multiset<int> ms4(vec.begin(), vec.end());  // 2,3,5,5

• 特殊插入方式

multiset<int> ms;
ms.insert(5);    // 常规插入
ms.insert(5);    // 再次插入相同值
ms.emplace(5);   // 高效构造插入（C++11）

// 批量插入
vector<int> vec{5,5,5};
ms.insert(vec.begin(), vec.end());  // 插入3个5

• 重复元素访问

// 方式1：遍历所有元素
for(const auto& val : ms) { // const限制红黑树不被修改，&表示引用，仅记录内存地址
    cout << val << " ";  // 输出所有元素（含重复）
}

// 方式2：范围查询（推荐方式）
auto [low, high] = ms.equal_range(5);   // 返回一个pair，里面有两个迭代器，第一个是lower_bound，第二个是upper_bound
for(auto it=low; it!=high; ++it) {
    cout << *it << " ";  // 输出所有5
}

// 方式3：计数查询
cout << "5出现次数：" << ms.count(5); 

• 选择性删除

// 删除所有5（返回删除数量）
size_t deleted = ms.erase(5);  

// 删除第一个5
auto it = ms.find(5);
if(it != ms.end()) ms.erase(it);

// 删除第2到第4个5（需配合equal_range）
auto [first, last] = ms.equal_range(5);
if(std::distance(first, last) >= 4) {   // distance()存在于头文件<iteator>,用于计算两个迭代器之间的元素数量
    ms.erase(std::next(first), std::next(first,3)); // next()生成迭代器的第N个后继位置副本,第二个参数默认为1
}                                                   // 存在于头文件<iteator>

Unordered_set:

unordered_set 是 C++11 引入的无序关联容器，基于哈希表实现，用于存储 唯一元素（无重复值），具有 O(1) 平均时间复杂度 的查找特性。

• 构造方式

• 元素操作

• 容量查询

• 容量管理

s.clear();        // 清空所有元素
s.swap(other);    // 与另一个 unordered_set 交换内容

• 遍历器遍历

for(auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " "; 
}

// C++11 范围循环
for(const auto& num : s) {
    cout << num << " ";
}

Map:

map 是 C++ STL 中的 有序关联容器，以 红黑树 实现，存储 唯一键值对（Key-Value Pair），支持按键自动排序，查找时间复杂度为 O(log n)。

• 容器声明

#include <map>  
using namespace std;  

// 基础声明：键类型string，值类型int，默认按键升序排列
map<string, int> m1;  

// 自定义排序规则：按键长度降序
struct LengthCompare {
    bool operator()(const string& a, const string& b) const {
        return a.length() > b.length(); 
    }
};
map<string, int, LengthCompare> m2; 

• 插入元素

• 访问元素

// 安全访问：检查是否存在
auto it = m1.find("apple");
if(it != m1.end()) {
    cout << it->second; // 输出值
}

// 直接访问（风险：可能插入默认值）
int count = m1["grape"]; // 若不存在，插入{grape,0}

// C++17 结构化绑定遍历
for(const auto& [key, value] : m1) {
    cout << key << " : " << value << endl;
}

• 关键成员函数

Multimap:

multimap 是 STL 中的 有序关联容器，允许 重复键（Key） 存在，底层基于红黑树实现，保持键按严格弱序规则自动排序。每个键关联一个值（Value），形成键值对集合。

• 容器声明

#include <map>  // 与 map 共用头文件
using namespace std;

// 基础声明：键类型 string，值类型 int，默认按键升序排列
multimap<string, int> mm1;  

// 自定义排序规则：按键长度降序
struct KeyLengthCompare {
    bool operator()(const string& a, const string& b) const {
        return a.length() > b.length();
    }
};
multimap<string, int, KeyLengthCompare> mm2;

• 元素插入

• 元素遍历

// 遍历所有元素（C++17 结构化绑定）
for(const auto& [key, value] : mm1) {
    cout << key << " => " << value << endl;
}

// 查找特定键的起始范围
auto range = mm1.equal_range("apple");
for(auto it = range.first; it != range.second; ++it) {
    cout << it->second << endl; // 输出所有 "apple" 对应的值
}

• 关键函数

Unordered_map:

unordered_map 是 C++11 引入的 哈希表实现的无序关联容器，存储唯一键值对，提供 O(1) 平均时间复杂度 的快速查找，适合高频查找但无需排序的场景。

• 构造方式

unordered_map<string, int> um1;     // 默认构造
unordered_map<string, int> m2{      // 初始化列表构造
    {"apple", 5}, 
    {"banana", 3},
    {"orange", 4}
};
unordered_map<string, int> m3(m2);  // 拷贝构造，深拷贝所有元素
    // 迭代器构造
vector<pair<string, int>> vec{{"a",1}, {"b",2}};    // 迭代器构造
unordered_map<string, int> m5(vec.begin(), vec.end());

• 查找与遍历

// 查找元素
auto it = um1.find("grape");
if(it != um1.end()) {
    cout << it->second << endl;  // 输出值
}

// C++17 结构化绑定遍历
for(const auto& [key, value] : um1) {
    cout << key << " => " << value << endl;
}

• 基本函数