目录
选择什么容器根据业务需求, 研读STL剖析了解底层数据结构, 更加清楚各种优势劣势
map, multimap:
set, multiset:
pair:
make_pair(t1, t2) —— 自动推断类型
pair的比较
先比较前者-first；再比较后者-second；依赖于元素的<或==
| key_type | 关键字类型 |
| mapped_type | set没有，关键字的关联类型 |
| value_tyep | 容器元素类型，对于set为key_type；对于map为pair<const key_type, mapped_type> |
set的iterator和const_iterator都是const的，即begin()和cbegin()得到的都是const迭代器
增
注意检查插入单独的元素时返回值，ret.second
| 操作 | map和set | multi版 |
|---|---|---|
| .insert(v) | 不存在时才插入或构造 | |
| .emplace(args) | 返回值：pair<iterator， bool>——bool判断成功与否，迭代器为插入元素 | 返回插入元素的迭代器 |
| .insert(p, v) | 迭代器p为指示器，指示从哪里开始找插入点，即使从.end()开始的，也能找到前面的插入点 | |
| .emplace(p, args) | 返回插入元素的迭代器 | |
| .insert(b, e) | 插入范围或列表内元素，返回void | |
| .insert(il) | 只插入不存在的 |
| .erace(k) | 返回size_type值，删除的数量 |
| .erace(p) | 若p不存在，未定义，若p == .end()，返回.end() |
| .erace(b, e) | 返回e |
| map和unordered_map的特定操作 | |
|---|---|
| [] | 存在返回；不存在，添加并值初始化 |
| .at() | 不存在，out_of_range |
通用操作
| .find(k) | 返回第一个找到的迭代器，不存在.end() |
| .count(k) | 数量 |
| .lower_bound(k) | 第一个>=k的迭代器 |
| .upper_bound(k) | 第一个>k的迭代器，和lower_bound得到一个范围 |
| .equal_range(k) | 返回迭代器pair<b, e>，k不存在，两个都为.end() |
根据通用操作得到的三种访问multi容器的方法
auto it = container.find(k);
auto cnt = container.count(k);
while (cnt)
{
*it ++;
-- cnt;
}auto begin = container.lower_bound(k);
auto end = container.upper_bound(k);
while (begin != end)
{
*begin ++;
}auto ret = container.equal_range(k);
auto begin = ret.first;
while (begin != ret.second)
{
*begin ++;
}unordered_map, unordered_multimap：
unordered_set, unordered_multiset：
无序容器存储上组织为一组桶，每个桶保存零个或多个元素
桶接口
| .bucket_count() | 当前桶个数 |
| .max_bucket_size() | 容器最大桶个数 |
| .bucket_size(n) | 第n个桶的元素个数 |
| .bucket(k) | k在哪个桶，返回整型 |
桶迭代
| local_iterator | 迭代器类型 |
| const_local_iterator | |
| .begin(n), .end(n) | 桶n的迭代器 |
| .cbegin(n), .cend(n) |
哈希策略
| 负载因子 | |
|---|---|
| .load_factor() | float，每个桶的平均元素个数 |
| .max_load_factor() | 试图维护的平均个数，需要时会加桶保持max_load_factor() > load_factor() |
| .rehash(n) | 重组存储，使桶个数>=n的同时，bucket_coun(实际有的) > size / max_load_factor(理论上维护factor需要的) |
| .reserve(n) | 重组存储，可以保存n个而不必rehash |
默认情况用==比较
内置类型，一些标准库设施如：string，智能指针，其他容器等等都哈希特例化，直接用
自定义类类型——自己提供==和哈希函数
size_t hasher(const MyClass &mc) // 这个用来找桶的
{
return hash<string>()(mc.str()); // str()的到MyClass里的成员，能用来标识
// hash<string>()得到一个临时可调用类对象
}
bool eqOp(const MyClass &mc1, const MyClass &mc2) // 这个用来找桶里元素的
{
return mc1.str() == mc2.str();
}
unordered_map<MyClass, decltype(hasher)*, decltype(eqOp)*> store;原文：https://www.cnblogs.com/YanceW/p/11701170.html