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++ 语言基础

全部评论

相关推荐

11-04 15:22
西北工业大学 Java
网易HR面面经
2025年11月04日&nbsp;网易HR面全程10分钟。请你先做个自我介绍。实习中你主要负责哪些板块的内容，以及核心产出是怎样的？你实习所在的部门，它的主要职能和部门定位是什么？你的实习经历对你有什么收获或帮助？在这个过程中，你有没有发现一些问题？你有没有自己的解决思路？可以分享一下。目前你手上有没有其他公司的offer？或者有没有进入终面、谈薪等环节？你的意向公司是哪一家？你拿到的offer或意向中，薪资和工作地点分别是怎样的？在工作地点上，你自己有没有比较偏向的城市？你自己的期望薪资是多少？HR说要11月下旬才通知结果，怎么要这么久啊。许愿能过
查看10道真题和解析
点赞 评论 收藏
分享
11-03 07:45
上海交通大学 硬件开发
点赞 评论 收藏
分享
10-29 17:08
山东大学 全栈开发
点赞 评论 收藏
分享
10-05 21:58
广西职业师范学院 Java
像这种破学校破简历是不是找不到实习了
像这种破学校破简历是不是找不到实习了
在看牛客的社畜很积极：身高体重那一行信息去掉，学校那一行的信息放上面，找半天都没找到你是哪个学校什么专业的
点赞 评论 收藏
分享
10-31 10:36
重庆大学 研发工程师
别在误会低代码了，真正的低代码不仅仅是简单的拖拉拽和表单流程搭建
在和客户交流的时候，发现很多客户觉得低代码或者零代码的平台只能做一些简单的业务系统，其实这点&nbsp;产品本身做得不够的，可能就是这样。但是JVS&nbsp;其实远远不止仅仅做一些简单的表单和流程，还可以做得更多，它是软件开发级别的低代码开发平台。JVS内包含了多种能力配置，包括多个能力配置引擎，通过设计数据与配置引擎可以直接渲染生成功能，无需再生成代码（生成代码的模式大概率是一次性的低代码），包括：列表页的配置器，可以配置各种列表页，列表页上的数据字段、展示内容、交互操作表单的配置器，构建用户信息查询录入的操作界面逻辑的配置器，构建自动化处理的业务功能流程的配置器，实现人工审批的功能图表的配置器，配置用于嵌入...
点赞 评论 收藏
分享
评论
2
1
分享

招聘动态

查看更多

字节跳动火山引擎

2026校园招聘

联想

2026届校园招聘

字节跳动

2026校园招聘

联想

26届AI专项｜内推码NK2026

快手

2026届校园招聘

中欧基金

2026届卓越之星校招

联想

2026届校园招聘

完美世界

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我来点评面试官 #
10574次浏览 82人参与
# 工作后，谈恋爱还和学生时代一样吗？ #
39359次浏览 372人参与
# 京东开奖 #
447447次浏览 2502人参与
# 同bg的你秋招战况如何？ #
167727次浏览 972人参与
# 职场破冰，你们都聊什么？ #
28682次浏览 152人参与
# 今年秋招是回暖还是遇冷 #
21192次浏览 137人参与
# 360集团校招 #
2547次浏览 21人参与
# 阿里云工作体验 #
31796次浏览 108人参与
# 你的领导最像哪种动物，为什么? #
24100次浏览 134人参与
# 我的AI电子员工 #
20957次浏览 152人参与
# 三一集团提前批进度交流 #
40202次浏览 228人参与
# 诺瓦星云求职进展汇总 #
225630次浏览 1732人参与
# 毕业论文进行时 #
2235次浏览 39人参与
# 教师节，你送祝福了吗 #
11519次浏览 76人参与
# 秋招开始捡漏了吗 #
62649次浏览 430人参与
# 来聊聊你目前的求职进展 #
686456次浏览 6921人参与
# 你实习是赚钱了还是亏钱了？ #
20545次浏览 186人参与
# 找工作八股要背到什么程度？ #
12206次浏览 196人参与
# 用一句话形容你的团队氛围 #
13218次浏览 145人参与
# 上班摸鱼，你都在干些什么？ #
29088次浏览 223人参与
# 三一重工求职进展汇总 #
22562次浏览 82人参与
# 你找工作是从容有余 or 匆忙滚爬？ #
7088次浏览 72人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务