【c++ primer读书笔记】【第11章】关联容器

【c++ primer读书笔记】【第11章】关联容器

1、关联容器类型

运用map和set的例子，统计单词程序：

#include<iostream>
#include<map>
#include<set>
#include<sstream>
#include<string>
using namespace std;int main(){map<string, size_t> word_count;set<string> exclude{ "an", "the" };string str = "although before an and aaa although the aaa";stringstream ss(str);string word;while (ss >> word){if (exclude.find(word) == d()) //只统计不在exclude中的单词++word_count[word];}for (const auto& w : word_count)cout << w.first << " occurs " << w.second << ((w.second>1) ? " times" : " time") << endl;system("pause");return 0;
}

2、定义关联容器

定义一个map时，必须指明关键字类型和值类型，定义一个set时，只需指明关键字类型。

初始化关联容器：

map<string,size_t> wor(word_count); //空容器
map<string,string> authors={{"joyce","jamese"},{"Austen","jane"}};//列表初始化,VS2013支持
map<string,string> au(authors);//用容器authors初始化au

3、对于有序容器map,multimap,set及multiset,关键字类型必须定义元素的比较方法。默认情况下，标准库使用关键字类型<运算符来比较两个关键字。

4、pair类型

一个pair保存两个数据成员，一个是first,一个是second，pair的数据成员是public的。

pair的默认构造函数对数据成员进行值初始化。

5、关联容器额外的类型别名

6、set的迭代器是const的。虽然set类型同时定义了iterator和const_iterator，但两种类型都是只允许只读访问set中的元素。

set<int> iset={1,2,3,4,5};
set<int>::iterator it=iset.begin();
if(it!&#d()){*it=42;   //错误:set中的关键字是只读的cout<<*it<<endl;  //正确
}

7、添加元素、删除元素

#include<iostream>
#include<map>
#include<string>
#include<utility>
using namespace std;int main(){map<string, size_t> word_count;map<string, size_t> wc = { { "ff", 2 }, { "tt", 1 } }; //在VS2013中支持word_count.insert({ "aa", 1 });  //c.insert(v),在VS2013中支持word_count.insert(make_pair("cc", 1));  //c.insert(v)word_count.insert(pair<string, size_t>("bb", 1));  //c.insert(v)word_count.insert(map<string, size_t>::value_type("aa", 1));  //c.insert(v)word_count.insert(wc.begin(), wc.end());//c.insert(b,e),b和e是迭代器，表示一个c::value_type类型值的范围，返回place("qq", 5);//c.emplace(args),对于map和set，只有当元素关键字不在c中才插入。//返回一个pair，包含一个迭代器，指向关键字的元素，以及一个指示插入是否成功的bool值  for (const auto& w : word_count)cout << w.first << " " << w.second << endl;cout << "------------------------------" << endl;ase("bb");  //c.erase(k),从c中删除每个关键字为k的元素，返回一个size_type类型值，表示删除元素的数量ase(word_count.begin());//c.erase(p),从c中删除迭代器p指定的元素，返回p之后元素的迭代器for (const auto& w : word_count)cout << w.first << " " << w.second << endl;cout << "------------------------------" << endl;ase(++word_count.begin(), --d());//c.erase(b,e),删除迭代器对b和e所表示范围中的元素，返回efor (const auto& w : word_count)cout << w.first << " " << w.second << endl;system("pause");return 0;
}

8、map的下标操作

map和unordered_map容器提供了下标运算符和一个对应的at函数。map和其他下标运算符不同的是，如果关键字不在容器中，它会创建一个元素并插入到map中去，关联值将进行初始化。

map<string,size_t> word_count;
word_count["aa"]=1; //插入关键字为"aa"的元素，关联值进行值初始化，然后将1赋予它
cout<<word_count["aa"]<<endl; //将"aa"作为下标提取元素，输出1
++word_count["aa"]; //标提取元素，将其加1
cout<<word_count["aa"]<<endl;//将"aa"作为下标提取元素，输出2

9、访问元素

#include<iostream>
#include<set>
#include<string>
#include<utility>
using namespace std;int main(){int ia[]={1,2,3,4,5,6,7,8,9};set<int> iset(begin(ia),end(ia));iset.find(1); //返回一个迭代器，指向key==1的元素iset.find(11); //返回一个迭代器，其值等于d()unt(1); //c.count(k),返回关键字等于k的元素数量，返回unt(11); //c.count(k),返回关键字等于k的元素数量，返回0auto low=iset.lower_bound(2);//c.lower_bound(k),返回一个迭代器，指向第一个关键字不小于k的元素auto upper=iset.upper_bound(5);//c.lower_bound(k),返回一个迭代器，指向第一个关键字大于k的元素while(low!=upper)cout<<*low++<<" ";auto range=iset.equal_range(3); //c.equal_range(k),返回一个迭代器pair，表示关键字等于k的元素的范围cout<<endl;system("pause");                       return 0;                              
}

lower_bound和upper_bound不适用于无序容器。
10、c++11定义了4个无序关联容器，这些容器不是使用比较运算符来组织元素的，而是使用一个哈希函数和关键字类型的==运算符。

使用无序容器 unordered_map统计单词

#include<iostream>
#include<unordered_map>
#include<set>
#include<sstream>
#include<string>
using namespace std;int main(){unordered_map<string, size_t> word_count; //统计单词出现次数，但单词不会按字典序排列set<string> exclude{ "an", "the" };string str = "although before an and aaa although the aaa";stringstream ss(str);string word;while (ss >> word){if (exclude.find(word) == d()) //只统计不在exclude中的单词++word_count[word];}for (const auto& w : word_count)cout << w.first << " occurs " << w.second << ((w.second>1) ? " times" : " time") << endl;system("pause");return 0;
}

无序容器在组织形式上为一组桶，每个桶保存零个或多个元素。使用一个哈希函数将元素映射到桶。所有相同关键字的元素会在同一个桶中。无序容器的质量依赖于哈希函数的质量和桶的大小和数量。

#include<iostream>
#include<unordered_set>
using namespace std;int main(){unordered_multiset<int> iset{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 4, 5, 6, 7 };cout << iset.bucket_count() << endl;   //正在使用的桶的数目cout << iset.max_bucket_count() << endl;//容纳的最多的桶的数目cout << iset.bucket_size(1) << endl; //第1个桶中有多少个元素cout << iset.bucket(4) << endl;  //关键字为4的元素在哪个桶中cout << iset.load_factor() << endl; //每个桶的平均元素数量，返回float值cout << iset.max_load_factor() << endl;//维护平均桶大小，返回float值。需要时添加新的桶使load_factor <= max_load_factor  hash(20); //重组存储，使得bucket_count>=20且bucket_count>size/max_load_factor()serve(20);//重组存储，使得iset可以保存20个元素且不必rehashsystem("pause");return 0;
}

12、无需容器对关键字类型的要求

无序容器使用关键字==来比较元素，它们还使用了一个hash<key_type>类型的对象来生成每个元素的hash值。

我们不能定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用hash模板，而是必须提供我们自己的hash模板。

为了将自己的类当作关键字，我们要自己提供==运算符和hash值计算函数。

转载于:.html