What & How & Why

关联容器

C++ Primer 笔记 第十一章


关联容器Associative Container)指使用 Key 进行元素存取的容器。这种存取方式使得关联容器的查询效率非常高

关联容器拥有两种类型:MapSet

  • Map 中的元素成对出现,包括一个 Key 与其对应的存储内容
  • Set 中的 Key 就是元素

从应用上来讲,需要快速查找指定内容的情形可以使用 Map,比如字典:字就是 key,而解释就是存储的内容。而利用 Set 可以实现高效的文字过滤。

STL 提供的关联容器分为 8 种,主要以三个方面来划分:

  • 是 set 或 map
  • Key 是否唯一
  • 是否按顺序存储元素(Key 是不是有序)

允许重复 Key 的关联容器以 multi 开头;不按顺序存储元素的关联容器以 unordered 开头。比如:

unordered_multmap
指的是一个元素内容成对出现的、Key 可以重复的、内容不按顺序存储的关联容器。所有容器的类型如下图:

关联容器的头文件
  • mapmultimap 类型定义于 <map> 头文件中
  • setmultiset 类型定义于 <set> 头文件中
  • 对应的 unordered 版本分别定义于 <unordered_map> / <unordered_set> 头文件中

使用关联容器

Map 用于存储一系列 key-value pair;这种元素的结构可以被视作从 Key 到 value 的映射。通常 Map 被视作关联容器中的 Array,只是其下标不再是 int,而是 Key 的值。Map 中的值是通过 Key 进行查找;比如查找对应人员的电话就可以写成:

person[name];
Set 用于存储一系列的 key。 Key 本身即为 Set 的元素。Set 在对已有信息进行筛选的任务中非常有用。

使用 Map

一个比较经典的用法使用 Map 检测某个词输入了多少次:

首先,Map 的定义需要指定 key 与 value 的类型:

map<string, size_t> word_count; 
//other def
string word;
其次,map可以通过 map_name[key_name] 的方式对 key 对应的 value 进行修改。我们这里对输入的 key(也就是输入的词,变量名 word)进行输出次数的累加,累加的值存入 key 对应的 value 里:
while(cin >> word)
	++word_count[word];
需要注意的是,当通过新的 key(word)创建 pair 的时候, value 的初始值为 0

当输入完成以后,使用循环将信息打印出来。Map 也可以使用 range for 打印:
for(const auto &w : word_count)
	cout << w.first << " occurs " 
		 << w.second << ((w.second > 1) ? "times" : "time")
	     << endl;
打印 pair 的时候需要分开打印。 first 成员保存 key, second 成员保存 value,也就是对应 key 的出现次数。

使用 Set

Set 常用于过滤关键词。比如下面的例子,我们将使用 Set 定义屏蔽词列表,使 Map 只统计未被屏蔽的关键词输入次数。

首先定义 Set。由于 Set 只包含 key,因此只需要指定 key 的类型:

set<string> exclude ={"The", "But", "And", "Or", "An", "A",
					  "the", "but", "and", "or", "an", "a"};
//other def
map<string, size_t> word_count; 
string word;
接下来使用循环输入数据。这里我们通过两个 set 成员 find()end() 实现条件的判断:
while (cin >> word)
	if(exclude.find(word) == exclude.end())
		++word_count[word];
find() 会接收一个 Key,并在调用它的对象中寻找是否有匹配的 Key。如果找到,返回指向该 Key 的迭代器;如果没有找到,则返回 off-the-end 迭代器,也就是这里的 exclude.end()。因此,上面的程序实际上意味着,只要 map 中的词不存在于黑名单中,则对其累加一次计数。

关联容器概述

关联容器与顺序容器都支持一般的容器操作 (见 Container Operations);但也有一些例外,比如:

  • 由于关联容器基于 Key 实现存储,因此不支持基于位移的顺序容器操作,比如 push_back()
  • 关联容器不支持构造、插入 pair 类型数据的操作。

除此之外,C++ 还提供了一些关联容器专属的操作和 type alias,并且,针对 unodered 系列的关系容器,C++ 提供了针对性的优化版本(基于 Hash 的优化版本)。

关联容器使用双向迭代器

定义关联容器

MapSet 初始化只要求 initializer 的类型满足要求即可。MapSet默认初始化会得到一个空的关联容器。此外,MapSet 都可以进行列表初始化;需要注意 Map 的写法稍微有些特别:

//default initialization
map<string, size_t> word_count; 
set<string> bad_check;

//list initialization
map<string, string> authors = { {"Joyce", "James"},
								{"Austen", "Jane"}, 
								{"Dickens", "Charles"} };

set<string> exclude = {"the", "but", "and", "or", "an", "a",
					   "The", "But", "And", "Or", "An","A"};
上例中,Map单个元素通过另外一对 curly braces 来表示,即:
{key, value}

定义 multimap 或 multiset

MapSet 不同,在 MultimapMultiset 中,Key 的映射关系变得不再唯一,多个 value 可以同时对应一个 Key(比如字典中,某个词有多种不同解释)。比如下面的例子,使用了相同的 vector 对 set 和 multiset 进行初始化:

// define a vector with 20 elements, holding two copies of each number from 0 to 9
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
    ivec.push_back(i);
    ivec.push_back(i);  // duplicate copies of each number
}
// iset holds unique elements from ivec; miset holds all 20 elements
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl;    // prints 20
cout << iset.size() << endl;    // prints 10
cout << miset.size() << endl;   // prints 20
cout << miset.size() << endl; // prints 20
由于 set 中的 key 是唯一的,因此其元素要比 multiset 少一半。

对 Key 的要求

有序关联容器使用 Key 对元素进行排序。因此,有序关联容器的 Key 需要定义关系运算(该要求与排序算法要求的可调用对象相同)。关联容器默认的比较操作为 <

有序关联容器中对 Key 的类型要求

与在排序算法中自定义比较策略类似,我们也可以按自定义的规则对 Key 进行排序。该规则需要需要 Key 类型满足 Strict weak ordering 的标准:

// two keys cannot both be "less than" each other
1) if F(key1, key2) == true, then F(key1, key2) == false

// k1 "less than" k2  and k2 ""less than k3, then k1 must be "less than" k3.
2) if F(key1, key2) == true, F(key2, key3) ==true, then F(key1, key3) == true

//definition of equivalent, and transitivity of the equivalent
3) if F(key1, key2) == false && F(key2, key1) == false, then key1 == key2 
4) if key1 == key2 && key2 == key3, then key1 == key3
可以看出 并不满足第一条与第三条。因此需要注意避免在规则中使用这两个关系运算。

当在 map 中使用 key 的时候,若两个 key 等价,则只允许有一个 value 与这些 key 相关,且通过这些 key 访问到的都是该相关的 value。

从实现上来说,为 key 类型定义一个行为正常的 $<$ 关系运算是非常重要的。

Refs:

为容器元素的排序指定比较策略

先明确几个理解:

  • 用于组织容器内元素的操作(比如排序),也属于容器类型的一部分,需要在声明的时候在三角括号内写上
  • 该类型的操作通常通过函数来实现
  • 传递该类型则通过函数指针来实现

默认情况下,有序关联容器通过 < 操作排序。如果元素没有定义该操作,我们可以通过以函数的方式来定义(或重定义)该操作。比如之前的 Sales_data 类,我们可以通过比较其 isbn 来对其进行排序:

//The comparison must meet the requirements of the Stirct Weak Ordering.
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs) {
    return lhs.isbn() < rhs.isbn();
}
我们通过函数指针将其作为类型参数传递给 set。需要注意的是:

  • 传递函数类型时,一般通过函数指针传递。
  • 普通列表项目如果此时使用 decltype,则 * 是一定要加上的,因为 decltype 会返回函数的类型。
  • 由于 ISBN 相同的书可能存在多个交易记录,因此使用 multiset
  • multiset bookstore 的构造函数使用的初始值 compareIsbn,无论带不带取地址符 &,最终都将会被转化为指向该函数的指针。

// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*>
    bookstore(compareIsbn);

代表策略的函数 compareIsbn 存储于 bookstore 中。上述的初始化建立了一个名为 bookstore 的,key 的比较策略为 compareIsbn 的空 multiset。

更多 multiset 的构造函数用法:链接

Pair 类型

Pair 类型是一种 STL 定义的模板类型,定义于 <utility> 头文件中。Pair 拥有两个成员,在定义的时候需要分别指定两个成员的类型。成员的类型不需要一致

pair<string, string> anon; // holds two strings
pair<string, size_t> word_count; // holds a string and an size_t
pair<string, vector<int>> line; // holds string and vector<int>
Pair 的默认构造函数为其成员提供值初始化;同时,也可以通过提供初始值初始化 pair:
pair<string, string> author{"James", "Joyce"};
Pair 的两个数据成员均为 public,可以通过其成员 first / second 进行访问:
cout << w.first << w.second << endl;
一些 pair 类型相关的操作:



返回 pair 类型

当需要以 Pair 类型做为返回值的时候,有几种方法可以使用:

  • list intialize the return value(C++ 11)

pair<string, int>
process(vector<string> &v)
{
     // process v
     if (!v.empty())
         return {v.back(), v.back().size()}; // list initialize
     else
         return pair<string, int>(); // explicitly constructed return value
}

  • 构造并返回 pair (早期版本)

if (!v.empty())
    return pair<string, int>(v.back(), v.back().size());

  • 使用 make_pair() 返回一个新的 Pair

if (!v.empty())
    return make_pair(v.back(), v.back().size());

关联容器的操作

关联容器还定义了一些属于自己的类型:

  • key_type,用于表示 key 的类型
  • mapped_typemap 类型专属,用于表示 map 中 key 对应的 value 的类型
  • value_type,一个泛化的类型:
    • 在 set 中表示 key_type
    • 在 map 中表示 pair<const key_type, mapped_type>

由于 map 的元素是以 key-value 的 pair 形式存在,且我们无法改变 key 的值;因此 pair 中的 key 部分是 const:

set<string>::value_type v1;      // v1 is a string
set<string>::key_type v2;        // v2 is a string
map<string, int>::value_type v3; // v3 is a pair<const string, int>
map<string, int>::key_type v4;   // v4 is a string
map<string, int>::mapped_type v5; // v5 is an int
type 的写法与顺序容器中的自定义类型一致,需要组合 scope 操作符使用:
map<string, int>::key_type

关联容器的迭代器

对关联容器迭代器的解引用运算会返回指向 value_type引用。由于 map 的 value_type 对应 pair,因此可以使用迭代器访问其 firstsecond 成员:

// get an iterator to an element in word_count
auto map_it = word_count.begin();
// *map_it is a reference to a pair<const string, size_t> object
cout << map_it->first;          // prints the key for this element
cout << " " << map_it->second;  // prints the value of the element
map_it->first = "new key";      // error: key is const
++map_it->second;     // ok: we can change the value through an iterator
需要注意的是,迭代器只能修改 Map 中元素的 value。

set 的迭代器都是只读的

无论 set 的迭代器是 non-const 还是 const,我们都只能通过该迭代器进行只读操作。这是因为 set 中的 key 依然是不可更改的:

set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end()) {
    *set_it = 42; // error: keys in a set are read-only
    cout << *set_it << endl; // ok: can read the key
}

使用迭代器对关联容器进行遍历

MapSet 也提供了 begin()end() 成员函数,用于获取器的起始位置和 off-the-end 位置。我们可以利用这些成员遍历容器:

/ get an iterator positioned on the first element
auto map_it = word_count.cbegin();
// compare the current iterator to the off-the-end iterator
while (map_it != word_count.cend()) {
// dereference the iterator to print the element key--value pairs
    cout << map_it->first << " occurs "
         << map_it->second << " times" << endl;
    ++map_it; // increment the iterator to denote the next element
}
上面的打印结果会根据字母表排序。实际上,使用迭代器遍历 map / set,得出的排序会按照 key 的升序来排列。

关联容器与泛型算法

不推荐对关联容器使用泛型算法:

  • 由于 key 是 const,要求写的泛型算法无法在关联容器上使用。
  • 泛型算法的读取与查找是序列性的,并不适用于关联容器的数据结构。

如果非要使用:

  • 将关联容器当做源序列,比如拷贝关联容器的内容到别的序列中
  • 使用 Inserter 的方式对关联容器进行算法的应用

添加元素

关联容器可以通过成员 insertemplace 向容器中添加元素。相关的操作如下:



需要注意的是,Mapset 添加元素的时候,均会验证 key 的唯一性。对于已存在的 key无论是插入操作还是构造操作,都是无效的。一些例子:
vector<int> ivec = {2,4,6,8,2,4,6,8}; // ivec has eight elements
set<int> set2; // empty set
set2.insert(ivec.cbegin(), ivec.cend()); // set2 has four elements
set2.insert({1,3,5,7,1,3,5,7}); // set2 now has eight elements

向 map 中添加元素

只要是 pair 类型的元素,都可以向 map 里添加。添加方式有 4 种:

  • 初始化列表
  • 使用 make_pair() 创建要插入的元素
  • 显式的使用 argument_list 构造元素
  • 使用 value_type 构造元素

// four ways to add word to word_count
word_count.insert({word, 1}); //list 
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1)); //argument list
word_count.insert(map<string, size_t>::value_type(word, 1)); // value_type

测试 insert 的返回值

对于像 MapSet 这样 Key 是独一无二的容器,insert 成员的指定调用形式会返回一个 pair ,用于告知插入是否成功。该 pair 由一个迭代器与一个 bool 类型组成;迭代器指代的是插入元素所在的 key 的位置,而 bool 类型则用于说明插入的状态。如果当前容器已经存在相同而对 key, 则 insert 操作无效,bool 返回 false 的值。

该 bool 返回值也可以用于计算输出词的频率:

// more verbose way to count number of times each word occurs in the input
map<string, size_t> word_count; // empty map from string to size_t
string word;
while (cin >> word) {
    // inserts an element with key equal to word and value 1;
    // if word is already in word_count, insert does nothing
    auto ret = word_count.insert({word, 1});
    if (!ret.second)         // word was already in word_count
        ++ret.first->second; // increment the counter
}
总的逻辑是,如果插入操作返回的 bool 数为假,则证明该词已经被插入过了(出现过了),因此增加一次该词的累积次数。

++ret.first→second 怎么解释?

  • ret: 存储插入操作返回值,即一个迭代器与 bool 组成的 pair
  • ret.first: 返回 pair 中的迭代器,指向元素 {word, 1}
  • ret.first→second: 元素 {word, 1} 的 value,1,也就是 word 当前累积出现的次数
  • ++ret.first→second:增加一次 word 出现的次数

这里的迭代器的类型是基于 map 类型的。本例中的迭代器类型是:

map<string, size_t>::iterator

向 multimap / multiset 中添加元素

multimap / multiset 的元素添加不受 key 的限制;也就是说,一个 key 可以对应多个 value。很多应用可以基于这样的结构实现:比如某个作者写了很多本书,则作者可以作为 key 值,他写的书可以做为 value。通过对 multimap 进行元素添加,我们可以把作者与他的书关联起来:

multimap<string, string> authors;
// adds the first element with the key Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
// ok: adds the second element with the key Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"});
该插入操作返回一个迭代器,指向最新添加的元素

删除元素

关联容器使用 erase 成员删除元素。erase 可以通过 key、单个迭代器和迭代器范围来指定容器中需要被移除的元素:



使用 key_type 类型作为参数的版本会移除所有 key 值相同的元素值,并返回移除元素的数量。该功能可以作为条件,判断是否进行了元素的移除:
// erase on a key returns the number of elements removed
if (word_count.erase(removal_word))
cout << "ok: " << removal_word << " removed\n";
else cout << "oops: " << removal_word << " not found!\n";
当操作容器具有唯一的 key 时,该返回值永远是 01。如果容器允许多个 key 存在,则可以获得移除的元素:
auto cnt = authors.erase("Barth, John"); // cnt = 2

使用下标访问 map

关系容器中,只有 map 接受下标 [] 操作(以及对应的 at())。该操作接受一个 key,返回 Key 对应的 value。该操作详情如下:



Set 不接受该操作,因为 set 中只存在 Key 值;Mulitmap(以及其 Unordered 版本)也不支持该操作,因为 Key 对应的 value 不唯一。除此之外还需要注意:

  • 通过下标访问 map 中不存在的元素时,会直接创建一个对应 key 的新元素。该元素的值会被值初始化
  • 生成新元素的操作是 insert() 操作,因此当 map 是 const 的时候不可使用

map <string, size_t> word_count; // empty map
// insert a value-initialized element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;

如何使用下标访问的返回值

需要注意的是:然而在 map 中,解引用与下标操作的返回值是不同的:

  • 通过下标访问 map ,返回的值是 map_type 的对象
  • 对 map 迭代器解引用,返回的值是 value_type 的对象

除此之外,使用下标访问的返回值是 lvalue。我们可以利用该性质对对应元素进行写操作:

cout << word_count["Anna"]; // fetch the element indexed by Anna; prints 1
++word_count["Anna"];       // fetch the element and add 1 to it
cout << word_count["Anna"]; // fetch the element and print it; prints 2

下标操作会添加不存在的元素。如果只是想查看容器是否包含指定元素,请不要使用下标访问该元素。

访问元素

关联容器提供了如下的方式供使用者访问元素:



如何使用上述的操作取决于应用对象,比如:

  • find 主要用于确认容器内是否存在主要元素
  • count 在 key 对应元素不唯一的情况下可以做更多事情

一些例子:

set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); // returns an iterator that refers to the element with key == 1
iset.find(11); // returns the iterator == iset.end()
iset.count(1); // returns 1
iset.count(11); // returns 0

使用 find 取代下标

find 成员访问不存在的元素时,不会将其添加到 map。如果只想确认 map 中是否存在某个 key,使用 find

if (word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;

multimap / set 中的元素寻找

Multimap 为例。 multimap 中,一个 key 可能对应多个 value,因此寻找 multimap 中的元素需要通过几个变量配合使用来完成。比如,如果想找出一个作者对应的所有出版书籍,我们可以通过如下的逻辑来进行查找和输出:

  1. 定义要查找的 key, 也就是作者的名字
  2. 定义要搜寻的次数,也就是作者著作的数量,可以使用 count(key) 计算出
  3. 该元素在容器中所处的位置,使用 find 成员即可获得指向第一本书籍位置的迭代器
  4. 使用搜寻的次数做为循环,循环中:
    1. 打印当前的书籍
    2. 将迭代器自增移动,指向下一本书籍
    3. 将搜寻次数自减,意味着一本书籍已经搜索完成

string author_name("Alain de Botton");
auto entries = authors.count(author_name); //number of books
auto iter = authors.find(author_name); //the position of the first book

while(entries) {
	cout << iter->second << endl; //print each book
	++iter; //to the next book
	--entries; 
}
迭代器实现版本

上述循环可以通过两个成员的返回结果来实现:

  • lower_bound(k):返回一个迭代器,指代不小于 k 的 key 中的第一个元素;如果 key 不存在,则返回 off-the-end 迭代器。
  • upper_bound(k):返回一个迭代器。如果当前有 key 正好大于 k,则返回 key 中的第一个元素。如果 k 最大,则返回 off-the-end 迭代器。

利用上述成员的功能,如果使用当前的 key,也就是作者的名字作为 k 值,就可以建立遍历作者所有书籍的循环:

curr_iter = lower_bound(curr_key); // curr_iter denotes the first element of curr_key
next_iter = upper_bound(curr_key); // next_iter denotes the first element of next_key


因此,实现代码可以写成:
auto curr_book = authors.lower_bound(author_name);
auto next_book = authors.upper_bound(author_name);

for (curr_book; curr_book != next_book; ++curr_book)
	cout << curr_book->second << endl;
如果查询不到该作者,则两个成员都会返回指向 of-the-end 的迭代器;这种情况下循环不会被执行。

equal_range 函数版本

比上述版本更简便的写法是使用 equal_range() 成员函数。该成员返回一个 pair 的迭代器。如果 key 存在,则第一个迭代器与 lower_bound 的结果一致,第二个迭代器与 lower_bound 的返回值一致。因此,我们只需通过 equal_range 就能建立起循环的范围:
for (auto pos = equal_range(author_name).first; 
	 pos != equal_range(author_name).second; ++pos) {
		cout << pos->second << endl;
	 }

实例:使用 Map 实现词转换

词的转换是一个很好的 Map 应用。它利用了 Map 元素中, Key-value 的一一对应性质,使用 value 中的长词汇来替换检测到的 key 中的缩写。比如 key 值 为 k,value 值为 okay,那么检测到输入中存在 k,就会替换成 okay

一个简单的实现方案大致分为三部分:

  • buildMap 函数,将指定的规则数据转换为 map,供主程序调用。
  • transform 函数,一个以词为单位,以指定 map 中的规则进行词转换的函数。
  • wordTransform 主函数,接收 / 处理 / 打印数据。



wordTransform 函数的实现

wordTransform 函数主要的功能是:

  • 接收 map 数据,并调用 buildMap 生成规则 map
  • 接收 input 的数据,并对数据进行拆分;将拆分好的数据交由 tansform 处理,并格式化输出打印结果:

void wordTransform(ifstream &mapData, ifstream &inputData)
{
	//build the tranform map
	auto transMap = buildMap(mapData);
	string line;

	while(getline(inputData, line))
	{
		std::istringstream wordStream(line);
		//output the result by word
		for(string word; wordStream >> word; )
			cout << transform(word, transMap) << " ";
		cout << endl;
	}	
}
这里通过了 getline() 接收每一行数据,并使用 istringstream 读取每一个词进行处理。每读取一个词,就使用 transform 函数对其判断并转化。

个人意见:书中对于空格的判定是多余的,正常输出即可打印出正确结果。

buildMap 函数的实现

buildMap 的功能很简单,读取文本数据并转化为对应的 map。几个要点:

  • 文本数据的单位为 key + space + value 的形式,因此需要分成两段进行读取。
  • 替换的时候需要检测 value 的值是否合法。本程序的主要目的是将缩写替换为全写,这里设定小于 1 的全写(value)不合法。
  • 在第二阶段读取 value 的时候,会将中间的空格一并读取;因此输出的时候需要使用 substr() 去掉。

const map<string, string> buildMap(ifstream &mapData)
{
	map<string, string> transMap;
	string abbr;
	string fullName;

	//reading data
	while(mapData >> abbr && getline(mapData, fullName))
	{
		if(fullName.size() > 1) // check that there is a transformation
			transMap[abbr] = fullName.substr(1); 
			//transMap.insert({abbr, fullName.substr(1)});
		else
			throw std::runtime_error("No rule for " + abbr); 
	}
	return transMap;
}
还有一点需要注意的是,本程序使用了下标的方法添加元素到 Map。 如果 key(缩写) 重名,则其对应的 value (全写) 将会被覆盖掉。如果希望保留旧的规则,可以替换使用 insert() 成员添加元素(方法如注释)。

transform 函数的实现

transform 函数接收指定的词。如果该词是 map 中定义的缩写,则将其按照 map 中的对应关系换成全写:

const string& 
transform(const string &s, const map<string, string> &mss)
{
	auto mapIter = mss.find(s);
	//if a transformable word 's' is found in rule data
	//return its fullname
	if(mapIter != mss.cend())
		return mapIter->second;
	else
		return s; // otherwise return the original unchanged
}
这里对不在 map 中的词做了不修改的处理。

无序关联容器

新标准中定义了四种无序关联容器。这些关联容器使用 == 或者指定的哈希函数Hash function)来组织管理元素。无序关联容器主要使用在:

  • 当 key 不需要有序的情况下
  • 当 key 的排序代价很高的情况下

但总的说来,尽管通过哈希函数来管理元素可以提供更好的平均性能,但对哈希函数的设计、测试与修改给我们带来了更多的工作量。因此,默认情况下,使用有序关联容器往往拥有更好的表现。

如果 Key 的无序是固有的,或者通过哈希函数管理元素可以解决性能的问题,使用无序关联容器。

使用无序容器

除了与哈希管理相关的成员,无序容器提供了与有序容器基本上一样的操作。不过因为其无序性,因此在输出的顺序上会与有序容器的输出有差别。

桶的管理

无序容器通过一系列的Bucket,也被侯捷老师称为篮子)来管理组织元素。每一个桶都拥有 0 个或更多的元素。无序容器通过哈希函数将元素分配进不同的桶内。哈希函数为每个桶都标记了指定的哈希值;当需要访问元素的时候,根据哈希值去对应的桶里搜寻元素。

当容器允许一个 key 对应多个元素的时候,所有与某个 key 相关的元素都会放到同一个桶中。因此,无序容器的性能依赖如两个要求:

  • 哈希函数是如何设计的
  • 桶里的元素有多少

当使用相同的 key 调用哈希函数的时候,哈希函数会确保返回同样的值。虽然在理想状态下,哈希函数应该为每一个元素都分配一个独立的哈希值;但由于容器允许 key 与 value 存在一对多的关系,因此很可能存在将同 key 下的 value 放入同一个桶中的情况。由于对单个桶中的元素查找是通过顺序查找的方式来进行的,这带来了一个问题:尽管通过 key 找元素对应的桶依然很快,但桶内的元素过多,会严重影响无序容器的性能

无序容器提供了如下的成员对桶进行管理:



无序容器对 key 的要求

默认情况下,无序容器使用 == 运算符来比较 Key(key_type). 我们也可以通过使用哈希值hash<key_type> 类型)来对元素进行比较。标准库提供了 std::hash 模板函数来生成哈希值。该函数支持 building-in 类型,某些标准库类型(比如string、smart pointer)等等。

不过,该模板函数并不能直接对自定义类型使用。计算自定义类型的哈希值有两种方法:

  • 创建自定义的哈希模板(之后的内容)
  • 使用哈希函数计算自定义类型中的某个受其支持的成员,并使用该成员来做为自定义类型的比较标准。

拿之前提到的 Sales_data 类作为例子。我们使用一个 multiset 来存放该类型的元素。multiset 的模板定义实际上允许我们指定哈希函数,以及比较相等性的函数:

template<
    class Key, //element type
    class Hash = std::hash<Key>,  //specified hash function
    class KeyEqual = std::equal_to<Key>, //fucntion that comparing equalty 
    class Allocator = std::allocator<Key>,  //allocator type
    > class unordered_multiset;
本例中,我们使用 std::hash 对类的 isbn 成员计算哈希值,并以此来进行元素分配。同时,我们也规定类相等的规则是其 isbn 相等:
size_t hasher(const Sales_data &sd)
{
	return hash<string>()(sd.isbn());
}

bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
	return lhs.isbn() == rhs.isbn();
}
因此,我们的 multiset 可以定义为:
std::unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*> bookstore(42, hasher, eqOp);
当然,最好使用 alias 简化写法:
using SdMultiset = std::unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>
SdMultiset bookstore(42, hasher, eqOp);
这里使用了函数指针作为传递的参数,与之前有序容器中使用自定义的 compareIsbn 函数用法相同。同时,我们为 bookstore 的构造提供了 3 个初始值,分别是桶的默认数量,哈希函数,比较函数。



关于 multiset 的构造函数列表:

上例使用的该构造函数进行初始化。

unordered_multiset ( size_type n,
                     const hasher& hf = hasher(),
                     const key_equal& eql = key_equal(),
                     const allocator_type& alloc = allocator_type() );
其他构造方式可以参考下面的引用。

Ref:std::unordered_multiset::unordered_multiset

如果类中已经定义了 == 运算,只提供哈希函数也可以:比如下例,我们不再需要提供 eqOp() 去定义 == 运算了:
// use FooHash to generate the hash code; Foo must have an == operator
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);