C++ Prime 第十一章 关联容器
2023-04-28~2023-05-05
11.1节练习
练习11.1：
map：关联容器，按照关键字值-对进行存储，通过关键字访问对应的值，每个键对应一个值，键不能重复
vector：顺序容器，通过顺序对值进行存储，可以通过下标访问对应的值，可以存储重复的元素
练习11.2：
map：按照键值对进行数据存储，并且需要快速查找和插入元素
set：需要存储唯一数据，并且需要快速查找和插入元素
deque：在任意位置频繁插入数据、删除数据（尤其是队首、尾），但不需要随机访问元素
list：在任意位置频繁插入、删除操作，不需要对元素进行随机访问
vector：频繁在尾部插入、删除数据，并且需要对元素进行随机访问
练习11.3：
#include<iostream>
#include<map>
using namespace std;
int main()
{
map<string, size_t> words;
string word;
while (cin >> word)
{
++words[word];
}
for (auto temp : words)
{
cout << temp.first << "times: " << temp.second << endl;
}
system("pause");
return 0;
}
练习11.4：
#include<iostream>
#include<map>
using namespace std;
void ConvertFormat(string& s)
{
for (int i = 0; i < s.size(); ++i)
{
s[i] = toupper(s[i]);
if (s[i] == ',' || s[i] == '.')
{
s.erase(i, 1);
}
}
}
int main()
{
map<string, size_t> words;
string word;
while (cin >> word)
{
ConvertFormat(word);
++words[word];
}
for (auto temp : words)
{
cout << temp.first << "times: " << temp.second << endl;
}
system("pause");
return 0;
}
11.2.1节练习
练习11.5：
set以键进行存储，map以键值对进行存储
练习11.6：
频繁添加、删除元素使用list 频繁随机访问使用map
练习11.7：
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
map<string, vector<string>> family;
vector<string> english = { "kangkang", "lihua" };
family["laowang"] = english;
family["laowang"].push_back("maruiya");
for (auto temp : family["laowang"])
{
cout << temp << endl;
}
system("pause");
return 0;
}
练习11.8：
使用set不用检查名字是否已经存在，因为set无法保存两个相同的键
#include<iostream>
#include<set>
#include<vector>
using namespace std;
void saveWordsBySet()
{
set<string> words;
string temp;
while (cin >> temp)
{
words.insert(temp);
}
cout << "set: " << endl;
for (auto temp : words)
{
cout << temp << endl;
}
}
void saveWordsByVector()
{
vector<string> words;
string temp;
while (cin >> temp)
{
auto flag = find(words.begin(), words.end(), temp);
if (flag == words.end())
{
words.push_back(temp);
}
}
cout << "vector: " << endl;
for (auto temp : words)
{
cout << temp << endl;
}
}
int main()
{
//saveWordsBySet();
saveWordsByVector();
system("pause");
return 0;
}
11.2.2节练习
练习11.9：
#include<iostream>
#include<map>
#include<list>
#include<string>
#include <sstream>
using namespace std;
int main()
{
map<string, list<int>> wordsLineNo;
string line;
int lineNo = 1;
while (getline(cin, line))
{
istringstream tempLine(line);
string tempString;
while (tempLine >> tempString)
{
wordsLineNo[tempString];
wordsLineNo[tempString].push_back(lineNo);
}
++lineNo;
}
for (auto wordSet : wordsLineNo)
{
cout << wordSet.first << endl;
for (auto lineNo : wordSet.second)
{
cout << lineNo << endl;
}
}
system("pause");
return 0;
}
练习11.10：
list迭代器不支持比较运算符，无法作为map的键
vector迭代器满足map的比较运算要求，可以作为map的键
练习11.11：
知识点函数指针：221页
#include<iostream>
#include<set>
using namespace std;
class Sales_data
{
public:
Sales_data() = default;
Sales_data(const string& book, unsigned units, double price)
: bookNo(book), unitsSold(units), revenue(price* units) {};
string bookNo;
private:
unsigned unitsSold = 0;
double revenue = 0.0;
};
bool compareIsbn(const Sales_data& s1, const Sales_data& s2)
{
return s1.bookNo < s2.bookNo;
}
int main()
{
//multiset<Sales_data, decltype(compareIsbn)*> SaleSet(compareIsbn);
//方法1:
//typedef bool (*pf)(const Sales_data & s1, const Sales_data & s2);
//方法2:
using pf = bool (*)(const Sales_data& s1, const Sales_data& s2);
multiset<Sales_data, pf> SaleSet(compareIsbn);
// 定义时指定pf作为SalesDate的排序准则->SaleSet将compare指针传递给pf
Sales_data s1("1001", 100, 100.1);
Sales_data s2("1002", 100, 100.1);
Sales_data s3("1000", 100, 100.1);
SaleSet.insert(s1);
SaleSet.insert(s2);
SaleSet.insert(s3);
for (auto& temp : SaleSet)
{
cout << temp.bookNo << endl;
}
system("pause");
return 0;
}
11.2.3节练习
练习11.12：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<pair<string, int>> nameAgePair;
vector<string> names = { "kangkang", "lihua", "maruiya" };
vector<int> ages = { 18, 20, 24 };
string name;
int age;
for (int i = 0; i < 3; ++i)
{
pair<string, int> pTemp(names[i], ages[i]);
nameAgePair.push_back(pTemp);
}
for (auto temp : nameAgePair)
{
cout << temp.first << " " << temp.second << endl;
}
system("pause");
return 0;
}
练习11.13：
方法1类似初始化更容易理解
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<pair<string, int>> nameAgePair;
vector<string> names = { "kangkang", "lihua", "maruiya" };
vector<int> ages = { 18, 20, 24 };
string name;
int age;
for (int i = 0; i < 3; ++i)
{
// 方法1:
//pair<string, int> pTemp(names[i], ages[i]);
// 方法2:
//auto pTemp = make_pair(names[i], ages[i]);
// 方法3:
pair<string, int> pTemp = { names[i], ages[i] };
nameAgePair.push_back(pTemp);
}
for (auto temp : nameAgePair)
{
cout << temp.first << " " << temp.second << endl;
}
system("pause");
return 0;
}
练习11.14：
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
map<string, vector<pair<string, int>>> family;
pair<string, int> p1 = { "kangkang", 18 };
vector<pair<string, int>> infos;
infos.push_back(p1);
family["laowang"] = infos;
pair<string, int> p2 = { "jane", 26 };
family["laowang"].push_back(p2);
for (auto temp : family["laowang"])
{
cout << temp.first << endl;
cout << temp.second << endl;
}
system("pause");
return 0;
}
11.3.1节练习
练习11.15：
key_type是int
value_type是pair<const int, vector<int>>
mapped_type是vector<int>
练习11.16：
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
map<string, int>myMap = { {"kangkang", 18} };
map<string, int>::iterator iter = myMap.begin();
int age = (*iter).second;
cout << age << endl;
system("pause");
return 0;
}
练习11.17:
copy(v.begin(), v.end(), inserter(c, c.end())); // 合法
copy(v.begin(), v.end(), back_inserter(c)); // 不合法，multiset没有push_back操作所以不能使用back_inserter
copy(c.begin(), c.end(), inserter(v, v.begin())); // 合法
copy(c.begin(), c.end(), back_inserter(v)); // 合法
练习11.18：
map<string, size_t>::iterator map_it
练习11.19：
#include<iostream>
#include<set>
using namespace std;
class Sales_data
{
public:
Sales_data() = default;
Sales_data(const string& book, unsigned units, double price)
: bookNo(book), unitsSold(units), revenue(price* units) {};
string bookNo;
private:
unsigned unitsSold = 0;
double revenue = 0.0;
};
bool compareIsbn(const Sales_data& s1, const Sales_data& s2)
{
return s1.bookNo < s2.bookNo;
}
int main()
{
//multiset<Sales_data, decltype(compareIsbn)*> SaleSet(compareIsbn);
//方法1:
//typedef bool (*pf)(const Sales_data & s1, const Sales_data & s2);
//方法2:
using pf = bool (*)(const Sales_data& s1, const Sales_data& s2);
multiset<Sales_data, pf> SaleSet(compareIsbn);
// 定义时指定pf作为SalesDate的排序准则->SaleSet将compare指针传递给pf
Sales_data s1("1001", 100, 100.1);
Sales_data s2("1002", 100, 100.1);
Sales_data s3("1000", 100, 100.1);
SaleSet.insert(s1);
SaleSet.insert(s2);
SaleSet.insert(s3);
multiset<Sales_data, pf>::iterator iter = SaleSet.begin();
cout << (*iter).bookNo << endl;
system("pause");
return 0;
}
11.3.2节练习
练习11.20：
insert版本更容易理解（初始化和递增分隔开来）
#include<iostream>
#include<map>
using namespace std;
int main()
{
map<string, size_t> words;
string word;
while (cin >> word)
{
auto ret = words.insert({ word, 1 });
if (!ret.second)
{
++(ret.first->second);
}
}
for (auto temp : words)
{
cout << temp.first << "times: " << temp.second << endl;
}
system("pause");
return 0;
}
练习11.21：
记录每个输入的单词的次数
练习11.22：
map<string, size_t> words;
string word = "example";
pair<map<const string, size_t>::iterator, bool> ret = words.insert(pair<string, size_t>(word, 1));
练习11.23：
略
11.3.4节练习：
练习11.24：
m下标0位置值初始化为1
练习11.25：
报错（语句意义：v下标位置重新赋值为1）
练习11.26：
map键类型对应的操作，返回的也是map键类型
map<int, int> m;
m[0] = 1;
map<int, int>::key_type test = m[0];
11.3.5节练习
练习11.27：
键大于1使用count和find、键唯一使用find
练习11.28：
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
map<string, int> m;
m["kangkang"] = 18;
map<string, int>::iterator iter = m.find("kangkang");
cout << (*iter).first << (*iter).second << endl;
system("pause");
return 0;
}
练习11.29：
返回end()
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
map<string, int> m;
map<string, int>::iterator up_iter = m.upper_bound("kangkang");
map<string, int>::iterator low_iter = m.lower_bound("kangkang");
pair<map<string, int>::iterator, map<string, int>::iterator> pair_iter = m.equal_range("kangkang");
if (up_iter == m.end())
{
cout << "up_iter is end()" << endl;
}
if (low_iter == m.end())
{
cout << "up_iter is end()" << endl;
}
if (pair_iter.first == m.end())
{
cout << "up_iter is end()" << endl;
}
if (pair_iter.second == m.end())
{
cout << "up_iter is end()" << endl;
}
system("pause");
return 0;
}
练习11.30：
pos.first：通过关键字寻找到的pair对象，该pair对象存储着键值对数据，pos.first.first是关键字，post.first.second是关键字对应的值
练习11.31：
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
multimap<string, string> bookinfo;
bookinfo.emplace("金庸", "天龙八部");
auto iter = bookinfo.find("金庸1");
if (iter != bookinfo.end())
{
bookinfo.erase(iter);
}
for (auto temp : bookinfo)
{
cout << temp.second << endl;
}
system("pause");
return 0;
}
练习11.32：
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
multimap<string, string> bookinfo;
bookinfo.emplace("金庸2", "射雕英雄传");
bookinfo.emplace("金庸1", "碧血剑");
bookinfo.emplace("金庸3", "天龙八部");
// multimap默认按照字典顺序存储元素
for (auto temp : bookinfo)
{
cout << temp.first << temp.second << endl;
}
system("pause");
return 0;
}
11.3.6节练习
练习11.33:
#include<iostream>
#include<fstream>
#include<string>
#include<sstream>
#include<map>
#include<vector>
using namespace std;
map<string, string> build_map(ifstream& input)
{
map<string, string> rules_map;
string key, value;
while (input >> key && getline(input, value))
{
rules_map[key] = value.substr(1);
}
return rules_map;
}
const string& transfrom(const string& s, map<string, string>& transform_ruls)
{
auto ret = transform_ruls.find(s);
if (ret != transform_ruls.cend())
{
return ret->second;
}
else
{
return s;
}
}
void word_transform(ifstream& input, map<string, string>& transform_ruls)
{
string line;
while (getline(input, line))
{
string word;
istringstream words(line);
while (words >> word)
{
cout << transfrom(word, transform_ruls);
cout << " ";
}
}
}
int main()
{
ifstream input_file("transform_words.txt");
ifstream rules_txt("transform_rules.txt");
auto rules = build_map(rules_txt);
word_transform(input_file, rules);
system("pause");
return 0;
}
练习11.34：
替换成下标运算符后，当出现关键词不在替换规则map中时会抛出异常
练习11.35：
当关键字已经存在与map中时，通过insert插入重复的关键字不会生效，通过下标方式会将该关键字的值重新赋值
练习11.36：
书中程序会抛出异常打印:no rules for xx,自己实现的单词转化版本会将空字符串赋值给对应键
11.4节练习
练习11.37:
无序容器查找、插入、删除效率高,需要键值对按照序存储时用有序容器
练习11.38:
略
C++Prime学习笔记 文章被收录于专栏
勇敢和愚蠢只有一剑之差
查看45道真题和解析