12、C++ Primer 4th 笔记，关联容器(2)

1、map 和 set 容器中，一个键只能对应一个实例。multimap和multiset类型允许一个键对应多个实例。其支持的操作分别与map和set的操作相同，只有一个例外，multimap不支持下标运算。set与multiset专门用于存储键。

2、关联容器 map 和 set 的元素是按顺序存储的。而 multimap 和multset 也一样。因此，在 multimap 和 multiset 容器中，如果某个键对应多个实例，则这些实例在容器中将相邻存放。迭代遍历 multimap 或 multiset 容器时，可保证依次返回特定键所关联的所有元素。

3、在multimap与multiset中寻找元素时，一般有以下三种方法：

1）使用 find 和 count 。count 函数求出某键出现的次数，而 find 操作则返回一个迭代器，指向第一个拥有正在查找的键的实例。

2）用标准库提供的迭代器

m.lower_bound(k)	返回一个迭代器，指向键不小于 k 的第一个元素
m.upper_bound(k)	返回一个迭代器，指向键大于 k 的第一个元素
m.equal_range(k)	返回一个迭代器的 pair 对象它的 first 成员等价于m.lower_bound(k)。而 second 成员则等价于 m.upper_bound(k)

    若该键没有关联的元素，则 lower_bound 和 upper_bound 返回相同的迭代

器：都指向同一个元素或同时指向 multimap 的超出末端位置。它们都指向在保

持容器元素顺序的前提下该键应被插入的位置。

4、一个查找文本的例子

#include "map"
#include "set"
#include "vector"
#include "string"
#include "fstream"
#include "iostream"
#include "sstream"
using namespace std;

class TextQuery
{
public:
	typedef std::vector<std::string>::size_type line_no;
	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:
	void store_file(std::ifstream&); //存储文件
	void build_map(); //将每个单词与相关联的行号建立映射
	std::vector<std::string> lines_of_text; //存储原文件的每一行
	std::map< std::string, std::set<line_no> > word_map; //映射结构
};

void TextQuery::store_file(std::ifstream &is)
{
	string textline;
	while(getline(is, textline))
	{
		lines_of_text.push_back(textline);
	}
}

void TextQuery::build_map()
{
	for(line_no line_num = 0; line_num != lines_of_text.size(); ++line_num)
	{
		istringstream line(lines_of_text[line_num]);
		string word;
		while (line >> word)
		{
			word_map[word].insert(line_num);
			//word_map.insert(make_pair(word, line_num));
			//word_map.insert(map<std::string, line_no>::value_type(word, line_no));
		}
	}
}

std::set<TextQuery::line_no>
TextQuery::run_query(const string &query_word) const
{
	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 
		return loc->second;
}

std::string TextQuery::text_line(line_no line) const
{
	if (line < lines_of_text.size())
		return lines_of_text[line];
	else
		throw std::out_of_range("line number out of range");
}

ifstream& open_file(ifstream &in, const string &file)
{
	in.close(); // close in case it was already open
	in.clear(); // clear any existing errors
	// if the open fails, the stream will be in an invalid state
	in.open(file.c_str()); // open the file we were given
	return in; // condition state is good if open succeeded
}

string make_plural(size_t ctr, const string &word,
				   const string &ending)
{
	return (ctr == 1) ? word : word + ending;
}

void printf_resluts(const set<TextQuery::line_no> &locs, const std::string &sought, const TextQuery &file)
{
	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;
	line_nums::const_iterator it = locs.begin();
	for (; it != locs.end(); it++)
	{
		cout << "\t(line"
			 << (*it) + 1 << ")"
			 << file.text_line(*it)
			 << endl;
	}
}

int main(int argc, char **argv)
{
	ifstream infile("C:\\1.txt");
	/*if (argc < 2 || !open_file(infile, argv[1]))
	{
		cerr << "No input file" << endl;
		return EXIT_FAILURE;
	}*/

	TextQuery tq;
	tq.read_file(infile);

	while (true)
	{
		cout << "Enter word to look for, or q to quit: ";
		string s;
		cin >> s;
		if (!cin || s == "q")
			break;
		set<TextQuery::line_no> locs = tq.run_query(s);
		printf_resluts(locs, s, tq);
	}
	return 0;
}

注意上面例子中：

word_map[word].insert(line_num);
不能替换成如下两种形式
//word_map.insert(make_pair(word, line_num));
//word_map.insert(map<std::string, line_no>::value_type(word, line_no));

因为make_pair的两个实参必须是具体的值，而不能是变量。

参考：

[1] http://blog.163.com/zhoumhan_0351/blog/static/399542272010227112325224/

http://blog.163.com/zhoumhan_0351/blog/static/39954227201032392545410/

http://blog.163.com/zhoumhan_0351/blog/static/399542272010229828061/

http://blog.163.com/zhoumhan_0351/blog/static/39954227201038102838349/

http://blog.163.com/zhoumhan_0351/blog/static/399542272010396030501/

http://blog.163.com/zhoumhan_0351/blog/static/39954227201039112031737/

http://blog.163.com/zhoumhan_0351/blog/static/39954227201022994439573/