深圳网站专业建设公司,企业查询显示利好什么意思,深圳市建设局质监站官方网站,零基础学wordpress pdf下载一 关联式容器是什么#xff1f;
c 中有两种容器类型#xff1a;关联式容器与序列式容器#xff08;顺序容器#xff09;
关联式中的容器是按照关键字来存储与访问的#xff0c;序列式容器#xff08;顺序容器#xff09;则是元素在容器中的相对位置来存储与访问的。…一 关联式容器是什么
c 中有两种容器类型关联式容器与序列式容器顺序容器
关联式中的容器是按照关键字来存储与访问的序列式容器顺序容器则是元素在容器中的相对位置来存储与访问的。
c 中的关联式容器主要是 set 与 map. 二 底层原理与源码
1. 红黑树 红黑树是一种平衡二叉搜索树balanced binary search tree即插入或者删除元素后依然能够保证树是平衡的所谓平衡意味着任意一个父节点其左右子树的深度相差不会太多。
平衡树也称 AVL 树任意节点的左右个子树的高度差不超过1。
这一特性也保证了在插入元素与查找元素时的效率。
红黑树核心法则 1. 每个节点要么是红色要么是黑色 2. 红黑树中的任意节点到达其每个叶子节点的黑色高度是相同的黑色高度值得是某个节点到达叶子节点的黑色节点的个数因叶子节点是黑色的所以也包括叶子节点 3. 两个红色节点之间不能相邻即对于任意一个红色节点而言其左右子节点定不是红色 4. 根节点必须是黑色的 5. 每个红色节点的两个子节点一定是黑色的 【红黑树】的详细实现(C)附代码 - 知乎 (zhihu.com) c 中的红黑树源代码位置
#include bits/stl_tree.htemplatetypename _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 分配内存的方式 #includeiostream
#include bits/stl_tree.hint main()
{
// templatetypename _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_treeint, int, std::_Identityint, std::lessint 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 源代码
templatetypename _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_treekey_type, value_type, _Identityvalue_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_treekey_type, value_type, _Identityvalue_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::allocatorstd::pairconst _Key, _Tp class map{public:typedef _Key key_type;typedef _Tp mapped_type;typedef std::pairconst _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::templaterebindvalue_type::other _Pair_alloc_type;typedef _Rb_treekey_type, value_type, _Select1stvalue_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::pairiterator, boolinsert(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::allocatorstd::pairconst _Key, _Tp class multimap{public:typedef _Key key_type;typedef _Tp mapped_type;typedef std::pairconst _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::templaterebindvalue_type::other _Pair_alloc_type;typedef _Rb_treekey_type, value_type, _Select1stvalue_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 源码如下 templatetypename _Pairstruct _Select1st: public unary_function_Pair, typename _Pair::first_type{typename _Pair::first_typeoperator()(_Pair __x) const{ return __x.first; }const typename _Pair::first_typeoperator()(const _Pair __x) const{ return __x.first; }
};
三 使用
1. set/multiset 1.1 set 函数
std::set - cppreference.com 1.1.1 构造函数
函数说明set()空构造函数 templatetypename _InputIterator set(_InputIterator __first, _InputIterator __last) range 构造函数 1.1.2 容器修改
函数说明clear()清空容器insert插入元素emplace插入元素可以只传入元素类的构造函数所需参数erase移除指定位置的元素 1.1.3 容器查找
函数说明count返回指定元素的个数begin()返回首元素的 iteratorend()返回尾元素下一地址的 iterator该 iterator 不能获取元素find查找指定元素若是存在返回指向该元素的 iterator若是不存在则返回尾 iteratorlower_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 示例
#includeiostream
#includesetint main()
{// 1. 构造函数std::setint unique_set1;int nums[] {1, 2, 3, 4, 5, 6};std::setint unique_set2(nums, nums6);std::setint 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()空构造函数 templatetypename _InputIterator set(_InputIterator __first, _InputIterator __last) range 构造函数 1.2.2 容器修改
函数说明clear()清空容器insert插入元素emplace插入元素可以只传入元素类的构造函数所需参数erase移除指定位置的元素 1.2.3 容器查找
函数说明count返回指定元素的个数begin()返回首元素的 iteratorend()返回尾元素下一地址的 iterator该 iterator 不能获取元素find查找指定元素若是存在返回指向该元素的 iterator若是不存在则返回尾 iteratorlower_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 示例
#includeiostream
#includesetint main()
{// 1. 构造函数std::multisetint multi_set1;int nums1[] {1, 2, 3, 4, 5, 6};std::multisetint multi_set2(nums1, nums16);std::multisetint 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_listvalue_type init)initializer list 构造函数 2.1.2 容器修改
函数说明clear()清空容器insert插入元素emplace插入元素可以只传入元素类的构造函数所需参数erase移除指定位置的元素 2.1.3 容器访问
函数说明count返回指定 key 元素的个数begin()返回首元素的 iteratorend()返回尾元素下一地址的 iterator该 iterator 不能获取元素find查找指定元素若是存在返回指向该元素的 iterator若是不存在则返回尾 iteratorlower_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 示例
#includeiostream
#includemapint main()
{// 1. 构造函数std::mapint, std::string unique_map1;std::mapint, std::string unique_map2 {{1, a}, {22, bb}, {3, c}};std::mapint, 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_listvalue_type init)initializer list 构造函数 2.1.2 容器修改
函数说明clear()清空容器insert插入元素emplace插入元素可以只传入元素类的构造函数所需参数erase移除指定位置的元素 2.1.3 容器访问
函数说明count返回指定 key 元素的个数begin()返回首元素的 iteratorend()返回尾元素下一地址的 iterator该 iterator 不能获取元素find查找指定元素若是存在返回指向该元素的 iterator若是不存在则返回尾 iteratorlower_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 示例
#includeiostream
#includemapint main()
{// 1. 构造函数std::multimapint, std::string multi_map1;std::multimapint, std::string multi_map2 {{1, a}, {22, bb}, {3, c}};std::multimapint, 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.htemplatetypename T
class my_set
{typedef T ValueType;typedef T KeyType;typedef std::_Rb_treeKeyType, ValueType, std::_IdentityValueType, std::lessKeyType Rb_type;typedef typename std::_Rb_treeT, T, std::_IdentityT, std::lessT::const_iterator const_Iterator;public:my_set(){}templatetypename InputIteratormy_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);}templatetypename ... Argsvoid emplace(Args ... args){rb_tree._M_emplace_unique(std::forwardArgs(args)...);}templatetypename ... Argsvoid emplace(Args ... args){rb_tree._M_emplace_unique(std::forwardArgs(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_setint unique_set1;int nums[] {1, 2, 3, 4, 5, 6};my_setint unique_set2(nums, nums6);my_setint 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.htemplatetypename T
class my_multiset
{typedef T ValueType;typedef T KeyType;typedef std::_Rb_treeKeyType, ValueType, std::_IdentityValueType, std::lessKeyType Rb_type;typedef typename std::_Rb_treeT, T, std::_IdentityT, std::lessT::const_iterator const_Iterator;public:my_multiset(){}templatetypename InputIteratormy_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);}templatetypename ... Argsvoid emplace(Args ... args){rb_tree._M_emplace_unique(std::forwardArgs(args)...);}templatetypename ... Argsvoid emplace(Args ... args){rb_tree._M_emplace_unique(std::forwardArgs(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
#includeiostream
#includemy_multiset.hint main()
{// 1. 构造函数my_multisetint multi_set1;int nums[] {1, 2, 3, 4, 5, 6};my_multisetint multi_set2(nums, nums6);my_multisetint 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
#includeinitializer_listtemplatetypename Key, typename Value
class my_map
{typedef std::pairKey, Value ValueType;typedef std::_Rb_treeKey, ValueType, std::_Select1stValueType, std::lessKey Rb_type;typedef typename Rb_type::iterator Iterator;public:my_map(){}templatetypename InputIteratormy_map(InputIterator first, InputIterator last){rb_tree._M_insert_unique(first, last);}my_map(std::initializer_listValueType 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);}templatetypename ... Argsvoid emplace(Args ... args){rb_tree._M_emplace_unique(std::forwardArgs(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_mapint, std::string unique_map1;my_mapint, std::string unique_map2 {{1, a}, {22, bb}, {3, c}};my_mapint, 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
#includeinitializer_listtemplatetypename Key, typename Value
class my_multimap
{typedef std::pairKey, Value ValueType;typedef std::_Rb_treeKey, ValueType, std::_Select1stValueType, std::lessKey Rb_type;typedef typename Rb_type::iterator Iterator;public:my_multimap(){}templatetypename InputIteratormy_multimap(InputIterator first, InputIterator last){rb_tree._M_insert_equal(first, last);}my_multimap(std::initializer_listValueType 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);}templatetypename ... Argsvoid emplace(Args ... args){rb_tree._M_emplace_equal(std::forwardArgs(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#includeiostream
#includemy_multimap.hint main()
{// 1. 构造函数my_multimapint, std::string multi_map1;my_multimapint, std::string multi_map2 {{1, a}, {22, bb}, {3, c}};my_multimapint, 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;
}
