c++prime笔记----关联容器

• 关联容器中的元素是按关键字来保存和访问的
• 共8个关联容器：set关键字即值，map关联数组，multi允许关键字重复，unordered哈希函数组织存储，否则是红黑树组织储存

map  set  //<map>  <set>
multimap  multiset  //<map> <set>
unordered_map  unordered_set  unordered_multimap  unordered_multiset  //<unorderedmap>  <unorderedset>

• 定义关联容器

map<int, int> words;  //空容器
set<string> set = {"the", "are"};  
map<string, string> authors = {{"l", "sy"}, {"s", "ly"}};

• 关键字类型的要求：必须定义元素比较方法

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs){
        return lhs.isbn() < rhs.isbn();
}

multiset<Sales_data, decltype(compareIsbn)*>  bookstore(compareIsbn);

• pair操作

pair<T1, T2> p, p(v1, v2), p = {v1, v2};
make_pair(v1, v2);   {1, 2}  ;   pair<int, int>(1, 2)   //返回一个pair
p.first   p.second

• 成员类型

map<int, int>::key_type k1;
map<int, int>::mapped_type    ,  ::value_type

• set的迭代器是const的，map的迭代器解引用是pair，不能改变pair的first成员（关键字成员）
• words.cbegin()->words.cend()：输出是按照升序进行的。
• 比较函数是严格弱序。a<b，返回true。

不能a<b，且b<a
a<b, b<c, 则a<c
!a<b,且!b<a，则a == b

• 添加元素

vector<int> ivec = {1, 2, 3};
set<int> set2;
set2.insert(ivec.begin(), ivec.end());
set2.insert({1, 2, 3, 4});

//map
word.insert({word, 1});
word.insert(make_pair(word, 1));
word.insert(pair<string, int>(word, 1));

c.insert(v)  //v 是value_type类型的元素
c.emplace(args)  //用args来构造一个元素。 返回pair(it, bool)  或者 it

c.insert(b, e)  //b, e是迭代器
c.insert(i1)    //i1是花括号列表， 返回void

c.insert(p, v)
c.emplace(p, args)   //迭代器p指出从哪里开始搜索新元素应该存储的位置。 返回迭代器

• 删除元素

c.erase(k)  //删除关键字k的元素， 返回k的数量
c.erase(p)  //删除迭代器p指定的元素，  返回一个指向p之后元素的迭代器
c.erase(b, e)  //删除迭代器区间(b, e)， 返回e

• map和unordered_map的下标操作

c[k]  //返回关键字为k的元素。如果k不在容器中，则添加并初始化.。 返回的是左值
c.at(k)  //如果k不在容器中，则抛出out_of_range的异常

• 统计元素

c.find(k)    //返回一个迭代器，指向第一个关键字为k的元素。若k不在c中，则返回尾后迭代器
c.count(k)    //返回关键字==k的元素数量
c.lower_bound(k)  ////返回一个迭代器，指向第一个关键字>=k的元素
c.upper_bound(k)  ////返回一个迭代器，指向第一个关键字>k的元素
c.equal_range(k)    //返回一个迭代器pair，表示关键字等于k的元素的范围

• multi的关联容器，相同关键字的元素会相邻存储

• 无序容器使用一个哈希函数和关键字类型的==运算符来组织元素

• 无序容器的性能依赖于哈希函数的质量和桶的数量和大小

• 关键字要求：==运算符来比较元素，hash<key_type>来生成每个元素的哈希值。标准库为内置类型（包括指针）提供hash模板，还有string和智能指针

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();
}

using SD_multiset = unordered_multiset<Sales_data , decltype(hasher)*, decltype(eqOp)*>;
SD_multiset  bookstore(42, hasher, eqOp);
//如果类定义了"=="运算符，只需重载哈希函数