Question

C++ 关联容器

Answer 1

关联容器不支持顺序容器的有关位置方面的操作，对于有序容器而言，标准库使用关键字类型的<运算符来比较两个关键字，在集合类型，关键字类型就是元素类型；在映射类型，关键字类型是元素的第一部分的类型。替代<的函数必须在关键字类型上定义一个 严格弱序 。

当解引用一个关联容器迭代器时，会得到一个类型为value_type的之的引用，不能修改关键成员的值。set的iterator和const_iterator都只允许只读

通常不对关联容器使用算法，因为它们的关键字都是const,故只能用于只读算法，使用关联容器定义的find方法比泛型要快

对于不允许关键字重复的关联容器，insert(v)返回一个pair类型，pair的first成员是指向给定元素的迭代器，second成员是一个表示是否插入成功的bool值。
insert(p,v) 表示从p开始搜索新元素应该存储的位置,返回指向给定元素的迭代器。
对于允许关键字重复的关联容器，insert(v)返回指向给定元素的迭代器

map和unordered_map提供下标运算符和一个对应的at函数，使用下标运算符，返回类型是mapped_type，如果关键字不在map中，会为它创建一个元素插入到map中，关联值将进行值初始化，at函数当关键字不在容器中，会抛出Out of range异常

lower_bound(k)：返回第一个不小于k的元素的迭代器
upper_bound(k)：返回第一个大于k元素的迭代器
equal_range(k): 返回一个迭代器pair,表示等于关键字k的元素范围，若k不在，返回两个end()

无序关联容器在存储上使用哈希函数和关键字 类型的==运算符，使用链地址法来解决哈希冲突，同时额外提供了哈希策略来重组容器。