【Accelerated C++】课时7：使用关联容器

# 0x01 支持高效查找的容器

之前提到的容器，`vector` 和 `list` 都属于顺序容器。

- `vector`：为了快速随机访问而被优化的，顺序访问的效率高。会自动扩缩容。但是如果要在向量内部删除或增加元素，就必须移动位于被插入或删除的元素后面的所有元素，这样效率很低。

- `list`：可以让我们在容器的任何位置插入和删除元素。vector 支持索引，但 list 不支持索引，但 list 支持迭代器。

顺序容器对于元素顺序排列，不利于高效查找。而关联容器根据元素自身的值自动安排序列，更利于高效查找。

最常见的一种**关联容器**结构存储了「键-值」对。这样的一个数据结构被称为「关联数组」。关联数组是库的一部分。在C++中最常用的一种关联数组是`map`（映射表）。它定义在`<map>`头中。

>可以联想到，Python中最常用的一种关联数组是字典。

![title](https://leanote.com/api/file/getImage?fileId=5e83fe51ab64411b510016a1)

# 0x02 计算单词数

![title](https://leanote.com/api/file/getImage?fileId=5e8403c9ab64411b510017c2)

**迭代器类型**

每一种标准容器，例如向量，都定义了两种相关的迭代器类型：

```
container-type::const_iterator
container-type::iterator
```

`container-type`指的是诸如`vector<Student_info>`这样的容器类型，它包括了容器元素的类型。如果我们想用一个迭代器来**修改存储在容器中的值**，使用`iterator`类型；如果我们仅仅需要读操作，那么使用`const_iterator`类型。

上面代码中的for循环中只是读取并顺序输出，无需修改map容器中的值，所以是`const_iterator`类型。

**map容器**

![title](https://leanote.com/api/file/getImage?fileId=5e8408fbab64411d500018fd)

![title](https://leanote.com/api/file/getImage?fileId=5e84095dab64411d5000190f)
![title](https://leanote.com/api/file/getImage?fileId=5e84098eab64411d50001915)

# 0x03 产生一个交叉引用表

现在想要编写程序来产生一个交叉引用表从而指示每一个单词在是在输入的哪些行出现的。

设计为：

```
map<string,vector<int> > 
//注意两个 > 之间应该隔一个空格，不然编译器会误认为是 >> 符号
```

- `vector<int>` 存储出现的那些行数。

**程序设计**

![title](https://leanote.com/api/file/getImage?fileId=5e841b70ab64411b51001c11)

**一个注意点**

![title](https://leanote.com/api/file/getImage?fileId=5e841bacab64411b51001c1a)

**缺省参数**

![title](https://leanote.com/api/file/getImage?fileId=5e841bceab64411d50001c7a)

**存入行数**

![title](https://leanote.com/api/file/getImage?fileId=5e841c22ab64411b51001c30)

**完整代码**

![title](https://leanote.com/api/file/getImage?fileId=5e84471dab64411b51002493)
![title](https://leanote.com/api/file/getImage?fileId=5e84472fab64411d50002536)
![title](https://leanote.com/api/file/getImage?fileId=5e84473aab64411d50002538)
![title](https://leanote.com/api/file/getImage?fileId=5e844745ab64411d5000253c)

或者：

``` 
#include <map>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <iterator>

using namespace std;

//定义split函数
//如果参数是空白区域则为true，否则为false
bool space(char c)
{
	return isspace(c);
}
//如果参数是空白区域则为false，否则为true
bool not_space(char c)
{
	return !isspace(c);
}
//split函数，用于把一行的单词录入一个向量中
vector<string> split(const string& str)
{
	typedef string::const_iterator iter;
	vector<string> ret;

iter i = str.begin();
	while (i != str.end())
	{
		//忽略前端的空白
		i = find_if(i, str.end(), not_space);
		//找出下一个单词的结尾
		iter j = find_if(i, str.end(), space);
		//复制在[i,j)中的字符
		if (i != str.end())
		{
			ret.push_back(string(i, j));
		}		
		i = j;
	}
	return ret;
}

//查找指向输入中每一个单词的所有行
map<string, vector<int> > xref(istream& in, vector<string> find_words(const string&) = split)
{
	string line; //输入的每一行，我们把它存入一个vector中，这个vector的每一个元素都是一行
	
	int line_number = 0;
	map<string, vector<int> > ret; //ret 是这个映射表（map）的名字，只是把>>分开写成了> >，不然编译器会误认为是>>符号！！！

//读下一行
	while (getline(in, line))
	{
		++line_number;

//把输入行分割成单词
		vector<string> words = find_words(line);

//记住出现在当前行的每一个单词
		for (vector<string>::const_iterator it = words.begin(); it != words.end(); ++it)
		{
			ret[*it].push_back(line_number);
		}
	}
	return ret;
}

int main()
{
	//缺省用split来调用xref
	map<string, vector<int> > ret = xref(cin); //调用此函数赋值给ret

//输出结果
	for (map<string,vector<int> >::const_iterator it = ret.begin(); it != ret.end(); ++it)
	{
		//输出单词
		cout << it->first << " occurs on line(s): ";
		//后面跟着一个或多个的行编号
		vector<int>::const_iterator line_it = it->second.begin();
		cout << *line_it;
		++line_it;
		//如果有的话输出其余的行编号
		while (line_it != it->second.end())
		{
			cout << "," << *line_it;
			++line_it;
		}
		//换一个新行以便把每一个单词与下一个分隔开来
		cout << endl;
	}
	return 0;
}
```
 
**执行效果**

![title](https://leanote.com/api/file/getImage?fileId=5e844783ab64411b510024b0)

# 0x04 生成句子

```
#include <map>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <iterator>
#include <stdexcept>
#include <stdlib.h>

using namespace std;
typedef vector<string> Rule; //规则本身是string类型的向量
typedef vector<Rule> Rule_collection; //规则集合的类型
typedef map<string, Rule_collection> Grammar; //文法：映射表的类型

//读入文法的函数
//从一个特定的输入流读入一个文法
Grammar read_grammar(istream& in) //cin是此类型的实参
{
	Grammar ret;
	string line; 
	//读输入
	while (getline(in, line))
	{
		//把输入分割成单词
		vector<string> entry = split(line);
		if (!entry.empty())
			//用种类来储存相关联的规则
			ret[entry[0]].push_back(Rule(entry.begin()+1,entry.end())); //两个参数定义了一个序列
	}
	return ret;
}

//读入文法，生成句子
vector<string> gen_sentence(const Grammar& g)
{
	vector<string> ret;
	gen_aux(g, "<sentence>",ret); //通过辅助函数gen_aux改变ret的值
	return ret;
}
//定义辅助函数 gen_aux
//这个函数判断一个单词是不是被括号围起来了
bool bracketed(const string& s)
{
	return s.size() > 1 && s[0] == '<' && s[s.size() - 1] == '>';
}
void gen_aux(const Grammar& g, const string& word, vector<string>& ret)
{
	if (!bracketed(word))
	{
		ret.push_back(word);
	}
	else
	{
		//为对应于word的规则定为
		Grammar::const_iterator it = g.find(word);
		if (it == g.end()) //说明g中没有word这样的元素存在，猪一般写成g[word]，会自动创建带有这个键的元素，搞乱map
			throw logic_error("empty rule");
		// 获取可能的规则集合
		const Rule_collection& c = it->second; //间接引用pair
		//从规则集合中随机选择一条规则
		const Rule& r = c[nrand(c.size())];
		//递归展开规则内所有的尖括号
		for (Rule::const_iterator i = r.begin(); i != r.end(); ++i)
			gen_aux(g, *i, ret);
	}
}
//返回[0,n)中的一个随机整数
int nrand(int n)
{
	if (n <= 0 || n > RAND_MAX)
		throw domain_error("Argument to nrand is out of range.");
	const int bucket_size = RAND_MAX / n;
	int r;
	do r = rand() / bucket_size;
	while (r >= n);
	return r;
}
int main()
{
	//生成句子
	vector<string> sentence = gen_sentence(read_grammar(cin));
	//输出第一个单词，如果存在的话；第一个单词的特殊之处主要是之前没有空格
	vector<string>::const_iterator it = sentence.begin();
	if (!sentence.empty())
	{
		cout << *it;
		++it;
	}
	//输出其余的单词，每一个单词之前都有一个空格
	while (it != sentence.end())
	{
		cout << " " << *it;
		++it;
	}
	cout << endl;
	return 0;
}
```

# 0x05 小结

![title](https://leanote.com/api/file/getImage?fileId=5e8465ceab64411b51002acc)
![title](https://leanote.com/api/file/getImage?fileId=5e8465e5ab64411d50002b54)

Snowming04's Blog

导航

最近发表

友情链接