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

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

1.关联式容器

根据应用场景的不同，STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列

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

键对值中的 key 表示键值，value 表示与 key 对应的信息

SGI-STL中关于键值对的定义：

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

2.set

set 的主要特征可总结为：

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