一、关联式容器

在之前的学习中，我们都接触了不少容器，如vector、list、deque等容器，这些容器统称为 序列式容器。而stack和queue是靠deque适配出来的，之前我们也模拟实现了，所以stack和queue是 容器适配器。今天我们还要学习一种容器：关联式容器，其中set、multiset、map和multimap都叫做 关联式容器，下面重点学习 set和multiset。

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是 <key, value>结构的键值对，在数据检索时比序列式容器效率更高。

所以容器分为三种类型：序列式容器、关联式容器、容器适配器。

二、set

1、set的介绍

这是set的模板参数列表：

T：set中存放元素的类型，实际上在底层是<value, value>的键值对。
Compare：默认是使用小于来比较的。(可以使用仿函数修改)
Alloc：set中元素空间管理的方式，使用allocator空间配置器管理。

它的底层是**平衡二叉搜索树（红黑树）**实现的，后续我们会模拟实现。

2、set的使用

2.1、元素的插入（insert接口）

insert插入元素一共有三种方式：

①直接插入一个元素

②在迭代器的位置插入一个元素

③使用范围插入函数

#include <iostream>
#include <set>
using namespace std;
int main()
{set<int> myset;myset.insert(3);myset.insert(5);myset.insert(3);myset.insert(1);myset.insert(1);myset.insert(7);set<int>::iterator it = myset.begin();while (it != myset.end()){// *it = 1;     set中是不允许修改的 cout << *it << " ";it++;}return 0;
}

结果：

可以看到这里我们插入的元素是[3, 5, 3, 1, 1, 7]，但是打印出来的值是[1, 3, 5, 7]。

很明显，set是**去重+排序**的，保证了set中的元素是唯一的，这就是set的特性。

而且set同样是支持迭代器，你可以使用迭代器或者范围for来访问容器中的元素。

对于set中的元素为什么不能修改？

• set的元素是唯一的，如果你进行修改，保不齐你修改的元素正好set中就有的。
• 修改了元素，不能保证set还是有序的，那么就必须重新调整树，这样效率是非常低的。

2.2、pair的简单讲解

官方文档说的很清楚，insert是有个返回值的：pair<iterator, bool>，这个是什么呢？这其实就是键值对，常常说的<K, V>就是键值对关系。

pair的源码中显示，它就是一个类。我们可以调用first和second来访问这个键值对。

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){}};

比如对于上述的insert的返回值，我们就可以打印出来看看。

int main()
{set<int> myset;myset.insert(3);myset.insert(5);pair<set<int>::iterator, bool> ret = myset.insert(3);cout << *ret.first << ":" << ret.second << endl;return 0;
}

结果：

当set中已经有了3之后，你再插入3进去就会失败。因为bool返回的0，也就是false。

2.3、元素的查找（find接口）

返回值很简单，如果找到该元素了，就返回该值的迭代器；否则就返回end。

int main()
{set<int> myset;myset.insert(3);myset.insert(5);myset.insert(3);if(myset.find(3) != myset.end()){cout << *myset.find(3) << "找到了" << endl;}return 0;
}

结果：

set的底层是平衡二叉搜索树，查找一个元素的效率就是树的高度，为logN。

2.4、判断元素是否在set中（count接口）

set中判断一个元素在不在set中，除了使用find以外，还有一个count接口可以判断。

它有一个返回值，如果存在就返回1，否则返回0。

int main()
{set<int> myset;myset.insert(3);if(myset.count(3))cout << *myset.find(3) << "找到了" << endl;return 0;
}

结果：

find接口：if(myset.find(3) != myset.end())，count接口：if(myset.count(3))。

可以看出count接口的代码要少一点，所以，以后想要判断一个元素是否在set中，使用count接口更爽一点。

2.5、元素的删除（erase接口）

set中erase一共有三种方式：迭代器位置删除，直接删除值，迭代器区间删除。

1.迭代器位置删除（这个很少用）：

int main()
{set<int> myset;myset.insert(3);myset.insert(5);myset.insert(3);myset.insert(1);myset.insert(1);myset.insert(7);cout << "删除前set中的元素：";for (auto e : myset)cout << e << " ";cout << endl;auto it = myset.find(1);if (it != myset.end()){myset.erase(it);}cout << "删除后set中的元素：";for (auto e : myset)cout << e << " ";cout << endl;

结果：

2.直接删除值：

int main()
{set<int> myset;myset.insert(3);myset.insert(5);myset.insert(3);myset.insert(1);myset.insert(1);myset.insert(7);cout << "删除前set中的元素：";for (auto e : myset)cout << e << " ";cout << endl;myset.erase(1);                  // 存在就直接删除myset.erase(10);                 // 删除不存在的值，也不会报错cout << "删除后set中的元素：";for (auto e : myset)cout << e << " ";cout << endl;return 0;
}

结果：

？ 思考：对于迭代器位置删除和直接删除值，它们两个有什么区别呢？

答：迭代器删除需要使用 find + erase(pos) 来删除该元素，如果迭代器位置不存在，就会报错；而对于直接删除值来说，存在即删除，不存在，啥事不发生。

所以建议使用erase的时候，使用直接删除值的方式。

2.6、区间查找：lower_bound和upper_bound

lower_bound和upper_bound是干什么的呢？看它们的参数和返回值，找寻一个值，然后返回一个迭代器位置。

• lower_bound是找寻序列中第一个大于等于目标值的元素。

• upper_bound是找寻序列中第一个大于目标值的元素。

#include <iostream>
#include <set>int main()
{std::set<int> myset;std::set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90itlow = myset.lower_bound(25);      // 返回30的位置         itup = myset.upper_bound(55);       // 返回60的位置              myset.erase(itlow, itup);           // 删除的区间是左闭右开的[itlow, itup）                   std::cout << "myset contains:";for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

结果：

可以看到使用lower_bound和upper_bound可以找到元素的位置，然后通过erase就可以快速的删除区间的元素。

2.7、查找特定值的范围：equal_range

set中还有一个接口：equal_range，可以快速的找到目标值的lower_bound和upper_bound。

int main()
{std::set<int> myset;for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;ret = myset.equal_range(25);std::cout << "the lower bound points to: " << *ret.first << '\n';std::cout << "the upper bound points to: " << *ret.second << '\n';return 0;
}

结果：

总结：

1、set是一个关联式容器，插入元素只需要value即可，不需要键值对。

2、set可以去重 + 排序。

3、set的底层是红黑树。

4、查找某个元素，时间复杂度是logN。

5、set中的元素不能修改。

2、multiset（有重复元素的set）

2.1、multiset的介绍

set是不能存放重复元素，但是multiset可以存放重复的元素。

所以multiset是 排序 + 不去重。

就是因为有无重复元素的影响，set和multiset的insert和erase有一点小小的区别。

set中的insert是会插入失败的（因为不允许有重复值），但是multiset的insert是不会插入失败的。

它的insert的返回值都不是pair类型的。

对于erase来说，会删除所有和目标值相等的元素。

2.2、multiset的使用

int main()
{vector<int> vc = { 40,20,40,50,10 };multiset<int> myMulset(vc.begin(), vc.end());for (auto e : myMulset){cout << e << " ";}return 0;
}

结果：

为了得到是升序的序列，所以它的底层是通过中序访问。有很多相同的值，multiset中使用find接口的时候，找到的第一个元素应该是中序的第一个元素。

OK，set和multiset的大致内容就是这些，下一个节我们将讲解map和multimap。