C++漫溯键值的长河：map && set

文章目录

• 1.关联式容器
• 2.set
• • 2.1 find
  • 2.2 lower_bound、upper_bound
  • 3.multiset
  • • 3.1 count
    • 3.2 equal_range
    • 4.map
    • • 4.1 insert
      • 4.2 operate->
      • 4.3 operate[ ]
      • 4.4 map的应用实践：随机链表的复制
      • 5.multimap
      • 希望读者们多多三连支持
      • 小编会继续更新
      • 你们的鼓励就是我前进的动力！

        迄今为止，除了二叉搜索树以外的结构，我们学习到的顺序表，链表，栈和队列等都属于这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身

        1.关联式容器

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

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

        键对值中的 key 表示键值，value 表示与 key 对应的信息

        SGI-STL中关于键值对的定义：

        template 
        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)
        	{}
        };
        

        🔥值得注意的是： pair 是有重载比较大小的，first 和 second 一起比

        2.set

        

        set 的主要特征可总结为：

        1. set 是按照一定次序存储元素的容器
        2. 在 set 中，元素的 value 也标识它( value 就是 key，类型为 T )，并且每个 value 必须是唯一的 set 中的元素不能在容器中修改(元素总是 const )，但是可以从容器中插入或删除它们
        3. 在内部，set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序
        4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代
        5. set 在底层是用二叉搜索树(红黑树)实现的

        🔥值得注意的是：

        1. 与 map/multimap 不同，map/multimap 中存储的是真正的键值对 ，set 中只放 value，但在底层实际存放的是由 构成的键值对(后面底层的博客会解释)
        2. set 中插入元素时，只需要插入 value 即可，不需要构造键值对
        3. set 中的元素不可以重复(因此可以使用 set 进行去重)。
        4. 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
        5. set 中的元素默认按照小于来比较，即 1、2、3…的顺序
        6. set 中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2​n
        7. set 中的元素不允许修改
        8. set 中的底层使用二叉搜索树(红黑树)来实现

        2.1 find

        

        由于 set 的基本功能，像 insert、erase、迭代器等都和 string、vector 等差不多，这里就不过多解释，详细的可以自行查看官方文档，本文将针对部分特殊的函数进行解析

        find 简单来说，就是寻找特定的键值，那么可以提出一个问题：

        set s;
        s.insert(3);
        s.insert(2);
        s.insert(4);
        s.insert(5);
        s.insert(1);
        s.insert(5);
        s.insert(2)
        s.insert(5);
        auto pos = s.find(3);//第一种
        auto pos = find(s.begin(), s.end(), 3);//第二种
        s.erase(3);
        

        哪一种 find 方式能更好的删除？显然是第一种

        因为第一种是 set 里面的 find，会以平衡二叉搜索树的方式去查找，大的往左走，小的往右走，时间复杂度为 O(logN)；第二种是 algorithm(算法头文件)中的 find，是以依次遍历的方式，即中序遍历的方式进行的，时间复杂度为 O(N)

        2.2 lower_bound、upper_bound

        set myset;
        set::iterator itlow, itup;
        for (int i = 1; i