本系列博客主要是在学习 C++ Primer 时的一些总结和笔记。
【C++ Primer 学习笔记】： 容器和算法之【关联容器】
关联容器
头文件
#include <utility> 
1 引言： pair 类型
2 关联容器
3 map 类型
3-1 定义
在使用关联容器时，它的键不但有一个类型，而且还有一个相关的比较函数。默认情况下，标准库使用键类型定义的 < 操作符来实现键（key type）的比较。
3-2 类型
在学习 map 的接口时，需谨记 value_type 是 pair 类型，它的值成员可以修改，但键成员不能修改
3-3 添加元素
定义了 map 容器后，下一步工作就是在容器中添加键－值元素对。该项工作可使用 insert 成员实现；或者，先用下标操作符获取元素，然后给获取的元素赋值。在这两种情况下，一个给定的键只能对应于一个元素这一事实影响了这些操作的行为。
3-4 使用下标访问元素
map<string,int> word_count;
int occurs = word_count["foobar"]; 但是，使用下标存在一个很危险的副作用：如果该键不在 map 容器中，那么下标操作会插入一个具有该键的新元素。
使用下标访问 map 与使用下标访问数组或 vector 的行为截然不同：用下标访问不存在的元素将导致在 map 容器中添加一个新元素，它的键即为该下标值
3-5 map：insert 的使用
3-6 查找并读取元素
map 容器提供了两个操作：count 和 find，用于检查某个键是否存在而不会插入该键。
对于 map 对象，count 成员的返回值只能是 0 或 1。
find 操作返回指向元素的迭代器，如果元素不存在，则返回 end 迭代器。
3-7 删除元素
map 容器的 erase 操作返回 void，而顺序容器的 erase 操作则返回一个迭代器，指向被删除元素后面的元素
3-8 迭代遍历
map 提供 begin 和 end 运算。
// get iterator positioned on the first element
map<string, int>::const_iterator map_it = word_count.begin();
// for each element in the map
while (map_it != word_count.end()) {
// print the element key, value pairs
cout << map_it->first << " occurs "
<< map_it->second << " times" << endl;
++map_it; // increment iterator to denote the next element 3-9 ”单词转换“实例
/*
* A program to transform words.
* Takes two arguments: The first is name of the word transformation
file
* The second is name of the input to transform
*/
int main(int argc, char **argv)
{
// map to hold the word transformation pairs:
// key is the word to look for in the input; value is word to use
in the output
map<string, string> trans_map;
string key, value;
if (argc != 3)
throw runtime_error("wrong number of arguments");
// open transformation file and check that open succeeded
ifstream map_file;
if (!open_file(map_file, argv[1]))
throw runtime_error("no transformation file");
// read the transformation map and build the map
while (map_file >> key >> value)
trans_map.insert(make_pair(key, value));
// ok, now we're ready to do the transformations
// open the input file and check that the open succeeded
ifstream input;
if (!open_file(input, argv[2]))
throw runtime_error("no input file");
string line; // hold each line from the input
// read the text to transform it a line at a time
while (getline(input, line)) {
istringstream stream(line); // read the line a word at a time
string word;
bool firstword = true; // controls whether a space is printed
while (stream >> word) {
// ok: the actual mapwork, this part is the heart of the program
map<string, string>::const_iterator map_it =
trans_map.find(word);
// if this word is in the transformation map
if (map_it != trans_map.end())
// replace it by the transformation value inthe map
word = map_it->second;
if (firstword)
firstword = false;
else
cout << " "; // print space between words
cout << word;
}
cout << endl; // done with this line of input
}
return 0;
} 4 set 类型
- set 不支持下标操作符，而且没有定义 mapped_type 类型。
- 在 set 容器中，value_type 不是 pair 类型，而是与 key_type 相同的类型。它们指的都是 set 中存储的元素类型。
- 与 map 一样，set 容器存储的键也必须唯一，而且不能修改。
4-1 定义和使用
头文件
#include <set> 正如不能修改 map 中元素的键部分一样，set 中的键也为 const。在获得指向 set 中某元素的迭代器后，只能对其做读操作，而不能做写操作。
4-2 ”单词排除“实例
void restricted_wc(ifstream &remove_file,
map<string, int> &word_count)
{
set<string> excluded; // set to hold words we'll ignore
string remove_word;
while (remove_file >> remove_word)
excluded.insert(remove_word);
// read input and keep a count for words that aren't in the
exclusion set
string word;
while (cin >> word)
// increment counter only if the word is not in excluded
if 5 multimap 和 multiset类型
- multimap 和 multiset 类型与相应的单元素版本具有相同的头文件定义：分别是 map 和 set 头文件。
- multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同，只有一个例外：multimap 不支持下标运算。不能对 multimap 对象使用下标操作，因为在这类容器中，某个键可能对应多个值。
5-1 元素的添加和删除
带有一个键参数的 erase 版本将删除拥有该键的所有元素，并返回删除元素的个数。而带有一个或一对迭代器参数的版本只删除指定的元素，并返回 void 类型：
multimap<string, string> authors;
string search_item("Kazuo Ishiguro");
// erase all elements with this key; returns number of elements removed
multimap<string, string>::size_type cnt = authors.erase(search_item); 5-2 multimap 和 multiset 中查找元素
关联容器 map 和 set 的元素是按顺序存储的。而 multimap 和 multset 也一样。因此，在 multimap 和 multiset 容器中，如果某个键对应多个实例，则这些实例在容器中将相邻存放。
迭代遍历 multimap 或 multiset 容器时，可保证依次返回特定键所关联的所有元素。
5-2-1 使用 find 和 count 操作
// author we'll look for
string search_item("Alain de Botton");
// how many entries are there for this author
typedef multimap<string, string>::size_type sz_type;
sz_type entries = authors.count(search_item);
// get iterator to the first entry for this author
multimap<string,string>::iterator iter = authors.find(search_item);
// loop through the number of entries there are for this author
for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter)
cout << iter->second << endl; // print each title 首先，调用 count 确定某作者所写的书籍数目，然后调用 find 获得指向第一个该键所关联的元素的迭代器。for 循环迭代的次数依赖于 count 返回的值。在特殊情况下，如果 count 返回 0 值，则该循环永不执行。
5-2-2 与众不同的面向迭代器的解决方案
lower_bound 返回的迭代器不一定指向拥有特定键的元素。如果该键不在容器中，则 lower_bound 返回在保持容器元素顺序的前提下该键应被插入的第一个位置。
// definitions of authors and search_item as above
// beg and end denote range of elements for this author
typedef multimap<string, string>::iterator authors_it;
authors_it beg = authors.lower_bound(search_item),
end = authors.upper_bound(search_item);
// loop through the number of entries there are for this author
while (beg != end) {
cout << beg->second << endl; // print each title 5-2-3 enual_range 函数
and search_item as above
// pos holds iterators that denote range of elements for this key
pair<authors_it, authors_it> pos = authors.equal_range(search_item);
// loop through the number of entries there are for this author
while (pos.first != pos.second) {
cout << pos.first->second << endl; // print each title
++pos.first;
} 本程序的 pos.first 等价于前一方法中的 beg，而 pos.second 等价于 end。
6 实例：文本查询程序
问题：我们的程序将读取用户指定的任意文本文件，然后允许用户从该文件中查找单词。查询的结果是该单词出现的次数，并列出每次出现所在的行。如果某单词在同一行中多次出现，程序将只显示该行一次。
分析：
1. 它必须允许用户指明要处理的文件名字。程序将存储该文件的内容，以便输出每个单词所在的原始行。
2. 它必须将每一行分解为各个单词，并记录每个单词所在的所有行。在输出行号时，应保证以升序输出，并且不重复。
3. 对特定单词的查询将返回出现该单词的所有行的行号。
4. 输出某单词所在的行文本时，程序必须能根据给定的行号从输入文件中获取相应的行。
数据结构
我们将用一个简单的类 TextQuery 实现这个程序。再加几种容器的配合使用，就可相当巧妙地满足上述要求。
1. 使用一个 vector 类型的对象存储整个输入文件的副本。输入文件的每一行是该 vector 对象的一个元素。因而，在希望输出某一行时，只需以行号为下标获取该行所在的元素即可。
2. 将每个单词所在的行号存储在一个 set 容器对象中。使用 set 就可确保每行只有一个条目，而且行号将自动按升序排列。
3. 使用一个 map 容器将每个单词与一个 set 容器对象关联起来，该 set 容器对象记录此单词所在的行号。
综上所述，我们定义的 TextQuery 类将有两个数据成员：储存输入文件的 vector 对象，以及一个 map 容器对象，该对象关联每个输入的单词以及记录该单词所在行号的 set 容器对象。
操作
类的接口需提供下列三
个 public 函数
• read_file 成员函数，其形参为一个 ifstream& 类型对象。该函数每次从文件中读入一行，并将它保存在 vector 容器中。输入完毕后，read_file 将创建关联每个单词及其所在行号的 map 容器。
• run_query 成员函数，其形参为一个 string 类型对象，返回一个 set 对象，该 set 对象包含出现该 string 对象的所有行的行号。
• text_line 成员函数，其形参为一个行号，返回输入文本中该行号对应的文本行。
为实现 read_file 功能，还需定义两个 private 函数来读取输入文本和创建 map 容器：
• store_file 函数读入文件，并将文件内容存储在 vector 容器对象中。
• build_map 函数将每一行分解为各个单词，创建 map 容器对象，同时记录每个单词出现行号。
6-1 TextQuery 类
class TextQuery {
public:
// typedef to make declarations easier
typedef std::vector<std::string>::size_type line_no;
/* interface:
* read_file builds internal data structures for the given file
* run_query finds the given word and returns set of lines on which it appears
* text_line returns a requested line from the input file
*/
void read_file(std::ifstream &is)
{ store_file(is); build_map(); }
std::set<line_no> run_query(const std::string&) const;
std::string text_line(line_no) const;
private:
// utility functions used by read_file
void store_file(std::ifstream&); // store input file
void build_map(); // associated each word with a set of line numbers
// remember the whole input file
std::vector<std::string> lines_of_text;
// map word to set of the lines on which it occurs
std::map< std::string, std::set<line_no> 6-2 成员函数
6-2-1 存储输入文件
// read input file: store each line as element in lines_of_text
void TextQuery::store_file(ifstream &is)
{
string textline;
while (getline(is, textline))
lines_of_text.push_back(textline);
} 6-2-2 建立单词 map 容器
// finds whitespace-separated words in the input vector
// and puts the word in word_map along with the line number
void TextQuery::build_map()
{
// process each line from the input vector
for (line_no line_num = 0; line_num != lines_of_text.size(); ++line_num)
{
//we'll use line to read the text a word at a time
istringstream line(lines_of_text[line_num]);
string word;
while (line >> word)
// add this line number to the set;
// subscript will add word to the map if it's not already there
word_map[word].insert(line_num);
}
} 6-2-3 支持查询
set<TextQuery::line_no>
TextQuery::run_query(const string &query_word) const
{
//Note: must use find and not subscript the map directly
//to avoid adding words to word_map!
map<string, set<line_no>::const_iterator
loc = word_map.find(query_word);
if (loc == word_map.end())
return set<line_no>(); // not found, return empty set
else
// fetch and return set of line numbers for this word
return 6-2-4 run_query 返回值的使用
string TextQuery::text_line(line_no line) const
{
if (line < lines_of_text.size())
return lines_of_text[line];
throw std::out_of_range("line number out of range");
} 6-3 TextQuery 的使用
// program takes single argument specifying the file to query
int main(int argc, char **argv)
{
// open the file from which user will query words
ifstream infile;
if (argc < 2 || !open_file(infile, argv[1])) {
cerr << "No input file!" << endl;
return EXIT_FAILURE;
}
TextQuery tq;
tq.read_file(infile); // builds query map
// iterate with the user: prompt for a word to find and print results
// loop indefinitely; the loop exit is inside the while
while (true) {
cout << "enter word to look for, or q to quit: ";
string s;
cin >> s;
// stop if hit eof on input or a 'q'is entered
if (!cin || s == "q") break;
// get the set of line numbers on which this word appears
set<TextQuery::line_no> locs = tq.run_query(s);
// print count and all occurrences, if any
print_results(locs, s, tq);
}
return 0;
} void print_results(const set<TextQuery::line_no>& locs, const string& sought, const TextQuery &file)
{
// if the word was found, then print count and all occurrences
typedef set<TextQuery::line_no> line_nums;
line_nums::size_type size = locs.size();
cout << "\n" << sought << " occurs "
<< size << " "
<< make_plural(size, "time", "s") << endl;
// print each line in which the word appeared
line_nums::const_iterator it = locs.begin();
for ( ; it != locs.end(); ++it) {
cout << "\t(line "
// don't confound user with text lines starting at 0
<< (*it) + 1 << ") "