C++关联容器(复习题篇)
本篇博客将介绍标准库关联容器，包括：
- 关联容器的概念和简单的使用
- 关联容器涉及的类型和操作，特别是与顺序容器的差异
- 无序关联容器，特别是与有序关联容器的差异
练习1.1 描述map和vector的不同
vector是顺序容器其中的元素是“顺序存储的”，每个元素都有唯一对应的位置编号，所有操作都是按编号(位置)进行的。例如，获取元素(头、尾、用下标获取任意位置)、插入删除元素(头、尾、任意位置)、遍历元素(按元素位置顺序逐一访问)。底层的数据结构是数组、链表，简单但已能保证上述操作的高效执行。而对于依赖值访问的元素，例如查找(搜索)给定值(find)，在这种数据结构上的实现是要通过遍历完成的，效果不佳。
map这种关联容器，就是为了高效实现“按值访问元素”这类操作而设计的。为了达到这一目的。容器中的元素是按关键字值存储的，关键字值与元素数据建立起对应关系，这就是"关联"的含义。底层数据结构是红黑树，哈希表等，可高效实现按关键字值查找、添加、删除元素等操作。
练习1.2 分别给出最适合使用list、vector、deque、map以及set的例子
若元素很小，大致数量预先可知，在程序运行过程中不会剧烈变化，大部分情况下只在末尾添加或删除需要频繁访问任意位置的元素，则vector可带来最高的效率。若需要频繁在头部和尾部添加或删除元素，则deque是最好的选择。
如果元素较大，数量预先不知道，或是程序运行中频繁变化，对元素的访问更多是顺序访问全部或很多元素，则list更为合适。
map很适合对一些对象按它们的某个特征进行访问的情形。可将学生信息作为元素值，学生的姓名作为元素的关键字值。
set就是集合类型。当需要保存特定的值集合--通常是满足/不满足某种要求的值集合，set最为方便。
练习1.3 编写自己的单词计数程序
代码如下所示：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
int main()
{
map<string,size_t> word_count; //从string到count的映射
string word;
int n;
cout<<"请输入有几个单词:";
cin>>n;
for(int i=0;i<n;i++)
{
cin>>word;
++word_count[word]; //若单词一样直接count+1，不相同则新存储+1
}
for(const auto &w:word_count)
{
cout<<w.first<<" 出现的次数:"<<w.second<<endl;
}
return 0;
}运行的结果如下：
练习1.4 扩展上述程序忽略大小写以及标点符号的单词计数器
在上述程序中添加进入容器之前进行一个函数的改写即可，遇到大小写则转换，遇到标点符号则删除。
更改后的程序如下所示：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
string &trans(string &s)
{
for(int i=0;i<=s.size();i++)
{
if(s[i]>='A'&&s[i]<='Z')
{
s[i]-=('A'-'a');
}
else if((s[i]==','&&s[i+1]=='.')||(s[i]=='.'&&s[i+1]==','))
s.erase(i,2);
else if(s[i]==','||s[i]=='.')
s.erase(i,1);
}
return s;
}
int main()
{
map<string,size_t> word_count; //从string到count的映射
string word;
int n;
cout<<"请输入有几个单词:";
cin>>n;
for(int i=0;i<n;i++)
{
cin>>word;
trans(word);
++word_count[word]; //若单词一样直接count+1，不相同则新存储+1
}
for(const auto &w:word_count)
{
cout<<w.first<<" 出现的次数:"<<w.second<<endl;
}
return 0;
}程序运行后如下所示：
练习1.5 解释map和set的差别。你如何选择使用哪一个？
当需要查找给定值所对应的数据时，应使用map，其中保存的是<关键字，值>对，按照关键字访问值。
如果只需要判定给定值是否存在时，应使用set，他是简单的值集合。
练习1.6 解释set和list的区别，你如何选择使用哪一个？
两者都可以保存元素集合
如果只需要顺序访问这些元素或者是按照位置访问元素，那么使用list。
如果需要快速判定是否有元素等于给定值，则应该使用set。
练习1.7 定义一个map，关键字时该家族的姓氏，值是一个vector，保存家族中孩子们的名。编写程序，实现添加新家族以及向家族中添加新的孩子。
代码如下所示：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
int main()
{
int m;
string fam,ily;
map<string,vector<string>>family;
cout<<"请输入数据个数:";
cin>>m;
for(int i=0;i<m;i++)
{
cout<<"请输入姓和名:";
cin>>fam;
cin>>ily;
family[fam].push_back(ily);
}
for(auto a:family)
{
cout<<"家族姓为:"<<a.first<<" ";
for(auto c:a.second)
{
cout<<"名为:"<<c<<" ";
}
cout<<endl;
}
return 0;
}运行结果如下：
family[fam].push_back(ily)，这个语句是当该容器中存在fam关键字时只存储ily进入容器中，如果不存在该关键字则新创建一个存入该容器中。
练习1.8 编写一个程序，在一个vector而不是set中保存不重复的单词，set的优点是什么？
使用vector保存不重复的单词，需要用find查找新读入的单词是否已经存在于vector中，若不存在(返回尾后迭代器)，才将单词存入vector中。
而使用set，检查是否重复的工作时由set模板负责的，程序员无须编写对应的代码，程序简洁很多。
更深层次的差别，vector时无序的线性表，find查找指定值时只能采用顺序查找的方式，所花费的时间与vector.size()呈线性关系。而set是用红黑树实现的，花费的时间与vector.size()呈对数关系。当单词数量非常多的时候，set的性能优势是巨大的。
当然，vector也不是毫无用处。它可以保存单词输入的顺序不改变，而set则不能，遍历set元素是按照值的升序被遍历的。
vector版本程序:
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
string &trans(string &s)
{
for(int i=0;i<=s.size();i++)
{
if(s[i]>='A'&&s[i]<='Z')
{
s[i]-=('A'-'a');
}
else if((s[i]==','&&s[i+1]=='.')||(s[i]=='.'&&s[i+1]==','))
s.erase(i,2);
else if(s[i]==','||s[i]=='.')
s.erase(i,1);
}
return s;
}
int main()
{
vector<string> unique_word;
int n;
string word;
cout<<"请输入单词的个数:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入单词:";
cin>>word;
trans(word);
if(find(unique_word.begin(),unique_word.end(),word)==unique_word.end()) //当没有重复单词的时候才进行存储
unique_word.push_back(word);
}
for(const auto &w:unique_word)
{
cout<<w<<" ";
}
}运行结果如下所示，重复的单词都只存储了一遍：
set版本程序：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
string &trans(string &s)
{
for(int i=0;i<=s.size();i++)
{
if(s[i]>='A'&&s[i]<='Z')
{
s[i]-=('A'-'a');
}
else if((s[i]==','&&s[i+1]=='.')||(s[i]=='.'&&s[i+1]==','))
s.erase(i,2);
else if(s[i]==','||s[i]=='.')
s.erase(i,1);
}
return s;
}
int main()
{
set<string> unique_word;
int n;
string word;
cout<<"请输入单词的个数:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入单词:";
cin>>word;
trans(word);
unique_word.insert(word);
}
for(const auto &w:unique_word)
{
cout<<w<<" ";
}
}运行结果如下所示：
可以清楚的观察到与vector输出的顺序不太一样吗，因为set容器会自动将值按照升序排列出来，所以和vector输出的形式不太一样，但是功能是一致的。
练习1.9 定义一个map，将单词与一个行号的list关联，list中保存的是单词所出现的行号。
map的定于为：map<string,list<int>> word_linno;
完整的程序如下所示。其中getline是读取一行，统计行号。在使用字符串流istringstream读取这个行中的每一个单词，记录单词行号。
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
string &trans(string &s)
{
for(int i=0;i<=s.size();i++)
{
if(s[i]>='A'&&s[i]<='Z')
{
s[i]-=('A'-'a');
}
else if((s[i]==','&&s[i+1]=='.')||(s[i]=='.'&&s[i+1]==','))
s.erase(i,2);
else if(s[i]==','||s[i]=='.')
s.erase(i,1);
}
return s;
}
int main()
{
ifstream in;
in.open("英文.txt",ios::in);
map<string,list<int>> words;
string line;
string word;
int lineno=0;
while(getline(in,line)) //从文本中读取一行的内容
{
lineno++;
istringstream l_in(line); //字符串流
while(l_in>>word)
{
trans(word);
words[word].push_back(lineno);
}
}
for(const auto &w:words)
{
cout<<w.first<<"所在行为:";
for(const auto &i:w.second)
{
cout<<i<<" ";
}
cout<<endl;
}
}运行的结果如下所示：
练习1.10 可以定义一个vector<int>::iterator到int的map吗？list<int>::iterator到int的map呢？对于这两种情况，如果不能，解释为什么？
由于有序容器要求关键字类型必须支持比较操作<，因此
map<vector<int>::iterator,int> m1；是可以的，因为vector的迭代器支持比较操作。
而list的迭代器不支持比较操作所以是不可以的。
练习1.11 编写程序，读入string和int的序列，将每个string和int存入一个pair中，pair保存在一个vector中。
一共有三种创建pair的方法如下所示：
nums.push_back({num,name}); //列表赋值pair
nums.push_back(pair<int,string>(num,name)); //正常赋值
nums.push_back(make_pair(num,name)); //使用make_pair赋值
最简洁的方式就是列表初始化的方式
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
int main()
{
vector<pair<int,string>> nums;
int n,num;
string name;
cout<<"请输入员工数量:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入员工的信息(工号和姓名):";
cin>>num>>name;
// nums.push_back({num,name}); //列表赋值pair
nums.push_back(pair<int,string>(num,name)); //正常赋值
// nums.push_back(make_pair(num,name)); //使用make_pair赋值
}
for(const auto w:nums)
{
cout<<"工号为:"<<w.first<<" 姓名为:"<<w.second<<endl;
}
}运行结果如下所示：
练习1.12 向map中添加三个内容，关键字中存储姓，值编写一个pair将孩子的名和生日都存储进去。
在本题中，我们将家庭的姓映射到孩子信息的列表，而不是简单的孩子名字的列表。因此，将vector中的元素类型声明为pair<string，string>，两个string存储名字和生日，在添加孩子的时候使用列表初始化方式创建pair存储在vector中即可。
代码如下所示：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
void add_famliy(map<string,vector<pair<string,string>>> &famliy,const string &fam)
{
famliy[fam];
}
void add_child(map<string,vector<pair<string,string>>> &famliy,const string &fam,const string &name,const string &birth)
{
famliy[fam].push_back({name,birth});
}
int main()
{
map<string,vector<pair<string,string>>> famlies;
string fam,name,birth;
int n;
cout<<"请输入人数:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请分别输入姓氏和名字以及出生年月日:";
cin>>fam>>name>>birth;
add_famliy(famlies,fam);
add_child(famlies,fam,name,birth);
}
for(auto f:famlies)
{
cout<<f.first<<"家的孩子: ";
for(auto c:f.second)
{
cout<<c.first<<" 生日是: "<<c.second<<" ";
}
cout<<endl;
}
}运行结果如下：
练习1.13 使用一个map迭代器编写一个表达式，将一个值赋予一个元素。
解引用关联容器的迭代器，得到的是value_type的值的引用。因此对map而言，得到的是一个pair类型的引用，其中first成员保存const的关键字，second成员保存值。因此通过迭代器只可以修改值而不可以修改关键字。
map<int,int> m;
auto it=m.begin();
it->second=0; //将关键字对应的值设置为0
练习1.14 单词计数程序，使用插入代替下表操作。
代码如下：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
int main()
{
map<string,size_t> word_count;
string word;
int n;
cout<<"请输入单词个数:";
cin>>n;
for(int i=0;i<n;i++)
{
cin>>word;
auto ret= word_count.insert({word,1});
if(!ret.second)
++ret.first->second;
}
for(const auto &w:word_count)
{
cout<<w.first<<"出现了"<<w.second<<"次\n";
}
} 运行结果如下所示：
使用insert操作的方式是：构造一个 pair(单词,1)，用insert将其插入容器，返回一个pair。若单词已存在，则返回pair的second成员为false，表示插入失败，程序员还需要通过返回的pair的first成员迭代器递增已有单词的计数器。判断单词是都以及已经存在的操作都由程序员负责编写。
使用下标操作的时候，当单词已经存在的时候则提取出元素的值；否则，下标操作将pair等插入容器中，提取出新的元素值。
练习1.15 对于什么问题你会使用count解决？什么时候你又会选择find呢？
find查找关键字在容器中出现的位置，而count则还会统计关键字出现的次数。
因此，如果我们希望知道容器中有多少元素的关键字与给定的关键字相同时，使用count。
当我们只关心关键字是否在容器中时，使用find就足够了。特别时，对于不允许出现重复关键字的关联容器，find和count的效果没有什么区别，使用find就可以了。当我们获取具有给定关键字的元素时，也需要使用find。
find和下标操作有一个重大区别，当给定关键字不存在容器中时，下标操作会直接插入一个具有关键字的元素。因此当我们像检查关键字是否存在时是使用find而不是下标操作。
练习1.16 如果给定的关键字不在容器中，upper_bound、lower_bound和equal_range分别会返回什么？
lower_bound返回第一个具有给定关键字的元素，upper_bound则返回最后一个具有给定关键字的元素之后的位置。即，这两个迭代器构成包含所有具有给定关键字的元素范围。若给定关键字不存在于容器之中，两个操作显然应构成一个空范围，它们返回相当的迭代器，之处关键字的正确插入位置——不影响关键字的排序。如给定关键字比容器中所有的关键字都大，则此位置时容器的尾后位置end。
equal_range返回一个pair，其first成员等价于lower_bound返回的迭代器，second成员等价于upper_bound返回的迭代器。因此若给定关键字不在容器中，first和second都指向关键字的正确插入位置，两个迭代器构成一个空范围。
练习1.17 编写程序，定义一个作者及其作品的multimap。使用find在multimap中查找一个元素并用erase删除它。确保你的程序在元素不在容器中时也可以正常运行。
将数据插入multimap中需要使用insert操作
在multimap中查找具有给定关键字元素，有几种方法：使用find只能查找第一个具有给定关键字的元素，要找到所有具有给定关键字的元素，需要编写循环。lower_bound和upper_bound配合使用，可以找到具有给定关键字值的范围。equal_range最为简单，依次即可获得要查找的元素范围，随后使用erase删除掉即可。需要先判断该范围是否为空，不为空再删除。
代码如下所示：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
void remove_author(multimap<string,string> &books,string &author)
{
auto pos=books.equal_range(author);
if(pos.first==pos.second)
cout<<"该容器中不存在"<<author<<"的作品!"<<endl; //不存在该作者
else
books.erase(pos.first,pos.second); //删除该作者所有的书籍
}
void print(multimap<string,string> &books)
{
cout<<"当前书目为:\n";
for(auto book:books)
{
cout<<"\t作者是:"<<book.first<<endl<<"\t含有书籍:"<<book.second<<endl;
cout<<endl;
}
cout<<endl;
}
int main()
{
multimap<string,string> books;
string author;
string auth;
string book;
int x;
cout<<"请输入您内容的数量:";
cin>>x;
for(int i=0;i<x;i++)
{
cout<<"输入作者和书籍名:";
cin>>author;
cin>>book;
books.insert({author,book});
}
print(books);
cout<<"请输入您要删除的作者:";
cin>>auth;
remove_author(books,auth);
print(books);
return 0;
}运行的结果如下所示：
练习1.18 实现一个自己版本的单词转换程序。
代码如下所示：
#include<iostream> //c++的头文件
#include<fstream> //文件流的头文件
#include<sstream> //字符串流的头文件
#include<map> //map容器的头文件
#include<unordered_map> //无序map文件
#include<list> //list头文件
#include<set> //set的头文件
#include<vector> //vector的头文件
#include<utility> //pair的头文件
#include<algorithm> //容器算法函数的头文件
using namespace std;
map <string,string> bulidmap(ifstream &map_file) //建立相关的转换映射
{
map<string,string> trans_map; //保存转换的规则，返回值
string key;
string value;
map_file.open("rule.txt",ios::in);
while(map_file>>key && getline(map_file,value))
{
if(value.size()>=1)
trans_map[key]=value.substr(1); //substr用于字符串截取两个参数截取从第一个位置开始的多少长度
else
throw runtime_error("no rule for"+key);
}
return trans_map;
}
const string &transform(const string &s,const map<string,string> &m)
{
auto map_it=m.find(s);
if(map_it!=m.cend())
return map_it->second;
else
return s;
}
void word_transform(ifstream &map_file,ifstream &input)
{
auto trans_map=bulidmap(map_file); //保存规则
cout<<"转换规则为:\n";
for(auto entry:trans_map) //规则转换的显示
{
cout<<"key:"<<entry.first<<"\tvalue:"<<entry.second<<endl;
}
cout<<endl<<endl;
string text;
input.open("text.txt",ios::in);
while(getline(input,text))
{
istringstream stream(text);
string word;
bool firstword=true;
while(stream>>word)
{
if(firstword) //每个单词间空一格的设置
firstword=false;
else
cout<<" ";
cout<<transform(word,trans_map);
}
cout<<endl;
}
}
int main()
{
ifstream rule;
ifstream text;
word_transform(rule,text);
}运行结果如下图所示：
