面向对象编程基础¶
本课程入选教育部产学合作协同育人项目 课程主页:http://cpp.njuer.org 课程老师:陈明 http://cv.mchen.org
ppt和代码下载地址
git clone https://gitee.com/cpp-njuer-org/book
第11章¶
关联容器¶
关联容器¶
关联容器和顺序容器有着根本的不同：
- 关联容器中的元素是按关键字来保存和访问的。
- 与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。
- 支持高效的关键字查找和访问
- 两个主要的关联容器（associative-container）类型是map和set。
- map中的元素是一些关键字-值（key-value）对：
- 关键字起到索引的作用，值则表示与索引相关联的数据
- 字典则是一个很好的使用map的例子：
- 可以将单词作为关键字，将单词释义作为值。
- set中每个元素只包含一个关键字；
- set支持高效的关键字查询操作——检查一个给定关键字是否在set中
关联容器¶
标准库提供8个关联容器,不同体现在三个维度上
- 或者是一个set，或者是一个map
- 或者要求不重复的关键字，或者允许重复关键字
- 允许重复关键字的容器的名字中都包含单词multi
- 按顺序保存元素，或无序保存
- 不保持关键字按顺序存储的容器的名字都以单词unordered开头
- 无序容器使用哈希函数来组织元素
- 因此
- 一个unordered_multi_set是一个允许重复关键字，元素无序保存的集合，
- 一个set则是一个要求不重复关键字，有序存储的集合。
- 头文件
- map和multimap定义在头文件map中
- set和multiset定义在头文件set中
- 无序容器则定义在头文件unordered_map和unordered_set中
关联容器¶
- 按顺序存储
map 关键数组：保存关键字-值对
set 关键字即值，即只保存关键字的容器
multimap 支持同一个键多次出现的map
multiset 支持同一个键多次出现的set
- 无序集合
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap 哈希组织的map，关键字可以重复出现
unordered_multiset 哈希组织的set，关键字可以重复出现
使用关联容器¶
map是关键字-值对的集合,map类型通常被称为关联数组（associative array）
- 将一个人的名字作为关键字，将其电话号码作为值。
- 这样的数据结构为"将名字映射到电话号码"
- 与“正常”数组类似，不同之处在于其下标不必是整数
- 通过一个关键字而不是位置来查找值
使用关联容器¶
set就是关键字的简单集合。
- 当只是想知道一个值是否存在时，set是最有用的。
- 一个企业可以定义一个名为bad_checks的set来保存那些曾经开过空头支票的人的
名字。在接受一张支票之前，可以查询bad_checks来检查顾客的名字是否在其中。
使用map¶
//单词计数程序：
map <string, size_t> word_count; // empty map
// insert a value-initialized element with key Anna;
// assign 1 to the value of that element
word_count["Anna"] = 1;
// fetch the element indexed by Anna; prints 1
cout << word_count["Anna"] << endl;
++word_count["Anna"]; // fetch the element and add 1 to it
cout << word_count["Anna"] << endl; // prints 2
使用map¶
//单词计数程序：
#include<map>
#include<string>
#include<iostream>
using namespace std;
int main(){
map<string,size_t> word_count;
string word;
while(cin>>word)
//如果word还未在map中，下标运算符会创建一个新元素，其关键字为word，值为0。
//不管元素是否是新创建的，我们将其值加1。
++word_count[word];
for(const auto& w : word_count)
//当从map中提取一个元素时，会得到一个pair类型的对象
//pair是一个模板类型，保存两个名为first和second的（公有）数据成员。
//map所使用的pair用first成员保存关键字，用second成员保存对应的值。
cout<<w.first<<","<<w.second<<endl;
return 0;
}
使用set¶
//忽略常见单词，如"the"、"and"、"or"等。我们可以使用set保存想忽略的单词，
//只对不在集合中的单词统计出现次数：
#include<map>
#include<string>
#include<set>
#include<iostream>
using namespace std;
int main(){
map<string,size_t> word_count;
set<string> exclude
={"The","But","And","Or","An","A",
"the","but","and","or","an","a"};
string word;
while(cin>>word)
//只统计不在set中的单词,find调用返回一个迭代器。
//如果给定关键字在set中，迭代器指向该关键字。否则，find返回尾后迭代器。
if(exclude.find(word)==exclude.end())
++word_count[word];
for(const auto& w : word_count)
cout<<w.first<<","<<w.second<<endl;
return 0;
}
练习¶
描述map和vector的不同。
map 是关联容器， vector 是顺序容器。
练习¶
分别给出最适合使用list、vector、deque、map以及set的例子。
list：双向链表，适合频繁插入删除元素的场景。
vector：适合频繁访问元素的场景。
deque：双端队列，适合频繁在头尾插入删除元素的场景。
map：字典。
set：适合有序不重复的元素的场景。
练习¶
编写你自己的单词计数程序。
#include <string>
#include <map>
#include <iostream>
using namespace std;
int main(){
map<string, int> word_count;
string tmp;
while (cin >> tmp){
word_count[tmp] += 1;
}
for (const auto& elem : word_count)
std::cout << elem.first << " : " << elem.second << endl;
return 0;
}
练习¶
扩展你的程序，忽略大小写和标点。例如，"example."、"example,"
和"Example"应该递增相同的计数器。
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <cctype>
void word_count_pro(std::map<std::string, int>& m){
std::string word;
while (std::cin >> word){
for (auto& ch : word)
ch = tolower(ch);
//要删除的元素移到容器末尾并返回要被删除元素的迭代器，
//然后通过erase成员函数来真正删除。一般remove_if和erase函数是成对出现的。
word.erase(std::remove_if(word.begin(),word.end(),ispunct),word.end());
++m[word];
}
for (const auto& e : m) std::cout << e.first << " : " << e.second << "\n";
}
int main(){
std::map<std::string, int> m;
word_count_pro(m);
return 0;
}
关联容器概述¶
关联容器（有序的和无序的）都支持普通容器操作
关联容器不支持顺序容器的位置相关的操作，例如push_front或push_back。
- 原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。
- 关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
除了与顺序容器相同的操作之外，关联容器还支持一些顺序容器不支持的操作和类型别名
- 此外，无序容器还提供一些用来调整哈希性能的操作
关联容器的迭代器都是双向的
定义关联容器¶
当定义一个map时，必须既指明关键字类型又指明值类型；
而定义一个set时，只需指明关键字类型，因为set中没有值。
每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。
- 我们也可以将关联容器初始化为另一个同类型容器的拷贝，
- 或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。
- 在新标准下，我们也可以对关联容器进行值初始化
定义关联容器¶
map<string,size_t> word_count;//空容器
//列表初始化
set<string> exclude
={"The","But","And","Or","An","A",
"the","but","and","or","an","a"};
//姓名映射
map<string,string> authors = {{"Joyce","James"},
{"Austen","Jane"},
{"Dickens","charles"}};
初始化器必须能转换为容器中元素的类型。
- 对于set，元素类型就是关键字类型。
- 当初始化一个map时，必须提供关键字类型和值类型。
我们将每个关键字-值对包围在花括号中{key,value}
来指出它们一起构成了map中的一个元素。
- 在每个花括号中，关键字是第一个元素，值是第二个。
初始化multimap或multiset¶
一个map或set中的关键字必须是唯一的
- 对于一个给定的关键字，只能有一个元素的关键字等于它。
- 用来统计单词数量的map中，每个单词只能有一个元素
容器multimap和multiset没有此限制，它们都允许多个元素具有相同的关键字
- 一个词典中，一个特定单词则可具有多个与之关联的词义。
初始化multimap或multiset¶
//我们将创建一个名为ivec的保存int的vector，
//它包含20个元素：0到9每个整数有两个拷贝。
//我们将使用此vector初始化一个set和一个multiset
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i); // duplicate copies of each number
}
// iset holds unique elements from ivec; miset holds all 20 elements
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl; // prints 20
cout << iset.size() << endl; // prints 10
cout << miset.size() << endl; // prints 20
练习¶
解释map和set的区别。你如何选择使用哪个？
map 是键值对，而 set 只有键没有值。
当需要存储键值对的时候使用 map，而只需要键的时候使用 set。
练习¶
解释set和list的区别。你如何选择使用哪个？
set 是有序不重复集合，底层实现是红黑树，
而 list 是无序可重复集合，底层实现是链表。
练习¶
定义一个map，关键字是家庭的姓，值是一个vector，保存家中孩子（们）的名。
编写代码，实现添加新的家庭以及向已有家庭中添加新的孩子。
map<string, vector<string>> m;
for (string ln; cout << "Last name:\n", cin >> ln && ln != "@q";)
for (string cn; cout << "|-Children's names:\n", cin >> cn && cn != "@q";)
m[ln].push_back(cn);
练习¶
编写一个程序，在一个vector而不是一个set中保存不重复的单词。使用set的优点是什么？
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int main()
{
std::vector<std::string> exclude = { "aa", "bb", "cc", "dd", "ee", "ff" };
for (std::string word; std::cout << "Enter plz:\n", std::cin >> word;)
{
auto is_excluded =
std::binary_search(exclude.cbegin(), exclude.cend(), word);
auto reply = is_excluded ? "excluded" : "not excluded";
std::cout << reply << std::endl;
}
return 0;
}
set的优点是集合本身的元素就是不重复。
关键字类型的要求¶
对于有序容器——map、multimap、set以及multiset，关键字类型必须定义元素比较的方法。
- 标准库使用关键字类型的<运算符来比较两个关键字
- 在集合类型中，关键字类型就是元素类型
- 在映射类型中，关键字类型是元素的第一部分的类型
传递给排序算法的可调用对象必须满足与关联容器中关键字一样的类型要求。
有序容器的关键字类型¶
可以向一个算法提供我们自己定义的比较操作
也可以提供自己定义的操作来代替关键字上的<运算符。
所提供的操作必须在关键字类型上定义一个严格弱序（strictweak ordering）。
可以将严格弱序看作“小于等于”，虽然实际定义的操作可能是一个复杂的函数。
有序容器的关键字类型¶
无论我们怎样定义比较函数，它必须具备如下基本性质：
- 两个关键字不能同时“小于等于”对方；
- 如果k1“小于等于”k2，那么k2绝不能“小于等于”k1。
- 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。
- 如果存在两个关键字，任何一个都不“小于等于”另一个，
那么我们称这两个关键字是“等价”的。
- 如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。
有序容器的关键字类型¶
- 如果两个关键字是等价的（即，任何一个都不“小于等于”另一个），
那么容器将它们视作相等来处理。
当用作map的关键字时，只能有一个元素与这两个关键字关联，
我们可以用两者中任意一个来访问对应的值。
在实际编程中，如果一个类型定义了“行为正常”的<运算符，则它可以用作关键字类型。
使用关键字类型的比较函数¶
用来组织一个容器中元素的操作的类型也是该容器类型的一部分。
为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。
用尖括号指出要定义哪种类型的容器，
自定义的操作类型必须在尖括号中紧跟着元素类型给出。
在尖括号中出现的每个类型，就仅仅是一个类型而已。当我们创建一个容器（对象）时，
才会以构造函数参数的形式提供真正的比较操作
（其类型必须与在尖括号中指定的类型相吻合）。
使用关键字类型的比较函数¶
例如，我们不能直接定义一个Sales_data的multiset，因为Sales_data没有<运算符。
但是，可以用compareIsbn函数来定义一个multiset。
此函数在Sales_data对象的ISBN成员上定义了一个严格弱序。
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() < rhs.isbn();
}
使用关键字类型的比较函数¶
为了使用自己定义的操作，在定义multiset时我们必须提供两个类型：
关键字类型Sales_data，以及比较操作类型——应该是一种函数指针类型
可以指向compareIsbn。当定义此容器类型的对象时，需要提供想要使用的操作的指针。
在本例中，我们提供一个指向compareIsbn的指针：
// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*>
bookstore(compareIsbn);
//此处，我们使用decltype来指出自定义操作的类型。
//当用decltype来获得一个函数指针类型时，
//必须加上一个*来指出我们要使用一个给定函数类型的指针
//用compareIsbn来初始化bookstore对象，这表示当我们向bookstore添加元素时，
//通过调用compareIsbn来为这些元素排序。
//即，bookstore中的元素将按它们的ISBN成员的值排序。
//可以用compareIsbn代替&compareIsbn作为构造函数的参数，
//因为当我们使用一个函数的名字时，在需要的情况下它会自动转化为一个指针
//当然，使用&compareIsbn的效果也是一样的。
练习¶
定义一个map，将单词与一个行号的list关联，list中保存的是单词所出现的行号。
std::map<std::string, std::list<std::size_t>> m;
练习¶
可以定义一个vector<int>::iterator 到 int 的map吗？
list<int>::iterator 到 int 的map呢？对于两种情况，如果不能，解释为什么。
可以定义 vector<int>::iterator 到 int 的map，
但是不能定义 list<int>::iterator 到 int 的map。
因为map的键必须实现 < 操作，list 的迭代器不支持比较运算。
练习¶
不使用decltype 重新定义 bookstore。
typedef bool (*pf)(const Sales_data &,const Sales_data &);
std::multiset<Sales_data, pf> bookstore(compareIsbn);
pair类型¶
名为pair的标准库类型，它定义在头文件utility中。
一个pair保存两个数据成员。
类似容器，pair是一个用来生成特定类型的模板。
当创建一个pair时，我们必须提供两个类型名，pair的数据成员将具有对应的类型。
两个类型不要求一样：
pair<string, string> anon; // holds two strings
pair<string, size_t> word_count; // holds a string and an size_t
pair<string, vector<int>> line; // holds string and vector<int>
//pair的默认构造函数对数据成员进行值初始化
//因此，anon是一个包含两个空string的pair，
//line保存一个空string和一个空vector。
//word_count中的size_t成员值为0，而string成员被初始化为空。
pair类型¶
//我们也可以为每个成员提供初始化器：
pair<string, string> author{"James", "Joyce"};
//pair的数据成员是public的。两个成员分别命名为first和second
//用普通的成员访问符号来访问它们
//map的元素是pair
map<string, int> word_count = {{"a", 1}, {"b", 2}};
pair操作¶
pair<T1, T2> p; p是一个pair，两个类型分别是T1和T2的成员都进行了值初始化。
pair<T1, T2> p(v1, v2); first和second分别用v1和v2进行初始化。
pair<T1, T2>p = {v1, v2}; 等价于p(v1, v2)
make_pair(v1, v2); pair的类型从v1和v2的类型推断出来。
p.first 返回p的名为first的数据成员。
p.second 返回p的名为second的数据成员。
p1 relop p2 运算关系符按字典序定义。
p1 == p2 必须两对元素两两相等
p1 != p2 同上
创建pair对象的函数¶
函数需要返回一个pair。在新标准下，我们可以对返回值进行列表初始化
pair<string, int>
process(vector<string> &v)
{
if (!v.empty())
return {v.back(), v.back().size()}; // list initialize
else
return pair<string, int>(); // explicitly constructed return value
}
//若v不为空，我们返回一个由v中最后一个string及其大小组成的pair。
//否则，隐式构造一个空pair，并返回它。
创建pair对象的函数¶
在较早的C++版本中，不允许用花括号包围的初始化器来返回pair这种类型的对象，
必须显式构造返回值：
if (!v.empty())
return pair<string, int>(v.back(), v.back().size());
我们还可以用make_pair来生成pair对象，pair的两个类型来自于make_pair的参数：
if (!v.empty())
return make_pair(v.back(), v.back().size());
练习¶
编写程序，读入string和int的序列，
将每个string和int存入一个pair 中，pair保存在一个vector中。
#include <vector>
#include <utility>
#include <string>
#include <iostream>
int main()
{
std::vector<std::pair<std::string, int>> vec;
std::string str;
int i;
while (std::cin >> str >> i)
vec.push_back(std::pair<std::string, int>(str, i));
for (const auto &p : vec)
std::cout << p.first << ":" << p.second << std::endl;
return 0;
}
练习¶
在上一题的程序中，至少有三种创建pair的方法。
编写此程序的三个版本，分别采用不同的方法创建pair。
解释你认为哪种形式最易于编写和理解，为什么？
vec.push_back(std::make_pair(str, i));
vec.push_back({ str, i });
vec.push_back(std::pair<string, int>(str, i));
使用花括号的初始化器最易于理解和编写。
练习¶
扩展编写的孩子姓到名的map，添加一个pair的vector，保存孩子的名和生日。
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::ostream;
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::make_pair;
using std::pair;
using std::vector;
using std::map;
练习¶
class Families
{
public:
using Child = pair<string, string>;
using Children = vector<Child>;
using Data = map<string, Children>;
void add(string const& last_name,
string const& first_name, string birthday){
auto child = make_pair(first_name, birthday);
_data[last_name].push_back(child);
}
void print() const{
for (auto const& pair : _data){
cout << pair.first << ":\n";
for (auto const& child : pair.second)
cout << child.first << " " << child.second << endl;
cout << endl;
}
}
private:
Data _data;
};
练习¶
int main()
{
Families families;
auto msg = "Please enter last name, first name and birthday:\n";
for (string l, f, b; cout << msg, cin >> l >> f >> b; families.add(l, f, b));
families.print();
return 0;
}
关联容器操作¶
关联容器额外的类型别名
key_type 此容器类型的关键字类型
mapped_type 每个关键字关联的类型，只适用于map
value_type 对于map，是pair<const key_type, mapped_type>;
对于set，和key_type相同。
对于set类型，key_type和value_type是一样的；set中保存的值就是关键字。
在一个map中，元素是关键字-值对。
- 即，每个元素是一个pair对象，包含一个关键字和一个关联的值。
- 由于我们不能改变一个元素的关键字，因此这些pair的关键字部分是const的
关联容器额外的类型别名¶
set<string>::value_type v1; //string
set<string>::key_type v2; //string
map<string,int>::value_type v3; //pair<const string, int>
map<string,int>::key_type v4; //string
map<string,int>::mapped_type v5; //int
//使用作用域运算符来提取一个类型的成员——例如，map<string，int>：：key_type
//只有map类型（unordered_map、unordered_multimap、multimap和map）
//才定义了mapped_type
关联容器迭代器¶
当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。
对map而言value_type是一个pair类型，
- 其first成员保存const的关键字，second成员保存值：
map <string, size_t> word_count; // empty map
//...
// get an iterator to an element in word_count
auto map_it = word_count.begin();
// *map_it is a reference to a pair<const string, size_t> object
cout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element
map_it->first = "new key";//error 关键字是const的
++map_it->second; // ok
一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值。
set的迭代器是const的¶
虽然set类型同时定义了iterator和const_iterator类型，
但两种类型都只允许只读访问set中的元素。
与不能改变一个map元素的关键字一样，一个set中的关键字也是const的。
可以用一个set迭代器来读取元素的值，但不能修改：
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if(set_it!=iset.end()){
*set_it=41;//错误 set关键字只读
cout<<*set_it<<endl;//可读 ok
}
遍历关联容器¶
map和set类型都支持begin和end操作。
我们可以用这些函数获取迭代器，然后用迭代器来遍历容器。
auto map_it = word_count.cbegin();
while(map_it != word_count.cend()){
cout<<map_it->first <<","<<map_it->second<<endl;
++map_it;
}
//本程序的输出是按字典序排列的。
//当使用一个迭代器遍历一个map、multimap、set或multiset时，
//迭代器按关键字升序遍历元素。
关联容器和算法¶
通常不对关联容器使用泛型算法
- 关键字是const这一特性意味着不能将关联容器传递给修改或重排容器元素的算法，
- 因为这类算法需要向元素写入值，
- 而set类型中的元素是const的，map中的元素是pair，其第一个成员是const的。
对关联容器使用泛型搜索算法几乎总是个坏主意。
关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。
关联容器中的元素不能通过它们的关键字进行（快速）查找，
- 例如，关联容器定义了一个名为find的成员，它通过一个给定的关键字直接获取元素。
- 我们可以用泛型find算法来查找一个元素，但此算法会进行顺序搜索。
- 使用关联容器定义的专用的find成员会比调用泛型find快得多。
关联容器和算法¶
在实际编程中，如果我们真要对一个关联容器使用算法，
- 要么是将它当作一个源序列，要么当作一个目的位置。
- 例如，可以用泛型copy算法将元素从一个关联容器拷贝到另一个序列。
- 类似的，可以调用inserter将一个插入器绑定到一个关联容器。
通过使用inserter，我们可以将关联容器当作一个目的位置来调用另一个算法。
练习¶
对一个int到vector<int>的map，其mapped_type、key_type和 value_type分别是什么？
mapped_type : vector<int>
key_type : int
value_type : std::pair<const int,vector<int> >
练习¶
使用一个map迭代器编写一个表达式，将一个值赋予一个元素。
std::map<int, string>::iterator it = m.begin();
it->second = "hello";
练习¶
假定c是一个string的multiset，v 是一个string 的vector，解释下面的调用。
指出每个调用是否合法：
copy(v.begin(), v.end(), inserter(c, c.end()));
copy(v.begin(), v.end(), back_inserter(c));
copy(c.begin(), c.end(), inserter(v, v.end()));
copy(c.begin(), c.end(), back_inserter(v));
第二个调用不合法，因为 multiset 没有 push_back 方法。其他调用都合法。
练习¶
写出map_it 的类型，不要使用auto 或 decltype。
map<string, size_t>::const_iterator map_it = word_count.cbegin();
练习¶
定义一个变量，通过对名为 bookstore 的multiset 调用begin()来初始化这个变量。
写出变量的类型，不要使用auto 或 decltype。
using compareType = bool (*)(const Sales_data &lhs, const Sales_data &rhs);
std::multiset<Sales_data, compareType> bookstore(compareIsbn);
std::multiset<Sales_data, compareType>::iterator c_it = bookstore.begin();
添加元素¶
关联容器的insert成员向容器中添加一个元素或一个元素范围。
由于map和set（以及对应的无序类型）包含不重复的关键字，
因此插入一个已存在的元素对容器没有任何影响：
ivec = {2,4,6,8,2,4,6,8}; // ivec now has eight elements
set<int> set2; // empty set
set2.insert(ivec.cbegin(), ivec.cend()); // set2 has four elements
set2.insert({1,3,5,7,1,3,5,7}); // set2 now has eight elements
//insert有两个版本，分别接受一对迭代器，或是一个初始化器列表，
//这两个版本的行为类似对应的构造函数
//——对于一个给定的关键字，只有第一个带此关键字的元素才被插入到容器中。
向map添加元素¶
对一个map进行insert操作时，必须记住元素类型是pair。
通常，对于想要插入的数据，并没有一个现成的pair对象。
可以在insert的参数列表中创建一个pair：
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));
//在新标准下，创建一个pair最简单的方法是在参数列表中使用花括号初始化。
//也可以调用make_pair或显式构造pair。最后一个insert调用中的参数：
/map<string, size_t>::value_type(s, 1))构造一个恰当的pair类型，
//并构造该类型的一个新对象，插入到map中。
关联容器insert操作¶
c.insert(v) c.emplace(args)
v是value_type类型的对象；args用来构造一个元素。
对于map和set，只有元素的关键字不存在c中才插入或构造元素。
函数返回一个pair，包含一个迭代器，指向具有指定关键字的元素，
以及一个指示插入是否成功的bool值。
对于multimap和multiset则会插入范围中的每个元素。
c.insert(b, e) c.insert(il)
b和e是迭代器，表示一个c::value_type类型值的范围；
il是这种值的花括号列表。函数返回void。
对于 map和set，只插入关键字不在c中的元素。
c.insert(p, v) c.emplace(p, args)
类似insert(v)，但将迭代器p作为一个提示，
指出从哪里开始搜索新元素应该存储的位置。
返回一个迭代器，指向具有给定关键字的元素。
检测insert的返回值¶
insert（或emplace）返回的值依赖于容器类型和参数
对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，
告诉我们插入操作是否成功。
- pair的first成员是一个迭代器，指向具有给定关键字的元素；
- second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。
- 如果关键字已在容器中，则insert什么事情也不做，且返回值中的bool部分为false。
- 如果关键字不存在，元素被插入容器中，且bool值为true。
检测insert的返回值¶
//用insert重写单词计数程序：
// count number of times each word occurs in the input
map<string, size_t> word_count; // empty map from string to size_t
string word;
while (cin >> word)
auto ret = word_count.insert({word,1});
if(!ret.second)
++ret.first->second;
//对于每个word，我们尝试将其插入到容器中，对应的值为1
//若word已在map中，则什么都不做，特别是与word相关联的计数器的值不变。
//若word还未在map中，则此string对象被添加到map中，且其计数器的值被置为1。
//if语句检查返回值的bool部分，若为false，则表明插入操作未发生。
//在此情况下，word已存在于word_count中，因此必须递增此元素所关联的计数器。
//if语句检查返回值的bool部分，若为false，则表明插入操作未发生。
//在此情况下，word已存在于word_count中，因此必须递增此元素所关联的计数器。
展开递增语句¶
在这个版本的单词计数程序中，递增计数器的语句很难理解。
通过添加一些括号来反映出运算符的优先级，会使表达式更容易理解一些：
++((ret.first)->second);// 等价的表达式
//下面我们一步一步来解释此表达式：
//ret 保存insert返回的值，是一个pair。
//ret.first是pair的第一个成员，是一个map迭代器，指向具有给定关键字的元素。
//ret.first-> 解引用此迭代器，提取map中的元素，元素也是一个pair。
//ret.first->second map中元素的值部分。++ret.first->second 递增此值。
//如果使用的是旧版本的编译器，或者是在阅读新标准推出之前编写的代码，
//ret的声明和初始化可能复杂些：
pair<map<string,size_t>>::iterator,bool> ret =
word_count.insert(make_pair(word,1));
//应该容易看出这条语句定义了一个pair，其第二个类型为bool类型。
//第一个类型理解起来有点儿困难，
//它是一个在map<string，size_t>类型上定义的iterator类型。
向multiset或multimap添加元素¶
我们有时希望能添加具有相同关键字的多个元素。
例如，可能想建立作者到他所著书籍题目的映射。
在此情况下，每个作者可能有多个条目，因此我们应该使用multimap而不是map。
由于一个multi容器中的关键字不必唯一，在这些类型上调用insert总会插入一个元素：
// map from author to title; there can be multiple titles per author
multimap<string, string> authors;
// add data to authors
authors.insert({"Alain de Botton", "On Love"});
authors.insert({"Alain de Botton", "Status Anxiety"});
//对允许重复关键字的容器，接受单个元素的insert操作返回一个指向新元素的迭代器。
//这里无须返回一个bool值，因为insert总是向这类容器中加入一个新元素。
练习¶
重写单词计数程序，使用insert代替下标操作。
你认为哪个程序更容易编写和阅读？解释原因。
#include <iostream>
#include <map>
#include <string>
using std::string;
using std::map;
using std::cin;
using std::cout;
int main(){
map<string, size_t> counts;
for (string word; cin >> word;){
auto result = counts.insert({ word, 1 });
if (!result.second)
++result.first->second;
}
for (auto const& count : counts)
cout << count.first << " " << count.second
<< ((count.second > 1) ? " times\n" : " time\n");
return 0;
}
//使用下标操作更简洁。
练习¶
假定word_count是一个string到size_t的map，word是一个string，解释下面循环的作用：
while (cin >> word)
++word_count.insert({word, 0}).first->second;
这条语句等价于：
while (cin >> word){
auto result = word_count.insert({word, 0});
++(result.first->second);
}
若insert成功：先添加一个元素，然后返回一个 pair，pair 的 first元素是一个迭代器。
这个迭代器指向刚刚添加的元素，这个元素是pair，然后递增pair的second成员。
若insert失败：递增已有指定关键字的元素的 second成员。
练习¶
给定一个map<string, vector<int>>，对此容器的插入一个元素的insert版本，
写出其参数类型和返回类型。
std::pair<std::string, std::vector<int>> // 参数类型
std::pair<std::map<std::string, std::vector<int>>::iterator, bool> // 返回类型
练习¶
之前练习中的map 以孩子的姓为关键字，保存他们的名的vector。用multimap 重写此map。
#include <map>
#include <string>
#include <iostream>
using std::string;
using std::multimap;
using std::cin;
using std::endl;
int main()
{
multimap<string, string> families;
for (string lname, cname; cin >> cname >> lname;
families.emplace(lname, cname));
for (auto const& family : families)
std::cout << family.second << " " << family.first << endl;
return 0;
}
删除元素¶
关联容器定义了三个版本的erase，与顺序容器一样，我们可以通过传递给erase
一个迭代器或一个迭代器对来删除一个元素或者一个元素范围。
- 这两个版本的erase与对应的顺序容器的操作非常相似
- 指定的元素被删除，函数返回void。
关联容器提供一个额外的erase操作，它接受一个key_type参数。
- 此版本删除所有匹配给定关键字的元素（如果存在的话）
- 返回实际删除的元素的数量。
删除元素¶
string removal_word = "the";
// 1. by key
// erase on a key returns the number of elements removed
//对于保存不重复关键字的容器，erase的返回值总是0或1。
//若返回值为0，则表明想要删除的元素并不在容器中
if (word_count.erase(removal_word))
cout << "ok: " << removal_word << " removed\n";
else cout << "oops: " << removal_word << " not found!\n";
// 2. by removing an iterator to the element we want removed
removal_word = "The"; // strings are case sensitive
map<string,size_t>::iterator where;
where = word_count.find(removal_word); // should be gone
if (where == word_count.end())
cout << "oops: " << removal_word << " not found!\n";
else {
word_count.erase(where); // erase iterator returns void
cout << "ok: " << removal_word << " removed!\n";
}
//对允许重复关键字的容器，删除元素的数量可能大于1：
auto cnt = authors.erase("Barth,John");
从关联容器中删除元素¶
c.erase(k) 从c中删除每个关键字为k的元素。
返回一个size_type值，指出删除的元素的数量。
c.erase(p) 从c中删除迭代器p指定的元素。p必须指向c中一个真实元素，
不能等于c.end()。返回一个指向p之后元素的迭代器，
若p指向c中的尾元素，则返回c.end()
c.erase(b, e) 删除迭代器对b和e所表示范围中的元素。返回e。
map的下标操作¶
map和unordered_map容器提供了下标运算符和一个对应的at函数
set类型不支持下标，因为set中没有与关键字相关联的“值”。
元素本身就是关键字，因此“获取与一个关键字相关联的值”的操作就没有意义了。
我们不能对一个multimap或一个unordered_multimap进行下标操作，
因为这些容器中可能有多个值与一个关键字相关联。
map的下标操作¶
类似我们用过的其他下标运算符，map下标运算符接受一个索引（即，一个关键字），
获取与此关键字相关联的值。
但是，与其他下标运算符不同的是，如果关键字并不在map中，
会为它创建一个元素并插入到map中，关联值将进行值初始化
map的下标操作¶
map<string,size_t> word_count ;
word_count["Anna"]=1;
//将会执行如下操作：·
//在word_count中搜索关键字为Anna的元素，未找到。·
//将一个新的关键字-值对插入到word_count中。
//关键字是一个const string，保存Anna。值进行值初始化，在本例中意味着值为0。
// 提取出新插入的元素，并将值1赋予它。
由于下标运算符可能插入一个新元素，我们只可以对非const的map使用下标操作。
map和unordered_map的下标操作¶
对一个map使用下标操作，其行为与数组或vector上的下标操作很不相同：
使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到map中。
c[k] 返回关键字为k的元素；
如果k不在c中，添加一个关键字为k的元素，对其值初始化。
c.at(k) 访问关键字为k的元素，带参数检查；
若k不存在在c中，抛出一个out_of_range异常。
使用下标操作的返回值¶
map的下标运算符与我们用过的其他下标运算符的另一个不同之处是其返回类型。
通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。
但对map则不然：
- 当对一个map进行下标操作时，会获得一个mapped_type对象；
- 但当解引用一个map迭代器时，会得到一个value_type对象。
与其他下标运算符相同的是，map的下标运算符返回一个左值。
由于返回的是一个左值，所以我们既可以读也可以写元素
使用下标操作的返回值¶
cout << word_count["Anna"] << endl;
++word_count["Anna"];
cout << word_count["Anna"] << endl;
//与vector与string不同，
//map的下标运算符返回的类型与解引用map迭代器得到的类型不同。
//如果关键字还未在map中，下标运算符会添加一个新元素，
//这一特性允许我们编写出异常简洁的程序。
//另一方面，有时只是想知道一个元素是否已在map中，但在不存在时并不想添加元素。
//在这种情况下，就不能使用下标运算符。
练习¶
下面的程序完成什么功能？
map<int, int> m;
m[0] = 1;
添加一个元素到map中，如果该键存在，则重新赋值。
练习¶
对比下面的程序与上一题程序
vector<int> v;
v[0] = 1;
未定义行为，vector 的下标越界访问。
练习¶
可以用什么类型来对一个map进行下标操作？
下标运算符返回的类型是什么？
请给出一个具体例子——即，定义一个map，
然后写出一个可以用来对map进行下标操作的类型以及下标运算符将会返会的类型。
std::map<int, std::string> m = { { 1,"ss" },{ 2,"sz" } };
using KeyType = std::map<int, std::string>::key_type;
using ReturnType = std::map<int, std::string>::mapped_type;
访问元素¶
关联容器提供多种查找一个指定元素的方法,应该使用哪个操作依赖于我们要解决什么问题。
如果我们所关心的是一个特定元素是否已在容器中，可能find是最佳选择。
对于不允许重复关键字的容器，可能使用find还是count没什么区别。
但对于允许重复关键字的容器，count还会做更多的工作：
- 如果元素在容器中，它还会统计有多少个元素有相同的关键字。
- 如果不需要计数，最好使用find：
set<int> iset = {1,2,3,4,5,6,7,8,9};
// returns an iterator that refers to the element with key == 1
iset.find(1);
iset.find(11); // returns the iterator == iset.end()
iset.count(1); // returns 1
iset.count(11); // returns 0
在一个关联容器中查找元素¶
c.find(k) 返回一个迭代器，指向第一个关键字为k的元素，
若k不在容器中，则返回尾后迭代器
c.count(k) 返回关键字等于k的元素的数量。
对于不允许重复关键字的容器，返回值永远是0或1。
c.lower_bound(k) 返回一个迭代器，指向第一个关键字不小于k的元素。
c.upper_bound(k) 返回一个迭代器，指向第一个关键字大于k的元素。
c.equal_range(k) 返回一个迭代器pair，表示关键字等于k的元素的范围。
若k不存在，pair的两个成员均等于c.end()。
- lower_bound和upper_bound不适用于无序容器。
- 下标和at操作只适用于非const的map和unordered_map。
对map使用find代替下标操作¶
对map和unordered_map类型，下标运算符提供了最简单的提取元素的方法。
但是，如我们所见，使用下标操作有一个严重的副作用：
- 如果关键字还未在map中，下标操作会插入一个具有给定关键字的元素。
- 这种行为是否正确完全依赖于我们的预期是什么。
- 例如，单词计数程序依赖于这样一个特性：使用一个不存在的关键字作为下标，
会插入一个新元素，其关键字为给定关键字，其值为0。
也就是说，下标操作的行为符合我们的预期。
但有时，我们只是想知道一个给定关键字是否在map中，而不想改变map。
这样就不能使用下标运算符来检查一个元素是否存在，
- 因为如果关键字不存在的话，下标运算符会插入一个新元素。
- 在这种情况下，应该使用find：
if(word_count.find("foobar")==word_count.end())
cout<<"foobar is not in the map"<<endl;
在multimap或multiset中查找元素¶
在一个不允许重复关键字的关联容器中查找一个元素是一件很简单的事情
- 元素要么在容器中，要么不在。
但对于允许重复关键字的容器来说，过程就更为复杂：
- 在容器中可能有很多元素具有给定的关键字。
- 如果一个multimap或multiset中有多个元素具有给定关键字，
则这些元素在容器中会相邻存储。
例如，给定一个从作者到著作题目的映射，我们可能想打印一个特定作者的所有著作。
可以用三种不同方法来解决这个问题。最直观的方法是使用find和count
在multimap或multiset中查找元素¶
string search_item("Alain de Botton"); // author we'll look for
auto entries = authors.count(search_item); // number of elements
auto iter = authors.find(search_item); // first entry for this author
// loop through the number of entries there are for this author
while(entries) {
cout << iter->second << endl; // print each title
++iter; // advance to the next title
--entries; // keep track of how many we've printed
}
//首先调用count确定此作者共有多少本著作，并调用find获得一个迭代器，
//指向第一个关键字为此作者的元素。for循环的迭代次数依赖于count的返回值。
//特别是，如果count返回0，则循环一次也不执行。
当我们遍历一个multimap或multiset时，保证可以得到序列中所有具有给定关键字的元素。
一种不同的，面向迭代器的解决方法¶
还可以用lower_bound和upper_bound,都接受一个关键字，返回一个迭代器。
如果关键字在容器中，
- lower_bound返回的迭代器将指向第一个具有给定关键字的元素，
- 而upper_bound返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。
如果元素不在multimap中，
- 则lower_bound和upper_bound会返回相等的迭代器
- 指向一个不影响排序的关键字插入位置。
一种不同的，面向迭代器的解决方法¶
用相同的关键字调用lower_bound和upper_bound会得到一个迭代器范围
- 表示所有具有该关键字的元素的范围。
- 当然，这两个操作返回的迭代器可能是容器的尾后迭代器。
- 如果我们查找的元素具有容器中最大的关键字，
则此关键字的upper_bound返回尾后迭代器。
- 如果关键字不存在，且大于容器中任何关键字，
则lower_bound返回的也是尾后迭代器。
lower_bound返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向。
如果关键字不在容器中，则lower_bound会返回关键字的第一个安全插入点
— 不影响容器中元素顺序的插入位置。
使用这两个操作，我们可以重写前面的程序：¶
// definitions of authors and search_item as above
// beg and end denote the range of elements for this author
for (auto beg = authors.lower_bound(search_item),
end = authors.upper_bound(search_item);
beg != end; ++beg)
cout << beg->second << endl; // print each title
//此程序与使用count和find的版本完成相同的工作，但更直接。
//对lower_bound的调用将beg定位到第一个与search_item匹配的元素（如果存在的话）
//如果容器中没有这样的元素，
//beg将指向第一个关键字大于search_item的元素，有可能是尾后迭代器。
//upper_bound调用将end指向最后一个匹配指定关键字的元素之后的元素
这两个操作并不报告关键字是否存在，重要的是它们的返回值可作为一个迭代器范围
如果没有元素与给定关键字匹配，则lower_bound和upper_bound会返回相等的迭代器
— 都指向给定关键字的插入点，能保持容器中元素顺序的插入位置。
如果lower_bound和upper_bound返回相同的迭代器，则给定关键字不在容器中。
equal_range函数¶
接受一个关键字，返回一个迭代器pair。
若关键字存在，
- 则第一个迭代器指向第一个与关键字匹配的元素，
- 第二个迭代器指向最后一个匹配元素之后的位置。
若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。
// definitions of authors and search_item as above
// pos holds iterators that denote the range of elements for this key
for (auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl; // print each title
//pos.first等价于beg，pos.second等价于end。
练习¶
对于什么问题你会使用count来解决？什么时候你又会选择find呢？
对于允许重复关键字的容器，应该用 count ;
对于不允许重复关键字的容器，应该用 find 。
练习¶
对一个string到int的vector的map，
定义并初始化一个变量来保存在其上调用find所返回的结果。
map<string, vector<int>> m;
map<string, vector<int>>::iterator it = m.find("key");
练习¶
如果给定的关键字不在容器中，
upper_bound、lower_bound 和 equal_range 分别会返回什么？
如果给定的关键字不在容器中，
则 lower_bound和 upper_bound 会返回相等的迭代器，
指向一个不影响排序的关键字插入位置。
而equal_range 会返回一个 pair，pair 中的两个迭代器都指向关键字可以插入的位置。
练习¶
对于本节最后一个程序中的输出表达式，解释运算对象pos.first->second的含义。
pos 是一个pair，pos.first 是一个迭代器，指向匹配关键字的元素，
该元素是一个 pair，访问该元素的第二个成员。
练习¶
编写程序，定义一个作者及其作品的multimap。
使用find在multimap中查找一个元素并用erase删除它。
确保你的程序在元素不在map 中时也能正常运行。
#include <map>
#include <string>
#include <iostream>
using std::string;
int main(){
std::multimap<string, string> authors{
{ "William Shakespeare", "Romeo and Juliet" },
{ "William Shakespeare", "Much Ado About Nothing" },
{ "Mao Zedong", "Selected Works of Mao Zedong" } };
string author = "William Shakespeare";
string work = "Romeo and Juliet";
auto found = authors.find(author);
auto count = authors.count(author);
练习¶
while (count){
if (found->second == work){
authors.erase(found);
break;
}
++found;
--count;
}
for (const auto &author : authors)
std::cout << author.first << " " << author.second << std::endl;
return 0;
}
练习¶
使用上一题定义的multimap编写一个程序，按字典序打印作者列表和他们的作品。
#include <map>
#include <set>
#include <string>
#include <iostream>
using std::string;
int main(){
std::multimap<string, string> authors{
{ "William Shakespeare", "Romeo and Juliet" },
{ "William Shakespeare", "Much Ado About Nothing" },
{ "Mao Zedong", "Selected Works of Mao Zedong" } };
std::map<string, std::multiset<string>> order_authors;
for (const auto &author : authors)
order_authors[author.first].insert(author.second);
for (const auto &author : order_authors){
std::cout << author.first << ": ";
for (const auto &work : author.second)
std::cout << work << " ";
std::cout << std::endl;
}
return 0;
}
一个单词转换的map¶
我们将以一个程序结束本节的内容，它将展示map的创建、搜索以及遍历。
这个程序的功能是这样的：给定一个string，将它转换为另一个string。
程序的输入是两个文件。第一个文件保存的是一些规则，用来转换第二个文件中的文本。
每条规则由两部分组成：一个可能出现在输入文件中的单词和一个用来替换它的短语。
表达的含义是，每当第一个单词出现在输入中时，我们就将它替换为对应的短语。
第二个输入文件包含要转换的文本。
如果单词转换文件的内容如下所示：
brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks!
l8r later
我们希望转换的文本为
where r u
y dont u send me a pic
k thk l8r
则程序应该生成这样的输出：
where are you
why dont you send me a picture
okay? thanks! later
单词转换程序¶
//函数word_transform管理整个过程。它接受两个ifstream参数：第一个参数应绑定到
//单词转换文件，第二个参数应绑定到我们要转换的文本文件。
//函数buildMap会读取转换规则文件，并创建一个map，用于保存每个单词到其转换内容
//的映射。函数transform接受一个string，如果存在转换规则，返回转换后的内容。
// first argument is the transformations file;
// second is file to transform
void word_transform(ifstream &map_file, ifstream &input)
{
auto trans_map = buildMap(map_file); // store the transformations
// for debugging purposes print the map after its built
cout << "Here is our transformation map: \n\n";
for (auto entry : trans_map)
cout << "key: " << entry.first
<< "\tvalue: " << entry.second << endl;
cout << "\n\n";
单词转换程序¶
// do the transformation of the given text
string text; // hold each line from the input
while (getline(input, text)) { // read a line of input
istringstream stream(text); // read each word
string word;
bool firstword = true; // controls whether a space is printed
while (stream >> word) {
if (firstword)
firstword = false;
else
cout << " "; // print a space between words
// transform returns its first argument or its transformation
cout << transform(word, trans_map); // print the output
}
cout << endl; // done with this line of input
}
}
建立转换映射¶
//函数buildMap读入给定文件，建立起转换映射。
map<string, string> buildMap(ifstream &map_file)
{
map<string, string> trans_map; // holds the transformations
string key; // a word to transform
string value; // phrase to use instead
// read the first word into key and the rest of the line into value
while (map_file >> key && getline(map_file, value))
if (value.size() > 1) // check that there is a transformation
trans_map[key] = value.substr(1); // skip leading space
else
throw runtime_error("no rule for " + key);
return trans_map;
}
生成转换文本¶
//函数transform进行实际的转换工作。
const string &
transform(const string &s, const map<string, string> &m)
{
// the actual map work; this part is the heart of the program
auto map_it = m.find(s);
// if this word is in the transformation map
if (map_it != m.cend())
return map_it->second; // use the replacement word
else
return s; // otherwise return the original unchanged
}
练习¶
实现你自己版本的单词转换程序。
#include <map>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
using std::string; using std::ifstream;
std::map<string, string> buildMap(ifstream &map_file){
std::map<string, string> trans_map;
for (string key, value; map_file >> key && getline(map_file, value); )
if (value.size() > 1) trans_map[key] =
value.substr(1).substr(0, value.find_last_not_of(' '));
return trans_map;
}
const string & transform(const string &s, const std::map<string, string> &m)
{
auto map_it = m.find(s);
return map_it == m.cend() ? s : map_it->second;
}
练习¶
void word_transform(ifstream &map, ifstream &input){
auto trans_map = buildMap(map);
for (string text; getline(input, text); ) {
std::istringstream iss(text);
for (string word; iss >> word; )
std::cout << transform(word, trans_map) << " ";
std::cout << std::endl;
}
}
int main(){
ifstream ifs_map("in.txt"), ifs_content("in2.txt");
if (ifs_map && ifs_content) word_transform(ifs_map, ifs_content);
else std::cerr << "can't find the documents." << std::endl;
return 0;
}
练习¶
如果你将transform 函数中的find替换为下标运算符，会发生什么情况？
如果使用下标运算符，当关键字未在容器中时，会往容器中添加一个新元素。
练习¶
在buildMap中，如果进行如下改写，会有什么效果？
trans_map[key] = value.substr(1);
//改为
trans_map.insert({key, value.substr(1)});
当一个转换规则的关键字多次出现的时候，使用下标运算符会保留最后一次添加的规则，
而用insert则保留第一次添加的规则。
练习¶
我们的程序并没检查输入文件的合法性。
特别是，它假定转换规则文件中的规则都是有意义的。
如果文件中的某一行包含一个关键字、一个空格，然后就结束了，会发生什么？
预测程序的行为并进行验证，再与你的程序进行比较。
如果关键字没有对应的规则，那么程序会抛出一个 runtime_error。
无序容器¶
无序关联容器（unordered associative container）
- 不是使用比较运算符来组织元素
- 而是使用一个哈希函数（hash function）和关键字类型的==运算符。
- 在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。
- 在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。
虽然理论上哈希技术能获得更好的平均性能，
但在实际中想要达到很好的效果还需要进行一些性能测试和调优工作。
使用无序容器通常更为简单（通常也会有更好的性能）。
如果关键字类型固有就是无序的，
或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。
使用无序容器¶
除了哈希管理操作之外，无序容器还提供了与有序容器相同的操作（find、insert等）
- 曾用于map和set的操作也能用于unordered_map和unordered_set。
- 类似的，无序容器也有允许重复关键字的版本。
通常可以用一个无序容器替换对应的有序容器，反之亦然。
由于元素未按顺序存储，
- 一个使用无序容器的程序的输出（通常）会与使用有序容器的版本不同。
//用unordered_map重写最初的单词计数程序
// count occurrences, but the words won't be in alphabetical order
unordered_map<string, size_t> word_count;
string word;
while (cin >> word)
++word_count[word]; // fetch and increment the counter for word
for (const auto &w : word_count) // for each element in the map
// print the results
cout << w.first << " occurs " << w.second
<< ((w.second > 1) ? " times" : " time") << endl;
//对于每个单词，我们将得到相同的计数结果。但单词不太可能按字典序输出。
管理桶¶
无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。
- 无序容器使用一个哈希函数将元素映射到桶。
- 为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。
容器将具有一个特定哈希值的所有元素都保存在相同的桶中。
如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。
因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。
管理桶¶
对于相同的参数，哈希函数必须总是产生相同的结果。
理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。
但是，将不同关键字的元素映射到相同的桶也是允许的。
当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。
计算一个元素的哈希值和在桶中搜索通常都是很快的操作。
但是，如果一个桶中保存了很多元素，那么查找一个特定元素就需要大量比较操作。
无序容器管理操作¶
这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。
桶接口
c.bucket_count() 正在使用的桶的数目
c.max_bucket_count() 容器能容纳的最多的桶的数目
c.bucket_size(n) 第n个桶中有多少个元素
c.bucket(k) 关键字为k的元素在哪个桶中
桶迭代
local_iterator 可以用来访问桶中元素的迭代器类型
const_local_iterator 桶迭代器的const版本
c.begin(n)，c.end(n) 桶n的首元素迭代器
c.cbegin(n)，c.cend(n) 与前两个函数类似，但返回const_local_iterator。
哈希策略
c.load_factor() 每个桶的平均元素数量，返回float值。
c.max_load_factor() c试图维护的平均比桶大小，返回float值。
c会在需要时添加新的桶，以使得load_factor<=max_load_factor
c.rehash(n) 重组存储，使得bucket_count>=n，
且bucket_count>size/max_load_factor
c.reverse(n) 重组存储，使得c可以保存n个元素且不必rehash。
无序容器对关键字类型的要求¶
默认情况下，无序容器使用关键字类型的==运算符来比较元素，
它们还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。
标准库为内置类型（包括指针）提供了hash模板。
还为一些标准库类型，包括string和智能指针类型定义了hash。
我们可以直接定义
- 关键字是内置类型（包括指针类型）、string还是智能指针类型的无序容器。
无序容器对关键字类型的要求¶
不能直接定义关键字类型为自定义类类型的无序容器。
与容器不同，不能直接使用哈希模板，而必须提供我们自己的hash模板版本
不使用默认的hash，而是使用另一种方法，
类似于为有序容器重载关键字类型的默认比较操作
为了能将Sale_data用作关键字，
- 需要提供函数来替代==运算符和哈希值计算函数。
我们从定义这些重载函数开始：
// how to override default hash and equality operator on key_type
size_t hasher(const Sales_data &sd)
{
return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() == rhs.isbn();
}
使用这些函数来定义一个unordered_multiset
using SD_multiset = unordered_multiset<Sales_data,
decltype(hasher)*, decltype(eqOp)*>;
// 参数是桶大小 哈希函数指针 相等判断运算符指针
SD_multiset bookstore(42, hasher, eqOp);
//为了简化bookstore的定义，首先为unordered_multiset定义了一个类型别名
//此集合的哈希和相等性判断操作与hasher和eqOp函数有着相同的类型。
//通过使用这种类型，在定义bookstore时可以将我们希望它使用的函数的指针传递给它。
如果我们的类定义了==运算符，则可以只重载哈希函数：
struct Foo { string s; };
bool operator==(const Foo& l, const Foo&r) { return l.s == r.s; }
size_t FooHash(const Foo& f) { return hash<string>()(f.s); }
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);
练习¶
一个无序容器与其有序版本相比有何优势？有序版本有何优势？
无序容器拥有更好的性能，有序容器使得元素始终有序。
练习¶
用 unordered_map 重写单词计数程序和单词转换程序。
#include <unordered_map>
#include <set>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
using std::string;
void wordCounting(){
std::unordered_map<string, size_t> word_count;
for (string word; std::cin >> word; ++word_count[word]);
for (const auto &w : word_count)
std::cout << w.first << " occurs " << w.second
<< (w.second > 1 ? "times" : "time") << std::endl;
}
练习¶
void wordTransformation(){
std::ifstream ifs_map("in.txt"), ifs_content("in2.txt");
if (!ifs_map || !ifs_content) {
std::cerr << "can't find the documents." << std::endl;
return;
}
std::unordered_map<string, string> trans_map;
for (string key, value; ifs_map >> key && getline(ifs_map, value); )
if (value.size() > 1) trans_map[key] =
value.substr(1).substr(0, value.find_last_not_of(' '));
for (string text, word; getline(ifs_content, text);
std::cout << std::endl)
for (std::istringstream iss(text); iss >> word; ) {
auto map_it = trans_map.find(word);
std::cout << (map_it == trans_map.cend() ?
word : map_it->second) << " ";
}
}
int main(){
wordCounting();
wordTransformation();
return 0;
}
小结¶
关联容器支持通过关键字高效查找和提取元素。
对关键字的使用将关联容器和顺序容器区分开来，顺序容器中是通过位置访问元素的。
标准库定义了8个关联容器，每个容器·
- 是一个map或是一个set。map保存关键字-值对；set只保存关键字。·
- 要求关键字唯一或不要求。·
- 保持关键字有序或不保证有序。
有序容器使用比较函数来比较关键字，从而将元素按顺序存储。
默认情况下，比较操作是采用关键字类型的<运算符。
无序容器使用关键字类型的==运算符和一个hash<key_type>类型的对象来组织元素。
小结¶
允许重复关键字的容器的名字中都包含multi；
而使用哈希技术的容器的名字都以unordered开头。
- 例如，set是一个有序集合，其中每个关键字只可以出现一次；
- unordered_multiset则是一个无序的关键字集合，其中关键字可以出现多次。
关联容器和顺序容器有很多共同的元素。但是，关联容器定义了一些新操作，
并对一些和顺序容器和关联容器都支持的操作重新定义了含义或返回类型。
操作的不同反映出关联容器使用关键字的特点。
有序容器的迭代器通过关键字有序访问容器中的元素。
无论在有序容器中还是在无序容器中，具有相同关键字的元素都是相邻存储的。
实践课¶
- 从课程主页 cpp.njuer.org 打开 《面向对象编程基础》实验课 cloud shell界面 https://developer.aliyun.com/adc/scenario/476f2ff6afad4221bac08e33cf6984fc
- 使用g++编译代码
- 编辑一个 readme.md 文档,键入本次实验心得.
- 使用git进行版本控制 可使用之前的gitee代码仓库
- 云服务器（elastic compute service,简称ecs） - aliyun linux 2是阿里云推出的 linux 发行版 - vim是从vi发展出来的一个文本编辑器. - g++ 是c++编译器
习题1
用 unordered_map 重写单词计数程序,
同时忽略大小写和标点。
例如，"example."、"example,"和"example"应该递增相同的计数器。
#include <iostream>
习题2
用 unordered_map 重写单词转换程序。
习题3
编写程序，定义一个作者及其作品的multimap。
使用find在multimap中查找一个元素并用erase删除它。
按字典序打印作者列表和他们的作品。
编辑c++代码和markdown文档,使用git进行版本控制
yum install -y git gcc-c++
使用git工具进行版本控制
git clone你之前的网络git仓库test(或其它名字)
cd test 进入文件夹test
(clone的仓库,可移动旧文件到目录weekN: mkdir -p weekN ; mv 文件名 weekN;)
vim test1.cpp
g++ ./test1.cpp 编译
./a.out 执行程序
vim test2.cpp
g++ ./test2.cpp 编译
./a.out 执行程序
vim test3.cpp
g++ ./test3.cpp 编译
./a.out 执行程序
git add . 加入当前文件夹下所有文件到暂存区
git config --global user.email "you@example.com"
git config --global user.name "Your Name"
vim readme.md 键入新内容（实验感想),按ESC 再按：wq退出
git add .
git commit –m "weekN" 表示提交到本地,备注weekN
git push 到你的git仓库
git log --oneline --graph 可看git记录
键入命令并截图或复制文字,并提交到群作业.
cat test* readme.md
提交¶
- 截图或复制文字,提交到群作业.
- 填写阿里云平台（本实验）的网页实验报告栏,发布保存.本次报告不需要分享提交
- 填写问卷调查 https://rnk6jc.aliwork.com/o/cppinfo
关于使用tmux¶
sudo yum install -y tmux
cd ~ && wget https://cpp.njuer.org/tmux && mv tmux .tmux.conf
tmux 进入会话 .
前缀按键prefix= ctrl+a,
prefix+c创建新面板,
prefix+"分屏,
prefix+k选上面,prefix+j选下面,
prefix+1选择第一,prefix+n选择第n,
prefix+d脱离会话
tmux attach-session -t 0 回到会话0
vim 共分为三种模式¶
- 命令模式
- 刚启动 vim,便进入了命令模式.其它模式下按ESC,可切换回命令模式
- i 切换到输入模式,以输入字符.
- x 删除当前光标所在处的字符.
- : 切换到底线命令模式,可输入命令.
- 输入模式
- 命令模式下按下i就进入了输入模式.
- ESC,退出输入模式,切换到命令模式
- 底线命令模式
- 命令模式下按下:（英文冒号）就进入了底线命令模式.
- wq 保存退出
vim 常用按键说明¶
除了 i, Esc, :wq 之外,其实 vim 还有非常多的按键可以使用.命令模式下：
- 光标移动
- j下 k上 h左 l右
- w前进一个词 b后退一个词
- Ctrl+d 向下半屏 ctrl+u 向上半屏
- G 移动到最后一行 gg 第一行 ngg 第n行
- 复制粘贴
- dd 删一行 ndd 删n行
- yy 复制一行 nyy复制n行
- p将复制的数据粘贴在下一行 P粘贴到上一行
- u恢复到前一个动作 ctrl+r重做上一个动作
- 搜索替换
- /word 向下找word ？word 向上找
- n重复搜索 N反向搜索
- :1,$s/word1/word2/g从第一行到最后一行寻找 word1 字符串,并将该字符串
取代为 word2
vim 常用按键说明¶
底线命令模式下：
- :set nu 显示行号
- :set nonu 取消行号
- :set paste 粘贴代码不乱序
【注：把caps lock按键映射为ctrl,能提高编辑效率.】
Markdown 文档语法¶
# 一级标题
## 二级标题
*斜体* **粗体**
- 列表项
- 子列表项
> 引用
[超链接](http://asdf.com)
|表格标题1|表格标题2|
|-|-|
|内容1|内容2|