C++进阶：详细讲解容器set与map（pair、multiset、multimap）

C++进阶：详细讲解容器set与map（pair、multiset、multimap）

上次介绍了搜索二叉树：C++进阶：二叉搜索树介绍、模拟实现（递归迭代两版本）及其应用

为了介绍后面的AVLTree和红黑树，我们要进行一些铺垫，就是set与map的介绍啦

文章目录

• 1.关联式容器与序列式容器
• 2.C++中的键值对——`pair`
• • 2.1pair定义
  • 2.2pair的对象创建与访问
  • 2.3make_pair() 函数和使用`{}` -简化创建过程
  • 3. set容器
  • • 3.1Constructs构造函数
    • 3.2Iterator 迭代器
    • 3.3 插入、删除、查找、count
    • • 3.3.1 insert（）插入
      • 3.3.2 erase（） 删除
      • 3.3.3 find（）查找
      • 3.3.4 count（）函数
      • 4.容器 multiset
      • 5.map 容器
      • • 5.1map 模板参数说明
        • 5.2 对象的创建
        • 5.3 迭代器，insert，find ，`[]`重载
        • • 5.3.1 迭代器
          • 5.3.2 insert() 函数
          • 5.3.3 find() 函数
          • 5.3.4 `[]`
          • 6.容器 multimap

            ---

            1.关联式容器与序列式容器

            关联式容器和序列式容器是 C++ 中两种不同的容器类型

            1. 关联式容器:

               • 关联式容器主要包括 std::set, std::map, std::multiset, std::multimap 等。
               • 这些容器是基于键值对(结构)的概念，通过键==（key）来唯一标识元素==。
               • 关联式容器内部使用二叉搜索树（通常是红黑树）或类似的数据结构，以保持元素的有序性。
               • 插入、删除、查找等操作的平均时间复杂度是 O(log n)。

               • 序列式容器:

                 • 序列式容器包括 std::vector, std::list, std::deque, std::array 等。
                 • 这些容器是基于线性结构的，元素在容器中的位置是由插入的顺序决定的。
                 • 插入、删除、查找等操作的平均时间复杂度因容器类型而异，但在最差情况下，可能达到 O(n)。

            ---

            2.C++中的键值对——pair

            在C++中，键值对是一种数据结构，通常用于表示关联关系

            键值对由两部分组成：键（Key）和值（Value）。这种结构允许通过键来检索和关联对应的值，key代表键值，value表示与key对应的信息

            2.1pair定义

            std::pair 是C++标准库中提供的一个简单的键值对实现。它包含在 头文件中。一个 std::pair 有两个公有成员：first 和 second，分别表示键和值==（firstkey ; secondvalue）==

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

            2.2pair的对象创建与访问

            文档中的构造函数的介绍：

            1. 默认构造函数：
            • pair();
            • 默认构造函数创建一个空的 std::pair 对象，不包含任何值。
              1. 拷贝构造函数：
              • template pair (const pair& pr);
              • 拷贝构造函数用于从另一个 std::pair 对象 pr 中复制键值对来构造一个新的 std::pair 对象。
                1. 初始化构造函数：
                • pair (const first_type& a, const second_type& b);
                • 初始化构造函数接受两个参数 a 和 b，分别用于初始化 std::pair 对象的 first 和 second 成员变量。

                  void test_pair(){pair p1;//空参pair p2(2, '2');pair p3(p2);//拷贝构造cout