关联性容器 关联容器是指C标准模板库中的一套类模板实现了有序关联数组可用于存放任意数据类型的元素C标准中定义的关联容器有 set map multiset multimap 关联容器类似于C中的无序关联容器差别为 关联容器是红黑树实现无序关联容器是哈希表实现 关联容器保证按键值有序遍历因此可以做范围查找而无序关联容器不可以关联支持一些导航类的操作如求出给定键最邻近的键最大键最小键操作 关联容器的迭代器不会失效除非所指元素被删除无序关联容器的iterator在修改元素时可能会失效所以对关联容器的遍历与修改在一定程度上可并行 哈希表查找时候要算hash这个最坏时间复杂度是Okey的长度基于比较的有序关联容器通常只使用头几个字符进行比较