C++漫溯键值的长河：map && set

迄今为止，除了二叉搜索树以外的结构，我们学习到的序次表，链表，栈和队列等都属于这些容器统称为序列式容器，因为其底层为线性序列的数据结构，内里存储的是元素自己
1.关联式容器

   根据应用场景的差别，STL 总共实现了两种差别结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：利用均衡搜索树(即红黑树)作为其底层效果，容器中的元素是一个有序的序列
  关联式容器也是用来存储数据的，与序列式容器差别的是，其内里存储的是<key, value>结构的键值对，在数据检索时比序列式容器服从更高
键对值中的 key 表示键值，value 表示与 key 对应的信息
SGI-STL中关于键值对的定义：

1. template <class T1, class T2>
2. struct pair
3. {
4.         typedef T1 first_type;
5.         typedef T2 second_type;
6.         T1 first;
7.         T2 second;
8.         pair() : first(T1()), second(T2())
9.         {}
10.        
11.         pair(const T1& a, const T2& b) : first(a), second(b)
12.         {}
13. };

复制代码

2.set

set 的主要特征可总结为：

• set 是按照一定序次存储元素的容器
  
• 在 set 中，元素的 value 也标识它( value 就是 key，类型为 T )，而且每个 value 必须是唯一的 set 中的元素不能在容器中修改(元素总是 const )，但是可以从容器中插入或删除它们
  
• 在内部，set 中的元素总是按照其内部比力对象(类型比力)所指示的特定严格弱排序准则举行排序
  
• set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据序次对子集举行直接迭代
  
• set 在底层是用二叉搜索树(红黑树)实现的