【C++】详解map和set基本接口及使用

小明 2025-05-03 12:06:47 8

文章目录

  • 一、关联式容器与键值对
    • 1.1关联式容器（3个序列性容器+3个容器适配器+4个关联式容器）
    • 1.2键值对pair
      • make_pair函数（map在插入的时候会很方便）
      • 1.3树形结构的关联式容器
      • 二、set
        • 2.1set的基本介绍
        • 2.1默认构造、迭代器区间构造、拷贝构造（深拷贝）
        • 2.2set的迭代器
        • 2.3set的插入与删除
          • 1.insert（有时候插入会直接改变树的结构）
          • 2.find&&erase
          • 3.`count`：**返回个数，可以判断一个值是否存在**
          • 三、multiset
          • 四、map（知识点多）
            • 4.1map的模板参数
            • 4.2map的构造
            • 4.3map的修改（[]的完整用法是最难理解的）
              • 1.insert插入（make_pair(x,y)别忘了写）
              • 2.引入[]之统计次数
              • 3.详解[]的使用以及底层原理
                • []的三个功能
                • []的底层原理
                • map[]的总结
                • 4.4综合题之map利用字符串流统计出现次数
                • 五、multimap
                • 六、leetcode真题
                  • 6.1set之俩个数组的交集
                  • 6.2map之前K个高频单词

                    一、关联式容器与键值对

                    1.1关联式容器（3个序列性容器+3个容器适配器+4个关联式容器）

                    关联式容器也���用来存储数据的，但与序列式容器不同的是，关联式容器里面存储的是 结构的键值对，因此**在数据检索时比序列式容器效率更高**。

                    1.2键值对pair

                    键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 – key 和 value；其中 key 代表键值，value 代表与 key 对应的信息。

                    我们利用英汉互译的字典来理解：该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

                    template 
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;   //key
	T2 second;  //value
	pair() : first(T1()), second(T2())  //默认构造
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};

                    可以看到，C++ 中的键值对是通过 pair 类来表示的，pair 类中的 first 就是键值 key，second 就是 key 对应的信息 value；那么以后我们在设计 KV 模型的容器时只需要在容器/容器的每一个节点中定义一个 pair 对象即可；

                    问题：为什么不直接在容器中定义 key 和 value 变量，而是将 key、value 合并到 pair 中整体作为一个类型来使用呢？

                    答：这是因为 C++ 一次只能返回一个值，如果我们将 key 和 value 单独定义在容器中，那么我们就无法同时返回 key 和 value；而如果我们将 key、value 定义到另一个类中，那我们就可以直接返回 pair，然后再到 pair 中分别去取 first 和 second 即可

                    make_pair函数（map在插入的时候会很方便）

                    由于 pair 是类模板，所以我们通常是以 显式实例化 + 匿名对象 的方式来进行使用，但是由于显式实例化比较麻烦，所以 C++ 还提供了make_pair 函数，其定义如下：

                    template 
pair make_pair(T1 x, T2 y)
{
	return (pair(x, y));
}

                    如上，make_pair 返回的是一个 pair 的匿名对象，匿名对象会自动调用 pair 的默认构造完成初始化；但由于 make_pair 是一个函数模板，所以模板参数的类型可以根据实参来自动推导完成隐式实例化，这样我们就不用每次都显式指明参数类型了。

                    小羊注：对于这个返回的是不是匿名对象，我有点不理解。

                    注：由于 make_pair 使用起来比 pair 方便很多，所以我们一般都是直接使用 make_pair，而不使用 pair

                    1.3树形结构的关联式容器

                    根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器

                    树型结构与哈希结构；树型结构的关联式容器主要有四种：

                    map、set、multimap、multiset

                    这四种容器的共同点是使用平衡二叉搜索树作为其底层结构，容器中的元素是一个有序的序列；本文将介绍这四个容器的使用

                    二、set

                    2.1set的基本介绍

                    set 是按照一定次序存储元素的容器，其底层是一棵平衡二叉搜索树 (红黑树)，由于二叉搜索树的每个节点的值满足左孩子

                    set 从1000个数据找查找某个数据最多找10次，从100万个数据中找某一个数据最多找20次，从10亿个数据中找某一个数据最多找30次；我们中国现在人口总数估计已经大于10亿了，那么如果想查找是不是得费很多次数？并不是，2^31=20亿直接解决问题，所以最多31次可以精确定位到一个人。

                    同时，set 是一种 K模型 的容器，也就是说，set 中只有键值 key，而没有对应的 value，并且每个 key 都是唯一的 ；set 中的元素也不允许修改，因为这可能会破坏搜索树的结构，但是 set 允许插入和删除。

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

                    Compare：仿函数，set中元素默认按照小于来比较

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

                    特点：

                    1. set 是K模型的容器，所以 set 中插入元素时，只需要插入 key 即可，不需要构造键值对
                    2. set中的元素不可以重复，因此可以使用set进行去重（multiset相反）
                    3. 由于 set 底层是搜索树，所以使用 set 的迭代器遍历 set 中的元素，可以得到有序序列，即 set 可以用来排序
                    4. set 默认使用的仿函数为 less，所以 set 中的元素默认按照小于来比较
                    5. 由于 set 底层是平衡树搜索树，所以 set 中查找某个元素，时间复杂度为 O(logN)
                    6. set 中的元素不允许修改，因为这可能破坏搜索树的结构
                    7. set 中的底层使用平衡二叉搜索树 (红黑树) 来实现

                    set 文档：set - C++ Reference (cplusplus.com)

                    2.1默认构造、迭代器区间构造、拷贝构造（深拷贝）

                    void test_set()
{
	int arr[] = { 1,2,3,4,5 };
	set s;//默认构造
	set s1(arr, arr + 5);//区间构造
	set s2(s1);//拷贝构造
	for (auto e : s1) cout 
    //输入121345
set
cout 
cout 
    set
        cout 
        cout 
    set  
        cout 
        s.erase(pos);
    }
    
    for (auto e : s) cout 
    int arr[] = {1,2,3,1,1,6,8};
    multiset
        cout 
	// 用数组array中的元素构造multiset
	int array[] = {1,2,3,3,3,5,1,2,3,4,3};
	multiset
		cout 
        s.erase(pos);
    }
	cout 
    map 1,1,1,2,3,4,5,6 };
    for (auto& e : arr)//引用记得加上
    {
        m.insert(make_pair(e, e));
        //m.insert(pair
        cout 
        cout 
    map
        cout 
//统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果",
    "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map
    map
        countMap.insert(make_pair(e, 1));
    }
    else
    {
        it-second++;//如果找到了，就给这个水果次数+1
    }
}
    map
        cout //统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果","苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map
        countMap[e]++;//如果找不到就插入，找到就给第二个值++
    }
    for (const auto& kv : countMap)
    {
        cout 
    map
        cout 
	(*((this-insert(make_pair(k, mapped_type()))).first)).second;
}

	pair
    //可以看到，insert的返回值是pair，pair的第一个参数是迭代器
    //bool：插入成功.....1，插入失败.....0
}

    string s="1 2 3 4 5 6 7 8 9 1 2 1 2 3 4 5 6 4 2 3 4";
    //注意，这里一定是得有空格的,为了和之后的string stream对应
    map
        int num;
        //num 
public:
    vector
        //排序＋去重
        set
            if(*it1==*it2)
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
            else if(*it1*it2)
            {
                it2++;
            }
            else
            {
                it1++;
            }
        }
        return ret;
    }
};

public:
    class greater
    {
        public:
        bool operator()(const pair
            return l.secondr.second||(l.second==r.second&&l.first
        unordered_map
            pq.push(*it);
            if(pq.size()k)
                pq.pop();
        }
        vector
            ret[i] = pq.top().first;
            pq.pop();
        }
        return ret;
    }
};
The End

标签：

微信