#C++

关联容器¶

约 560 个字 60 行代码 9 张图片预计阅读时间 4 分钟

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

使用关联容器¶

set和map的使用

C++

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；因为关联容器是通过关键字存储的
关联容器不支持构造函数或插入操作

关键字类型要求¶

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

C++

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类型¶

C++

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的

遍历关联容器¶

C++

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

添加元素¶

_~c++ se
vector ivec = {2,2,3,4};
set 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(word, 1));
word_count.insert(map::value_type(word, 1));

Text Only

![](https://github.com/tom-jerr/MyblogImg/raw/main/C++/IO/insert_related_iter.png)

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

~~~c++
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类型的对象来生成每个元素的hash值

C++

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

无序容器和有序版本优势¶

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