C++关联容器，STL关联容器

关联容器内部的元素都是排好序的，有以下四种。

• set：排好序的集合，不允许有相同元素。
• multiset：排好序的集合，允许有相同元素。
• map：每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的。不允许有多个元素的关键字相同。
• multimap：和 map 类似，差别在于元素的关键字可以相同。

不能修改 set 或 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 set 或 multiset 容器中某个元素的值，正确的做法是先删除该元素，再插入新元素。

同理，也不能修改 map 和 multimap 容器中元素的关键字。

关联容器内部的元素或关键字之间比较大小可以用<运算符，也可以用自定义的比较器。因为有序，所以在关联容器上进行查找的速度较快。

使用关联容器的目的也就在于快速查找。当一个元素被插入关联容器时，该元素会和已有的元素进行比较，最终被插入一个合适的位置。

在关联容器中查找元素和插入元素的时间复杂度都是 O(log(n))。从 begin() 到 end() 遍历整个关联容器，就是从小到大遍历整个容器。

在排好序的 vector 和 deque 上进行折半查找，时间复杂度也可以是 O(log(n))。但是，对于插入、删除和查询交替进行的情况，使用 vector 和 deque 的效率不高。因为它们上面的插入和删除操作会引起元素的移动，时间复杂度是 O(n)。

关联容器一般是用平衡二叉树实现的。平衡二叉树的原理属于“数据结构”课程的内容，本教程不做介绍。

除了所有容器共有的成员函数外，关联容器还具有以下成员函数：

• find：查找某个值。
• lower_bound：查找某个下界。
• upper_bound：查找某个上界。
• equal_range：同时查找上界和下界。
• count：计算等于某个值的元素个数。
• insert：插人一个元素或一个区间。