《C++ Primer》读书笔记 第十一章 关联容器

第十一章 关联容器

2 2 2 = 8种:

  • setmap
  • multi:允许重复关键字(定义在<map><set>
  • unordered:无序保存(定义在unordered_mapunordered_set

11.1 使用关联容器

基本使用。

11.2 关联容器概述

11.2.1 定义关联容器

11.2.2 关键字类型的要求

有序容器需要关键字类型支持行为正常的比较操作。

1
2
3
4
5
6
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() < rhs.isbn();
}

multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn); // 后面的 compareIsbn 可以换成 &compareIsbn

注意:用 decltype 来获得一个函数指针类型时,必须加上一个*指出我们要得到的是函数的指针。

11.2.3 pair 类型

<utility>中。

如果函数返回 pair:

1
2
3
4
5
6
7
pair<string, int> process(vector<string> &v)
{
if(...)
return {v.back(), v.back().size()}; // 列表初始化(C++11)
else
return pair<string, int>(); // 隐式构造返回值
}

还可以使用:

1
2
return pair<string, int>(v.back(), v.back().size());
return make_pair(v.back(), v.back().size());

11.3 关联容器操作

11.3.1 关联容器迭代器

  • 关键字类型(包括 pair 的 first)是 const 的。
  • 对 map 解引用得到的类型是 value_type,是个 pair。
  • set 的 iterator 和 const_iterator 都是只读的,不能改变 set 的元素。
  • 通常不对关联容器使用泛型算法,关键字是 const 这一特性使得算法不能对容器进行修改或重排。关联容器可用于只读算法,如 find,但还是优先使用成员函数版本。
  • 实际使用中,若是用在泛型算法上,要么当作一个源序列,要么当作一个目标位置(使用 inserter)。

11.3.2 添加元素

1
2
3
4
5
6
set1.insert(ivec.cbegin(), ivec.cend());
set1.insert({1, 2, 3});
map1.insert({word, 1});
map1.insert(make_pair(word, 1));
map1.insert(pair<string, size_t>(word, 1));
map1.insert(map<string, size_t>::value_type(word, 1));

对于不返回重复关键字的容器,这些函数返回一个 pair,其 first 是一个迭代器,指向具有给定关键字的元素;second 成员是一个 bool 值,指出是插入成功还是已经存在于容器。

一个单词计数的例子:

1
2
3
4
5
6
7
map<string, size_t> word_count;
string word;
while (cin >> word){
auto ret = word_count.insert({word, 1});
if (!ret.second)
++ret.first->second;
}

auto 的类型是:

1
pair<map<string, size_t>::iterator, bool>

注意,对于mutisetmultimap,一定会插入成功,因此只返回迭代器。

11.3.3 删除元素

11.3.4 map 的下标操作

如果关键字不在 map vs ,下标运算符会创建一个元素并插入到 map 中,并进行值初始化。所以,我们只能对非 const 的 map 使用下标操作。

注意在 map 中,下标操作的返回值和对迭代器进行解引用不一样。前者是 mapped_type,后者是 value_type。但相同的一点是都是左值。

11.3.5 访问元素

注意:lower_bound 和 upper_bound 不适用于无序容器。下标和 at 只适用于非 const 的 map 和 unordered_map。

不能用下标运算符来检查一个元素是否存在!

如果是在 multimap 或 multiset 查找给定关键字,有三种方法(它们一定是连续存储的):

  1. find 和 count:
1
2
3
4
5
6
7
auto count = map1.count(key);
auto iter = map1.find (key);
while(count){
count << iter->second << endl;
++iter;
--count;
}
  1. 迭代器组:
1
2
3
4
5
for (auto beg = map1.lower_bound(key),
end = map1.upper_bound(key);
beg != end;
++beg)
cout << beg->second << endl;
  1. equal_range函数
1
2
3
4
for (auto pos = map1.equal_range(key);
pos.first != pos.second;
++pos.first)
cout << pos.first->second << endl;

11.3.6 一个单词转换的 map

11.4 无序容器

无序容器使用一个哈希函数将元素映射到桶。

无序容器对关键字类型使用==比较元素,还使用hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内置类型,还有string和智能指针等标准库类型定义了hash。

但是,我们不能定义关键字类型为自定义类类型的无序容器。必须提供自己的 hash 模版。16.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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();
}

using SD_multiset = unordered_multiset<Sales_data, decltype(haser)*, decltype(eqOp)* >;

SD_multiset bookstore(42, hasher, eqOp);

// 如果已经定义了 == 运算符,则只重载哈希函数:
unordered_set<Foo, decltype(FooHash)* > fooSet(10, FooHash);