c++Primer 11章关联容器

1.使用关联容器

使用map

map<string, size_t> word_count;
string word;
while(cin>>word)
	++word_count[word];
for(const auto &w : word_count)
	cout<<w.first<<" occurs"<<w.second<<((w.second >1)?" times":" time")<<endl;

使用set

map<string, size_t> word_count;
set<string> exclude = {"The","But","And","Or","An","A","the","but","and","or","an","a"};

string word;

while(cin >> word)
	if(exclude.find(word) == exclude.end())
		++word_count[word];

2.概述

关联容器不支持顺序容器的位置相关的操作，例如push_front push_back。而且关联容器也不支持构造函数或插入函数这些接受一个元素值和一个数量值的操作。
关联容器的迭代器都是双向的。

2.1 定义关联容器

可以创建一个指定类型的空容器，也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。

map<string, size_t> word_count;

set<string> exclude = {"the","but","and"};

map<string,string> authors = {{"joyce","james"},{"austen","jane"}};

当初始化一个map时，必须提供关键字类型和值类型。

multimap和multiset允许多个元素具有相同的关键字。

vector<int> ivec;
for(vector<int>::size_type i = 0; i != 10; i++)
{
	ivec.push_back(i);
	ivec.push_back(i);
}

set<int> iset(ivec.cbegin(),ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());

cout<<ivec.size()<<endl;	//20
cout<<iset.size()<<endl;	//10
cout<<miset.size()<<endl;	//20

2.2 关键字类型的要求

对于有序容器map、multimap、set、multiset，关键字类型必须定义元素比较的方法。默认情况下，使用<运算符比较两个关键字。

使用关键字类型的比较函数

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
	return lhs.isbn() < rhs.isbn();
}

为了定义自己的操作，在定义multiset时必须提供两个类型：关键字类型Sales_data，以及比较操作类型－应该是一种函数指针类型，可以指向compareIsbn。当定义次容器类型的对象时，需要提供想要使用的操作的指针。

multiset<Sales_data,decltype(compareIsbn)*> bookstore(compareIsbn);

//也可以下面这样。
using compareType = bool (*)(const Sales_data &lhs, const Sales_data &rhs);
std::multiset<Sales_data, compareType> bookstore(compareIsbn);

添加元素时，通过调用compareIsbn来为这些元素排序。

bool less(int lhs, int rhs)
{
	return lhs < rhs;
}

int main()
{
	using Less = bool(*)(int,int);
	multiset<int,Less> m(less);
}

2.3 pair类型

定义在utility中。一个pair保存两个数据成员。pair是一个用来生成特定类型的模板，当创建一个pair时，

pair<string,string> anon;

pair<string,size_t> word_count;

pair<string,vector<int>> line;

pair的默认构造函数对数据成员进行值初始化。

pair<string, string> author{"James","Joyce"};

pair的数据成员是public的，分别为first和second。

cout<<w.first<<" occurs "<<w.second<<((w.second > 1)?" times":" time")<<endl;

语法	解释
pair< T1,T2 > p;	p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化
pair< T1,T2 > p(v1, v2)	p是一个类型分别为T1和T2的pair；first和second成员分别用v1和v2进行初始化
pair< T1,T2 > p = {v1, v2}	等价于p(v1, v2)
make_pair<v1,v2)	返回一个用v1和v2初始化的pair。pair的类型从v1和v2的类型推断出来
p.first	返回p的名为first的数据成员
p.second	返回p的名为second的数据成员
p1 relop p2	关系运算符(< > <= >=)按字典序定义。例如，当p1.first < p2.first 或!(p2.first < p1.first) && p1.second < p2.second成立时，p1 < p2为true。关系运算符利用元素的<运算符实现
p1 == p2	当first和second成员分别相等时，两个pair相等。相等性判断利用元素的==运算符实现
p1 != p2

创建pair对象的函数

pair<string, int> process(vector<string> &v)
{
	if(!v.empty())
		return {v.back(), v.back().size()};//列表初始化
		
	else
		return pair<string,int>();	//隐式构造返回值
}

也可以使用make_pair。

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

3 关联容器操作

语法	解释
key_type	此容器类型的关键字类型
mapped_type	每个关键字关联的类型：只适用于map
value_type	对于set，与key_type相同；对于map，为pair

对于set类型，key_type和value_type是一样的。在一个map中，元素是关键字-键对。由于我们不能改变一个元素的关键字，因此这些pair的关键字部分是const的。

set<string>::value_type v1;	//v1是一个string
set<string>::key_type	v2;		//v2是一个string
map<string, int>::value_type v3;	//v3是一个pair<const string,int>
map<string, int>::key_type v4;	//v4是一个string
map<string, int>::mapped_type v5;	//v5是一个int

使用作用域运算符来踢去一个类型的成员。只有map类型才定义了mapped_type。

3.1 关联容器迭代器

解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。对map而言，value_type是一个pair类型，其first成员保存const的关键字，second成员保存值。

auto map_it = word_count.begin();
//*map_it是一个指向pair<const string, size_t>对象的引用
cout<<map_it->first;
cout<<" "<<map_it->second;
map_it->first = "new key";	//错误：关键字是const的
++map_it->second;

一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值。

set的迭代器是const的
与不能改变一个map元素的关键字一样，一个set中的关键字也是const的。

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; // 错误：set中的关键字是只读的
	cout << *set_it << endl; // 正确：可以读关键字
}

遍历关联容器

1	auto map_it = word_count.cbegin(); while (map_it != word_count.cend()) { cout << map_it->first << " occurs "<< map_it->second << " times" << endl; + +map_it; }

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

我们通常不对关联容器使用泛型算法。

3.2 添加元素

vector<int> ivec = {2,4,6,8,2,4,6,8}; 
set<int> set2;
set2.insert(ivec.cbegin(), ivec.cend());
set2.insert({1,3,5,7,1,3,5,7});

word_count.insert({word, 1});
word_count.insert(make_pair(word, 1)); 
word_count.insert(pair<string, size_t>(word, 1)); 
word_count.insert(map<string, size_t>::value_type(word, 1));

检测insert的返回值

依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，告诉我们插入操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值，指出元素是否插入成功。

1
2

map<string, size_t> word_count;
string word;
while (cin >> word) {
	auto ret = word_count.insert({word, 1});	//如果word已存在word_count中，insert什么也不做
	if (!ret.second)
		++ret.first->second;
}

3.3 删除元素

三个版本：erase一个迭代器、一个元素范围，指定的元素被删除，返回void。接受一个key_type参数，删除所有匹配给定关键字的元素，返回实际删除的元素的数量。

1	if (word_count.erase(removal_word)) cout << "ok: " << removal_word << " removed\n"; else cout << "oops: " << removal_word << " not found!\n";

语法	解释
c.erase(k)	从c中删除每个关键字为k的元素。返回一个size_type值，指出删除的元素的数量
c.erase(p)	从c中删除迭代器p指向的元素。p必须指向c中一个真实元素，不能等于c.end()。返回一个指向p之后的元素的迭代器，若p指向c中的尾元素，则返回c.end()
c.erase(b,e)	删除迭代器对b和e所表示的范围中元素。返回e

3.4 下标操作

map和unordered_map容器提供下标运算符和一个对应的at函数。set不支持。multimap和unordered_multimap也不支持。

map<string, size_t> word_count;
word_count["Anna"] = 1;
``` 
进行操作：

1. 在word_count中搜索关键字为Anna的元素，未找到
2. 将一个新的关键字－值对插入到word_count中。关键字是一个const string，保存Anna。值进行值初始化，在本例中意味着值为0
3. 提取出新插入的元素，并将值q赋予它

语法					| 解释
--------------------|----------------------------|
c[k]					| 返回关键字为k的元素；如果k不在c中，添加一个关键字为k的元素，对其进行初始化
c.at(k)				| 访问关键字为k的元素，带参数检查：如果k不在c中，抛出一个out_of_range异常

与vector与string不同，map的下标运算符返回的类型与解引用map迭代器得到的类型不同。

3.5 访问元素

对于不允许重复关键字的容器，可能使用find还是count没区别。对于允许重复关键字的容器，count会做更多的工作。

set iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); //返回一个迭代器，指向key==1的元素
iset.find(11); //返回一个迭代器，
iset.count(1);
iset.count(11);

1 2	对map使用find代替下标操作，下标运算符可能会插入新元素。

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

1 2	在multimap或multiset中查找元素

string search_item(“Alain de Botton”); //
authors.count(search_item);
authors.find(search_item);
while(entries) {
cout << iter->second << endl;
–entries;
}

1 2	一种不同的，面向迭代器的解决方法

for(auto beg = authors.lower_bound(search_item),end=authors.upper_bound(search_item); beg != end; ++beg)
cout<second<

lower_bound返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向。如果关键字不在容器中，则lower_bound会返回关键字的第一个安全插入点－不影响容器中元素顺序的插入位置。
如果lower_bound和upper_bound返回相同的迭代器，则给定关键字不在容器中。

equal_range函数
返回pair，first成员保存的迭代器与lower_bound返回的迭代器一样；second保存的迭代器与upper_bound返回的迭代器一样。

for(auto pos = authors.equal_range(search_item); pos.first != pos.second;++pos.first)
cout<second<


4 无序容器

新标准定义了4个无序关联容器，使用哈希函数和关键字类型的==运算符。
无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用哈希函数将元素映射到桶。

// unordered_set::bucket_count

#include

int main ()
{
std::unordered_set myset =
{“Mercury”,”Venus”,”Earth”,”Mars”,”Jupiter”,”Saturn”,”Uranus”,”Neptune”};

unsigned n = myset.bucket_count();

std::cout << “myset has “ << n << “ buckets.\n”;

for (unsigned i=0; i<n; ++i) {
std::cout << “bucket #” << i << “ contains:”;
for (auto it = myset.begin(i); it!=myset.end(i); ++it)
std::cout << “ “ << *it;
std::cout << “\n”;
}

return 0;
}

输出：
	
	myset has 11 buckets.
	bucket #0 contains: 
	bucket #1 contains: Venus
	bucket #2 contains: Jupiter
	bucket #3 contains: 
	bucket #4 contains: Neptune Mercury
	bucket #5 contains: 
	bucket #6 contains: Earth
	bucket #7 contains: Uranus Saturn
	bucket #8 contains: Mars
	bucket #9 contains: 
	bucket #10 contains: 
	
	
对关键字类型的要求

定义关键字类型为自定义类类型的无序容器，需要提供自己的hash模板和==运算符。

size_t hasher(const Sales_data &sd)
{
return hash()(sd.isbn());
}

bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() == rhs.isbn();
}

using SD_multiset = unordered_multiset;

SD_multiset bookstore(32,hasher,eqOp);
```