一 关联式容器是什么？
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 构造函数
| 函数 | 说明 |
| set() | 空构造函数 |
template<typename _InputIterator> 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_bound | Iterator 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 示例
#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 构造函数
| 函数 | 说明 |
| set() | 空构造函数 |
template<typename _InputIterator> 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_bound | Iterator 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 示例
#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 构造函数
| 函数 | 说明 |
| map | 默认构造函数 |
| template< class InputIt > map( InputIt first, InputIt last) | range 构造函数 |
| map( std::initializer_list<value_type> init) | initializer list 构造函数 |
2.1.2 容器修改
| 函数 | 说明 |
| clear() | 清空容器 |
| insert | 插入元素 |
| emplace | 插入元素，可以只传入元素类的构造函数所需参数 |
| erase | 移除指定位置的元素 |
2.1.3 容器访问
| 函数 | 说明 |
| count | 返回指定 key 元素的个数 |
| begin() | 返回首元素的 iterator |
| end() | 返回尾元素下一地址的 iterator，该 iterator 不能获取元素 |
| find | 查找指定元素，若是存在返回指向该元素的 iterator；若是不存在，则返回尾 iterator |
| lower_bound | Iterator 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. |
| at | Returns 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 示例
#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 构造函数
| 函数 | 说明 |
| map | 默认构造函数 |
| template< class InputIt > map( InputIt first, InputIt last) | range 构造函数 |
| map( std::initializer_list<value_type> init) | initializer list 构造函数 |
2.1.2 容器修改
| 函数 | 说明 |
| clear() | 清空容器 |
| insert | 插入元素 |
| emplace | 插入元素，可以只传入元素类的构造函数所需参数 |
| erase | 移除指定位置的元素 |
2.1.3 容器访问
| 函数 | 说明 |
| count | 返回指定 key 元素的个数 |
| begin() | 返回首元素的 iterator |
| end() | 返回尾元素下一地址的 iterator，该 iterator 不能获取元素 |
| find | 查找指定元素，若是存在返回指向该元素的 iterator；若是不存在，则返回尾 iterator |
| lower_bound | Iterator 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 示例
#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;
}
