【数据结构】map和set

r囧r小猫 2024-03-17 16:55 14阅读 0赞

#### 文章目录 ####

*  map和set
 *   *  1. 关联式容器
     *  2. 键值对
     *  3. 树形结构的关联式容器
     *   *  3.1 set
         *  3.2 set的模板参数列表
         *  3.3 set的构造
         *  3.4 set的使用举例
     *  4. map
     *   *  4.1 map的使用
     *  5. multiset
     *   *  5.1 multiset的使用
     *  6. multimap
     *  7. 经典题目

## map和set ##

### 1. 关联式容器 ###

`vector`、`list、deque`这些容器都是序列式容器。因为底层是线性序列的数据结构，里面存储的是元素本身。那么什么是关联式容器？

**关联式容器**也是用来存储数据的，但是里面存储的是<key, value>结构的键值对。在进行数据检索式比序列式容器效率更高

### 2. 键值对 ###

**用来表示有一一对应的一种结构，这个结构当中一般有两个成员key和value**。key代表的是键值，value表示与key对应的信息。

比如我们现在建立一个英汉互译的字典。字典当中必然有英文单词对应的中文含义。并且英文单词与中文含义是一一对应的关系

### 3. 树形结构的关联式容器 ###

树形结构与哈希结构。**树型结构的关联容器主要有四种**：map、set、mulitmap、multiset。这四种容器的共同特点是：使用平衡搜索树（即红黑树）作为底层，容器中的元素是一个有序的序列。

#### 3.1 set ####

[文档介绍][Link 1]

1.  set是按照一定次序存储元素的容器
2.  在set中，元素的value也标识它（value就是key），并且每一个value必须是唯一的。set中的元素不能在容器中修改。但是可以从容器中插入和删除它们
3.  在内部，set中的元素总是按照内部比较对象（类型比较）所指示的特定严格排序准则进行排序

注意：

1.  set插入元素的时候，只需要插入value，不需要构造键值对
2.  set中的元素不可以重复（因此可以使用set进行去重）
3.  使用set的迭代器遍历元素，可以得到一个有序序列
4.  set中的元素默认是按照小于来比较的

#### 3.2 set的模板参数列表 ####

`template < class T, // set::key_type/value_type`

`class Compare = less<T>, // set::key_compare/value_compare`

`class Alloc = allocator<T> // set::allocator_type > class set;`

T：set当中存放元素的类型，实际在底层存储<value, value> 键值对

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

Alloc：set当中元素空间的管理方式，使用STL提供的空间适配器来管理

#### 3.3 set的构造 ####

![ihwuib7x44-1688775645299.png][]

从上到下依次为：

1.  构造空的set
2.  用【first，last）空间内的元素构造set
3.  set的拷贝构造

剩下的操作文档当中，都有显示，使用的时候查看即可

#### 3.4 set的使用举例 ####

#include <iostream>
    #include <set>
    
    using namespace std;
    
    int main()
    {
        
    	int arr[] = {
         1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    
    	set<int> s(arr, arr + (sizeof(arr) / sizeof(arr[0])));
    
    	cout << s.size() << endl;
    
    	for (auto& e : s)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	for (auto i = s.rbegin(); i != s.rend(); i++)
    	{
        
    		cout << *i << " ";
    	}
    	cout << endl;
    
    	cout << s.count(3) << endl;
    }

### 4. map ###

[map的介绍][map]

1.  在map当中，键值key通常用于排序和唯一标识元素，值value当中存储与此值key 关联的内容。键值key和value类型可能不同，并且在map的内部，key与value通过成员类型`value_type`绑定在一起，别名为`pair`
2.  在内部，map中的元素总是按照键值key进行比较排序的
3.  map允许根据顺序对元素进行直接迭代（对map进行迭代时，可以得到一个有序的序列）
4.  map支持下标访问

#### 4.1 map的使用 ####

可以看文档，了解使用。

在key不在map当中时，通过operator获取会发生什么问题？

有一个与`operator[]`类似的操作`at()`都是通过key找到与key对应的value返回其引用。不同的是：**operator\[\]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛出异常**

#include "iostream"
    #include "map "
    
    using namespace std;
    
    int main()
    {
        
        map<string, string> map;
        map.insert(pair<string, string>("peach", "桃子"));
        map.insert(make_pair("banan", "香蕉"));
    
        //operator[]的原理是：
        //	用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中      
        // 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
        //	如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
        //	operator[]函数最后将insert返回值键值对中的value返回
    
        map["apple"] = "苹果";
    
        cout << map.size() << endl;
        cout << endl;
        for (const auto &item: map)
        {
        
            cout << item.first << "----->" << item.second << endl;
        }
        cout << endl;
    
        auto ret = map.insert(make_pair("peach", "桃子"));
        if (ret.second)
        {
        
            cout << "插入成功" << endl;
        }
        else
        {
        
            cout << "插入失败" << endl;
        }
    
        map.erase("peach");
    
        if (map.count("apple") == 1) {
        
            cout << map.find("apple")->second << "已经存在" << endl;
        }
        else
        {
        
            cout << "不存在";
        }
        return 0;
    }

### 5. multiset ###

[multiset介绍][multiset]

注意：

1.  multiset在底层存储的是<value, value>键值对
2.  multiset插入接口中，只需要插入即可
3.  multiset当中的元素是可以重复的，当时set当中的value是唯一的

#### 5.1 multiset的使用 ####

#include "iostream"
    #include "set"
    
    using namespace std;
    
    int main()
    {
        
        int arr[] = {
        1, 2, 3, 4, 2, 1, 3, 9, 0, 2, 3, 5};
    
        multiset<int> multiset(arr, arr + (sizeof(arr)/ sizeof(arr[0])));
    
        for (const auto &item: multiset)
        {
        
            cout << item << " ";
        }
    
        cout << endl;
    
        return 0;
    }

### 6. multimap ###

注意：multimap与map唯一不同的是：map当中的key是唯一的，但是multimap当中的值是可以重复的

### 7. 经典题目 ###

[前k个高频单词][k]

class Solution {
        
        class Compare {
        
        public:
            bool operator()(const pair<string, int>& left, const pair<string, int>& right)
            {
        
                return left.second > right.second;
            }
        };
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
        
            map<string, int> mapCount;
    
            for (const auto &item: words)
            {
        
                mapCount[item]++;
            }
            vector<pair<string, int>> v(mapCount.begin(), mapCount.end());
            stable_sort(v.begin(), v.end(), Compare());
    
            vector<string> ret;
            for (int i = 0; i < k; ++i) {
        
                // cout << v[i].first << ":" << v[i].second << endl;
                ret.push_back(v[i].first);
            }
            return ret;
        }
    };

[两个数组的交集][Link 2]

![1dcjsqzi4k-1688784723294.png][]

注意：以上都是排序的情况下

class Solution {
        
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        
            set<int> t1(nums1.begin(), nums1.end());
            set<int> t2(nums2.begin(), nums2.end());
    
            auto it1 = t1.begin();
            auto it2 = t2.begin();
            vector<int> v;
            while (it1 != t1.end() && it2 != t2.end()) {
        
                if (*it1 < *it2) {
        
                    it1++;
                } else if (*it1 > *it2) {
        
                    it2++;
                } else {
        
                    v.push_back(*it1);
                    it1++;
                    it2++;
                }
            }
    //        for (const auto &item: v) {
        
    //            cout << item << " ";
    //        }
            return v;
        }
    };

[Link 1]: https://cplusplus.com/reference/set/set/?kw=set
[ihwuib7x44-1688775645299.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5c1cdd4f1ac44a6ebf43959a6176f9f4.png
[map]: https://cplusplus.com/reference/map/map/
[multiset]: https://cplusplus.com/reference/set/multiset/
[k]: https://leetcode.cn/problems/top-k-frequent-words/
[Link 2]: https://leetcode.cn/problems/intersection-of-two-arrays/
[1dcjsqzi4k-1688784723294.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/703094783e2d4c3680bfacc210dc6cba.png