C++ STL 容器设计实现 -- map/set
6、map/multimap/set/multiset
6.1、rb_tree
map 和 multimap 以及 set 和 multiset 底层数据结构都是红黑树，如果对红黑树数据结构感兴趣，可以参考关于红黑树的分享
这里简单介绍一下 map 和 multimap 底层红黑树的布局。rb_tree 有一个 rb_tree_impl 类型的数据成员，rb_tree_impl 实现红黑树，rb_tree 是对 rb_tree_impl 的封装。
header 是实现的技巧，header.parent 保存根结点 root，header.left 保存最左元素，是中序遍历的首元素，header.right 保存最右元素，是中序遍历的最末元素，root->parent 指向的是 header。
向 rbtree 插入元素时，需要确定插入的位置，保持二叉搜索树的性质。rbtree 提供两个接口：_M_get_insert_unique_pos() 和 _M_get_insert_equal_pos() 函数。前者适用于插入后所有元素必须唯一，否则插入失败；后置没有这个限制，是普通插入情况。
_M_get_insert_equal_pos() 函数定义如下，比较直观。在 rbtree 从根节点开始搜索，如果当前结点大于 k，在其左子树继续搜索，否则在其右子树搜索，直到 x 为空，k 插入 y 的左子树或者右子树。
/// stl_tree.h
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_equal_pos(const key_type& __k)
{
typedef pair<_Base_ptr, _Base_ptr> _Res;
_Link_type __x = _M_begin();
_Base_ptr __y = _M_end();
while (__x != 0)
{
__y = __x;
__x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
} // x == null，退出循环
return _Res(__x, __y);
}
_M_get_insert_unique_pos() 函数就复杂一点，因为要确保插入 k 之后，rbtree 没有重复的节点。首先和 _M_get_insert_equal_pos() 函数相同，也是找到执行插入的结点 y。然后检查，rbtree 中是否已经存在某个节点，其值和 k 相同。
- 如果 k 插入到 y 的左子树，k < y 已经符合，还需要核查 k 是否大于 y 中序遍历前一个结点的值；
- 如果 k 插入到 y 的右子树，需要确认 y < k；
/// stl_tree.h
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_unique_pos(const key_type& __k)
{
typedef pair<_Base_ptr, _Base_ptr> _Res;
_Link_type __x = _M_begin();
_Base_ptr __y = _M_end();
bool __comp = true;
while (__x != 0)
{
__y = __x;
__comp = _M_impl._M_key_compare(__k, _S_key(__x)); // k < x/y --> true
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
if (__comp) // k < y，插入后 y->left = x
{
if (__j == begin())
return _Res(__x, __y);
else
--__j; // 找到 y 中序遍历的前节点
}
if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) // j < k
return _Res(__x, __y);
return _Res(__j._M_node, 0);
}
为了方便处理插入，rbtree 定义了 _Audo_node 类，使用 RAII，管理 node 的申请于释放。
/// stl_tree.h
// An RAII _Node handle
struct _Auto_node
{
template<typename... _Args>
_Auto_node(_Rb_tree& __t, _Args&&... __args)
: _M_t(__t),
_M_node(__t._M_create_node(std::forward<_Args>(__args)...))
{ }
~_Auto_node()
{
if (_M_node)
_M_t._M_drop_node(_M_node);
}
_Auto_node(_Auto_node&& __n)
: _M_t(__n._M_t), _M_node(__n._M_node)
{ __n._M_node = nullptr; }
const _Key&
_M_key() const
{ return _S_key(_M_node); }
iterator
_M_insert(pair<_Base_ptr, _Base_ptr> __p)
{
auto __it = _M_t._M_insert_node(__p.first, __p.second, _M_node);
_M_node = nullptr;
return __it;
}
iterator
_M_insert_equal_lower()
{
auto __it = _M_t._M_insert_equal_lower_node(_M_node);
_M_node = nullptr;
return __it;
}
_Rb_tree& _M_t;
_Link_type _M_node;
};
6.2、map
map 就是对 rbtree 的封装，只有一个 rbtree 类型的数据成员。rbtree 节点数据域 vaule_type 是 std::pair 类型，first 和 second 分别存放 key 和 value。
/// stl_map.h
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;
public:
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
class value_compare
: public std::binary_function<value_type, value_type, bool>
{
friend class map<_Key, _Tp, _Compare, _Alloc>;
protected:
_Compare comp;
value_compare(_Compare __c)
: comp(__c) { }
public:
bool operator()(const value_type& __x, const value_type& __y) const
{ return comp(__x.first, __y.first); }
};
#pragma GCC diagnostic pop
private:
/// This turns a red-black tree into a [multi]map.
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<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;
#if __cplusplus >= 201703L
template<typename _Up, typename _Vp = remove_reference_t<_Up>>
static constexpr bool __usable_key
= __or_v<is_same<const _Vp, const _Key>,
__and_<is_scalar<_Vp>, is_scalar<_Key>>>;
#endif
public:
// many of these are specified differently in ISO, but the following are
// "functionally equivalent"
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef typename _Rep_type::iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
typedef typename _Rep_type::reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
#if __cplusplus > 201402L
using node_type = typename _Rep_type::node_type;
using insert_return_type = typename _Rep_type::insert_return_type;
#endif
/* ... */
};
6.2.1、operator[]
operator[] 用于访问 map 元素，如果元素不存在，则执行插入操作。
/// stl_map.h
mapped_type&
operator[](const key_type& __k)
{
// concept requirements
__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
iterator __i = lower_bound(__k);
// __i->first is greater than or equivalent to __k.
if (__i == end() || key_comp()(__k, (*__i).first))
#if __cplusplus >= 201103L
__i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
std::tuple<const key_type&>(__k),
std::tuple<>());
#else
__i = insert(__i, value_type(__k, mapped_type()));
#endif
return (*__i).second;
}
_M_emplace_hint_unique() 函数首先调用 _M_get_insert_hint_unique_pos() 查找插入位置，如果可以插入，则执行插入操作。
/// stl_tree.h
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template<typename... _Args>
auto
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
-> iterator
{
_Auto_node __z(*this, std::forward<_Args>(__args)...);
auto __res = _M_get_insert_hint_unique_pos(__pos, __z._M_key());
if (__res.second)
return __z._M_insert(__res);
return iterator(__res.first);
}
_M_get_insert_hint_unique_pos() 函数会先处理 easy-case
- 可以插入在最右节点右子树，插入
- 可以插入在最左节点左子树，插入
- k < pos && --pos < k，插入
- pos < k && ++pos > k，插入
- 其他情况，调用 _M_get_insert_unique_pos() 函数搜索插入位置。
上面 -- 表示中序遍历前一个节点，++ 表示中序遍历后一个节点。
/// stl_tree.h
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_hint_unique_pos(const_iterator __position,
const key_type& __k)
{
iterator __pos = __position._M_const_cast();
typedef pair<_Base_ptr, _Base_ptr> _Res;
// end()
if (__pos._M_node == _M_end())
{
if (size() > 0
&& _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
return _Res(0, _M_rightmost()); // 在最右节点右子树插入
else
return _M_get_insert_unique_pos(__k); // 检索
}
else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
{
// First, try before...
iterator __before = __pos;
if (__pos._M_node == _M_leftmost()) // begin()
return _Res(_M_leftmost(), _M_leftmost()); // 在最左节点左子树插入
else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
{ // k < pos && --pos < k
if (_S_right(__before._M_node) == 0)
return _Res(0, __before._M_node);
else
return _Res(__pos._M_node, __pos._M_node);
}
else
return _M_get_insert_unique_pos(__k);
}
else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
{
// ... then try after.
iterator __after = __pos;
if (__pos._M_node == _M_rightmost())
return _Res(0, _M_rightmost()); // 在最右节点右子树插入
else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
{ // pos < k && ++pos > k
if (_S_right(__pos._M_node) == 0)
return _Res(0, __pos._M_node);
else
return _Res(__after._M_node, __after._M_node);
}
else
return _M_get_insert_unique_pos(__k);
}
else
// Equivalent keys.
return _Res(__pos._M_node, 0);
}
6.2.2、insert()
insert() 函数返回一个 std::pair 遍历，first 是一个迭代器，second 是一个 bool 遍历，表示插入是否成功。如果成功，first 指向插入的元素。
/// stl_map.h
std::pair<iterator, bool>
insert(value_type&& __x)
{ return _M_t._M_insert_unique(std::move(__x)); }
_M_insert_unique() 函数逻辑比较简单，先调用 _M_get_insert_unique_pos() 函数搜索插入位置，如果可以插入，就执行插入函数。
/// stl_tree.h
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
template<typename _Arg>
#endif
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator, bool>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
#if __cplusplus >= 201103L
_M_insert_unique(_Arg&& __v)
#else
/* ... */
#endif
{
typedef pair<iterator, bool> _Res;
pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_unique_pos(_KeyOfValue()(__v));
if (__res.second)
{
_Alloc_node __an(*this);
return _Res(_M_insert_(__res.first, __res.second,
_GLIBCXX_FORWARD(_Arg, __v), __an),
true);
}
return _Res(iterator(__res.first), false); // 插入失败
}
6.3、multimap
multimap 和 map 定义相同，知识处理插入操作时，不检查插入后是否有相同的元素。
/// stl_multimap.h
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:
#ifdef _GLIBCXX_CONCEPT_CHECKS
// concept requirements
typedef typename _Alloc::value_type _Alloc_value_type;
# if __cplusplus < 201103L
__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
# endif
__glibcxx_class_requires4(_Compare, bool, _Key, _Key,
_BinaryFunctionConcept)
__glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
#endif
#if __cplusplus >= 201103L
#if __cplusplus > 201703L || defined __STRICT_ANSI__
static_assert(is_same<typename _Alloc::value_type, value_type>::value,
"std::multimap must have the same value_type as its allocator");
#endif
#endif
public:
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
class value_compare
: public std::binary_function<value_type, value_type, bool>
{
friend class multimap<_Key, _Tp, _Compare, _Alloc>;
protected:
_Compare comp;
value_compare(_Compare __c)
: comp(__c) { }
public:
bool operator()(const value_type& __x, const value_type& __y) const
{ return comp(__x.first, __y.first); }
};
#pragma GCC diagnostic pop
private:
/// This turns a red-black tree into a [multi]map.
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<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;
public:
// many of these are specified differently in ISO, but the following are
// "functionally equivalent"
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef typename _Rep_type::iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
typedef typename _Rep_type::reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
#if __cplusplus > 201402L
using node_type = typename _Rep_type::node_type;
#endif
/* ... */
};
6.3.1、insert
insert() 函数返回一个迭代器，指向插入的元素。
/// stl_multimap.h
iterator
insert(const value_type& __x)
{ return _M_t._M_insert_equal(__x); }
iterator
insert(value_type&& __x)
{ return _M_t._M_insert_equal(std::move(__x)); }
_M_insert_equal() 函数首先调用 _M_get_insert_equal_pos() 函数检索插入位置，然后执行插入。
/// stl_tree.h
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
template<typename _Arg>
#endif
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
#if __cplusplus >= 201103L
_M_insert_equal(_Arg&& __v)
#else
/* ... */
#endif
{
pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_equal_pos(_KeyOfValue()(__v));
_Alloc_node __an(*this);
return _M_insert_(__res.first, __res.second,
_GLIBCXX_FORWARD(_Arg, __v), __an);
}
6.3.2、lower_bound()
lower_bound() 函数返回一个迭代器，迭代器指向第一个不小于 x 的元素。
/// stl_multimap.h
iterator
lower_bound(const key_type& __x)
{ return _M_t.lower_bound(__x); }
rbtree 红黑树 lower_bound() 函数实现比较简单，当 k <= x 时，在左子树查找，否则在右子树查找。与 k 相等的元素，就在 y 的右边，也就是中序遍历在 y 的后续节点。
/// stl_tree.h
iterator
lower_bound(const key_type& __k)
{ return _M_lower_bound(_M_begin(), _M_end(), __k); }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_lower_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k)
{
while (__x != 0)
if (!_M_impl._M_key_compare(_S_key(__x), __k)) // k <= x
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x); // x < k
return iterator(__y);
}
6.3.3、upper_bound()
upper_bound() 函数返回一个迭代器，迭代器指向第一个大于 x 的元素。
/// stl_multimap.h
iterator
upper_bound(const key_type& __x)
{ return _M_t.upper_bound(__x); }
_M_upper_bound() 函数当 k < x 时，在左子树查找，否则在右子树查找。这样子，与 k 相等元素，在 y 的左边，中序遍历时，是 y 的前序节点。
/// stl_tree.h
iterator
upper_bound(const key_type& __k)
{ return _M_upper_bound(_M_begin(), _M_end(), __k); }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_upper_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k)
{
while (__x != 0)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
6.4、set
set 和 map 的定义基本相同，唯一的不同是 rbtree 的元素类型是 value_type。除此之外，其他定义相同，没有特殊之处。
/// stl_set.h
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>::template
rebind<_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;
public:
///@{
/// Iterator-related typedefs.
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 103. set::iterator is required to be modifiable,
// but this allows modification of keys.
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
///@}
#if __cplusplus > 201402L
using node_type = typename _Rep_type::node_type;
using insert_return_type = typename _Rep_type::insert_return_type;
#endif
/* ... */
};
insert() 函数也和 map::insert 定义相同
/// stl_set.h
std::pair<iterator, bool>
insert(const value_type& __x)
{
std::pair<typename _Rep_type::iterator, bool> __p =
_M_t._M_insert_unique(__x);
return std::pair<iterator, bool>(__p.first, __p.second);
}
6.5、multiset
multiset 也和 multimap 定义基本相同，只是 rbtree 节点元素是 value_type。
/// stl_multiset.h
template <typename _Key, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<_Key> >
class multiset
{
public:
// 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>::template
rebind<_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;
public:
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 103. set::iterator is required to be modifiable,
// but this allows modification of keys.
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
#if __cplusplus > 201402L
using node_type = typename _Rep_type::node_type;
#endif
/* ... */
};
insert()/lower_bound()/upper_bound() 函数也和 multimap 对应的相同。
/// stl_multiset.h
iterator
insert(const value_type& __x)
{ return _M_t._M_insert_equal(__x); }
iterator
lower_bound(const key_type& __x)
{ return _M_t.lower_bound(__x); }
iterator
upper_bound(const key_type& __x)
{ return _M_t.upper_bound(__x); }
#晒一晒我的offer##实习，投递多份简历没人回复怎么办##c++#C/C++基础 文章被收录于专栏
C/C++ 语言基础
