目录

一、关联式容器和序列式容器

二、set系列的使用

1. set类介绍

2. 构造和迭代器

3. set的增删查

insert

find和count

erase

lower_bound和upper_bound

4. set的使用场景

5. multiset和set的差异

三、map系列的使用

1. map类介绍

2. pair类型

3. 构造和迭代器

结构化绑定：

4. map的增删查

insert

find、count以及erase

lower_bound和upper_bound

5. operator[ ]重载

6. map和multimap的差异

总结：

---

一、关联式容器和序列式容器

首先我们先来了解两个概念，关联式容器和序列式容器。

之前我们已经接触了string、vector、list、deque、array、forward_list等容器，这些容器统称为序列式容器，因为逻辑结构是线性的容器，两个位置存储的值一般没有紧密的关系，即使交换一下这两个位置的值也依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

而关联式容器的逻辑结构一般是非线性的，两个位置有紧密的关系，交换一下就会破坏存储结构。顺序容器中的元素是按关键字来保存和访问的。关联式容器有unordered_map/unordered_set系列和map/set系列。

本篇文章讲解的map和set底层是红黑树，是一颗平衡二叉搜索树。set是一个有序集合的容器，用于key搜索场景，而map是一个键值对容器，用于key/value搜索场景。

二、set系列的使用

1. set类介绍

• 第一个模板参数T是容器的数据类型
• 第二个模板参数是一个仿函数，因为set默认要求T支持比较大小，如果不支持可以传入一个仿函数自行实现
• 第三个模板参数是空间配置器

一般情况下我们只需要传第一个参数即可。

set底层是红黑树，迭代器使用的是中序遍历，所以是有序的。

2. 构造和迭代器

构造方面我们学会用几个常用的即可

1. 无参默认构造

set<int> s1;// 默认构造

2. 迭代器区间构造

vector<int> arr = { 7, 5, 3 };
set<int> s2(arr.begin(), arr.end());// 迭代器区间

3. 拷贝构造

set<int> s3(s2);// 拷贝构造

4. initializer_list列表构造

// initializer_list列表构造
set<int> s4({1, 2, 3});// 隐式类型转换
set<int> s5{ 5, 8, 3 };// 直接初始化
set<int> s6 = { 3, 2, 1 };// 拷贝列表初始化

可以看到这些方式都成功初始化了，但要注意：不论用何种方式初始化，容器都会按红黑树的结构一个个插入。

迭代器支持正向迭代器和反向迭代器，但两种迭代器都不支持修改数据。

set<int>::iterator it1 = s6.begin();
set<int>::reverse_iterator it2 = s6.rbegin();

3. set的增删查

insert

insert插入，一共有三种形式：

第一，插入单个数据，如果数据已存在则不会插入

第二，initializer_list列表插入，已经在容器中存在的值不会插入

第三，迭代器区间插入，已经在容器中存在的值不会插入

set<int> s1;
s1.insert(5);// 单个值插入
s1.insert({ 3, 13, 1, 7, 5 });// 列表插入
vector<int> v1{ 1, 2 ,3, 4, 5 };
s1.insert(v1.begin(), v1.end());// 迭代器区间插入

find和count

find用于查找 val ，返回 val 所在的迭代器，没有找到就返回 end()

count用于查找 val ，返回 val 的个数

erase

erase也有三种使用方式

1. 删除一个迭代器位置的值

2. 删除等于val的值，val存在就返回1，没有则返回0

3. 删除一段迭代器区间的值

s1.erase(1);// 删除val值
s1.erase(s1.begin(), next(s1.begin(), 2));// 删除迭代器区间
s1.erase(s1.begin());// 删除一个迭代器位置的值

注意：set迭代器不是随机迭代器，不支持+n的操作。另外不要删除end()位置的值，因为end()指向的位置是容器结尾的下一个位置。

lower_bound和upper_bound

lower_bound返回大于等于 val 位置的迭代器

upper_bound返回小于等于 val 位置的迭代器

4. set的使用场景

由于set底层是红黑树，且不支持插入相同元素，所以可以利用insert和迭代器实现去重+排序

如图，实现了去重+排序，默认是升序排序，如果想实现降序，可以加一个大于的仿函数

set< int, greater<int> >

又因为迭代器遍历是有序的，所以可以快速得到最大值最小值并删除。并且可以通过find快速查找到对应数据并删除。所以可以快捷地对set进行修改。

5. multiset和set的差异

multiset中的multi是多个的意思，所以multiset和set的区别就在于，multiset支持多个相同数据的插入（值冗余），且使用multiset不需要额外包含头文件，有set头文件就可以使用。

因为multiset支持值冗余，所以insert/find/count/erase这些接口有所差异：

• insert插入只能实现排序而不能实现去重
• find只会查找第一个值为val的数据
• count会返回值为val的数据的实际个数
• erase用值删除时会删除所有值为val的数据

三、map系列的使用

1. map类介绍

Key就是map底层关键字的类型，T是map底层value的类型，map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的 内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

2. pair类型

map底层的红黑树中的数据以pair<key,  T>的形式存储。T支持修改，key不支持修改。

以下是pair类的实现：

typedef pair<const Key, T> value_type;
template <class T1, class T2>
 struct pair 
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;

    pair()
        : first(T1())
        , second(T2())
    {}

    pair(const T1& a, const T2& b)
        : first(a), second(b)
    {}

    template<class U, class V> 
    pair (const pair<U,V>& pr)
        : first(pr.first)
        , second(pr.second)
    {}
};

3. 构造和迭代器

map的构造与set类似，有4种方式：

1. 无参默认构造

2. 迭代器区间构造

3. 拷贝构造

4. initializer_list列表构造

map<int, string> s1;// 无参默认构造
vector<pair<int, string>> vec = { {1, "one"}, {2, "two"}, {3, "three"} };
map<int, string> s2(vec.begin(), vec.end());// 迭代器区间构造
map<int, string> s3(s2);// 拷贝构造
// initializer_list列表构造
map<int, string> s4{ {1, "Alice"},{2, "Bob"},{3, "Charlie"} };
map<int, string> s5({{ 1, "Alice" }, { 2, "Bob" }, { 3, "Charlie" }});
map<int, string> s6 = { {1, "Alice"},{2, "Bob"},{3, "Charlie"} };

map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，不支持修改key的数据，但可以修改value的数据。

注意：由于数据存储在一个pair类的对象中，所以不支持直接cout<< *it; 只能一个一个输出(*it)的成员变量。且由于it是指针，map重载了->操作符，所以可以用->的方式输出。

结构化绑定：

C++17之后支持结构化绑定，可以更加便捷地访问数组、结构体等数据类型。

用法：auto [  数据1， 数据2， 数据3......  ]   =  对应的数据类型

// 结构化绑定
for (auto& [k, v] : s5) {
	cout << k << " " << v << endl;
}

auto [x, y] = pair<int, string>(5, "aaaaa");
cout << x << " " << y << endl;

4. map的增删查

insert

map的insert在插入数据上与set有所不同，他插入的是pair键值对。但依旧是三种方式

1. 单个数据插入

2. initializer_list列表插入

3. 迭代器区间插入

map<int, string> s1;
s1.insert({ 1, "Alice" });// 单个值插入
s1.insert({ {1, "Alice"}, {2, "Bob"} });// initializer_list列表插入
vector<pair<int, string>> vec({ { 1, "Alice" }, {3, "Charlie"} });
s1.insert(vec.begin(), vec.end());// 迭代器区间插入

find、count以及erase

map的查找和删除都是只对key进行操作，与value没有关系，所以说和set是完全类似的。只不过find返回的迭代器还能通过pair对象访问并修改value的值。

find用于查找k，返回k对应的迭代器，没有则返回end()

count用于统计k的个数

erase有三种方式：

1. 删除一个迭代器位置的值

2. 删除等于k的值，k存在就返回1，没有则返回0

3. 删除一段迭代器区间的值

lower_bound和upper_bound

lower_bound返回大于等于 val 位置的迭代器

upper_bound返回小于等于 val 位置的迭代器

5. operator[ ]重载

由于map存储的数据是一个pair类型的对象，所以重载的[ ]运算符也很特殊。operator[ ]是对pair对象进操作，并且operator[ ]不仅仅用于修改value值，他也支持插入数据和查找数据，所以这是一个多功能的复合接口。

1. 如果k不在中就是插入

2. 如果k在map中就是查找加修改

operator[ ]的底层实际是做了这个操作，看起来较复杂，但可以看到调用了insert接口，所以能实现插入功能

示例代码：

map<int, string> s1;
s1[9];// 插入，默认value为" "
s1[1] = "Alice";// 插入，并将value置为"Alice"
s1[1] = "Bob";// 查找k为1的位置，并将value修改为"Bob"
cout << s1[1] << endl;// 查找，返回值是value

6. map和multimap的差异

使用multimap同样不需要额外包含头文件。而multimap主要是关键值key冗余，所以multimap的接口 insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个，这里就不再展示。

比较重要的一点是multimap不支持operator[ ]， 因为multimap有关键值key冗余，所以不能准确地找到目标的value值修改，所以[ ]是用不了的。

总结：

以上就是本文的所有内容了，如果觉得有帮助的话可以点赞收藏加关注支持一下！