一、介绍
1. Hashtable和bucket
由于unordered_map内部采用的hashtable的数据结构存储，所以，每个特定的key会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable是可能存在冲突的（多个key通过计算映射到同一个位置），在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的（像桶子一样，可以装多个元素）。
所以unordered_map内部其实是由很多哈希桶组成的，每个哈希桶中可能没有元素，也可能有多个元素。
无序容器管理操作
- 有序容器通过比较运算符来组织元素
- 无序容器通过哈希函数和==运算符来组织元素
这是因为无序容器在存储上组织为一组桶：
- 哈希函数将元素映射到桶
- 在桶中搜索某个元素时需要用到==运算符
如果一个桶中保存了很多元素，那么查找一个特定元素就需要大量比较操作
无序容器提供了一些管理桶和哈希策略的操作：
桶接口
• c.bucket_count()
• c.max_bucket_count()
• c.bucket_size(n)
• c.bucket(k)
桶迭代
• local_iterator
• const_local_iterator
• c.begin(n), c.end(n)
• c.cbegin(n), c.cend(n)
哈希策略
• c.load_factor()
• c.max_load_factor()
• c.rehash(n)
• c.reserve(n)
2. 构造函数
unordered_map的构造方式有几种：
•
构造空的容器
• 复制构造
•
范围构造
• 用数组构造
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std; typedef unordered_map<string, string> stringmap;
stringmap merge(stringmap a, stringmap b)
{
stringmap temp(a);
temp.insert(b.begin(), b.end());
return temp;
} int main()
{
stringmap first; // 空
stringmap second({ {"apple", "red"}, {"lemon", "yellow"} }); // 用数组初始
stringmap third({ {"orange", "orange"}, {"strawberry", "red"} }); // 用数组初始
stringmap fourth(second); // 复制初始化
stringmap fifth(merge(third, fourth)); // 移动初始化
stringmap sixth(fifth.begin(), fifth.end()); // 范围初始化 cout << "sixth contains:" << endl;
for (auto& x : sixth)
cout << x.first << ": " << x.second << endl;
return ;
}
运行结果：
#include<string>
#include<iostream>
#include<map>
using namespace std; struct person
{
string name;
int age; person(string name, int age)
{
this->name = name;
this->age = age;
} bool operator < (const person& p) const
{
return this->age < p.age;
}
}; map<person, int> m;
int main()
{
person p1("Tom1", );
person p2("Tom2", );
person p3("Tom3", );
person p4("Tom4", );
person p5("Tom5", );
m.insert(make_pair(p3, ));
m.insert(make_pair(p4, ));
m.insert(make_pair(p5, ));
m.insert(make_pair(p1, ));
m.insert(make_pair(p2, )); for (map<person, int>::iterator iter = m.begin(); iter != m.end(); iter++)
{
cout << iter->first.name << "\t" << iter->first.age << endl;
} return ;
}
运行结果：
【分析】：因为Tom2和Tom3的age相同，由我们定义的operator<只是比较的age，所以Tom3覆盖了Tom2，结果中没有Tom2。