一、关联式容器和键值对
1.关联式容器
前面的STL的容器，如vector、list、deque等都是序列式容器，因为
（1）底层的数据结构是线性的
（2）存储的是元素本身
（3）数据和数据之间没有关联
关联式容器也是用来存储数据的， 不过里面存储的是键值对，数据检索时，效率比序列式容器高。STL有两种关联式容器：树形结构和哈希结构。树形结构的关联式容器有4种：set、map 、multiset、mapltimap，它们的底层都是平衡搜索树（红黑树）。
2.键值对
用来表示具有一一对应关系的结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
比如：英汉互译字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义一一对应，即通过该英文单词，在词典中就可以找到与其对应的中文含义。
二、set
1.set特点
set是按照一定次序存储元素的容器，它有以下特点：
（1）在set中，用value标识元素(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
（2）在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
（3）set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
（4）set在底层是用二叉搜索树(红黑树)实现的。
注意：
（1）与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
（2）set中插入元素时，只需要插入value即可，不需要构造键值对。
（3）set中的元素不可以重复(因此可以使用set进行去重)。
（4）使用set的迭代器遍历set中的元素，可以得到有序序列
（5）set中的元素默认按照小于来比较
（6）set中查找某个元素，时间复杂度为：
（7）set中的元素不允许修改，因为底层的二叉搜索树是有序的，如果修改了元素，会破坏有序的性质
（8）set中的底层使用二叉搜索树(红黑树)来实现
2.set类
（1） set类对象构造
1. template < class T, // set::key_type/value_type 元素的类型 2. class Compare = less<T>, // set::key_compare/value_compare 比较方式，默认小于 3. class Alloc = allocator<T> // set::allocator_type 使用STL提供的空间配置器管理方式 4. > class set; 5. 6. //构造set 7. explicit set (const key_compare& comp = key_compare(), 8. const allocator_type& alloc = allocator_type()); 9. template <class InputIterator> 10. 11. //使用迭代器区间构造set 12. set (InputIterator first, InputIterator last, 13. const key_compare& comp = key_compare(), 14. const allocator_type& alloc = allocator_type()); 15. 16. //拷贝构造set 17. set (const set& x);
创建set对象：
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<iostream> 3. using namespace std; 4. 5. int main() 6. { 7. set<int> s;//创建一个set对象s 8. //向s中插入元素 9. 10. set<int> s1(s.begin(),s.end());//用s的区间构造s1 11. set<int> s2(s1);//用s1拷贝构造s2 12. 13. return 0; 14. }
（2）insert插入
1. s.insert(6); 2. s.insert(2); 3. s.insert(5); 4. s.insert(8); 5. s.insert(5);
set的作用：排序+去重
（3）set遍历
①迭代器遍历：
正向迭代器遍历：
1. iterator begin();//正向迭代器 2. const_iterator begin() const;//正向const迭代器
1. //set 排序+去重 2. //遍历1： 3. set<int>::iterator it= s.begin(); 4. while (it != s.end()) 5. { 6. cout << *it << " "; 7. it++; 8. } 9. cout << endl;
打印结果：
反向迭代器遍历：
1. reverse_iterator rbegin();//反向迭代器 2. const_reverse_iterator rbegin() const;//反向const迭代器
1. set<int>::reverse_iterator it= s.rbegin(); 2. while (it != s.rend()) 3. { 4. cout << *it << " "; 5. it++; 6. } 7. cout << endl;
打印是倒序的：
②范围for遍历
1. set<string> s1; 2. s1.insert("spring"); 3. s1.insert("summer"); 4. s1.insert("autumn"); 5. s1.insert("winter"); 6. 7. for (const auto& e : s1)//如果不加引用，s1中的每个元素都是深拷贝，每次都要调用拷贝构造，代价大 8. { 9. cout << e << " "; 10. } 11. cout << endl;
打印结果：
（4）find查找
iterator find (const value_type& val) const;//找到了就返回这个元素的迭代器，否则返回end
如：
1. set<string>::iterator ret = s1.find("autumn"); 2. if (ret != s1.end()) 3. { 4. cout << *ret << endl; 5. } 6. else 7. { 8. cout << "没找到" << endl; 9. }
（5）erase删除
1. void erase (iterator position);//删除指定位置元素 2. size_type erase (const value_type& val);//从set中删除指定的值 3. void erase (iterator first, iterator last);//删除指定区间
①删除指定位置元素：
删除元素5：
1. set<int> s; 2. s.insert(6); 3. s.insert(2); 4. s.insert(5); 5. s.insert(8); 6. s.insert(5); 7. 8. set<int>::iterator ret = s.find(5); 9. if (ret != s.end()) 10. { 11. s.erase(ret); 12. } 13. 14. for (auto e : s) 15. { 16. cout << e << " "; 17. } 18. cout << endl;
②删除指定值元素
删除值为8的元素：
1. set<int> s; 2. s.insert(6); 3. s.insert(2); 4. s.insert(5); 5. s.insert(8); 6. s.insert(5); 7. 8. //删除值为8的元素 9. s.erase(8); 10. 11. for (auto e : s) 12. { 13. cout << e << " "; 14. } 15. cout << endl;
③删除指定区间
删除5之前的元素：
1. set<int> s; 2. s.insert(6); 3. s.insert(2); 4. s.insert(5); 5. s.insert(8); 6. s.insert(5); 7. 8. //删除5之前的元素 9. set<int>::iterator ret = s.find(5); 10. s.erase(s.begin(), ret); 11. 12. for (auto e : s) 13. { 14. cout << e << " "; 15. } 16. cout << endl;
（6）计数count( )
计算set中值为val的元素的个数：
size_type count (const value_type& val) const;//计算set中值为val的元素的个数
由于set中的元素不重复，因此，set的count的计算结果≤1。
计算s中值为5的元素的个数：
1. set<int> s; 2. 3. s.insert(6); 4. s.insert(2); 5. s.insert(5); 6. s.insert(8); 7. s.insert(5); 8. 9. cout << s.count(5) << endl;
（7）交换swap( )
交换*this和x的根
void swap (set& x);
1. set<int> s; 2. s.insert(6); 3. s.insert(2); 4. s.insert(5); 5. s.insert(8); 6. s.insert(5); 7. 8. cout << "交换前s: "; 9. for (auto e : s) 10. { 11. cout << e << " "; 12. } 13. cout << endl; 14. 15. set<int> s1; 16. s1.insert(12); 17. s1.insert(18); 18. s1.insert(16); 19. s1.insert(11); 20. s1.insert(13); 21. 22. cout << "交换前s1: "; 23. for (auto e : s1) 24. { 25. cout << e << " "; 26. } 27. cout << endl; 28. 29. //s.swap(s1); 30. swap(s, s1); 31. 32. cout << "交换后s: "; 33. for (auto e : s) 34. { 35. cout << e << " "; 36. } 37. cout << endl; 38. 39. cout << "交换后s1: "; 40. for (auto e : s1) 41. { 42. cout << e << " "; 43. } 44. cout << endl;
如果将
s.swap(s1);
写成
swap(s,s1);
那么就会从交换根变成深拷贝。
（8）判空empty( )
判断set是否为空：
bool empty() const;
判断s是否为空：
cout << s.empty() << endl;
0表示不为空：
（9）求set的元素个数size( )
求set的元素个数：
size_type size() const;
求s的元素个数：
cout << s.size() << endl;
（10）清空所有元素clear( )
清空set中的元素：
void clear();
清空s中的所有元素：
1. s.clear(); 2. 3. for (auto e : s) 4. { 5. cout << e << " "; 6. } 7. cout << endl;
