【C++】关联式容器

目录

前言：

一，set容器

二，multiset容器

三，map容器

四，multimap容器

---

前言：

        在C++中，STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。然而，在C++的STL中还存在关联式容器，它也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

        键值对用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和 value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    pair() 
        : first(T1())
        , second(T2())
    {    }
    pair(const T1& a, const T2& b) 
        : first(a)
        , second(b)
    {    }
};

        根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用二叉搜索树(准确来说是红黑树，即平衡二叉搜索树)作为其底层结果，容器中的元素是一个有序的序列。

---

一，set容器

set综合使用文档：set的使用

注意：

        1，与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。

        2，set中插入元素时，只需要插入value即可，不需要构造键值对。

        3，set中的元素不可以重复(因此可以使用set进行去重)。

        4，使用set的迭代器遍历set中的元素，可以得到有序序列

        5，set中的元素默认按照小于来比较

        6，set中查找某个元素，时间复杂度为：log n

        7，set中的元素不允许修改，因为它是一个关联式容器，如果允许修改里面的元素，那么可能会破坏内部排序

        8，set中的底层使用二叉搜索树(红黑树)来实现

set的模板参数列表

T：set中存放元素的类型，实际在底层存储的键值对。

Compare：set中元素默认按照小于来比较。

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。(非必要情况可不用管)

set的构造

set的功能

        C++STL容器中很多必要功能都是一样的，如迭代器、反向迭代器、常量迭代器、empty、size等。这里我们只介绍下set与之需要注意的功能接口，具体其它简单的功能查看文档即可。

函数声明	功能介绍
pair<iterator, bool> insert(const value_type& x)	在set中插入元素x，实际插入的是<x, x>构成的 键值对，如果插入成功，返回<该元素在set中的 位置，true>, 如果插入失败，说明x在set中已经 存在，返回<x在set中的位置，false>
void erase ( iterator position )	删除set中position位置上的元素
size_type erase ( const key_type& x )	删除set中值为x的元素，返回删除的元素的个数
void erase ( iterator first, iterator last )	删除set中[first, last)区间中的元素
void swap(set<Key, Compare, Allocator>& st)	交换set中的元素
void clear ( )	将set中的元素清空
iterator find ( const key_type& x ) const	返回set中值为x的元素的位置
size_type count ( const key_type& x ) const	返回set中值为x的元素的个数

set的使用

#include <iostream>

using namespace std;

void settest()
{
    //set不存在相同数据
    set<int> s;
    //插入时不会插入重复数据
    s.insert(5);
    s.insert(5);
    s.insert(1);
    s.insert(1);
    s.insert(9);
    s.insert(2);
    s.insert(3);
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    cout << s.erase(7) << " " << s.erase(5) << endl; //没有此值，返回假(0)。若存在此值，返回真(1)
    set<int>::iterator its = --s.end();
    s.erase(its); //删除接口为迭代器时没有返回值
    //由于set中没有重复数据，所以count统计时只会返回1或0
    cout << s.count(3) << " " << s.count(9) << " " << s.count(7) << endl; //count返回元素数量

    set<int>::iterator sit = s.begin();
    while (sit != s.end()) {
        //*it += 8; set中的数据不能被修改
        cout << *sit << " ";
    }
    cout << endl;

    set<int>::iterator it = s.find(3);
    if (it == s.end()) {
        cout << "没有找到" << endl;
    }
    else {
        cout << "找到了" << endl;
    }

    cout << endl;
}

int main() {
    settest();
    return 0;
}

---

二，multiset容器

multiset综合使用文档：multiset的使用

说明：

        1，multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。

        2，在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成的键值对，因此value本身就是key，key就是value，类型为T)。multiset元素的值不能在容器中进行修改(因为元素总是const的，一旦修改将破坏内部结构)。

注意：

        1，multiset中，底层存储的是键值对。

        2，mulitset与set操作基本一样，与set的区别是，multiset中的元素可以重复，set是中value是唯一的。 

        3，使用迭代器对multiset中的元素进行遍历，可以得到有序的序列。

        4，multiset中的元素不能修改。

        5，在multiset中找某个元素，时间复杂度为O(log N)。

multiset的使用

        此处只简单演示与set的不同，其他接口与set相同。

#include <iostream>

using namespace std;

void multisettest()
{
    //multiset容器可以存在相同数据
    multiset<int> s;
    //插入时可以插入相同数据
    s.insert(5);
    s.insert(5);
    s.insert(1);
    s.insert(1);
    s.insert(9);
    s.insert(2);
    s.insert(3);
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    cout << s.count(5) << " " << s.count(9) << " " << s.count(7) << endl;  //统计数据数量
    cout << endl;
}

int main() {
    multisettest();
    return 0;
}

---

三，map容器

map综合使用文档：map的使用

说明：

        1，map是关联容器，它按照特定的次序(按照key来比较)存储，由键值key和值value组合而成的元素。

        2，在map中，键值key通常用于排序和唯一地标识元素(即不可重复)，而值value中存储与此键值key关联的内容(即可以重复)。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type 绑定在一起，为其取别名称为pair: typedef pair value_type。也就是说 map 中的每个元素都是一个 pair 对象。

        3，在内部，map中的元素总是按照键值key进行比较排序的(这里也可修改，需要自己实现)。注意，这里无论如何都不会按value进行排序。

        4，map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

map的模板参数说明

key：键值对中key的类型

T：键值对中value的类型

Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比
较，一般情况下(即内置类型元素)该参数不需要传递，如果无法比较时(即自定义类型)，需要用户
自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)。

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的
空间配置器。除非必要，一般不用管。

map接口功能

        由于map内部结构的实现跟set一样，都是二叉搜索树（即平衡二叉搜索树，也叫做红黑树）所以大多数接口都是一样。这里要注意接口的是 "operator[]"。该接口参数是key，返回值是key对应的value，当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value。此接口的实现可理解为以下代码：

V& operator[](const K& key) {
    pair<iterator, bool> p = insert(make_pair(key, V()));
    return ret.first->second;
}

当第一次进行调用时，map[key]的返回值是一个模板的默认构造

当key值已经存在时，插入失败，直接返回value，不会造成任何影响

        map底层结构的红黑树中，每个节点包含一个键和一个值，虽然它们并不是作为一个 std::pair 对象存储的，但是在运用时我们可看成map中的每个元素都为pair型，可使用pair的接口。

接口声明	接口功能
pair<iterator, bool> insert(const value_type& x)	在map中插入键值对x，注意x是一个键值对，返回 值也是键值对：iterator代表新插入元素的位置， bool代表释放插入是否成功
void erase(iterator position)	删除position位置上的元素
size_type erase ( const key_type& x )	删除键值为x的元素，返回删除元素的个数
void erase ( iterator first, iterator last )	删除[first, last)区间中的元素
void swap(map<Key, T, Compare, Allocator>& mp)	交换两个map中的元素
void clear ( )	清空容器元素
iterator find ( const key_type& x )	在map中插入key为x的元素， 找到返回该元素的位置的迭代器，否则返回end
size_type count ( const key_type& x ) const	返回key为x的键值在map中的个数， 注意，map中key是唯一的， 因此该函数的返回值 要么为0，要么为1， 因此也可以用该函数来检测一个key是否在map中

#include <iostream>
#include <string>

#include <map>
using namespace std;

void maptest()
{
    map<string, string> m;
    m.insert(pair<string, string>("apple", "苹果"));

    pair<string, string> p = { "string", "字符串" };
    m.insert(p);

    //make_pair可理解为pair<T1, T2>，是一个函数模板，只是单纯的写法简单
    m.insert(make_pair("sort", "排序")); //C++ 98中不支持多参数隐式类型转换，通常用make_pair
    m.insert({ "vector", "顺序表" });  //C++ 11中支持多参数隐式类型转换(多参数构造函数)

    map<string, string>::iterator it = m.begin();
    while (it != m.end()) {
        //cout << *it << endl;  map存储的元素是pair对象。pair不支持流操作
        cout << (*it).first << " : " << (*it).second << endl;
        //cout << it->first << " : " << it->second << endl;与上等效。但不能使用m.first或m.second进行访问，map内部没有此接口。

        //注意：first和second接口在pair结构中，只有pair类型才可以使用
        it++;
    }
    cout << endl;

    for (auto& e : m) {  //这里建议使用引用，因为map里的元素基础是pair，发生拷贝的代价非常大
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl << endl;
}

void mapuse()
{
    map<string, int> m;
    //注意类型：pair<iterator, bool> insert(const value_type & val); 
    pair<map<string, int>::iterator, bool> p = m.insert(make_pair("sort", 1));
    if (p.second) {  //插入成功时，bool返回1，失败返回0
        cout << p.first->first << " : " << p.first->second << endl;
    }
    else {
        cout << "插入失败" << endl;
    }
    cout << endl;

    m["vector"] = 2; //插入key和value
    m["list"] = 3; 
    m["deque"];  //value调用默认构造，这里为0
    m["list"] = 5;  //修改"list"的value
    cout << m["vector"] << endl; //查找

    for (auto& e : m) {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}

int main() {
    maptest();

    mapuse();
    return 0;
}

        很多场景下，我们可能会使用map容器按照键值对中value进行排序，但map本身容器是不被允许的。若是想按照value排序实现，这里可使用vector<pair<key, value>>顺序表结构来存储map容器中的键值对，然后使用sort排序算法，且自定义如何实现排序规则来实现自定义排序。如下类型题：

class Solution {
public:

    //自定义排序比较
    struct greater
    {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y)
        {
            return x.second > y.second || (x.second == y.second && x.first < y.first);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (auto e : words)
        {
            m[e]++;
        }

        //将map里面所有pair键值对元素存放到vector顺序表下进行自定义排序
        vector<pair<string, int>> v(m.begin(), m.end());
        sort(v.begin(), v.end(), greater());

        vector<string> vs;
        vector<pair<string, int>>::iterator it = v.begin();
        while (k--)
        {
            vs.push_back(it->first);
            it++;
        }
        return vs;
    }
};

---

四，multimap容器

multimap综合使用文档：multimap的使用

multimap的用法与map一样，唯一要注意的有两点：

        1，multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复。

        2，multimap中没有重载operator[]操作，因为key有重复的数据，operator[]无法确定value。

这里的map/multimap运用，可参考set/multiset。两者基本是相辅相成的。

本文链接：https://www.kjpai.cn/news/2024-04-08/155547.html，文章来源：网络cs，作者：往北，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！