C++-关联容器

关联容器

• 关联容器支持高效的关键字查找和访问；主要的两个关联容器是map和set

使用关联容器

• set和map的使用

map<string, size_t> word_cnt;
set<string> exclude = {"The", "But"};
 
string word;
while(cin >> word)
    // 只统计不在exclude中的单词
    if(exclude.find(word) == exclude.end())
        ++word_cnt[word];

概述

• 关联容器不支持顺序容器的位置相关的操作，例如push_front或push_back；因为关联容器是通过关键字存储的
• 关联容器不支持构造函数或插入操作

关键字类型要求

• 有序容器：严格弱序；可以看作小于等于
• 使用自己的定义操作，定义时需要传递第二个参数（一种函数指针）

bool cmp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}
// 或者使用一个仿函数进行比较操作(参数和返回值都必须使用const修饰)
struct cmp {
    bool operator()(const int a, const int b) const {
        return a > b;
    }
};
set<int, cmp> st;
map<int, int, cmp> mp;
 
multiset<Sales_data, decltype(cmp)*> bookstore(cmp);

pair类型

pair<string, int> process(vector<string> &v)
{
    if(!v.empty())
        return {v.back(), v.back().size()};
    else 
        return pair<string, int>();	// 隐式构造返回值
}

关联容器操作

关联容器迭代器

• 解引用得到一个value_type的值的引用；不能改变关键字成员
• set的迭代器是const的

遍历关联容器

// 获得一个指向首元素的迭代器
auto map_it = word_cnt.cbegin();
while(map_it != word_cnt.cend())
{
    cout << map_it->first << map_it->second << endl;
    ++map_it;
}

添加元素

vector<int> ivec = {2,2,3,4};
set<int> set2;
set2.insert(ivec.cbegin(), ivec.cend());	// set2 has 3 elements
set2.insert({1,1,2,3});						// set2 has 4 elements
 
// map操作，添加元素的类型是pair
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, int>(word, 1));
word_count.insert(map<string, int>::value_type(word, 1));

• insert返回值是一个pair，第一个值是一个迭代器，指向具有关键字的元素；第二个是一个bool值

pair<map<string, size_t>::iterator, bool> ret = word_cnt.insert(make_pair(word, 1));

删除元素

• 接受一个迭代器，一对迭代器和一个key_type的参数
• erase

map的下标操作

• 提供了下标运算符和at操作

• map解引用返回value_type对象；下标返回mapped_type对象
• 由于下标运算符可能会插入一个新元素，只能对非const的map使用下标操作

访问元素

• 如果lower_bound和upper_bound返回相同的迭代器，给定关键字不在容器中

无序容器

• 不使用比较运算符组织元素，而是使用一个哈希函数和关键字类型的==运算符来组织元素
• 如果关键字本身无序，可以用哈希解决，就可以使用无序容器

管理桶

• 无序容器存储上组织为一组桶，每个桶保存0或多个元素

无序容器对关键字类型的要求

• 使用一个hash<key_type>类型的对象来生成每个元素的hash值

// 需要提供函数替代==运算符和hash值计算函数
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);

无序容器和有序版本优势

• 无序版本性能更好，使用更简单
• 有序版本维护了关键字的序