• C++ -- 学习系列 关联式容器 set 与 map

    一   关联式容器是什么？

    c++ 中有两种容器类型：关联式容器与序列式容器（顺序容器）

    关联式中的容器是按照关键字来存储与访问的，序列式容器（顺序容器）则是元素在容器中的相对位置来存储与访问的。

    c++ 中的关联式容器主要是 set 与 map.

    二   底层原理与源码

    1. 红黑树

           红黑树是一种平衡二叉搜索树（balanced binary search tree），即插入或者删除元素后，依然能够保证树是平衡的，所谓平衡意味着任意一个父节点，其左右子树的深度相差不会太多。

    平衡树也称 AVL 树，任意节点的左右个子树的高度差不超过1。

    这一特性也保证了在插入元素与查找元素时的效率。

    红黑树核心法则：

    1. 每个节点要么是红色，要么是黑色

    2. 红黑树中的任意节点到达其每个叶子节点的黑色高度是相同的（黑色高度值得是某个节点到达叶子节点的黑色节点的个数，因叶子节点是黑色的，所以也包括叶子节点）

    3. 两个红色节点之间不能相邻，即对于任意一个红色节点而言，其左右子节点定不是红色

    4. 根节点必须是黑色的

    5. 每个红色节点的两个子节点一定是黑色的

    【红黑树】的详细实现(C++)附代码 - 知乎 (zhihu.com)

    c++ 中的红黑树源代码位置

    #include  

    1.  template<typename _Key, typename _Val, typename _KeyOfValue,
    2.            typename _Compare, typename _Alloc = allocator<_Val> >
    3.     class _Rb_tree
    4.     {
    5.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    6.         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
    7.  
    8.       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
    9.  
    10.     protected:
    11.       typedef _Rb_tree_node_base* 		_Base_ptr;
    12.       typedef const _Rb_tree_node_base* 	_Const_Base_ptr;
    13.       typedef _Rb_tree_node<_Val>* 		_Link_type;
    14.       typedef const _Rb_tree_node<_Val>*	_Const_Link_type;
    15.    
    16.    ......
    17.  
    18. };
     

     

    源码中的模板参数解释如下：
     

     
 
    1. Key 为存储在红黑树中的关键字类型
     
 
    2. Value 实际存储数据的类型
     
 
    3. KeyOfValue 表示如何通过 Value 获取到 Key，通常是一个函数
     
 
    4. Compare 则为比较元素大小的函数，可自定义实现
     
 
    5. Alloc 分配内存的方式
     

     

    1. #include
    2. #include 
    3.  
    4.  
    5. int main()
    6. {
    7. //    template
    8. //      struct _Identity
    9. //      : public unary_function<_Tp,_Tp>
    10. //      {
    11. //        _Tp&
    12. //        operator()(_Tp& __x) const
    13. //        { return __x; }
    14.  
    15. //        const _Tp&
    16. //        operator()(const _Tp& __x) const
    17. //        { return __x; }
    18. //      };
    19.     
    20.      std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>> rb_tree;
    21.  
    22.     std::cout << rb_tree.empty() << std::endl;
    23.     std::cout << rb_tree.size() << std::endl;
    24.  
    25.     // 1. 插入元素不允许重复.
    26.     rb_tree._M_insert_unique(1);
    27.     rb_tree._M_insert_unique(2);
    28.     rb_tree._M_insert_unique(3);
    29.     rb_tree._M_insert_unique(4);
    30.     rb_tree._M_insert_unique(5);
    31.  
    32.     std::cout << rb_tree.size() << std::endl;
    33.  
    34.     rb_tree._M_insert_unique(1);
    35.  
    36.     std::cout << rb_tree.size() << std::endl;
    37.  
    38.     std::cout << "------" << std::endl;
    39.     // 2. 插入元素允许重复.
    40.     rb_tree._M_insert_equal(1);
    41.     rb_tree._M_insert_equal(1);
    42.     rb_tree._M_insert_equal(1);
    43.     std::cout << rb_tree.size() << std::endl;
    44.  
    45.     for(auto iter = rb_tree.begin(); iter != rb_tree.end(); iter++)
    46.     {
    47.         std::cout << *iter <<" ";
    48.     }
    49.     std::cout <<""<
    50.  
    51.     return 0;
    52. }
     

     

    2. 基于红黑树的关联式容器
     

    2.1 set/multiset
     

    set/multiset 是以红黑树为底层结构的，因此存入的元素具有自动排序的特性，排序的依据是 key ，而 set/miltiset  元素的 key 与 value是合二为一的，其value 就是 key；
     

    set/multiset  提供遍历操作与迭代器 iterator, 通过 不断的 iterator++ 遍历可以获取到已经排好序的元素；
     

    我们无法通过 迭代器来改变 set/multiset 的值，这样设计的原因是 若是可以随意修改值，那么按照key 排好的顺序便有可能不存在了，从代码上来讲，set/multiset 用的迭代器是底层红黑树类 _Rb_tree 的 const iterator ，禁止使用者赋值。
     

     2.1.1 set 源代码
     

    1. template<typename _Key, typename _Compare = std::less<_Key>,
    2. 	   typename _Alloc = std::allocator<_Key> >
    3.     class set
    4.     {
    5.     public:
    6.       // typedefs:
    7.       //@{
    8.       /// Public typedefs.
    9.       typedef _Key     key_type;
    10.       typedef _Key     value_type;
    11.       typedef _Compare key_compare;
    12.       typedef _Compare value_compare;
    13.       typedef _Alloc   allocator_type;
    14.  
    15.     private:
    16.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    17. 	rebind<_Key>::other _Key_alloc_type;
    18.  
    19.       typedef _Rb_tree,
    20. 		       key_compare, _Key_alloc_type> _Rep_type;
    21.       _Rep_type _M_t;  // Red-black tree representing set.
    22.  
    23.       typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
    24.  
    25.     .....
    26.      iterator
    27.       insert(const_iterator __position, const value_type& __x)
    28.       { return _M_t._M_insert_unique_(__position, __x); }
    29.     .....
    30. };
     

    通过源码可以看出，set 底层使用的是 _Rb_tree , insert 函数底层调用的是 _Rb_tree 的 insert_unique 函数，即 _Rb_tree 中的元素不重复。
     

     

    2.1.2 multiset 源码
     

    1.  template <typename _Key, typename _Compare = std::less<_Key>,
    2. 	    typename _Alloc = std::allocator<_Key> >
    3.     class multiset
    4.     {
    5. #ifdef _GLIBCXX_CONCEPT_CHECKS
    6.       // concept requirements
    7.       typedef typename _Alloc::value_type		_Alloc_value_type;
    8. # if __cplusplus < 201103L
    9.       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
    10. # endif
    11.       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
    12. 				_BinaryFunctionConcept)
    13.       __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
    14. #endif
    15.  
    16.     public:
    17.       // typedefs:
    18.       typedef _Key     key_type;
    19.       typedef _Key     value_type;
    20.       typedef _Compare key_compare;
    21.       typedef _Compare value_compare;
    22.       typedef _Alloc   allocator_type;
    23.  
    24.     private:
    25.       /// This turns a red-black tree into a [multi]set.
    26.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    27. 	rebind<_Key>::other _Key_alloc_type;
    28.  
    29.       typedef _Rb_tree,
    30. 		       key_compare, _Key_alloc_type> _Rep_type;
    31.       /// The actual tree structure.
    32.       _Rep_type _M_t;
    33.  
    34.       typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
    35.  
    36.   ......
    37.  
    38.       iterator
    39.       insert(const value_type& __x)
    40.       { return _M_t._M_insert_equal(__x); }
    41.  
    42.   ......
    43.  
    44. };
     

    通过源码可以看出，multiset 底层使用的是 _Rb_tree , insert 函数底层调用的是 _Rb_tree 的 insert_equal 函数，即 _Rb_tree 中的元素允许重复。
     

    2.2 map/multimap
     

    map/multimap 是以红黑树为底层结构的，因此存入的元素具有自动排序的特性，排序的依据是 key;
     

    map/multimap 提供遍历操作与迭代器 iterator, 通过 不断的 iterator++ 遍历可以获取到已经按照 key 排好序的元素；
     

    我们无法通过 迭代器来改变 map/multimap 的值，这样设计的原因是 若是可以随意修改值，那么按照 key 排好的顺序便有可能不存在了，但是我们可以修改 key 对应的 data 值。因而 map/multimap 内部将 key type 设为 const ,如此可以避免对 key 的随意修改。
     

    map 的key 是独一无二的，所以底层使用 _Rb_tree 的 insert_unique 函数;
     

    multimap 的key允许重复，所以底层使用 _Rb_tree 的 insert_equal 函数
     

    2.2.1  map 源码
     

    1. template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
    2. 	    typename _Alloc = std::allocatorconst _Key, _Tp> > >
    3.     class map
    4.     {
    5.     public:
    6.       typedef _Key					key_type;
    7.       typedef _Tp					mapped_type;
    8.       typedef std::pair<const _Key, _Tp>		value_type;
    9.       typedef _Compare					key_compare;
    10.       typedef _Alloc					allocator_type;
    11.  private:
    12.       /// This turns a red-black tree into a [multi]map.
    13.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    14. 	rebind::other _Pair_alloc_type;
    15.  
    16.       typedef _Rb_tree,
    17. 		       key_compare, _Pair_alloc_type> _Rep_type;
    18.  
    19.       /// The actual tree structure.
    20.       _Rep_type _M_t;
    21.  
    22.       typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
    23.    
    24.  .....
    25.      std::pairbool>
    26.       insert(const value_type& __x)
    27.       { return _M_t._M_insert_unique(__x); }
    28.  .....
    29. };
     

    通过源码可以看到 map 的 insert 函数底层调用的是 insert_unique 函数，所以 map 的 key 是唯一的。
     

    2.2.2 multimap 源码
     

    1. template <typename _Key, typename _Tp,
    2. 	    typename _Compare = std::less<_Key>,
    3. 	    typename _Alloc = std::allocatorconst _Key, _Tp> > >
    4.     class multimap
    5.     {
    6.     public:
    7.       typedef _Key					key_type;
    8.       typedef _Tp					mapped_type;
    9.       typedef std::pair<const _Key, _Tp>		value_type;
    10.       typedef _Compare					key_compare;
    11.       typedef _Alloc					allocator_type;
    12.    
    13.     private:
    14.       /// This turns a red-black tree into a [multi]map.
    15.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    16. 	rebind::other _Pair_alloc_type;
    17.  
    18.       typedef _Rb_tree,
    19. 		       key_compare, _Pair_alloc_type> _Rep_type;
    20.       /// The actual tree structure.
    21.       _Rep_type _M_t;
    22.  
    23.       typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
    24.  
    25.    ......
    26.     iterator
    27.       insert(const value_type& __x)
    28.       { return _M_t._M_insert_equal(__x); }
    29.    ......
    30. };
     

    通过源码可以看到 multimap 的 insert 函数底层调用的是 insert_equal 函数，所以 map 的 key 是可以重复的。
     

    2.2.3  Select1st
     

    前面的源码中提到了  Select1st，该函数的作用是获取 pair 中的第一个元素，应用在 map 中，获取的就是 key
     

    Select1st 源码如下：
     

    1.  template<typename _Pair>
    2.     struct _Select1st
    3.     : public unary_function<_Pair, typename _Pair::first_type>
    4.     {
    5.       typename _Pair::first_type&
    6.       operator()(_Pair& __x) const
    7.       { return __x.first; }
    8.  
    9.       const typename _Pair::first_type&
    10.       operator()(const _Pair& __x) const
    11.       { return __x.first; }
    12. };
     

    三  使用
     

    1. set/multiset
     

      1.1 set 函数
     

    std::set - cppreference.com       
     

       1.1.1  构造函数
     

    函数说明
    set()空构造函数
     
     template	set(_InputIterator __first, _InputIterator __last)
         		range 构造函数
     

        1.1.2  容器修改
     

    函数说明
    clear()清空容器
    insert插入元素
    emplace插入元素，可以只传入元素类的构造函数所需参数
    erase移除指定位置的元素
     

        1.1.3  容器查找
     

    函数说明
    count返回指定元素的个数
    begin()返回首元素的 iterator
    end()返回尾元素下一地址的 iterator，该 iterator 不能获取元素
    find查找指定元素，若是存在返回指向该元素的 iterator；若是不存在，则返回尾 iterator
    lower_boundIterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.
    uppser_bound 
    Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned.
     
     

    1.1.4  容器容量
     

    函数说明
    empty()判断 set 是否为空
    size()返回 set 中的元素个数
     

    1.1.5  示例
     

    1. #include
    2. #include
    3.  
    4.  
    5. int main()
    6. {
    7.      // 1. 构造函数
    8.     std::set<int>  unique_set1;
    9.  
    10.     int nums[] = {1, 2, 3, 4, 5, 6};
    11.     std::set<int>  unique_set2(nums, nums+6);
    12.  
    13.     std::set<int>  unique_set3(unique_set2.begin(), unique_set2.end());
    14.  
    15.     // 2. 容器修改
    16.     unique_set1.insert(1);
    17.     unique_set1.insert(2);
    18.     unique_set1.insert(3);
    19.     unique_set1.emplace(4);
    20.     unique_set1.emplace(5);
    21.  
    22.     unique_set1.erase(4);
    23.  
    24.     // 3. 容器查找
    25.     std::cout << unique_set1.count(3) << std::endl; // 1
    26.     auto item1_iter = unique_set1.find(3);
    27.  
    28.     std::cout << (item1_iter == unique_set1.end()) << ", " << *item1_iter << std::endl; // 0 , 3
    29.  
    30.     auto item2_iter = unique_set1.lower_bound(4);
    31.     std::cout << (item2_iter == unique_set1.end()) << ", " << *item2_iter << std::endl; // 0 , 3
    32.  
    33.     auto item3_iter = unique_set1.upper_bound(5);
    34.     std::cout << (item3_iter == unique_set1.end()) << ", " << *item3_iter << std::endl;
    35.     // 0 , 5
    36.     for(auto iter = unique_set1.begin(); iter != unique_set1.end(); iter++)
    37.     {
    38.         std::cout << *iter << " "; // 1. 2, 3, 5
    39.     }
    40.     std::cout << "" << std::endl;
    41.  
    42.     // 4. 容器容量
    43.     std::cout << unique_set1.size() << std::endl; // 4
    44.     std::cout << unique_set1.empty() << std::endl; // 0
    45.  
    46.     unique_set1.clear();
    47.  
    48.     std::cout << unique_set1.size() << std::endl; // 0
    49.     std::cout << unique_set1.empty() << std::endl; // 1
    50.  
    51.     return 0;
    52. }
     

     1.2 multiset 函数
     

        std::multiset - cppreference.com
     

     1.2.1  构造函数
     

    函数说明
    set()空构造函数
     
     template	set(_InputIterator __first, _InputIterator __last)
         		range 构造函数
     

        1.2.2  容器修改
     

    函数说明
    clear()清空容器
    insert插入元素
    emplace插入元素，可以只传入元素类的构造函数所需参数
    erase移除指定位置的元素
     

        1.2.3  容器查找
     

    函数说明
    count返回指定元素的个数
    begin()返回首元素的 iterator
    end()返回尾元素下一地址的 iterator，该 iterator 不能获取元素
    find查找指定元素，若是存在返回指向该元素的 iterator；若是不存在，则返回尾 iterator
    lower_boundIterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.
    uppser_bound 
    Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned.
     
     

    1.2.4  容器容量
     

    函数说明
    empty()判断 set 是否为空
    size()返回 set 中的元素个数
     

    1.2.5  示例
     

    1. #include
    2. #include
    3.  
    4. int main()
    5. {
    6.      // 1. 构造函数
    7.     std::multiset<int>  multi_set1;
    8.     int nums1[] = {1, 2, 3, 4, 5, 6};
    9.     std::multiset<int>  multi_set2(nums1, nums1+6);
    10.     std::multiset<int>  multi_set3(multi_set2.begin(), multi_set2.end());
    11.  
    12.     // 2. 容器修改
    13.     multi_set1.insert(1);
    14.     multi_set1.insert(2);
    15.     multi_set1.insert(3);
    16.     multi_set1.insert(3);
    17.     multi_set1.insert(3);
    18.     multi_set1.emplace(4);
    19.     multi_set1.emplace(5);
    20.  
    21.     multi_set1.erase(4);
    22.  
    23.  
    24.     // 3. 容器查找
    25.     std::cout << multi_set1.count(3) << std::endl; // 3
    26.     auto item1_iter = multi_set1.find(3);
    27.  
    28.     std::cout << (item1_iter == multi_set1.end()) << ", " << *item1_iter << std::endl; // 0, 3
    29.  
    30.     auto item2_iter = multi_set1.lower_bound(4);
    31.     std::cout << (item2_iter == multi_set1.end()) << ", " << *item2_iter << std::endl; // 0, 5
    32.  
    33.     auto item3_iter = multi_set1.upper_bound(4);
    34.     std::cout << (item3_iter == multi_set1.end()) << ", " << *item3_iter << std::endl; // 0, 5
    35.  
    36.     for(auto iter = multi_set1.begin(); iter != multi_set1.end(); iter++)
    37.     {
    38.         std::cout << *iter << " "; // 1 2 3 3 3 5
    39.     }
    40.     std::cout << "" << std::endl;
    41.  
    42.     // 4. 容器容量
    43.     std::cout << multi_set1.size() << std::endl; // 6
    44.     std::cout << multi_set1.empty() << std::endl; // 0
    45.  
    46.     multi_set1.clear();
    47.  
    48.     std::cout << multi_set1.size() << std::endl; // 0
    49.     std::cout << multi_set1.empty() << std::endl; // 1
    50.     
    51.     return 0;
    52. }
     

    2. map/multimap
     

    2.1 map 函数
     

            2.1.1  构造函数
     

    函数说明
    map默认构造函数
    template< class InputIt > 
    map( InputIt first, InputIt last)
         		range 构造函数
    map( std::initializer_list init)initializer list 构造函数
     

            2.1.2  容器修改
     

    函数说明
    clear()清空容器
    insert插入元素
    emplace插入元素，可以只传入元素类的构造函数所需参数
    erase移除指定位置的元素
     

            2.1.3  容器访问
     

    函数说明
    count返回指定 key 元素的个数
    begin()返回首元素的 iterator
    end()返回尾元素下一地址的 iterator，该 iterator 不能获取元素
    find查找指定元素，若是存在返回指向该元素的 iterator；若是不存在，则返回尾 iterator
    lower_boundIterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.
    uppser_bound 
    Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned.
     
    atReturns a reference to the mapped value of the element with key equivalent to key. If no such element exists, an exception of type std::out_of_range is thrown.
    operator[]Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.
     

            2.1.4  容器容量
     

    函数说明
    empty()判断 set 是否为空
    size()返回 set 中的元素个数
     

            2.1.5  示例
     

    1. #include
    2. #include
    3.  
    4. int main()
    5. {
    6.     // 1. 构造函数
    7.     std::map<int, std::string>  unique_map1;
    8.     std::map<int, std::string>  unique_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};
    9.     std::map<int, std::string>  unique_map3(unique_map2.begin(), unique_map2.end());
    10.  
    11.     // 2. 容器修改
    12.     unique_map1.insert({5, "e"});
    13.     unique_map1.insert({6, "f"});
    14.     unique_map1.emplace(7, "g");
    15.     unique_map1.emplace(8, "h");
    16.     unique_map1.insert({16, "ff"});
    17.  
    18.     unique_map1.erase(16);
    19.  
    20.     // 3. 容器访问
    21.     std::cout << unique_map1.count(6) << std::endl; // 1
    22.     auto item_iter1 = unique_map1.find(6);
    23.     std::cout << (item_iter1 == unique_map1.end())  << std::endl; // 0
    24.     std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, f
    25.     auto item_iter2 = unique_map1.lower_bound(6);
    26.     std::cout << item_iter2->first << ", " << item_iter2->second << std::endl; // 6, f
    27.     auto item_iter3 = unique_map1.upper_bound(7);
    28.  
    29.     std::cout << item_iter3->first << ", " << item_iter3->second << std::endl; // 8, h
    30.  
    31.     std::cout << unique_map1.at(7) << std::endl; // g
    32.     std::cout << unique_map1[7] << std::endl; // g
    33.  
    34.     // 4. 容器容量
    35.      std::cout << unique_map1.empty() << std::endl; // 0
    36.      std::cout << unique_map1.size() << std::endl; // 4
    37.  
    38.      unique_map1.clear();
    39.      std::cout << unique_map1.empty() << std::endl; // 1
    40.      std::cout << unique_map1.size() << std::endl; // 0    
    41.  
    42.      return 0;
    43. }
     

     2.2 multimap 函数
     

             2.1.1  构造函数
     

    函数说明
    map默认构造函数
    template< class InputIt > 
    map( InputIt first, InputIt last)
         		range 构造函数
    map( std::initializer_list init)initializer list 构造函数
     

              2.1.2  容器修改
     

    函数说明
    clear()清空容器
    insert插入元素
    emplace插入元素，可以只传入元素类的构造函数所需参数
    erase移除指定位置的元素
     

            2.1.3  容器访问
     

    函数说明
    count返回指定 key 元素的个数
    begin()返回首元素的 iterator
    end()返回尾元素下一地址的 iterator，该 iterator 不能获取元素
    find查找指定元素，若是存在返回指向该元素的 iterator；若是不存在，则返回尾 iterator
    lower_boundIterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.
    uppser_bound 
    Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned.
     
     

            2.1.4  容器容量
     

    函数说明
    empty()判断 set 是否为空
    size()返回 set 中的元素个数
     

            2.1.5  示例
     

    1. #include
    2. #include
    3.  
    4. int main()
    5. {
    6.  // 1. 构造函数
    7.      std::multimap<int, std::string>  multi_map1;
    8.      std::multimap<int, std::string>  multi_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};
    9.      std::multimap<int, std::string>  multi_map3(multi_map2.begin(), multi_map2.end());
    10.  
    11.      // 2. 容器修改
    12.      multi_map1.insert({5, "e"});
    13.      multi_map1.insert({6, "f"});
    14.      multi_map1.emplace(7, "g1");
    15.      multi_map1.emplace(7, "g2");
    16.      multi_map1.emplace(7, "g3");
    17.  
    18.      multi_map1.emplace(8, "h");
    19.      multi_map1.insert({16, "ff"});
    20.  
    21.      multi_map1.erase(16);
    22.  
    23.      // 3. 容器访问
    24.      std::cout << multi_map1.count(6) << std::endl; // 1
    25.      auto item_iter1 = multi_map1.find(6);
    26.      std::cout << (item_iter1 == multi_map1.end())  << std::endl; // 0
    27.      std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, f
    28.      auto item_iter2 = multi_map1.lower_bound(6);
    29.      std::cout << item_iter2->first << ", " << item_iter2->second << std::endl; // 6, f
    30.      auto item_iter3 = multi_map1.upper_bound(7);
    31.  
    32.      std::cout << item_iter3->first << ", " << item_iter3->second << std::endl; // 8, h
    33.  
    34.      // 4. 容器容量
    35.       std::cout << multi_map1.empty() << std::endl; // 0
    36.       std::cout << multi_map1.size() << std::endl; // 6
    37.  
    38.       multi_map1.clear();
    39.       std::cout << multi_map1.empty() << std::endl; // 1
    40.       std::cout << multi_map1.size() << std::endl; // 0
    41.  
    42.       return 0;
    43. }
     

    四  简单实现
     

          1. my_set
     

    1. // my_set.h
    2.  
    3. #include 
    4.  
    5. template<typename T>
    6. class my_set
    7. {
    8.   typedef T ValueType;
    9.   typedef T KeyType;
    10.   typedef std::_Rb_tree, std::less> Rb_type;
    11.   typedef typename std::_Rb_tree, std::less>::const_iterator  const_Iterator;
    12.  
    13. public:
    14.     my_set()
    15.     {
    16.  
    17.     }
    18.  
    19.     template<typename InputIterator>
    20.     my_set(InputIterator first, InputIterator last)
    21.     {
    22.         rb_tree._M_insert_unique(first, last);
    23.     }
    24.  
    25.     ~my_set()
    26.     {
    27.     }
    28.  
    29.     const_Iterator begin()
    30.     {
    31.         return rb_tree.begin();
    32.     }
    33.  
    34.     const_Iterator end()
    35.     {
    36.         return rb_tree.end();
    37.     }
    38.  
    39.     void clear()
    40.     {
    41.         rb_tree.clear();
    42.     }
    43.  
    44.     void insert(ValueType& val)
    45.     {
    46.         rb_tree._M_insert_unique(val);
    47.     }
    48.  
    49.     void insert(ValueType&& val)
    50.     {
    51.         rb_tree._M_insert_unique(val);
    52.     }
    53.  
    54.     template<typename ... Args>
    55.     void emplace(Args&& ... args)
    56.     {
    57.         rb_tree._M_emplace_unique(std::forward(args)...);
    58.     }
    59.  
    60.     template<typename ... Args>
    61.     void emplace(Args& ... args)
    62.     {
    63.         rb_tree._M_emplace_unique(std::forward(args)...);
    64.     }
    65.  
    66.     void erase(ValueType& val)
    67.     {
    68.         rb_tree.erase(val);
    69.     }
    70.  
    71.     void erase(ValueType&& val)
    72.     {
    73.         rb_tree.erase(val);
    74.  
    75.     }
    76.  
    77.     std::size_t count(ValueType& val)
    78.     {
    79.         return rb_tree.count(val);
    80.     }
    81.  
    82.     std::size_t count(ValueType&& val)
    83.     {
    84.         return rb_tree.count(val);
    85.     }
    86.  
    87.     const_Iterator find(ValueType& val)
    88.     {
    89.         return rb_tree.find(val);
    90.     }
    91.  
    92.     const_Iterator find(ValueType&& val)
    93.     {
    94.         return rb_tree.find(val);
    95.     }
    96.  
    97.     bool empty()
    98.     {
    99.         return rb_tree.empty();
    100.     }
    101.  
    102.     std::size_t size()
    103.     {
    104.         return rb_tree.size();
    105.     }
    106.  
    107. private:
    108.     Rb_type rb_tree;
    109.  
    110. };
    111.  
    112. // main.cpp
    113. int main()
    114. {
    115.     // 1. 构造函数
    116.     my_set<int>  unique_set1;
    117.     int nums[] = {1, 2, 3, 4, 5, 6};
    118.     my_set<int>  unique_set2(nums, nums+6);
    119.     my_set<int>  unique_set3(unique_set2.begin(), unique_set2.end());
    120.  
    121.     // 2. 容器修改
    122.     unique_set1.insert(1);
    123.     unique_set1.insert(2);
    124.     unique_set1.insert(3);
    125.     unique_set1.emplace(4);
    126.     unique_set1.emplace(5);
    127.  
    128.     unique_set1.erase(4);
    129.  
    130.  
    131.     // 3. 容器查找
    132.     std::cout << unique_set1.count(3) << std::endl; // 1
    133.     auto item1_iter = unique_set1.find(3);
    134.  
    135.     std::cout << (item1_iter == unique_set1.end()) << ", " << *item1_iter << std::endl; // 0. 3
    136.  
    137.     for(auto iter = unique_set1.begin(); iter != unique_set1.end(); iter++)
    138.     {
    139.         std::cout << *iter << " "; // 1 2 3 5
    140.     }
    141.     std::cout << "" << std::endl;
    142.  
    143.     // 4. 容器容量
    144.     std::cout << unique_set1.size() << std::endl; // 4
    145.     std::cout << unique_set1.empty() << std::endl; // 0
    146.  
    147.     unique_set1.clear();
    148.  
    149.     std::cout << unique_set1.size() << std::endl; // 0
    150.     std::cout << unique_set1.empty() << std::endl; // 1
    151.     return 0;
    152. }
     

          2. my_multiset
     

    1. // my_multiset.h
    2.  
    3. #include 
    4.  
    5. template<typename T>
    6. class my_multiset
    7. {
    8.   typedef T ValueType;
    9.   typedef T KeyType;
    10.   typedef std::_Rb_tree, std::less> Rb_type;
    11.   typedef typename std::_Rb_tree, std::less>::const_iterator  const_Iterator;
    12.  
    13. public:
    14.     my_multiset()
    15.     {
    16.  
    17.     }
    18.  
    19.     template<typename InputIterator>
    20.     my_multiset(InputIterator first, InputIterator last)
    21.     {
    22.         rb_tree._M_insert_equal(first, last);
    23.     }
    24.  
    25.     ~my_multiset()
    26.     {
    27.     }
    28.  
    29.     const_Iterator begin()
    30.     {
    31.         return rb_tree.begin();
    32.     }
    33.  
    34.     const_Iterator end()
    35.     {
    36.         return rb_tree.end();
    37.     }
    38.  
    39.     void clear()
    40.     {
    41.         rb_tree.clear();
    42.     }
    43.  
    44.     void insert(ValueType& val)
    45.     {
    46.         rb_tree._M_insert_equal(val);
    47.     }
    48.  
    49.     void insert(ValueType&& val)
    50.     {
    51.         rb_tree._M_insert_equal(val);
    52.     }
    53.  
    54.     template<typename ... Args>
    55.     void emplace(Args&& ... args)
    56.     {
    57.         rb_tree._M_emplace_unique(std::forward(args)...);
    58.     }
    59.  
    60.     template<typename ... Args>
    61.     void emplace(Args& ... args)
    62.     {
    63.         rb_tree._M_emplace_unique(std::forward(args)...);
    64.     }
    65.  
    66.     void erase(ValueType& val)
    67.     {
    68.         rb_tree.erase(val);
    69.     }
    70.  
    71.     void erase(ValueType&& val)
    72.     {
    73.         rb_tree.erase(val);
    74.     }
    75.  
    76.     std::size_t count(ValueType& val)
    77.     {
    78.         return rb_tree.count(val);
    79.     }
    80.  
    81.     std::size_t count(ValueType&& val)
    82.     {
    83.         return rb_tree.count(val);
    84.     }
    85.  
    86.     const_Iterator find(ValueType& val)
    87.     {
    88.         return rb_tree.find(val);
    89.     }
    90.  
    91.     const_Iterator find(ValueType&& val)
    92.     {
    93.         return rb_tree.find(val);
    94.     }
    95.  
    96.     bool empty()
    97.     {
    98.         return rb_tree.empty();
    99.     }
    100.  
    101.     std::size_t size()
    102.     {
    103.         return rb_tree.size();
    104.     }
    105.  
    106. private:
    107.     Rb_type rb_tree;
    108.  
    109. };
    110.  
    111. // main.cpp
    112. #include
    113. #include"my_multiset.h"
    114.  
    115. int main()
    116. {
    117.     // 1. 构造函数
    118.     my_multiset<int>  multi_set1;
    119.     int nums[] = {1, 2, 3, 4, 5, 6};
    120.     my_multiset<int>  multi_set2(nums, nums+6);
    121.     my_multiset<int>  multi_set3(multi_set2.begin(), multi_set2.end());
    122.  
    123.     // 2. 容器修改
    124.     multi_set1.insert(1);
    125.     multi_set1.insert(2);
    126.     multi_set1.insert(3);
    127.     multi_set1.insert(3);
    128.     multi_set1.insert(3);
    129.     multi_set1.emplace(4);
    130.     multi_set1.emplace(5);
    131.  
    132.     multi_set1.erase(4);
    133.  
    134.     // 3. 容器查找
    135.     std::cout << multi_set1.count(3) << std::endl; // 1
    136.     auto item1_iter = multi_set1.find(3);
    137.  
    138.     std::cout << (item1_iter == multi_set1.end()) << ", " << *item1_iter << std::endl; // 0, 3
    139.  
    140.     for(auto iter = multi_set1.begin(); iter != multi_set1.end(); iter++)
    141.     {
    142.         std::cout << *iter << " "; // 1 2 3 3 3 5
    143.     }
    144.     std::cout << "" << std::endl;
    145.  
    146.     // 4. 容器容量
    147.     std::cout << multi_set1.size() << std::endl; // 6
    148.     std::cout << multi_set1.empty() << std::endl; // 0
    149.  
    150.     multi_set1.clear();
    151.  
    152.     std::cout << multi_set1.size() << std::endl; // 0
    153.     std::cout << multi_set1.empty() << std::endl; // 1
    154.     return 0;
    155. }
    156.  
     

         3. my_map
     

           
     

    1. // my_map.h
    2. #include 
    3. #include
    4.  
    5. template<typename Key, typename Value>
    6. class my_map
    7. {
    8.     typedef std::pair  ValueType;
    9.     typedef std::_Rb_tree, std::less> Rb_type;
    10.     typedef typename  Rb_type::iterator Iterator;
    11.  
    12. public:
    13.     my_map()
    14.     {
    15.  
    16.     }
    17.  
    18.     template<typename InputIterator>
    19.     my_map(InputIterator first, InputIterator last)
    20.     {
    21.         rb_tree._M_insert_unique(first, last);
    22.     }
    23.  
    24.     my_map(std::initializer_list init_list)
    25.     {
    26.         rb_tree._M_insert_unique(init_list.begin(), init_list.end());
    27.     }
    28.  
    29.     ~my_map()
    30.     {
    31.  
    32.     }
    33.  
    34.     Iterator begin()
    35.     {
    36.         return rb_tree.begin();
    37.     }
    38.  
    39.     Iterator end()
    40.     {
    41.         return rb_tree.end();
    42.     }
    43.  
    44.     void clear()
    45.     {
    46.         rb_tree.clear();
    47.     }
    48.  
    49.     void insert(ValueType& val)
    50.     {
    51.         rb_tree._M_insert_unique(val);
    52.     }
    53.  
    54.     void insert(ValueType&& val)
    55.     {
    56.         rb_tree._M_insert_unique(val);
    57.     }
    58.  
    59.     template<typename ... Args>
    60.     void emplace(Args&& ... args)
    61.     {
    62.         rb_tree._M_emplace_unique(std::forward(args)...);
    63.     }
    64.  
    65.     void erase(Iterator iter)
    66.     {
    67.         rb_tree.erase(iter);
    68.     }
    69.  
    70.     std::size_t count(Key& key)
    71.     {
    72.         return rb_tree.count(key);
    73.     }
    74.  
    75.     std::size_t count(Key&& key)
    76.     {
    77.         return rb_tree.count(key);
    78.     }
    79.  
    80.     Iterator find(Key& key)
    81.     {
    82.         return rb_tree.find(key);
    83.     }
    84.  
    85.     Iterator find(Key&& key)
    86.     {
    87.         return rb_tree.find(key);
    88.     }
    89.  
    90.     Value& at(Key& key)
    91.     {
    92.         return (*rb_tree.lower_bound(key)).second;
    93.     }
    94.  
    95.     Value& at(Key&& key)
    96.     {
    97.         return (*rb_tree.lower_bound(key)).second;
    98.     }
    99.  
    100.     Value& operator[](Key& key)
    101.     {
    102.         return (*rb_tree.lower_bound(key)).second;
    103.     }
    104.  
    105.     Value& operator[](Key&& key)
    106.     {
    107.         return (*rb_tree.lower_bound(key)).second;
    108.     }
    109.  
    110.     bool empty()
    111.     {
    112.         return rb_tree.empty();
    113.     }
    114.  
    115.     std::size_t size()
    116.     {
    117.         return rb_tree.size();
    118.     }
    119.  
    120.     void erase(Key& key)
    121.     {
    122.         rb_tree.erase(key);
    123.     }
    124.  
    125.     void erase(Key&& key)
    126.     {
    127.         rb_tree.erase(key);
    128.     }
    129.  
    130. private:
    131.     Rb_type rb_tree;
    132. };
    133.  
    134.  
    135. // main.cpp
    136.  
    137. int main()
    138. {
    139.     // 1. 构造函数
    140.     my_map<int, std::string>  unique_map1;
    141.     my_map<int, std::string>  unique_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};
    142.     my_map<int, std::string>  unique_map3(unique_map2.begin(), unique_map2.end());
    143.  
    144.     // 2. 容器修改
    145.     unique_map1.insert({5, "e"});
    146.     unique_map1.insert({6, "f"});
    147.     unique_map1.emplace(7, "g");
    148.     unique_map1.emplace(8, "h");
    149.     unique_map1.insert({16, "ff"});
    150.  
    151.     unique_map1.erase(16);
    152.  
    153.     // 3. 容器访问
    154.     std::cout << unique_map1.count(6) << std::endl; // 1
    155.     auto item_iter1 = unique_map1.find(6);
    156.     std::cout << (item_iter1 == unique_map1.end())  << std::endl; // 0
    157.     std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, f
    158.  
    159.     std::cout << unique_map1.at(7) << std::endl; // g
    160.     std::cout << unique_map1[7] << std::endl; // g
    161.  
    162.     // 4. 容器容量
    163.      std::cout << unique_map1.empty() << std::endl; // 0
    164.      std::cout << unique_map1.size() << std::endl; // 4
    165.  
    166.      unique_map1.clear();
    167.      std::cout << unique_map1.empty() << std::endl; // 1
    168.      std::cout << unique_map1.size() << std::endl; // 0
    169.     return 0;
    170. }
     

         4. my_multimap
     

    1. // my_multimap.h
    2.  
    3. #include 
    4. #include
    5.  
    6. template<typename Key, typename Value>
    7. class my_multimap
    8. {
    9.     typedef std::pair  ValueType;
    10.     typedef std::_Rb_tree, std::less> Rb_type;
    11.     typedef typename  Rb_type::iterator Iterator;
    12.  
    13. public:
    14.     my_multimap()
    15.     {
    16.  
    17.     }
    18.  
    19.     template<typename InputIterator>
    20.     my_multimap(InputIterator first, InputIterator last)
    21.     {
    22.         rb_tree._M_insert_equal(first, last);
    23.     }
    24.  
    25.     my_multimap(std::initializer_list init_list)
    26.     {
    27.         rb_tree._M_insert_equal(init_list.begin(), init_list.end());
    28.     }
    29.  
    30.     ~my_multimap()
    31.     {
    32.  
    33.     }
    34.  
    35.     Iterator begin()
    36.     {
    37.         return rb_tree.begin();
    38.     }
    39.  
    40.     Iterator end()
    41.     {
    42.         return rb_tree.end();
    43.     }
    44.  
    45.     void clear()
    46.     {
    47.         rb_tree.clear();
    48.     }
    49.  
    50.     void insert(ValueType& val)
    51.     {
    52.         rb_tree._M_insert_equal(val);
    53.     }
    54.  
    55.     void insert(ValueType&& val)
    56.     {
    57.         rb_tree._M_insert_equal(val);
    58.     }
    59.  
    60.     template<typename ... Args>
    61.     void emplace(Args&& ... args)
    62.     {
    63.         rb_tree._M_emplace_equal(std::forward(args)...);
    64.     }
    65.  
    66.     void erase(Iterator iter)
    67.     {
    68.         rb_tree.erase(iter);
    69.     }
    70.  
    71.     std::size_t count(Key& key)
    72.     {
    73.         return rb_tree.count(key);
    74.     }
    75.  
    76.     std::size_t count(Key&& key)
    77.     {
    78.         return rb_tree.count(key);
    79.     }
    80.  
    81.     Iterator find(Key& key)
    82.     {
    83.         return rb_tree.find(key);
    84.     }
    85.  
    86.     Iterator find(Key&& key)
    87.     {
    88.         return rb_tree.find(key);
    89.     }
    90.  
    91.     bool empty()
    92.     {
    93.         return rb_tree.empty();
    94.     }
    95.  
    96.     std::size_t size()
    97.     {
    98.         return rb_tree.size();
    99.     }
    100.  
    101.     void erase(Key& key)
    102.     {
    103.         rb_tree.erase(key);
    104.     }
    105.  
    106.     void erase(Key&& key)
    107.     {
    108.         rb_tree.erase(key);
    109.     }
    110.  
    111. private:
    112.     Rb_type rb_tree;
    113. };
    114.  
    115. // main.cpp
    116.  
    117. #include
    118. #include"my_multimap.h"
    119.  
    120. int main()
    121. {
    122.      // 1. 构造函数
    123.      my_multimap<int, std::string>  multi_map1;
    124.      my_multimap<int, std::string>  multi_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};
    125.      my_multimap<int, std::string>  multi_map3(multi_map2.begin(), multi_map2.end());
    126.  
    127.      // 2. 容器修改
    128.      multi_map1.insert({5, "e"});
    129.      multi_map1.insert({6, "f"});
    130.      multi_map1.emplace(7, "g");
    131.      multi_map1.emplace(7, "g");
    132.      multi_map1.emplace(7, "g");
    133.      multi_map1.emplace(8, "h");
    134.      multi_map1.insert({16, "ff"});
    135.  
    136.      multi_map1.erase(16);
    137.  
    138.      // 3. 容器访问
    139.      std::cout << multi_map1.count(6) << std::endl; // 1
    140.      auto item_iter1 = multi_map1.find(6);
    141.      std::cout << (item_iter1 == multi_map1.end())  << std::endl; // 0
    142.      std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, f
    143.  
    144.      // 4. 容器容量
    145.       std::cout << multi_map1.empty() << std::endl; // 0
    146.       std::cout << multi_map1.size() << std::endl; // 6
    147.  
    148.       multi_map1.clear();
    149.       std::cout << multi_map1.empty() << std::endl; // 1
    150.       std::cout << multi_map1.size() << std::endl; // 0
    151.     return 0;
    152. }
  • 相关阅读:
    网络安全（黑客）——自学2024
    花 30 美金请 AI 画家弄了个 logo，网友：画得非常好，下次别画了！
    java并发编程-实现线程的方法
    老卫带你学---leetcode刷题(240. 搜索二维矩阵 II)
    [Chrome插件开发]监听网页请求和响应
    三年，能否成为一名真正的架构师
    【MySQL】存储引擎
    中电金信技术实践｜Redis哨兵原理及安装部署分享
    Java 实例 - 字符串小写转大写和测试两个字符串区域是否相等
    ElasticSearch 之 文本搜索
  • 原文地址：https://blog.csdn.net/qq_33775774/article/details/133484870