C++关联容器(复习题篇)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
本篇博客将介绍标准库关联容器包括
- 关联容器的概念和简单的使用
- 关联容器涉及的类型和操作特别是与顺序容器的差异
- 无序关联容器特别是与有序关联容器的差异
练习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<stringstring>两个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);
}运行结果如下图所示
