C++ Primer 第十一章

关联容器

使用关联容器

关联容器

使用关联容器

map

//统计每个单词在输入中出现的次数
map<string，size_t > word_count; // string到size_t 的空map
string word;
while (cin >> word)
	++word_count[word] ;				//提取word的计数器并将其加1
for (const auto &w : word_ count) // 对map中的每个元素
	//打印结果
	cout << w.first << " occurs”<< w.second << ((w.second>1)?”times":”time") << endl;

set

//统计输入中每个单词出现的次数
map<string，size_t > word_count; 	// string 到size_ t的空map .
set<string> exclude = { "The", "But", "And"， "Or"， "An", "A",
						"the"，"but", "and"， "or"， "an"， "a"};
string word;
while (cin >> word)
	//只统计不在exclude中的单词
	if (exclude. find (word) == exclude.end() )
	++word_ count [word]; 			// 获取并递增word的计数器

关联容器概述

定义关联容器

map<string，size_ t> word_ count; //空容器
//列表初始化
set<string> exclude = { "the", "but", "and", "or", "an", "a",
						"The", "But"， "And"， "Or", "An"， "A"};
//三个元素; authors将姓映射为名
map<string，string> authors = { {"Joyce", "James"},
								{ "Austen", "Jane"},
								{"Dickens", "Charles"} };

初始化multimap或multiset

multi容器允许多个元素具有相同的关键字：

// 定义一个有20个元素的vector,保存0到9每个整数的两个拷贝
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
	ivec.push_ back(i) ;
	ivec.push_ back(i); 		// 每个数重复保存一次
}
// iset包含来自ivec的不重复的元素; miset包含所有20个元素
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

关键字类型的要求

对于有序容器中的关键字类型必须定义比较元素的方法。

使用关键字类型比较函数

可以指定一个比较函数来进行比较，需要在容器定义时紧跟着关键字类型给出。

当使用Sales_data类时因为没有<运算符，所以我们需要自己定义：

bool compareIsbn (const Sales_data &1hs， const Sales_data &rhs)
{
	return lhs.isbn() < rhs.isbn() ;
}
//然后定义容器时传入该函数,需要提供想要使用的操作的指针：
//bookstore中多条记录可以有相同的ISBN
// bookstore中的元素以ISBN的顺序进行排列
multiset<Sales_data, dec1type(compareIsbn)*>
	bookstore (compareIsbn);

使用decltype指出自定义操作的类型，必须加上*指出给定的函数指针。

pair类型

在头文件utility中，一个pair保存两个数据成员：

pair<string, string> anon;				//保存两个string
pair<string, size_ t> word_ count;		//保存一个string和一个size_ t
pair<string, vector<int>> line;			//保存string和vector<int>

也可以使用列表初始化

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

成员均为public使用first和second进行访问

//打印结果
cout << w.first << "occurs" << w.second<< ( (w.second > 1)? ”time s: ”time" ) << endl ;

返回pair的函数

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

else中返回的是一个空pair

早期版本中不可以列表初始化返回则必须显示构造或使用make_pair来生成：

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

关联容器的操作

关联容器迭代器

解引用关联容器得到迭代器得到一个value_type，对于map得到一个pair，first成员中保存的是const关键字，它是不可以更改的，second保存值。而set中value_type与value_type是一样的。

遍历关联容器

使用迭代器遍历容器

//获得一个指向首元素的迭代器
auto map_it = word_count.cbegin() ;
//比较当前迭代器和尾后迭代器.
while (map_it != word_count.cend() ) {
	//解引用迭代器，打印关键字-值对
	cout << map_it->first << ”occurs” << map_it->second << " times" << endl;
	++map_it; // 递增迭代器，移动到下一个元素
}

打印出来的函数为升序排列。

关联容器和算法

通常不对关联容器使用泛型算法，关键字的const特性意味着不可以重排或修改元素，set中的元素时const的，所以只可以使用只读的算法，推荐使用容器内部的find，它会比泛型算法快得多，泛型find使用的是顺序搜索。

添加元素

使用insert添加一个元素或元素范围，

//set容器
vector<int> ivec = {2,4,6,8,2,4,6,8};				// ivec有8个元素
set<int> set2										//空集合
set2.insert(ivec.cbegin()，ivec.cend());				//set2有4个元素
set2.insert({1,3,5,7,1,3,5,7});						// set2现在有8个元素
//insert可以接受一对迭代器，也可以接受一个初始化列表。

//map容器
//向word_count插入word的4种方法
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返回值依赖容器类型和参数，对于map和set，添加单一元素返回的是一个pair，first指向给定的关键字元素，second是bool值，指出插入成功还是失败（已存在）。

//统计每个单词在输入中出现次数的一种更烦琐的方法
map<string，size_t> word_count; // 从string到size_t的空map.
string word;
while (cin >> word) {
	//插入一个元素，关键字等于word, 值为1;
	//若word已在word_ count中，insert什么也不做
	auto ret = word_count.insert ({word, 1}) ;
	if (!ret.second)				// word已在word_ count中
		++ret.first->second; 		//递增计数器
}

展开递增语句

++ret.first->second;这句话就代表增加插入的那个元素中的second++。

multi容器添加元素

这种容器可以包含多个相同的关键字

mul timap<string, string> authors;
//插入第一个元素，关键字为Barth， John
authors.insert ({"Barth，John", "Sot-Weed Factor"});
//正确:添加第二个元素，关键字也是Barth， John
authors.insert({"Barth, John", "Lost in the Funhouse"}) ;

删除元素

erase可以接受一个迭代器或者是一对迭代器来删除一个或一个范围的元素。还可以接受一个key_type，删除所匹配的关键字元素。

//删除一个关键字，返回删除的元素数量
if (word_count.erase (removal_word) )
	cout << "ok:”<< removal_word << ”removed\n";
else cout << "oops: ”<< removal_ word << ”not found! \n";

如果是multi容器，可能删除多个元素

auto cnt = authors.erase ("Barth，John") ;

上面authors中添加了两个相同的元素，则cnt等于2。

map的下标操作

map和unordered_map具有下标运算和at函数，set中不可以使用。

map通过下标运算，接受一个索引（即关键字）获取与之关联的值，但不同的是，如果没有此关键字，会创建一个关键字，并将对应的值初始化。

map <string， size_t> word_count; / / empty map
//插入一个关键字为Anna的元素，关联值进行值初始化;然后将1赋予它
word_count ["Anna"] = 1;

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

使用下标操作的返回值

通常解引用的一个迭代器的类型与下标运算返回的类型是一样的，但map不同，会得到有个mappped_type对象，且为左值。

访问元素

count可以统计元素个数，对于不允许重复元素存在的容器，推荐使用find。

map使用find代替下标操作

map容器的下标操作如果关键字不存在，则会插入这个新的关键字，所以在只是想知道有没有这个关键字时可以用find代替。

multi容器查找元素

方法一：

string search_ item("Alain de Botton") ;		//要查找的作者
auto entries = authors. count (search_ item) ;	//元素的数量
auto iter = authors. find (search_ item) ;		//此作者的第一本书
//用一个循环查找此作者的所有著作
while (entries) {
	cout << iter->second << endl ;				//打印每个题目
	++iter;										//前进到下一本书
	--entries;									//记录已经打印了多少本书
}

方法二

lower_bound和up_bound分别返回匹配的第一个位置和最后一个位置的后一个位置。不存在则返回可插入位置

// authors 和search_ item 的定义，与前面的程序一样
//beg和end表示对应此作者的元素的范围.
for (auto beg = authors. lower_bound (search_item) ,
		  end = authors.upper_bound (search_item) ;
		  beg != end; ++beg)
	cout << beg->second << endl; //打印每个题目

方法三

equal_range函数接受关键字，返回pair。若关键字存在则第一个指向第一个与之匹配的位置，第二个是最后一个与之匹配位置的后一个位置。若不存在则返回可插入位置。

// authors 和search_item的定义， 与前面的程序一样
// pos保存迭代器对，表示与关键字匹配的元素范围
for (auto pos = authors.equal_range (search_item) ;
	 pos.first != pos.second; ++pos.first)
	cout << pos.first->second << endl; //打印每个题目

单词转换map（跳）

无序容器

使用无序容器

unordered_map或者unordered_set，他们都有与前面类似的操作，通常可以用一个无序容器替换对应的有序容器，但顺序会与有序容器不同。

管理桶

无序容器在储存上为一组桶，无序容器使用一个哈希函数将所有元素映射到桶中，容器将具有一个特定的哈希值的所有元素保存在相同的桶中，访问时先按照哈希值找到对应的桶，再在桶中找对应的元素。因此容器性能依赖哈希函数的质量和桶的数量和大小。

最理想的情况应该是哈希函数将所有元素尽可能的均匀的分配到每个桶中。

无序容器对关键字类型的要求

默认情况下，无序容器使用关键字类型的==运算符来比较元素，还使用一个hash 类型的对象来生成每个元素的哈希值。例如当我们想要将一个int值使用哈希函数，就是hash,

但是我们不能直接定义关键字类型为自定义类类型的无序容器。可以不直接使用哈希模板而是使用自己的hash版本。例如Sale_data用作关键字，我们需要提供函数来代替==运算符和哈希计算函数。

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(hasher)*, decltype(eqOp)*>;
//参数是桶大小、哈希函数指针和相等性判断运算符指针
SD_multiset bookstore(42, hasher, eqOp) ;

如果类内具有==运算符，可以只重载哈希函数

//使用FooHash生成哈希值; Foo必须有==运算符
unordered_set<Foo, decltype (FooHash)*> fooSet (10，FooHash);