1 概念

1.1 map

map：
关联容器：

• 1 会以键值从小到大排序（内部实现为：红黑树）；
• 2 如果是字符串映射到整数，必须使用string，不能使用char数组；
• 3 使用迭代器，可以同时查到键值和映射后的值；
• 4 存储的“键-值”对，键值唯一。

1.2 pair

pair:
头文件：<utility>
相当于简化版的map，常用代替二元结构体以及构造函数。

数据结构内部实现：

struct pair{typeName1 first;typeName2 second;
}

可以进行比较(==,>,>=,<,<=,!=)，首先以first的大小为标准，然后只有first相等，才会去判断second。

对于一个键类型为K而值类型为V的映射表来说，关联的pair类型是pair<const K, V>。键是常量，因此无法修改元素的键值，如果不是常量，那么我们可能会对其进行修改。

2 map使用示例

2.1 问题描述

使用映射表编写一个程序，这个程序描述了一种语句结构（或称为语法）并且能生成符合这个描述的随机语句。

例如：能将一个英文句子描述成一个名词和一个动词或者是一个名词或动词与一个对象的组合。

例如下面是程序的结果：

2.2 思路

• 1 读入文法
  • 文法的表示规则为；
    • vetor<string> Rule;表示规则的类型；（如动词、名词）
    • vetor<Rule> Rule_collection;表示规则集合的类型；（比如<sentence>开头的造句规范）
    • map<string, Rule_collection> Grammar;表示映射表的类型；（如<v>对应着sits、jumps，<sentence>对应着 the <nm> <v> <p>）
  • 将每个语句的第一个类型作为键，后面的的string作映射后的值
• 2 生成语句
  • 找到一条对应<sentence>的规则，然后分段构造输出，将不同的规则和规则的内容组成输出。
• 3 选择随机元素
  • 使用rand()生成随机数。

##2.3 实现代码

//造句
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <cctype>
#include <stdexcept>
#include <cstdlib>using std::cin; using std::cout;
using std::endl;
using std::map; using std::string;
using std::vector; using std::istream;
using std::logic_error;
using std::domain_error;typedef vector<string> Rule;
typedef vector<Rule> Rule_collection;
typedef map<string, Rule_collection> Grammar;//是空白区域为true
bool space(char c){return isspace(c);
}
//不是空白区域为true
bool not_space(char c){return  !isspace(c);
}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;
}Grammar read_grammar(istream& in){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;
}bool backeted(const string& s){return  s.size() > 1 && s[0] == '<' && s[s.size() - 1] == '>';
}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;}void gen_aux(const Grammar& g, const string& word, vector<string>& ret){if(!backeted(word)){ret.push_back(word);}else{//为对应的word规则定位Grammar::const_iterator it = g.find(word);if(it == g.end()){throw logic_error("empty rule");}//获取可能的规则const Rule_collection& c = it->second;//进入到vector<vector<string>>//从规则集合中随机选择一条规则const Rule& r = c[nrand(c.size())];//到vector<string>for (Rule::const_iterator i = r.begin(); i != r.end(); ++i) {gen_aux(g, *i, ret);}}
}vector<string> gen_sentence(const Grammar& g){vector<string> ret;//展开第二个参数传递过来的字符串//在第一个参数的文法（语句结构）中查找这个字符串并将它的输出放在第三个参数中gen_aux(g, "<sentence>", ret);return ret;
}int main(int argc, char const *argv[]){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;
}
/*
<sentence> the <nm> <v> <p>
<n> cat
<n> dog
<n> table
<nm> <n>
<nm> <a> <nm>
<a> large
<a> brown
<a> absurd
<v> sits
<v> jumps
<p> on te stairs
<p> under the sky
<p> wherever it wants*/