做网站租用服务器企业建站 平台

一   关联式容器是什么？

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

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

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

二   底层原理与源码

1. 红黑树

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

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

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

红黑树核心法则：

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

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

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

4. 根节点必须是黑色的

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

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

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

#include <bits/stl_tree.h

 template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc = allocator<_Val> >class _Rb_tree{typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<_Rb_tree_node<_Val> >::other _Node_allocator;typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;protected:typedef _Rb_tree_node_base* 		_Base_ptr;typedef const _Rb_tree_node_base* 	_Const_Base_ptr;typedef _Rb_tree_node<_Val>* 		_Link_type;typedef const _Rb_tree_node<_Val>*	_Const_Link_type;......};

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

1. Key 为存储在红黑树中的关键字类型

2. Value 实际存储数据的类型

3. KeyOfValue 表示如何通过 Value 获取到 Key，通常是一个函数

4. Compare 则为比较元素大小的函数，可自定义实现

5. Alloc 分配内存的方式

#include<iostream>
#include <bits/stl_tree.h>int main()
{
//    template<typename _Tp>
//      struct _Identity
//      : public unary_function<_Tp,_Tp>
//      {
//        _Tp&
//        operator()(_Tp& __x) const
//        { return __x; }//        const _Tp&
//        operator()(const _Tp& __x) const
//        { return __x; }
//      };std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>> rb_tree;std::cout << rb_tree.empty() << std::endl;std::cout << rb_tree.size() << std::endl;// 1. 插入元素不允许重复.rb_tree._M_insert_unique(1);rb_tree._M_insert_unique(2);rb_tree._M_insert_unique(3);rb_tree._M_insert_unique(4);rb_tree._M_insert_unique(5);std::cout << rb_tree.size() << std::endl;rb_tree._M_insert_unique(1);std::cout << rb_tree.size() << std::endl;std::cout << "------" << std::endl;// 2. 插入元素允许重复.rb_tree._M_insert_equal(1);rb_tree._M_insert_equal(1);rb_tree._M_insert_equal(1);std::cout << rb_tree.size() << std::endl;for(auto iter = rb_tree.begin(); iter != rb_tree.end(); iter++){std::cout << *iter <<" ";}std::cout <<""<<std::endl;return 0;
}

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 源代码

template<typename _Key, typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<_Key> >class set{public:// typedefs://@{/// Public typedefs.typedef _Key     key_type;typedef _Key     value_type;typedef _Compare key_compare;typedef _Compare value_compare;typedef _Alloc   allocator_type;private:typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<_Key>::other _Key_alloc_type;typedef _Rb_tree<key_type, value_type, _Identity<value_type>,key_compare, _Key_alloc_type> _Rep_type;_Rep_type _M_t;  // Red-black tree representing set.typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;.....iteratorinsert(const_iterator __position, const value_type& __x){ return _M_t._M_insert_unique_(__position, __x); }.....
};

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

2.1.2 multiset 源码

 template <typename _Key, typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<_Key> >class multiset{
#ifdef _GLIBCXX_CONCEPT_CHECKS// concept requirementstypedef typename _Alloc::value_type		_Alloc_value_type;
# if __cplusplus < 201103L__glibcxx_class_requires(_Key, _SGIAssignableConcept)
# endif__glibcxx_class_requires4(_Compare, bool, _Key, _Key,_BinaryFunctionConcept)__glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
#endifpublic:// typedefs:typedef _Key     key_type;typedef _Key     value_type;typedef _Compare key_compare;typedef _Compare value_compare;typedef _Alloc   allocator_type;private:/// This turns a red-black tree into a [multi]set.typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<_Key>::other _Key_alloc_type;typedef _Rb_tree<key_type, value_type, _Identity<value_type>,key_compare, _Key_alloc_type> _Rep_type;/// The actual tree structure._Rep_type _M_t;typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;......iteratorinsert(const value_type& __x){ return _M_t._M_insert_equal(__x); }......};

通过源码可以看出，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 源码

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >class map{public:typedef _Key					key_type;typedef _Tp					mapped_type;typedef std::pair<const _Key, _Tp>		value_type;typedef _Compare					key_compare;typedef _Alloc					allocator_type;private:/// This turns a red-black tree into a [multi]map.typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<value_type>::other _Pair_alloc_type;typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,key_compare, _Pair_alloc_type> _Rep_type;/// The actual tree structure._Rep_type _M_t;typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;.....std::pair<iterator, bool>insert(const value_type& __x){ return _M_t._M_insert_unique(__x); }.....
};

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

2.2.2 multimap 源码

template <typename _Key, typename _Tp,typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >class multimap{public:typedef _Key					key_type;typedef _Tp					mapped_type;typedef std::pair<const _Key, _Tp>		value_type;typedef _Compare					key_compare;typedef _Alloc					allocator_type;private:/// This turns a red-black tree into a [multi]map.typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<value_type>::other _Pair_alloc_type;typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,key_compare, _Pair_alloc_type> _Rep_type;/// The actual tree structure._Rep_type _M_t;typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;......iteratorinsert(const value_type& __x){ return _M_t._M_insert_equal(__x); }......
};

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

2.2.3  Select1st

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

Select1st 源码如下：

 template<typename _Pair>struct _Select1st: public unary_function<_Pair, typename _Pair::first_type>{typename _Pair::first_type&operator()(_Pair& __x) const{ return __x.first; }const typename _Pair::first_type&operator()(const _Pair& __x) const{ return __x.first; }
};

三  使用

1. set/multiset

  1.1 set 函数

std::set - cppreference.com       

   1.1.1  构造函数

 template<typename _InputIterator>	set(_InputIterator __first, _InputIterator __last)

    1.1.2  容器修改

    1.1.3  容器查找

1.1.4  容器容量

1.1.5  示例

#include<iostream>
#include<set>int main()
{// 1. 构造函数std::set<int>  unique_set1;int nums[] = {1, 2, 3, 4, 5, 6};std::set<int>  unique_set2(nums, nums+6);std::set<int>  unique_set3(unique_set2.begin(), unique_set2.end());// 2. 容器修改unique_set1.insert(1);unique_set1.insert(2);unique_set1.insert(3);unique_set1.emplace(4);unique_set1.emplace(5);unique_set1.erase(4);// 3. 容器查找std::cout << unique_set1.count(3) << std::endl; // 1auto item1_iter = unique_set1.find(3);std::cout << (item1_iter == unique_set1.end()) << ", " << *item1_iter << std::endl; // 0 , 3auto item2_iter = unique_set1.lower_bound(4);std::cout << (item2_iter == unique_set1.end()) << ", " << *item2_iter << std::endl; // 0 , 3auto item3_iter = unique_set1.upper_bound(5);std::cout << (item3_iter == unique_set1.end()) << ", " << *item3_iter << std::endl;// 0 , 5for(auto iter = unique_set1.begin(); iter != unique_set1.end(); iter++){std::cout << *iter << " "; // 1. 2, 3, 5}std::cout << "" << std::endl;// 4. 容器容量std::cout << unique_set1.size() << std::endl; // 4std::cout << unique_set1.empty() << std::endl; // 0unique_set1.clear();std::cout << unique_set1.size() << std::endl; // 0std::cout << unique_set1.empty() << std::endl; // 1return 0;
}

 1.2 multiset 函数

    std::multiset - cppreference.com

 1.2.1  构造函数

 template<typename _InputIterator>	set(_InputIterator __first, _InputIterator __last)

    1.2.2  容器修改

    1.2.3  容器查找

1.2.4  容器容量

1.2.5  示例

#include<iostream>
#include<set>int main()
{// 1. 构造函数std::multiset<int>  multi_set1;int nums1[] = {1, 2, 3, 4, 5, 6};std::multiset<int>  multi_set2(nums1, nums1+6);std::multiset<int>  multi_set3(multi_set2.begin(), multi_set2.end());// 2. 容器修改multi_set1.insert(1);multi_set1.insert(2);multi_set1.insert(3);multi_set1.insert(3);multi_set1.insert(3);multi_set1.emplace(4);multi_set1.emplace(5);multi_set1.erase(4);// 3. 容器查找std::cout << multi_set1.count(3) << std::endl; // 3auto item1_iter = multi_set1.find(3);std::cout << (item1_iter == multi_set1.end()) << ", " << *item1_iter << std::endl; // 0, 3auto item2_iter = multi_set1.lower_bound(4);std::cout << (item2_iter == multi_set1.end()) << ", " << *item2_iter << std::endl; // 0, 5auto item3_iter = multi_set1.upper_bound(4);std::cout << (item3_iter == multi_set1.end()) << ", " << *item3_iter << std::endl; // 0, 5for(auto iter = multi_set1.begin(); iter != multi_set1.end(); iter++){std::cout << *iter << " "; // 1 2 3 3 3 5}std::cout << "" << std::endl;// 4. 容器容量std::cout << multi_set1.size() << std::endl; // 6std::cout << multi_set1.empty() << std::endl; // 0multi_set1.clear();std::cout << multi_set1.size() << std::endl; // 0std::cout << multi_set1.empty() << std::endl; // 1return 0;
}

2. map/multimap

2.1 map 函数

        2.1.1  构造函数

        2.1.2  容器修改

        2.1.3  容器访问

        2.1.4  容器容量

        2.1.5  示例

#include<iostream>
#include<map>int main()
{// 1. 构造函数std::map<int, std::string>  unique_map1;std::map<int, std::string>  unique_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};std::map<int, std::string>  unique_map3(unique_map2.begin(), unique_map2.end());// 2. 容器修改unique_map1.insert({5, "e"});unique_map1.insert({6, "f"});unique_map1.emplace(7, "g");unique_map1.emplace(8, "h");unique_map1.insert({16, "ff"});unique_map1.erase(16);// 3. 容器访问std::cout << unique_map1.count(6) << std::endl; // 1auto item_iter1 = unique_map1.find(6);std::cout << (item_iter1 == unique_map1.end())  << std::endl; // 0std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, fauto item_iter2 = unique_map1.lower_bound(6);std::cout << item_iter2->first << ", " << item_iter2->second << std::endl; // 6, fauto item_iter3 = unique_map1.upper_bound(7);std::cout << item_iter3->first << ", " << item_iter3->second << std::endl; // 8, hstd::cout << unique_map1.at(7) << std::endl; // gstd::cout << unique_map1[7] << std::endl; // g// 4. 容器容量std::cout << unique_map1.empty() << std::endl; // 0std::cout << unique_map1.size() << std::endl; // 4unique_map1.clear();std::cout << unique_map1.empty() << std::endl; // 1std::cout << unique_map1.size() << std::endl; // 0    return 0;
}

 2.2 multimap 函数

         2.1.1  构造函数

          2.1.2  容器修改

        2.1.3  容器访问

        2.1.4  容器容量

        2.1.5  示例

#include<iostream>
#include<map>int main()
{// 1. 构造函数std::multimap<int, std::string>  multi_map1;std::multimap<int, std::string>  multi_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};std::multimap<int, std::string>  multi_map3(multi_map2.begin(), multi_map2.end());// 2. 容器修改multi_map1.insert({5, "e"});multi_map1.insert({6, "f"});multi_map1.emplace(7, "g1");multi_map1.emplace(7, "g2");multi_map1.emplace(7, "g3");multi_map1.emplace(8, "h");multi_map1.insert({16, "ff"});multi_map1.erase(16);// 3. 容器访问std::cout << multi_map1.count(6) << std::endl; // 1auto item_iter1 = multi_map1.find(6);std::cout << (item_iter1 == multi_map1.end())  << std::endl; // 0std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, fauto item_iter2 = multi_map1.lower_bound(6);std::cout << item_iter2->first << ", " << item_iter2->second << std::endl; // 6, fauto item_iter3 = multi_map1.upper_bound(7);std::cout << item_iter3->first << ", " << item_iter3->second << std::endl; // 8, h// 4. 容器容量std::cout << multi_map1.empty() << std::endl; // 0std::cout << multi_map1.size() << std::endl; // 6multi_map1.clear();std::cout << multi_map1.empty() << std::endl; // 1std::cout << multi_map1.size() << std::endl; // 0return 0;
}

四  简单实现

      1. my_set

// my_set.h#include <bits/stl_tree.h>template<typename T>
class my_set
{typedef T ValueType;typedef T KeyType;typedef std::_Rb_tree<KeyType, ValueType, std::_Identity<ValueType>, std::less<KeyType>> Rb_type;typedef typename std::_Rb_tree<T, T, std::_Identity<T>, std::less<T>>::const_iterator  const_Iterator;public:my_set(){}template<typename InputIterator>my_set(InputIterator first, InputIterator last){rb_tree._M_insert_unique(first, last);}~my_set(){}const_Iterator begin(){return rb_tree.begin();}const_Iterator end(){return rb_tree.end();}void clear(){rb_tree.clear();}void insert(ValueType& val){rb_tree._M_insert_unique(val);}void insert(ValueType&& val){rb_tree._M_insert_unique(val);}template<typename ... Args>void emplace(Args&& ... args){rb_tree._M_emplace_unique(std::forward<Args>(args)...);}template<typename ... Args>void emplace(Args& ... args){rb_tree._M_emplace_unique(std::forward<Args>(args)...);}void erase(ValueType& val){rb_tree.erase(val);}void erase(ValueType&& val){rb_tree.erase(val);}std::size_t count(ValueType& val){return rb_tree.count(val);}std::size_t count(ValueType&& val){return rb_tree.count(val);}const_Iterator find(ValueType& val){return rb_tree.find(val);}const_Iterator find(ValueType&& val){return rb_tree.find(val);}bool empty(){return rb_tree.empty();}std::size_t size(){return rb_tree.size();}private:Rb_type rb_tree;};// main.cpp
int main()
{// 1. 构造函数my_set<int>  unique_set1;int nums[] = {1, 2, 3, 4, 5, 6};my_set<int>  unique_set2(nums, nums+6);my_set<int>  unique_set3(unique_set2.begin(), unique_set2.end());// 2. 容器修改unique_set1.insert(1);unique_set1.insert(2);unique_set1.insert(3);unique_set1.emplace(4);unique_set1.emplace(5);unique_set1.erase(4);// 3. 容器查找std::cout << unique_set1.count(3) << std::endl; // 1auto item1_iter = unique_set1.find(3);std::cout << (item1_iter == unique_set1.end()) << ", " << *item1_iter << std::endl; // 0. 3for(auto iter = unique_set1.begin(); iter != unique_set1.end(); iter++){std::cout << *iter << " "; // 1 2 3 5}std::cout << "" << std::endl;// 4. 容器容量std::cout << unique_set1.size() << std::endl; // 4std::cout << unique_set1.empty() << std::endl; // 0unique_set1.clear();std::cout << unique_set1.size() << std::endl; // 0std::cout << unique_set1.empty() << std::endl; // 1return 0;
}

      2. my_multiset

// my_multiset.h#include <bits/stl_tree.h>template<typename T>
class my_multiset
{typedef T ValueType;typedef T KeyType;typedef std::_Rb_tree<KeyType, ValueType, std::_Identity<ValueType>, std::less<KeyType>> Rb_type;typedef typename std::_Rb_tree<T, T, std::_Identity<T>, std::less<T>>::const_iterator  const_Iterator;public:my_multiset(){}template<typename InputIterator>my_multiset(InputIterator first, InputIterator last){rb_tree._M_insert_equal(first, last);}~my_multiset(){}const_Iterator begin(){return rb_tree.begin();}const_Iterator end(){return rb_tree.end();}void clear(){rb_tree.clear();}void insert(ValueType& val){rb_tree._M_insert_equal(val);}void insert(ValueType&& val){rb_tree._M_insert_equal(val);}template<typename ... Args>void emplace(Args&& ... args){rb_tree._M_emplace_unique(std::forward<Args>(args)...);}template<typename ... Args>void emplace(Args& ... args){rb_tree._M_emplace_unique(std::forward<Args>(args)...);}void erase(ValueType& val){rb_tree.erase(val);}void erase(ValueType&& val){rb_tree.erase(val);}std::size_t count(ValueType& val){return rb_tree.count(val);}std::size_t count(ValueType&& val){return rb_tree.count(val);}const_Iterator find(ValueType& val){return rb_tree.find(val);}const_Iterator find(ValueType&& val){return rb_tree.find(val);}bool empty(){return rb_tree.empty();}std::size_t size(){return rb_tree.size();}private:Rb_type rb_tree;};// main.cpp
#include<iostream>
#include"my_multiset.h"int main()
{// 1. 构造函数my_multiset<int>  multi_set1;int nums[] = {1, 2, 3, 4, 5, 6};my_multiset<int>  multi_set2(nums, nums+6);my_multiset<int>  multi_set3(multi_set2.begin(), multi_set2.end());// 2. 容器修改multi_set1.insert(1);multi_set1.insert(2);multi_set1.insert(3);multi_set1.insert(3);multi_set1.insert(3);multi_set1.emplace(4);multi_set1.emplace(5);multi_set1.erase(4);// 3. 容器查找std::cout << multi_set1.count(3) << std::endl; // 1auto item1_iter = multi_set1.find(3);std::cout << (item1_iter == multi_set1.end()) << ", " << *item1_iter << std::endl; // 0, 3for(auto iter = multi_set1.begin(); iter != multi_set1.end(); iter++){std::cout << *iter << " "; // 1 2 3 3 3 5}std::cout << "" << std::endl;// 4. 容器容量std::cout << multi_set1.size() << std::endl; // 6std::cout << multi_set1.empty() << std::endl; // 0multi_set1.clear();std::cout << multi_set1.size() << std::endl; // 0std::cout << multi_set1.empty() << std::endl; // 1return 0;
}

     3. my_map

// my_map.h
#include <bits/stl_tree.h>
#include<initializer_list>template<typename Key, typename Value>
class my_map
{typedef std::pair<Key, Value>  ValueType;typedef std::_Rb_tree<Key, ValueType, std::_Select1st<ValueType>, std::less<Key>> Rb_type;typedef typename  Rb_type::iterator Iterator;public:my_map(){}template<typename InputIterator>my_map(InputIterator first, InputIterator last){rb_tree._M_insert_unique(first, last);}my_map(std::initializer_list<ValueType> init_list){rb_tree._M_insert_unique(init_list.begin(), init_list.end());}~my_map(){}Iterator begin(){return rb_tree.begin();}Iterator end(){return rb_tree.end();}void clear(){rb_tree.clear();}void insert(ValueType& val){rb_tree._M_insert_unique(val);}void insert(ValueType&& val){rb_tree._M_insert_unique(val);}template<typename ... Args>void emplace(Args&& ... args){rb_tree._M_emplace_unique(std::forward<Args>(args)...);}void erase(Iterator iter){rb_tree.erase(iter);}std::size_t count(Key& key){return rb_tree.count(key);}std::size_t count(Key&& key){return rb_tree.count(key);}Iterator find(Key& key){return rb_tree.find(key);}Iterator find(Key&& key){return rb_tree.find(key);}Value& at(Key& key){return (*rb_tree.lower_bound(key)).second;}Value& at(Key&& key){return (*rb_tree.lower_bound(key)).second;}Value& operator[](Key& key){return (*rb_tree.lower_bound(key)).second;}Value& operator[](Key&& key){return (*rb_tree.lower_bound(key)).second;}bool empty(){return rb_tree.empty();}std::size_t size(){return rb_tree.size();}void erase(Key& key){rb_tree.erase(key);}void erase(Key&& key){rb_tree.erase(key);}private:Rb_type rb_tree;
};// main.cppint main()
{// 1. 构造函数my_map<int, std::string>  unique_map1;my_map<int, std::string>  unique_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};my_map<int, std::string>  unique_map3(unique_map2.begin(), unique_map2.end());// 2. 容器修改unique_map1.insert({5, "e"});unique_map1.insert({6, "f"});unique_map1.emplace(7, "g");unique_map1.emplace(8, "h");unique_map1.insert({16, "ff"});unique_map1.erase(16);// 3. 容器访问std::cout << unique_map1.count(6) << std::endl; // 1auto item_iter1 = unique_map1.find(6);std::cout << (item_iter1 == unique_map1.end())  << std::endl; // 0std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, fstd::cout << unique_map1.at(7) << std::endl; // gstd::cout << unique_map1[7] << std::endl; // g// 4. 容器容量std::cout << unique_map1.empty() << std::endl; // 0std::cout << unique_map1.size() << std::endl; // 4unique_map1.clear();std::cout << unique_map1.empty() << std::endl; // 1std::cout << unique_map1.size() << std::endl; // 0return 0;
}

     4. my_multimap

// my_multimap.h#include <bits/stl_tree.h>
#include<initializer_list>template<typename Key, typename Value>
class my_multimap
{typedef std::pair<Key, Value>  ValueType;typedef std::_Rb_tree<Key, ValueType, std::_Select1st<ValueType>, std::less<Key>> Rb_type;typedef typename  Rb_type::iterator Iterator;public:my_multimap(){}template<typename InputIterator>my_multimap(InputIterator first, InputIterator last){rb_tree._M_insert_equal(first, last);}my_multimap(std::initializer_list<ValueType> init_list){rb_tree._M_insert_equal(init_list.begin(), init_list.end());}~my_multimap(){}Iterator begin(){return rb_tree.begin();}Iterator end(){return rb_tree.end();}void clear(){rb_tree.clear();}void insert(ValueType& val){rb_tree._M_insert_equal(val);}void insert(ValueType&& val){rb_tree._M_insert_equal(val);}template<typename ... Args>void emplace(Args&& ... args){rb_tree._M_emplace_equal(std::forward<Args>(args)...);}void erase(Iterator iter){rb_tree.erase(iter);}std::size_t count(Key& key){return rb_tree.count(key);}std::size_t count(Key&& key){return rb_tree.count(key);}Iterator find(Key& key){return rb_tree.find(key);}Iterator find(Key&& key){return rb_tree.find(key);}bool empty(){return rb_tree.empty();}std::size_t size(){return rb_tree.size();}void erase(Key& key){rb_tree.erase(key);}void erase(Key&& key){rb_tree.erase(key);}private:Rb_type rb_tree;
};// main.cpp#include<iostream>
#include"my_multimap.h"int main()
{// 1. 构造函数my_multimap<int, std::string>  multi_map1;my_multimap<int, std::string>  multi_map2 = {{1, "a"}, {22, "bb"}, {3, "c"}};my_multimap<int, std::string>  multi_map3(multi_map2.begin(), multi_map2.end());// 2. 容器修改multi_map1.insert({5, "e"});multi_map1.insert({6, "f"});multi_map1.emplace(7, "g");multi_map1.emplace(7, "g");multi_map1.emplace(7, "g");multi_map1.emplace(8, "h");multi_map1.insert({16, "ff"});multi_map1.erase(16);// 3. 容器访问std::cout << multi_map1.count(6) << std::endl; // 1auto item_iter1 = multi_map1.find(6);std::cout << (item_iter1 == multi_map1.end())  << std::endl; // 0std::cout << item_iter1->first << ", " << item_iter1->second << std::endl; // 6, f// 4. 容器容量std::cout << multi_map1.empty() << std::endl; // 0std::cout << multi_map1.size() << std::endl; // 6multi_map1.clear();std::cout << multi_map1.empty() << std::endl; // 1std::cout << multi_map1.size() << std::endl; // 0return 0;
}