0.目录
- map
- unordered_map
- set
- unordered_set
- multimap
- unordered_multimap
- multiset
- unordered_multiset
1.map
stl中的关联容器，底层以红黑树实现，根据key值与比较函数有序排列，查找时间复杂度为O(log2 n)。根据key的唯一性不允许有重复元素。
#include <map>
std::map<KeyType, ValueType> m;
m.insert(std::make_pair(key, value)); // 三种插入方式，当key已存在时插入失败
m.insert(std::pair<type1, type2>(key, value));
m.insert({ key, value });
m[key] = value; // 若key不存在则插入，已存在则更新value
value = m[key]; // 取key对应的值。注意：当key不存在时同样会执行插入操作
m.find(key); // 查找key对应的元素，成功返回对应iterator，失败返回m.end()
m.count(key); // 查找key是否存在，是返回1，否返回0
m.erase(key); // 删除对应的元素，成功返回1（成功删除元素数），失败返回0（该元素不存在）
m.erase(iterator); // 删除iterator指向的元素，返回下一个元素的iterator，删除后map为空则返回m.end()
// 该iterator必须为有效迭代器，不能是结束迭代器
m.erase(iterator1, iterator2); // 删除[iterator1, iterator2)区间内的元素，返回下一个元素的iterator
std::map<KeyType, ValueType>::iterator iter = m.begin();
iter->first = key; // 错误，元素的键值无法修改
iter->second = value; // 修改value
比较函数
map中默认按key值的升序排列，即std::less<T>，若想更换比较方式，可以使用标准库中的比较函数：
std::map<KeyType, ValueType, std::less<KeyType>> m; // key1 < key2
std::map<KeyType, ValueType, std::less_equal<KeyType>> m; // key1 <= key2
std::map<KeyType, ValueType, std::greater<KeyType>> m; // key1 > key2
std::map<KeyType, ValueType, std::greater_equal<KeyType>> m; // key1 >= key2
对于自定义的类型的key，需要重载操作符<：
//方法1
struct KeyType
{
int a;
int b;
bool operator< (const KeyType& k) const
{
return a < k.a && b < k.b;
}
};
std::map<KeyType, ValueType> m;
std::map<KeyType, ValueType, std::less<KeyType>> m;
或特例化标准库函数：
//方法2
templete<>
struct std::less<KeyType>
{
bool operator() (const KeyType& k1, const KeyType& k2) const
{
return k1.a < k1.a && k1.b < k2.b;
}
};
std::map<KeyType, ValueType> m;
std::map<KeyType, ValueType, std::less<KeyType>> m;
也可以自定义比较函数：
//方法3
struct KeyCompare
{
bool operator() (const KeyType& k1, const KeyType& k2) const
{
return k1.a < k1.a && k1.b < k2.b;
}
};
std::map<KeyType, ValueType, KeyCompare> m;
2.unordered_map
stl中的关联容器，底层以哈希表实现，内部无序排列。查找时间复杂度为O(1)。根据key的唯一性不允许有重复元素。
元素的位置由键的哈希值确定，因而必须有一个适用于键类型的哈希函数。如果用类对象作为键，需要为它定义一个实现了哈希函数的函数对象
键可以不通过搜索就访问无序 map 中的对象，可以很快检索出无序 map 中的元素。迭代遍历无序 map 中的元素序列的速度一般没有有序 map 快。
#include<unordered_map>
std::unordered_map<KeyType, ValueType> m;
m.insert(std::make_pair(key, value)); // 三种插入方式，当key已存在时插入失败
m.insert(std::pair<type1, type2>(key, value));
m.insert({ key, value });
m[key] = value; // 若key不存在则插入，已存在则更新value
value = m[key]; // 取key对应的值。注意：当key不存在时同样会执行插入操作
m.find(key); // 查找key对应的元素，成功返回对应iterator，失败返回m.end()
m.count(key); // 查找key是否存在，是返回1，否返回0
m.erase(key); // 删除对应的元素，成功返回1（成功删除元素数），失败返回0（该元素不存在）
m.erase(iterator); // 删除iterator指向的元素，返回下一个元素的iterator，删除后map为空则返回m.end()
// 该iterator必须为有效迭代器，不能是结束迭代器
m.erase(iterator1, iterator2); // 删除[iterator1, iterator2)区间内的元素，返回下一个元素的iterator
迭代器非法化
| 操作 | 非法化 |
|---|---|
| 所有只读操作、swap、std::swap | 从不 |
| clear、rehash、reserve、opreator= | 始终 |
| insert、emplace、emplace_hint、operator[] | 仅若重哈希导致 |
| erase | 仅为指向被擦除元素者 |
注：
- swap 函数不非法化容器内的任何迭代器，但它们非法化标记交换区域结尾的迭代器。
- 指向存储于容器中的关键或元素的引用和指针仅因擦除该元素才被非法化，即使在非法化对应迭代器时。
比较函数
unordered_map根据key的hash值判断元素是否相同，为解决hash碰撞还需要判断两个元素是否相同，因此对于自定义类型，需要实现hash()和operator==:
struct KeyType
{
int a;
int b;
size_t hash() const
{
// 得到hash值，为避免hash碰撞，一般可将各项成员取hash值后移位异或
return std::hash<decltype(a)>()(a) + std::hash<decltype(b)>()(b);
}
bool operator== (const KeyType& k) const
{
return k.a == a && k.b == b;
}
};
//unordered_map 容器的哈希函数只能接受和键同类型的单个参数，可以定义一个满足这些条件的函数对象类型，调用KeyType::hash():
struct KeyHash
{
size_t operator() (const KeyType& k) const
{
return k.hash();
}
};
std::unordered_map<KeyType, ValueType, KeyHash> m;
或特例化std::hash<T>和std::equal_to<T>：
template<>
struct std::hash<KeyType>
{
size_t operator() (const KeyType& k) const noexcept
{
// 得到hash值，为避免hash碰撞，一般可将各项成员取hash值后移位异或
return std::hash<decltype(k.a)>()(k.a) + std::hash<decltype(k.b)>()(k.b);
}
};
// std::equal_to<T>也可以通过类内重载opreater==来实现
template<>
struct std::equal_to<KeyType>
{
bool operator() (const KeyType& k1, const KeyType& k2) const noexcept
{
return ((k1.a == k2.a) && (k1.b == k2.b))；
}
};
std::unordered_map<KeyType, ValueType> m;
也可以自定义hash函数和比较函数：
struct KeyHash
{
size_t operator() (const KeyType& k) const
{
return std::hash<decltype(k.a)>()(k.a) + std::hash<decltype(k.b)>()(k.b);
}
};
struct KeyCompare
{
bool operator() (const KeyType& k1, const KeyType& k2) const noexcept
{
return ((k1.a == k2.a) && (k1.b == k2.b))；
}
};
std::unordered_map<KeyType, ValueType, KeyHash, KeyCompare> m;
元素存储
unordered_map中的元素按key的hash值存储在hash表中，这个表中的条目被称为格子，每个格子可以包含几个元素。
一个给定的哈希值会选择特定的格子，因为哈希值可能的个数几乎可以肯定会大于格子的个数，两个不同的哈希值可能会映射到同一个格子上。因此，不同键会产生相同的哈希值，会产生碰撞，而且两个不同的哈希值选择相同的格子也会导致碰撞的产生。
下面的一些参数可以影响元素存储的管理：
- 容器中格子的个数有一个默认值，但也可以定指定初始个数。
- 载入因子是每个格子平均保存的元素的个数。这个值等于容器中元素个数除以格子的个数。
最大载入因子，默认是 1.0，但也可以修改。这是载入因子的上限。当容器达到最大载入因子时，容器会为格子分配更多的空间，这通常也会对容器中的元素重新进行哈希。
任何时候都不要将单个格子中的最大元素个数和最大载入因子混淆。假设有一个容器，它有 8 个格子，前两个格子中各有 3 个元素，剩下的格子都为空。那么这时候的最大载入因子为 6/8，也就是 0.75，小于默认的最大载入因子 1.0，所以这没有什么问题。
std::unordered_map<int, int> m = { { 1, 1 }, { 2, 2 }, 10 }; // 可以在初始化列表中指定格子数
在维持当前载入因子的前提下，如果插入元素数超过了格子可以满足的个数，容器将增加格子的个数。为了将元素重新分配到新的格子中，元素会被再次哈希，当前存在的任何迭代器都会失效。
可以调用成员函数 rehash() 来改变格子的个数：
m.rehash(15); // Make bucket count 15
// rehash() 的参数可以比当前格子数多或少
// 这条语句会将格子的个数变为 15，只要它不导致当前因子超过最大载入因子
// 容器中的所有元素都会被重新哈希分配到新的格子中，而且当前所有的迭代器都会失效
// 如果指定的格子个数导致载入因子超过最大载入因子，那么格子会自动增加来避免超出最大值。
m.bucket_count(); // 获得当前格子数
m.max_load_factor(); // 获得最大载入因子
m.max_load_factor(2 * m.max_load_factor()); // 调整最大载入因子
m.load_factor(); // 当前载入因子
m.reserve(100); // 设置格子的个数，使它们在容纳给定个数的元素的同时将负载因子维持在最大数之内
// 设置了格子的个数，使它可以容纳 100 个元素而不超过最大载入因子的限制
// 这会导致容器中的内容被重新哈希，从而使所有的当前迭代器失效
// 也可以不考虑载入因子和格子个数来生成和使用 unordered_map 容器。容器自己会处理这些事情。
注：
- 每个格子中的元素不超过一个时，访问速度最快，但需要很多内存而且会有很多的空格子
- 增大最大载入因子可以使每个格子容纳更多的元素，从而使格子的总数越少
- 每个格子中的元素越多，访问元素的速度越慢
- 最重要的事是要避免反复哈希容器的内容
3.set
4.unordered_set
5.multimap
multimap 容器保存的是有序的键/值对，但它可以保存重复的元素，默认的比较键的函数是 less<K>()，大部分成员函数的使用方式和 map 相同。
- multimap 容器的成员函数 insert() 可以插入一个或多个元素，而且插入总是成功
- emplace() 插入到当前所有具有相同键的元素的后面，emplace_hint()尽可能在第一个参数所指向位置的前面生成一个新元素
- multimap 不支持下标运算符，因为键并不能确定一个唯一元素
