一、关联式容器和键值对

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;

【C++】-- STL之map和set详解（一）