C++关联容器

chaomai included in Cpp

2014-02-28 1759 words 4 minutes

Contents

关联容器支持普通容器操作，不支持，

顺序容器位置相关的操作，push_back等；
构造函数或插入操作接受一个元素值和一个数量值得操作。

定义

定义一个map时必须指定关键字类型和值类型，set只需关键字类型。

初始化

可以用下面的方式来初始化，

同类型容器的copy；
指定值范围（begin和end）；
列表初始化。

有序关联容器关键字类型的要求

有序关联容器关键字类型必须定义元素比较的方法。默认情况下，使用<进行比较。

1
2
3
4
// list的iterator并无<
map<list<int>::iterator, int> ml; // 声明不会报错
list<int> li;
ml[li.begin()] = 0; // 报错

对于有序容器，有序容器的关键字必须是严格弱序的，可看做“小于等于”。

自定义比较操作

用于组织一个容器中元素的操作的类型也是容器类型的一部分，如果需要自定义操作，则在定义容器的时候就指明。

1
2
boo compare(...) { ... }
multiset<Sales_sata, decltype(compare) *> bookstore(compare);

创建对象时，提供的操作类型（函数指针）必须与尖括号中的类型吻合。规则与函数的const形参和实参的规则一致，忽略top const。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
auto comp = [](int a, int b) { return false; };
multiset<int, bool (*)(const int, const int)> m(comp);

auto comp1 = [](const int a, const int b) { return false; };
multiset<int, bool (*)(int, int)> m1(comp1);

auto comp2 = [](int* const a, int* const b) { return false; };
multiset<int, bool (*)(int*, int*)> m2(comp2);

auto comp3 = [](int* a, int* b) { return false; };
multiset<int, bool (*)(int* const, int* const)> m3(comp3);

auto comp4 = [](int* a, int* b) { return false; };
multiset<int, bool (*)(const int*, const int*)> m4(comp4); // 错误

pair

模板，接受两个类型名，pair的数据成员将有对应的类型，两个类型不要求一样。

创建对象时，pair的默认构造函数对数据成员进行值初始化（vector也可以）。

1
pair<string, size_t> word_count;

若函数返回pair，可对返回值进行列表初始化，不必显式构造返回值。

关联容器的操作

map中，每个元素就是一个pair对象，由于关键字不可变，因此pair的关键字部分是const。set的关键字也是const。

1
2
3
map<string, int>::value_type v1; // pair<const string, int>
map<string, int>::key_type v2; // string
map<string, int>::map_type v3; // int

关联容器的迭代器

对关联容器迭代器解引用，可得到容器的value_type的引用。

对于set，虽然set定义了iterator和const_iterator，但是都不能改变set中的元素。

当迭代器遍历一个map，multimap，set或multiset时，按关键字升序遍历。

关联容器和算法

由于关键字是const，因此不能用于修改或重排容器的算法（都需要向元素写入值）。只可用于读取元素的算法。

添加元素

insert和emplace可以对关联容器进行插入，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
c.insert(v)
c.emplace(args)
// map和set返回pair<iterator, bool>，iterator指向有此关键字的元素，bool说明是否元素是否已经存在，即是否插入成功。multimap和multiset总是进插入，只返回bool。

c.insert(b, e)
c.insert(li)
// 返回void

c.insert(p, v)
c.emplace(p, args)
// p指明了从哪里开始新元素的存储位置

删除元素

关联容器有三个版本的erase，

1
2
3
4
5
6
7
8
c.erase(k)
// 删除所有key为k的元素，返回size_type，表明删除的数量

c.erase(p)
// 返回被删除元素后的迭代器

c.erase(b, e)
// 返回e

map的下标

由于set并无关联值，下标操作对set无意义，故set不支持。multimap和multiset可能存在多个与某个key关联的值，故也不支持。

下标操作返回mapped_type，是左值。如果关键字不在map中，下标操作会，

创建一个元素并插入，关联值将进行值初始化；
提取元素并赋值。

注意，

与vector和string不同，map的下标操作和解引用返回的类型（mapped_type和value_type）不一样；
如果元素不存在，at并不会创建，而是抛出out_of_range；
下标操作可能会改变map，对const的map无法使用；

对于const的map，只要at不修改元素，就可以用。

1
2
3
4
const map<string, int> m{{"hello", 1}};
cout << m.at("hello") << endl;
cout << m["hello"] << endl; // 错误，即使是普通访问
m.at("hello") = 1; // 错误

无序关联容器

使用hash function和==来组织元素，用hash<key_type>类型的对象生成每个元素的hash值，有序关联容器的操作可以用于无序容器。

标准库为内置类型（包括指针类型）和部分标准库类型（包括string和智能指针）类型定义了hash。但不能直接把自定义类型作为key来定义无序容器，可以

提供自己的hash模板版本；
定义hash function和==运算符。

1
2
3
4
5
6
7
8
9
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();
}

unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*> set(42, hasher,  eqOp);