###前言：（序列式容器和关联式容器）
前面我们已经学习的部分的STL的容器，例如string、list、vecto、deque、array、forward_list。这些都是序列式容器，逻辑结构为线性序列，两个数据之间没用很强的关联性；
关联式容器也是来存储数据的，它的逻辑结构是非线性序列的，两个数据之间的关联性很强，交换一下或者改变一下，那么他们之间的存储结构就被破坏了；关联式容器有map/set系列的和unordered_map和unordered_map系列的。
一、set
1、set类的介绍
set是存储数据的容器，它的存储数据的规则按照红黑树的规则；左子树的节点数据都小于根节点的数据，右子树的节点数据都大于根节点的数据大小；
声明：
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
>
class set;- T是set底层的关键字类型；
- set默认支持的是小于的比较，less<T>，可以传greater<T>；
- set底层存储的数据的内存是从空间适配器中申请的，可以自己实现内存池，那么就传给第三个参数；
- 一般来说，我们不需要传后面的两个参数
- 底层是红黑树，增删查的时间复杂度是O(logN)；
- 底层迭代器走的是平衡二叉搜索树的中序遍历，所以迭代器对应的数据是有序的，
2、set的构造和迭代器
set的迭代器是双向的迭代器，所以支持反向迭代器；
迭代器走的是中序，所以默认遍历按照升序顺序；
set的iterator和const_iterator都不错支持修改数据，因为修改数据可能会破坏底层搜索树的结构
###代码示例：
#include<iostream>
#include<set>
using namespace std;void Print(set<int>& s)
{for (auto i : s){cout << i << " ";}cout << endl;
}
void test1()
{//无参构造set<int> s1;Print(s1);//迭代器区间构造int arr[] = { 5,6,7,1,2,3,4 };set<int> s2(arr, arr + 7);set<int> s3(s2.begin(), s2.end());Print(s2);Print(s3);//拷贝构造set<int> s4(s3);Print(s4);//列表构造set<int> s5({ 9,1,3,4,5,7,6,8,2 });Print(s5);
}
void test2()
{set<int> s({1,2,3,4,9,8,7,6,5});//正向迭代器set<int>::iterator i = s.begin();while (i != s.end()){cout << *i << " ";i++;}cout << endl;//反向迭代器set<int> ::reverse_iterator ri = s.rbegin();while (ri != s.rend()){cout << *ri << " ";ri++;}cout << endl;
}
3、set的增删查
1、插入insert
set不支持插入相同的值,若是插入相同的值，那么就插入失败；
插入接口原型声明：
// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
###代码示例：
void test3()//插入单个值
{set<int> s1;s1.insert(2);s1.insert(3);s1.insert(8);s1.insert(1);for (auto i : s1){cout << i << ' ';}cout << endl;//相同元素不插入pair<set<int>::iterator,bool> ret =s1.insert(8);for (auto i : s1){cout << i << ' ';}cout << endl;
}
void test4()//插入一段列表
{set<int> s;for (int i = 10; i <= 100; i += 10){s.insert(i);}for (auto i : s){cout << i << ' ';}cout << endl;s.insert({ 300,200,100,10 });for (auto i : s){cout << i << ' ';}cout << endl;
}
2、查找find
原型：
iterator find(const value_type& val)const;
若是查找成功则返回这个数据对应的迭代器；若是查找失败则返回end迭代器。
###代码示例：
void test5()
{set<int> s;for (int i = 10; i <= 100; i += 10){s.insert(i);}for (auto i : s){cout << i << ' ';}cout << endl;//查找一个存在的值set<int>::iterator pos1 = s.find(10);if (pos1 != s.end())cout << *pos1 << endl;elsecout << "该数据不存在" << endl;//查找一个不存在的值set<int>::iterator pos2 = s.find(101);if (pos2 != s.end())cout << *pos2 << endl;elsecout << "该数据不存在" << endl;
3、删除erase
原型：
1、void erase(iterator pos);
2、size_type erase(const value_type& val);
3、void erase(iterator first,iterator last);
- 第一个就是删除 迭代器指向位置的值；
- 第二个删除指定的值，返回类型size_type代表的是删除了多少个这个指定的值，set没有相同的值，那么就是删除成功返回1，反之返回0；
- 第三个删除指定迭代器区间的数据。
###代码示例：
void test6()
{set<int> s = { 4,2,7,2,8,5,9 };cout << "原set数据：" << endl;for (auto e : s){cout << e << " ";}cout << endl;// 删除最⼩值cout << "删除最小值：" << endl;s.erase(s.begin());//迭代按中序走，开始的就是最小的值for (auto e : s){cout << e << " ";}cout << endl;cout << "删除指定值x，输入x：" << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);//指定一个值删除if (num == 0){cout << x << "不存在！" << endl;}for (auto e : s){cout << e << " ";}cout << endl;cout << "删除迭代器区间的值：" << endl;set<int> ::iterator first = s.begin();set<int> ::iterator last = s.end();s.erase(first, --last);//结果只剩下最后一个数据for (auto e : s){cout << e << " ";}cout << endl;
}
4、set的lower_bound和upper_bound
原型
iterator lower_bound(const value_type& val)const;
iterator upper_bound(const value_type& val)const;
- 第一个是返回大于或者等于val值的迭代器；
- 第二个时返回大于val值的迭代器。
###代码示例：
void test7()
{set<int> s;for (int i = 10; i <= 100; i += 10){s.insert(i);}for (auto i : s){cout << i << ' ';}cout << endl;set<int>::iterator it_low = s.lower_bound(20);cout << *it_low << endl;set<int>::iterator it_up = s.upper_bound(50);cout << *it_up << endl;//删除掉这两个迭代器之间的数据，左闭右开s.erase(it_low, it_up);for (auto i : s){cout << i << ' ';}
}
二、multiset
multiset和set几乎完全一致，只是multiset支持冗余，也就是支持存储相同的值。所以它的增删查也会随之发生小变化；
头文件和set相同
- insert：能插入相同的值；
- find：查找到要找的值，那就去它的左子树看看有无相同的值，若是有就返回左子树的节点迭代器，只到左子树中没有这个值为止；也就是中序中的第一个；
- erase：指定删除一个值，那么也会删除所有与之相同的值。
###具体代码：
void test8()
{multiset<int> s1{ 4,2,7,2,4,8,4,5,4,9 };for (auto i : s1){cout << i << " ";}cout << endl;cout << "输入需要查找的值：" << endl;int x = 0; cin >> x;multiset<int>::iterator i = s1.find(x);if (i != s1.end())cout <<"这个值存在：" << *i << endl;elsecout << "该数据不存在" << endl;//与set不同，multiset的count会返回实际个数cout <<"数据个数：" << s1.count(4) << endl;//erase会删除所有相同的值s1.erase(4);auto j = s1.begin();while (j != s1.end()){cout << *j << " ";j++;}
}
