C++ set和map

一、关联式容器

1.1 键值对

1.1.1 概念

1.1.2 pair

1.2 树形结构的关联式容器

二、set

2.1 set 的介绍

2.2 set 的使用

2.2.1 set 的构造

2.2.2 set 的迭代器

2.2.3 set 的容量操作

2.2.4 set 的修改操作

2.2.5 set 的查找操作

三、multiset

3.1 multiset 的介绍

3.2 multiset 的使用

四、map

4.1 map 的介绍

4.2 map 的使用

4.2.1 map 的构造

4.2.2 map 的迭代器

4.2.3 map 的容量与元素访问

4.2.4 map 的修改操作

4.2.5 map 的查找操作

五、multimap

5.1 multimap 的介绍

5.2 multimap 的使用

一、关联式容器

序列式容器（如vector、list、deque等）是一种按照线性顺序存储元素的数据结构，元素按顺序存储，查找需遍历（O(n)）。适合需维护插入顺序、频繁随机访问的情况。

关联式容器（如 set、map,、unordered_set、unordered_map）用于存储键值对（Key-Value Pairs），通过键（Key）组织元素，不关心插入顺序。内部使用红黑树（有序）或哈希表（无序）实现，查找/插入/删除平均 O(log n)（树结构）或 O(1)（哈希表）。

1.1 键值对

1.1.1 概念

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value ，key 代表键值，value 表示与 key 对应的信息。

C++ STL通常用 std::pair 来存储和传递键值对。

1.1.2 pair

std::pair 是STL中的一种模板类，用于表示一个包含两个元素的组合，它有两个成员变量，称为键（first）和值（second）。

头文件：<utility> 一些标准库隐式地包含了<utility>

template <class T1, class T2> struct pair;

构造函数
pair();	默认构造
template<class U, class V> pair (const pair<U,V>& pr);	拷贝构造
pair (const first_type& a, const second_type& b);	带参构造
pair& operator= (const pair& pr);	拷贝赋值

为了方便创建 std::pair 对象，C++ 标准库还提供了一个辅助函数 std::make_pair，定义如下：

template <typename T1, typename T2>
std::pair<T1, T2> make_pair(T1&& x, T2&& y) {return std::pair<T1, T2>(std::forward<T1>(x), std::forward<T2>(y));
}

例：

std::pair<double,int> myPair1;
myPair1.first = 1.1; myPair1.second = 2;std::pair<int,std::string> myPair2(2,"Hello");std::pair<int,std::string> myPair3(myPair2);
std::cout << "myPair3: " << myPair3.first << "," << myPair3.second << std::endl;// 2 Hellostd::pair<int,std::string> myPair4 = myPair3;
std::pair<int,std::string> myPair5 = {5,"myPair5"};std::pair<int,std::string> myPair6 = std::make_pair(6,"myPair6");

1.2 树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。

树型结构的关联式容器主要有四种：map、set、multimap、multiset。

这四种容器的共同点是：使用红黑树（一种平衡搜索树）作为其底层结构，且容器中的元素是一个有序的序列。

二、set

2.1 set 的介绍

std::set 是一个关联式容器，用于存储唯一的元素，元素按照一定次序存储。

特点：

set 中的元素是唯一的，不允许重复（所以可以使用 set 进行去重）；且元素总是 const ，不允许修改，但可以插入、删除
元素会根据比较函数（默认是 std::less<T>，升序）自动排序
底层通过红黑树实现

注意：

与 map/multimap 不同，map/multimap 中存储的是真正的键值对<key, value>，set 中只放
value，但在底层实际存放的是由<value, value>构成的键值对
插入元素时，只需要插入 value 即可，不需要构造键值对
使用迭代器遍历 set 中的元素，可以得到有序序列
查找元素的时间复杂度为 $O(log_2n)$

2.2 set 的使用

头文件：<set>

模板参数列表：

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;

T: set中存放元素的类型，实际在底层存储<value, value>的键值对
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

2.2.1 set 的构造

函数声明	功能介绍
set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());	构造空的 set
set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type());	用[first, last)区间中的元素构造 set
set (const set& x, const allocator_type& alloc);	set 的拷贝构造

例：

std::set<string> mySet1;
std::set<int, std::greater<int>> mySet2;// 降序std::vector<int> v({ 4,7,0,1,3,6,8,2,9,5 });
std::set<int> mySet3(v.begin(), v.end());

2.2.2 set 的迭代器

函数声明	功能介绍
iterator begin(); const_iterator begin() const;	返回 set 中起始位置元素的迭代器 / const迭代器
iterator end(); const_iterator end() const;	返回 set 中最后一个元素后面的迭代器 / const迭代器
reverse_iterator rbegin(); const_reverse_iterator rbegin() const;	返回 set 最后一个数据位置的反向迭代器 / const反向迭代器
reverse_iterator rend(); const_reverse_iterator rend() const;	返回 set 第一个元素前面位置的反向迭代器 / const反向迭代器

C++11提供了cbegin、cend、crbegin、crend 函数表示const版本，语义更清晰。（ps:实际不常用）

std::vector<int> v({ 4,7,0,1,3,6,8,2,9,5 });
std::set<int> mySet(v.begin(), v.end());std::set<int>::iterator it = mySet.begin();
while (it != mySet.end())cout << *(it++) << " ";// 自动排序

注意： set 的迭代器是双向迭代器，支持 ++、-- 等操作，不支持随机访问（it + 1、it - 1、it[n]）

2.2.3 set 的容量操作

函数声明	功能介绍
bool empty() const;	检测 set 是否为空，空返回 true，否则返回 false
size_type size() const;	返回 set 中有效元素的个数

2.2.4 set 的修改操作

函数声明	功能介绍
insert	在 set 中插入元素
(1) iterator erase (const_iterator position); (2) size_type erase (const value_type& val); (3) iterator erase (const_iterator first, const_iterator last);	（1）删除指定迭代器位置的元素，返回下一个元素位置的迭代器（2）删除值为 val 的元素，返回被删除的个数（3）删除 [first,last) 范围内的元素，返回被删除元素之后的元素位置的迭代器
void swap (set& x);	交换set中的元素
void clear();	将set中的元素清空
template <class... Args> pair<iterator,bool> emplace (Args&&... args); (c++11)	直接构造和插入元素（避免了拷贝或移动，因而效率会有略微提升）

在set中插入单个元素 val 时，返回值类型为 pair<iterator,bool> 。它的 first 指向插入的元素（如果插入成功）或已存在的相同元素；second 表示是否成功插入。这种设计即能快速访问要插入元素的位置，也能判断插入是否成功。
带有 hint 的插入，第一个参数 position 表示插入位置的提示。可以优化插入操作的性能，尤其是在插入大量元素时。通常用于优化场景，所以不关心是否插入成功，返回值为 iterator

例：

std::set<int> s;
std::pair<std::set<int>::iterator, bool> res = s.insert(1);
// 再插入一个相同元素 1
auto res2 = s.insert(1);
if (!res2.second) cout << "插入失败！已存在相同元素" << endl;// 使用hint场景：连续插入有序数据
auto hint = s.find(1);
for (int val : {2, 3, 4, 5, 6}) {hint = s.insert(hint, val); // 每次更新 hint 为上一次插入的位置
}//插入一个区间
std::vector<int> v({ 7,3,3,8,8,2,10,9 });
s.insert(v.begin(), v.end());
for (auto& e : s) cout << e << ' ';//1~10

erase 具有迭代器失效的问题，返回值 iterator 常用于更新迭代器。

set<int> s = {1,2,3,4,5,6};
set<int>::iterator it = s.begin();
while (it != s.end())
{it = s.erase(it);
}

2.2.5 set 的查找操作

函数声明	功能介绍
iterator find (const value_type& val);	返回set中值为 val 元素位置的迭代器；如果未找到，则返回 end()
size_type count (const value_type& val) const;	返回set中值为 val 的元素的个数（由于set中元素不重复，常用于检测元素是否存在）
iterator lower_bound (const value_type& val);	返回第一个不小于 val 的元素位置的迭代器
iterator upper_bound (const value_type& val);	返回第一个大于 val 的元素位置迭代器
pair<iterator,iterator> equal_range (const value_type& val);	用于查找给定值在集合中的范围

关于 find 与 count：

//在set中，count可与find达到同样的效果 
std::set<int> s;
for (int i = 1; i <= 5; ++i)s.insert(i * 10);
// 10 20 30 40 50
const int val = 10;
auto it = s.find(val);
if (it != s.end()) cout << "找到了" << endl;
else cout << "未找到" << endl;if (s.count(val)) cout << "找到了" << endl;
else cout << "未找到" << endl;

lower_bound 通常与 upper_bound 搭配使用:

std::set<int> s;
for (int i = 1; i <= 5; ++i)s.insert(i * 10);
// 10 20 30 40 50
auto itlow = s.lower_bound(20); // >= 20
auto itup = s.upper_bound(30); // > 30
s.erase(itlow, itup);// [20,40)
for (auto e : s) cout << e << " ";// 10 40 50auto ret = s.equal_range(40);// 等价于lower_bound(40) + upper_bound(40)
cout << *ret.first << " " << *ret.second << endl;// 40 50

为什么这样设计？为了符合 C++ STL 中的“左闭右开”区间设计原则，即[first,last)，保持一致性。

三、multiset

3.1 multiset 的介绍

std::multiset 用于存储可重复元素，且元素会自动按顺序排列（默认按小到大排序）。

multiset 与 set 类似，区别在于 set 的元素是唯一的，而 multiset 的元素是可重复的。
multiset 的元素总是 const ，不允许修改，但可以插入、删除
底层结构为红黑树，且底层存储的也是由<value, value>构成的键值对

3.2 multiset 的使用

template < class T,                        // multiset::key_type/value_typeclass Compare = less<T>,        // multiset::key_compare/value_compareclass Alloc = allocator<T>      // multiset::allocator_type> class multiset;

头文件： <set>

multiset 的使用与 set 大致一致，这里只简单介绍一些有区别的接口。

multiset::insert 的返回值是 iterator ，表示新插入元素的迭代器。因为插入相同元素总会成功。

set 插入元素时会检查元素是否存在；multiset 插入（合法）元素总会成功，无论元素是否存在。
在 std::multiset 中插入相同元素时会保持“后插入”顺序，即新插入的元素会出现在相同元素最后的位置。（相对稳定排序）

例：

multiset<int> ms = {1,2,2,3};
multiset<int>::iterator it = ms.insert(2);
cout << "下一个元素："<< *(++it) << endl;// 3

multiset::find 返回指向第一个匹配元素的迭代器；multiset::erase 若用迭代器删除，删除指定迭代器位置的元素，若用指定值删除，删除所有等于这个值的元素。

例：

multiset<int> ms = {1,2,2,2,3};
ms.erase(ms.find(2));// 只删除第一个2
size_t n = ms.erase(2);// 删除所有的2,且返回删除的个数

multiset::count 统计某个元素的出现次数。set::count 用于判断元素是否存在。

multiset<int> ms = {1,2,2,2,3};
cout << ms.count(2) << endl;// 3

lower_bound 、upper_bound 、equal_range 更适用于 multiset ，可以直接找到指定元素的 [first,last) 位置

例：

multiset<int> ms = {10,20,20,20,30};
auto lb = ms.lower_bound(20);
auto ub = ms.upper_bound(20);
// 等同于 range.first range.second
auto range = ms.equal_range(20);ms.erase(lb,ub);

四、map

4.1 map 的介绍

std::map 是一个关联容器，用于存储键值对<key，value>，并且按键的顺序自动排序。键 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键 key 关联的内容。

键 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;

特点：

map 中的键是唯一的，不能有重复的键（值可以重复）；key 总是const，不能被修改，而值 value 可以修改
元素（键值对）自动按 key 的升序排列（可自定义比较函数）
map支持下标访问符，即[key]，可以找到与 key 对应的 value

注意：

map 的底层用红黑树实现
插入 / 查找 / 删除效率：O(log n)
使用 [] 可以访问、插入、修改元素，如果只是想查找，不要用 []

4.2 map 的使用

头文件：<map>

模版参数列表：

template < class Key,                                     // map::key_typeclass T,                                       // map::mapped_typeclass Compare = less<Key>,                     // map::key_compareclass Alloc = allocator<pair<const Key,T> >    // map::allocator_type> class map;

key：键值对中 key 的类型
T：键值对中 value 的类型
Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

4.2.1 map 的构造

函数声明	功能介绍
map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());	构造空的 map
map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());	用[first, last)区间中的元素构造 map
map (const map& x);	map 的拷贝构造

例：

map<int,std::string> m1;
map<int, std::string, greater<int>> m2;
map<std::string, int> m3 = {{"Tom", 18},{"Alice", 20}};//c++11
map<std::string, int> m4(m3);  // 拷贝std::vector<std::pair<int, std::string>> vec = {{1, "one"}, {2, "two"}, {3, "three"}
};map<int, std::string> m5(vec.begin(), vec.end());

4.2.2 map 的迭代器

函数声明	功能介绍
iterator begin(); const_iterator begin() const;	返回 map 中起始位置元素的迭代器 / const迭代器
iterator end(); const_iterator end() const;	返回 map 中最后一个元素后面的迭代器 / const迭代器
reverse_iterator rbegin(); const_reverse_iterator rbegin() const;	返回 map 最后一个数据位置的反向迭代器 / const反向迭代器
reverse_iterator rend(); const_reverse_iterator rend() const;	返回 map 第一个元素前面位置的反向迭代器 / const反向迭代器

同 set ，C++11提供了cbegin、cend、crbegin、crend 函数表示const版本。

map 的迭代器也是双向迭代器，同 set 。

 map<std::string, int> m = {{"Tom", 18},{"Alice", 20}};//c++11map<std::string,int>::iterator it = m.begin();while (it != m.end()){cout << it->first << " : " << it->second << endl;}for (auto& e : m){cout << e.first << " : " << e.second << endl;}

4.2.3 map 的容量与元素访问

函数声明	功能介绍
bool empty() const;	检测 map 是否为空，空返回 true，否则返回 false
size_type size() const;	返回 map 中有效元素的个数
mapped_type& operator[] (const key_type& k); mapped_type& operator[] (key_type&& k);	返回 key 对应的 value 的引用
(c++11) mapped_type& at (const key_type& k); const mapped_type& at (const key_type& k) const;	返回 key 对应的 value 的引用

map 中 operator[] 的特点：

如果 map[key] 不存在则自动插入并完成初始化
返回 value 的引用，因此可以修改 value

map<int,int> m;
m[5]; //插入key为5的元素并默认构造相应的value (插入)
m[5] = 10;// (修改)
m[3] = 6;// (插入+修改)
if (m[2] == 1){};//同样也会插入key为2的元素

调用此函数相当于 (*((this->insert(make_pair(k,mapped_type()))).first)).second

注意：operator[] 不能用于 const std::map ，因此可能自动插入新元素

要读取元素而不插入或要只读访问时，可以使用 at() 函数。与 operator[] 的不同之处在于，当 key 不存在时，operator[] 会插入新元素并返回该 value；而 at() 函数直接抛出 std::out_of_range 异常。

at 可以用于 const std::map

例：

map<std::string,int> m;
m["One"] = 1;// 插入<"One",1>
m.at("One") = 0; // 修改
m.at("Two") = 2; // 抛异常 'std::out_of_range'const map<std::string,int> m2(m);
m2.at("One"); // 可以用于const map
m2["One"];// 报错

4.2.4 map 的修改操作

函数声明	功能介绍
insert	在 map 中插入元素
(1) iterator erase (const_iterator position); (2) size_type erase (const key_type& k); (3) iterator erase (const_iterator first, const_iterator last);	（1）删除指定迭代器位置的元素，返回下一个元素位置的迭代器（2）删除键为 k 的元素，返回被删除的个数（3）删除 [first,last) 范围内的元素，返回被删除元素之后的元素位置的迭代器
void swap (map& x);	交换 map 中的元素
void clear();	将 map 中的元素清空
template <class... Args> pair<iterator,bool> emplace (Args&&... args); (c++11)	直接构造和插入元素（避免了拷贝或移动，因而效率会有略微提升）

参考 set::insert 。(1)返回值类型为 pair<iterator,bool> 。它的 first 指向插入的元素（如果插入成功）或已存在的相同元素；second 表示是否成功插入。

常用的插入方式：（也可以用 map[key] 插入）

map<std::string,int> m;
m.insert(make_pair("A",10));
auto ret = m.insert({"A",10});// 插入失败
if (!ret.second) cout << "键" << ret.first->first << "已存在,插入失败" << endl;m.insert({{"B",20},{"C",30}});// C++ 11 insert(initializer_list)

注意使用 erase 时传参为 key 而不是 pair，表示删除键为 key 的键值对。

4.2.5 map 的查找操作

函数声明	功能介绍
iterator find (const key_type& k); const_iterator find (const key_type& k) const;	返回 map 中键为 k 元素位置的迭代器；如果未找到，则返回 end()
size_type count (const key_type& k) const;	返回 map 中键为 k 的元素的个数（常用于检测元素是否存在）
iterator lower_bound (const key_type& k); const_iterator lower_bound (const key_type& k) const;	返回第一个键不小于 k 的元素位置的迭代器
iterator upper_bound (const key_type& k); const_iterator upper_bound (const key_type& k) const;	返回第一个键大于 k 的元素位置迭代器
pair<iterator,iterator> equal_range (const key_type& k); pair<const_iterator,const_iterator> equal_range (const key_type& k) const;	用于查找给定键在集合中的范围

使用方式参考 set ，注意传参时传键 key。(因为 map 是按键值排序的)

五、multimap

5.1 multimap 的介绍

std::multimap 是一种允许一个键对应多个值的关联容器。

multimap 允许多个相同的 key , 且 key 总是const
不支持 operator[] 操作，因为一个键可能对应多个值
multimap 会按 key 排序，并按插入顺序排列相同 key 的值（有序且稳定）。
底层用红黑树实现

5.2 multimap 的使用

可以参考 multiset 相较于 set ，multimap 相较于 map 与其类似。

头文件：<map>

template < class Key,                                     // multimap::key_typeclass T,                                       // multimap::mapped_typeclass Compare = less<Key>,                     // multimap::key_compareclass Alloc = allocator<pair<const Key,T> >    // multimap::allocator_type> class multimap;

multimap 可以插入键相同的元素，即使是一模一样的键值对。返回值为 iterator ，因为插入总是成功的。

multimap<int, std::string> mm;
mm.insert(pair<int, std::string>(1, "A"));
mm.insert(make_pair(1, "A"));
mm.insert(make_pair(1, "B"));
for (auto &e: mm)
{cout << e.first << " : " << e.second << endl;
}
size_t n = mm.erase(1);
cout << "erase的个数: " << n << endl;

multimap::count 可以统计键为 k 的元素的个数。

mulitmap 不支持 operator[] 。