Boost C++ 库

……这是世界上最受推崇、设计最精良的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu, C++ Coding Standards

类模板 treap_set - Boost C++ 函数库
PrevUpHomeNext

类模板 treap_set

boost::intrusive::treap_set

提要

// In header: <boost/intrusive/treap_set.hpp>

template<typename T, class ... Options> 
class treap_set {
public:
  // types
  typedef implementation_defined::value_type             value_type;            
  typedef implementation_defined::value_traits           value_traits;          
  typedef implementation_defined::key_type               key_type;              
  typedef implementation_defined::key_of_value           key_of_value;          
  typedef implementation_defined::pointer                pointer;               
  typedef implementation_defined::const_pointer          const_pointer;         
  typedef implementation_defined::reference              reference;             
  typedef implementation_defined::const_reference        const_reference;       
  typedef implementation_defined::difference_type        difference_type;       
  typedef implementation_defined::size_type              size_type;             
  typedef implementation_defined::value_compare          value_compare;         
  typedef implementation_defined::key_compare            key_compare;           
  typedef implementation_defined::priority_type          priority_type;         
  typedef implementation_defined::priority_compare       priority_compare;      
  typedef implementation_defined::iterator               iterator;              
  typedef implementation_defined::const_iterator         const_iterator;        
  typedef implementation_defined::reverse_iterator       reverse_iterator;      
  typedef implementation_defined::const_reverse_iterator const_reverse_iterator;
  typedef implementation_defined::insert_commit_data     insert_commit_data;    
  typedef implementation_defined::node_traits            node_traits;           
  typedef implementation_defined::node                   node;                  
  typedef implementation_defined::node_ptr               node_ptr;              
  typedef implementation_defined::const_node_ptr         const_node_ptr;        
  typedef implementation_defined::node_algorithms        node_algorithms;       

  // public member functions
  treap_set();
  explicit treap_set(const key_compare &, 
                     const priority_compare & = priority_compare(), 
                     const value_traits & = value_traits());
  template<typename Iterator> 
    treap_set(Iterator, Iterator, const key_compare & = key_compare(), 
              const priority_compare & = priority_compare(), 
              const value_traits & = value_traits());
  treap_set(treap_set &&);
  treap_set & operator=(treap_set &&);
  ~treap_set();
  iterator begin() noexcept;
  const_iterator begin() const noexcept;
  const_iterator cbegin() const noexcept;
  iterator end() noexcept;
  const_iterator end() const noexcept;
  const_iterator cend() const noexcept;
  reverse_iterator rbegin() noexcept;
  const_reverse_iterator rbegin() const noexcept;
  const_reverse_iterator crbegin() const noexcept;
  reverse_iterator rend() noexcept;
  const_reverse_iterator rend() const noexcept;
  const_reverse_iterator crend() const noexcept;
  iterator root() noexcept;
  const_iterator root() const noexcept;
  const_iterator croot() const noexcept;
  key_compare key_comp() const;
  value_compare value_comp() const;
  bool empty() const noexcept;
  size_type size() const noexcept;
  void swap(treap_set &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const treap_set &, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(treap_set &&, Cloner, Disposer);
  iterator top() noexcept;
  const_iterator top() const noexcept;
  const_iterator ctop() const noexcept;
  reverse_iterator rtop() noexcept;
  const_reverse_iterator rtop() const noexcept;
  const_reverse_iterator crtop() const noexcept;
  priority_compare priority_comp() const;
  std::pair< iterator, bool > insert(reference);
  iterator insert(const_iterator, reference);
  std::pair< iterator, bool > 
  insert_check(const key_type &, const priority_type &, insert_commit_data &);
  std::pair< iterator, bool > 
  insert_check(const_iterator, const key_type &, const priority_type &, 
               insert_commit_data &);
  template<typename KeyType, typename KeyTypeKeyCompare, typename PrioType, 
           typename PrioValuePrioCompare> 
    std::pair< iterator, bool > 
    insert_check(const KeyType &, KeyTypeKeyCompare, const PrioType &, 
                 PrioValuePrioCompare, insert_commit_data &);
  template<typename KeyType, typename KeyTypeKeyCompare, typename PrioType, 
           typename PrioValuePrioCompare> 
    std::pair< iterator, bool > 
    insert_check(const_iterator, const KeyType &, KeyTypeKeyCompare, 
                 const PrioType &, PrioValuePrioCompare, 
                 insert_commit_data &);
  template<typename Iterator> void insert(Iterator, Iterator);
  iterator insert_commit(reference, const insert_commit_data &) noexcept;
  iterator insert_before(const_iterator, reference) noexcept;
  void push_back(reference) noexcept;
  void push_front(reference) noexcept;
  iterator erase(const_iterator) noexcept;
  iterator erase(const_iterator, const_iterator) noexcept;
  size_type erase(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    size_type erase(const KeyType &, KeyTypeKeyCompare);
  template<typename Disposer> 
    iterator erase_and_dispose(const_iterator, Disposer) noexcept;
  template<typename Disposer> 
    iterator erase_and_dispose(const_iterator, const_iterator, Disposer) noexcept;
  template<typename Disposer> 
    size_type erase_and_dispose(const key_type &, Disposer);
  template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
    size_type erase_and_dispose(const KeyType &, KeyTypeKeyCompare, Disposer);
  void clear() noexcept;
  template<typename Disposer> void clear_and_dispose(Disposer) noexcept;
  size_type count(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    size_type count(const KeyType &, KeyTypeKeyCompare) const;
  iterator lower_bound(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator lower_bound(const KeyType &, KeyTypeKeyCompare);
  const_iterator lower_bound(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    const_iterator lower_bound(const KeyType &, KeyTypeKeyCompare) const;
  iterator upper_bound(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator upper_bound(const KeyType &, KeyTypeKeyCompare);
  const_iterator upper_bound(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    const_iterator upper_bound(const KeyType &, KeyTypeKeyCompare) const;
  iterator find(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator find(const KeyType &, KeyTypeKeyCompare);
  const_iterator find(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    const_iterator find(const KeyType &, KeyTypeKeyCompare) const;
  std::pair< iterator, iterator > equal_range(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< iterator, iterator > 
    equal_range(const KeyType &, KeyTypeKeyCompare);
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< const_iterator, const_iterator > 
    equal_range(const KeyType &, KeyTypeKeyCompare) const;
  std::pair< iterator, iterator > 
  bounded_range(const key_type &, const key_type &, bool, bool);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< iterator, iterator > 
    bounded_range(const KeyType &, const KeyType &, KeyTypeKeyCompare, bool, 
                  bool);
  std::pair< const_iterator, const_iterator > 
  bounded_range(const key_type &, const key_type &, bool, bool) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< const_iterator, const_iterator > 
    bounded_range(const KeyType &, const KeyType &, KeyTypeKeyCompare, bool, 
                  bool) const;
  iterator iterator_to(reference) noexcept;
  const_iterator iterator_to(const_reference) const noexcept;
  pointer unlink_leftmost_without_rebalance() noexcept;
  void replace_node(iterator, reference) noexcept;
  void remove_node(reference) noexcept;
  template<class ... Options2> void merge(treap_set< T, Options2... > &);
  template<class ... Options2> void merge(treap_multiset< T, Options2... > &);

  // public static functions
  static treap_set & container_from_end_iterator(iterator) noexcept;
  static const treap_set & 
  container_from_end_iterator(const_iterator) noexcept;
  static treap_set & container_from_iterator(iterator) noexcept;
  static const treap_set & container_from_iterator(const_iterator) noexcept;
  static iterator s_iterator_to(reference) noexcept;
  static const_iterator s_iterator_to(const_reference) noexcept;
  static void init_node(reference) noexcept;

  // public data members
  static const bool constant_time_size;
};

描述

类模板 treap_set 是一个侵入式容器,它模仿了 C++ 标准中所述的 std::set 的大部分接口。

模板参数 T 是由容器管理的类型。用户可以指定额外的选项,如果没有提供选项,则使用默认选项。

该容器支持以下选项:base_hook<>/member_hook<>/value_traits<>constant_time_size<>size_type<>compare<>priority<>priority_of_value<>

treap_set 公共成员函数

  1. treap_set();

    效果:构造一个空容器。

    复杂度:常量。

    抛出:如果 value_traits::node_traits::node 构造函数抛出(预定义的 Boost.Intrusive 钩子不会发生这种情况),或者 value_compare/priority_compare 对象的拷贝构造函数抛出。基本保证。

  2. explicit treap_set(const key_compare & cmp, 
                       const priority_compare & pcmp = priority_compare(), 
                       const value_traits & v_traits = value_traits());
  3. template<typename Iterator> 
      treap_set(Iterator b, Iterator e, const key_compare & cmp = key_compare(), 
                const priority_compare & pcmp = priority_compare(), 
                const value_traits & v_traits = value_traits());
  4. treap_set(treap_set && x);

    效果:待办

  5. treap_set & operator=(treap_set && x);

    效果:待办

  6. ~treap_set();

    效果:从当前容器中分离所有元素。集合中的对象不会被删除(即不会调用析构函数),但根据 value_traits 模板参数的节点会被重新初始化,因此可以重用。

    复杂度:相对于 *this 中的元素为线性。

    抛出:无。

  7. iterator begin() noexcept;

    效果:返回一个指向容器开头的迭代器。

    复杂度:常量。

    抛出:无。

  8. const_iterator begin() const noexcept;

    效果:返回一个指向容器开头的 const_iterator。

    复杂度:常量。

    抛出:无。

  9. const_iterator cbegin() const noexcept;

    效果:返回一个指向容器开头的 const_iterator。

    复杂度:常量。

    抛出:无。

  10. iterator end() noexcept;

    效果:返回一个指向容器末尾的迭代器。

    复杂度:常量。

    抛出:无。

  11. const_iterator end() const noexcept;

    效果:返回一个指向容器末尾的 const_iterator。

    复杂度:常量。

    抛出:无。

  12. const_iterator cend() const noexcept;

    效果:返回一个指向容器末尾的 const_iterator。

    复杂度:常量。

    抛出:无。

  13. reverse_iterator rbegin() noexcept;

    效果:返回一个指向反向容器开头的 reverse_iterator。

    复杂度:常量。

    抛出:无。

  14. const_reverse_iterator rbegin() const noexcept;

    效果:返回一个指向反向容器开头的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  15. const_reverse_iterator crbegin() const noexcept;

    效果:返回一个指向反向容器开头的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  16. reverse_iterator rend() noexcept;

    效果:返回一个指向反向容器末尾的 reverse_iterator。

    复杂度:常量。

    抛出:无。

  17. const_reverse_iterator rend() const noexcept;

    效果:返回一个指向反向容器末尾的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  18. const_reverse_iterator crend() const noexcept;

    效果:返回一个指向反向容器末尾的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  19. iterator root() noexcept;

    效果:返回一个指向容器根节点的迭代器,如果不存在则返回 end()

    复杂度:常量。

    抛出:无。

  20. const_iterator root() const noexcept;

    效果:返回一个指向容器根节点的 const_iterator,如果不存在则返回 cend()

    复杂度:常量。

    抛出:无。

  21. const_iterator croot() const noexcept;

    效果:返回一个指向容器根节点的 const_iterator,如果不存在则返回 cend()

    复杂度:常量。

    抛出:无。

  22. key_compare key_comp() const;

    效果:返回容器使用的 key_compare 对象。

    复杂度:常量。

    抛出:如果 key_compare 的复制构造函数抛出。

  23. value_compare value_comp() const;

    效果:返回容器使用的 value_compare 对象。

    复杂度:常量。

    抛出:如果 value_compare 的复制构造函数抛出。

  24. bool empty() const noexcept;

    效果:如果容器为空,则返回 true。

    复杂度:常量。

    抛出:无。

  25. size_type size() const noexcept;

    效果:返回容器中存储的元素数量。

    复杂度:如果启用了常量时间大小选项,则为常量时间;否则,相对于 *this 中的元素为线性。

    抛出:无。

  26. void swap(treap_set & other);

    效果:交换两个 treap 的内容。

    复杂度:常量。

    抛出:如果比较函子的 swap 调用抛出。

  27. template<typename Cloner, typename Disposer> 
      void clone_from(const treap_set & src, Cloner cloner, Disposer disposer);

    要求:Disposer::operator()(pointer) 不应抛出。Cloner 应产生与原始节点等效的节点。

    效果:通过调用 Disposer::operator()(pointer) 来擦除 *this 中的所有元素,通过调用 Cloner::operator()(const_reference) 来克隆 src 中的所有元素,并将它们插入到 *this 中。从源容器复制谓词。

    如果 cloner 抛出,所有克隆的元素都会被解除链接并调用 Disposer::operator()(pointer) 进行处理。

    复杂度:相对于擦除和插入的元素为线性。

    抛出:如果 cloner 抛出或谓词复制赋值抛出。基本保证。

  28. template<typename Cloner, typename Disposer> 
      void clone_from(treap_set && src, Cloner cloner, Disposer disposer);

    要求:Disposer::operator()(pointer) 不应抛出。Cloner 应产生与原始节点等效的节点。

    效果:通过调用 Disposer::operator()(pointer) 来擦除 *this 中的所有元素,通过调用 Cloner::operator()(reference) 来克隆 src 中的所有元素,并将它们插入到 *this 中。从源容器复制谓词。

    如果 cloner 抛出,所有克隆的元素都会被解除链接并调用 Disposer::operator()(pointer) 进行处理。

    复杂度:相对于擦除和插入的元素为线性。

    抛出:如果 cloner 抛出或谓词复制赋值抛出。基本保证。

  29. iterator top() noexcept;

    效果:返回指向 treap 中最高优先级对象的迭代器。

    复杂度:常量。

    抛出:无。

  30. const_iterator top() const noexcept;

    效果:返回一个指向 treap 中最高优先级对象的 const_iterator。

    复杂度:常量。

    抛出:无。

  31. const_iterator ctop() const noexcept;

    效果:返回一个指向 treap 中最高优先级对象的 const_iterator。

    复杂度:常量。

    抛出:无。

  32. reverse_iterator rtop() noexcept;

    效果:返回指向反向 treap 中最高优先级对象的 reverse_iterator。

    复杂度:常量。

    抛出:无。

  33. const_reverse_iterator rtop() const noexcept;

    效果:返回指向反向 treap 中最高优先级对象的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  34. const_reverse_iterator crtop() const noexcept;

    效果:返回指向反向 treap 中最高优先级对象的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  35. priority_compare priority_comp() const;

    效果:返回指向反向 treap 中最高优先级对象的 const_reverse_iterator。

    复杂度:常量。

    抛出:无。

  36. std::pair< iterator, bool > insert(reference value);

    要求:value 必须是左值。

    效果:如果 value 不存在于容器中,则将其插入容器。

    复杂度:插入元素的平均复杂度最多为对数。

    抛出:如果内部 key_compare 或 priority_compare 函数抛出异常。强保证。

    注意:不影响迭代器和引用的有效性。不调用拷贝构造函数。

  37. iterator insert(const_iterator hint, reference value);

    要求:value 必须是左值,并且 "hint" 必须是一个有效的迭代器。

    效果:尝试将 x 插入容器,使用 "hint" 作为插入位置的提示。

    复杂度:通常为对数,但如果 t 紧挨着 hint 插入,则为摊销常量时间(最坏情况下两次比较)。

    抛出:如果内部 key_compare 或 priority_compare 函数抛出异常。强保证。

    注意:不影响迭代器和引用的有效性。不调用拷贝构造函数。

  38. std::pair< iterator, bool > 
    insert_check(const key_type & key, const priority_type & prio, 
                 insert_commit_data & commit_data);
  39. std::pair< iterator, bool > 
    insert_check(const_iterator hint, const key_type & key, 
                 const priority_type & prio, insert_commit_data & commit_data);
  40. template<typename KeyType, typename KeyTypeKeyCompare, typename PrioType, 
             typename PrioValuePrioCompare> 
      std::pair< iterator, bool > 
      insert_check(const KeyType & key, KeyTypeKeyCompare comp, 
                   const PrioType & prio, PrioValuePrioCompare pcomp, 
                   insert_commit_data & commit_data);
  41. template<typename KeyType, typename KeyTypeKeyCompare, typename PrioType, 
             typename PrioValuePrioCompare> 
      std::pair< iterator, bool > 
      insert_check(const_iterator hint, const KeyType & key, 
                   KeyTypeKeyCompare comp, const PrioType & prio, 
                   PrioValuePrioCompare pcomp, insert_commit_data & commit_data);
  42. template<typename Iterator> void insert(Iterator b, Iterator e);

    要求:解引用迭代器必须产生类型为 value_type 的左值。

    效果:尝试将范围中的每个元素插入容器。

    复杂度:插入范围通常为 O(N * log(N)),其中 N 是范围的大小。但是,如果范围已根据 key_comp() 排序,则为 O(N)。

    抛出:如果内部 key_compare 或 priority_compare 函数抛出异常。强保证。

    注意:不影响迭代器和引用的有效性。不调用拷贝构造函数。

  43. iterator insert_commit(reference value, 
                           const insert_commit_data & commit_data) noexcept;

    要求:value 必须是 type value_type 的左值。commit_data 必须是从之前调用“insert_check”获得的。“insert_check”填充“commit_data”与调用“insert_commit”之间不应该有任何对象被插入或擦除。

    效果:使用“insert_check”之前填充的“commit_data”获得的信息,将 value 插入到 avl_set 中。

    返回:指向新插入对象的迭代器。

    复杂度:常量时间。

    抛出:无。

    注意:只有在先前执行了 "insert_check" 来填充 "commit_data" 时,此函数才有意义。在 "insert_check" 和 "insert_commit" 调用之间,不应插入或删除任何值。

  44. iterator insert_before(const_iterator pos, reference value) noexcept;

    要求:value 必须是左值,"pos" 必须是一个有效迭代器(或 end),并且根据谓词,它将是插入 value 后的后继。

    效果:在 "pos" 之前将 x 插入容器。

    复杂度:常量时间。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:此函数不检查前置条件,因此如果“pos”不是“value”的后继,则容器排序不变性将被破坏。这是一个低级函数,仅供高级用户出于性能原因使用。

  45. void push_back(reference value) noexcept;

    要求:value 必须是左值,并且它不小于已插入的最大键。

    效果:将 x 插入容器的最后一个位置。

    复杂度:常量时间。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:此函数不检查前置条件,因此如果 value 小于最大的已插入键,则容器排序不变性将被破坏。此函数比使用“insert_before”效率稍高。这是一个低级函数,仅供高级用户出于性能原因使用。

  46. void push_front(reference value) noexcept;

    要求:value 必须是左值,并且它不大于已插入的最小键。

    效果:将 x 插入容器的第一个位置。

    复杂度:常量时间。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:此函数不检查前置条件,因此如果 value 大于最小的已插入键,则容器排序不变性将被破坏。此函数比使用“insert_before”效率稍高。这是一个低级函数,仅供高级用户出于性能原因使用。

  47. iterator erase(const_iterator i) noexcept;

    效果:擦除由 i 指向的元素。

    复杂度:擦除元素的平均复杂度为常量时间。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:使被擦除元素的迭代器(但不影响引用)无效。不调用析构函数。

  48. iterator erase(const_iterator b, const_iterator e) noexcept;

    效果:擦除由 b 和 e 指向的范围。

    复杂度:擦除范围的平均复杂度至多为 O(log(size() + N)),其中 N 是范围中的元素数量。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:使被擦除元素的迭代器(但不影响引用)无效。不调用析构函数。

  49. size_type erase(const key_type & key);

    效果:擦除所有具有给定值的元素。

    返回:被擦除的元素数量。

    复杂度:O(log(size() + N)。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:使被擦除元素的迭代器(但不影响引用)无效。不调用析构函数。

  50. template<typename KeyType, typename KeyTypeKeyCompare> 
      size_type erase(const KeyType & key, KeyTypeKeyCompare comp);

    效果:根据比较函子 "comp" 擦除所有具有给定键的元素。

    返回:被擦除的元素数量。

    复杂度:O(log(size() + N)。

    抛出:如果内部 priority_compare 函数抛出异常。等效保证为 while(beg != end) erase(beg++);

    注意:使被擦除元素的迭代器(但不影响引用)无效。不调用析构函数。

  51. template<typename Disposer> 
      iterator erase_and_dispose(const_iterator i, Disposer disposer) noexcept;

    要求:Disposer::operator()(pointer) 不应抛出。

    效果:擦除由 i 指向的元素。Disposer::operator()(pointer) 将被调用以处理移除的元素。

    复杂度:擦除元素的平均复杂度为常量时间。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:使被擦除元素的迭代器无效。

  52. template<typename Disposer> 
      iterator erase_and_dispose(const_iterator b, const_iterator e, 
                                 Disposer disposer) noexcept;

    要求:Disposer::operator()(pointer) 不应抛出。

    效果:擦除由 b 和 e 指向的范围。Disposer::operator()(pointer) 将被调用以处理移除的元素。

    复杂度:擦除范围的平均复杂度至多为 O(log(size() + N)),其中 N 是范围中的元素数量。

    抛出:如果内部 priority_compare 函数抛出异常。强保证。

    注意:使被擦除元素的迭代器无效。

  53. template<typename Disposer> 
      size_type erase_and_dispose(const key_type & key, Disposer disposer);

    要求:Disposer::operator()(pointer) 不应抛出。

    效果:擦除所有具有给定值的元素。Disposer::operator()(pointer) 将被调用以处理移除的元素。

    返回:被擦除的元素数量。

    复杂度:O(log(size() + N)。

    抛出:如果 priority_compare 函数抛出异常,则为弱保证且堆不变量被破坏。最安全的方法是清空或销毁容器。

    注意:使被擦除元素的迭代器(但不影响引用)无效。不调用析构函数。

  54. template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
      size_type erase_and_dispose(const KeyType & key, KeyTypeKeyCompare comp, 
                                  Disposer disposer);

    要求:Disposer::operator()(pointer) 不应抛出。

    效果:根据比较函子 "comp" 擦除所有具有给定键的元素。Disposer::operator()(pointer) 将被调用以处理移除的元素。

    返回:被擦除的元素数量。

    复杂度:O(log(size() + N)。

    抛出:如果 priority_compare 函数抛出异常,则为弱保证且堆不变量被破坏。最安全的方法是清空或销毁容器。

    注意:使被擦除元素的迭代器无效。

  55. void clear() noexcept;

    效果:擦除所有元素。

    复杂度:相对于容器中的元素数量为线性。如果 value_type 是安全模式或自动解除链接;否则为常量时间。

    抛出:无。

    注意:使被擦除元素的迭代器(但不影响引用)无效。不调用析构函数。

  56. template<typename Disposer> void clear_and_dispose(Disposer disposer) noexcept;

    效果:擦除所有元素,并为每个要擦除的节点调用 disposer(p)。复杂度:擦除范围的平均复杂度至多为 O(log(size() + N)),其中 N 是容器中的元素数量。

    抛出:无。

    注意:使被擦除元素的迭代器(但不影响引用)无效。调用 disposer 函子 N 次。

  57. size_type count(const key_type & key) const;
  58. template<typename KeyType, typename KeyTypeKeyCompare> 
      size_type count(const KeyType & key, KeyTypeKeyCompare comp) const;

    要求:key 是一个值,使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 是划分的,其中 comp(nk, key) 暗示 !comp(key, nk),且 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:返回具有给定键的包含元素的数量。

    复杂度:包含元素的数量的对数加上具有给定键的对象数量的线性。

    抛出:如果 comp 抛出。

  59. iterator lower_bound(const key_type & key);
  60. template<typename KeyType, typename KeyTypeKeyCompare> 
      iterator lower_bound(const KeyType & key, KeyTypeKeyCompare comp);
  61. const_iterator lower_bound(const key_type & key) const;
  62. template<typename KeyType, typename KeyTypeKeyCompare> 
      const_iterator 
      lower_bound(const KeyType & key, KeyTypeKeyCompare comp) const;
  63. iterator upper_bound(const key_type & key);
  64. template<typename KeyType, typename KeyTypeKeyCompare> 
      iterator upper_bound(const KeyType & key, KeyTypeKeyCompare comp);

    要求:key 是一个值,使得 *this 相对于 !comp(key, nk) 是划分的,其中 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:返回一个指向第一个键大于 k 的元素的迭代器(根据 comp),如果不存在则返回 end()

    复杂度:对数。

    抛出:如果 comp 抛出。

  65. const_iterator upper_bound(const key_type & key) const;
  66. template<typename KeyType, typename KeyTypeKeyCompare> 
      const_iterator 
      upper_bound(const KeyType & key, KeyTypeKeyCompare comp) const;

    要求:key 是一个值,使得 *this 相对于 !comp(key, nk) 是划分的,其中 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:返回一个指向第一个键大于 k 的元素的迭代器(根据 comp),如果不存在则返回 end()

    复杂度:对数。

    抛出:如果 comp 抛出。

  67. iterator find(const key_type & key);
  68. template<typename KeyType, typename KeyTypeKeyCompare> 
      iterator find(const KeyType & key, KeyTypeKeyCompare comp);

    要求:key 是一个值,使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 是划分的,其中 comp(nk, key) 暗示 !comp(key, nk),且 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:查找一个指向第一个键为 k 的元素的迭代器,如果不存在则返回 end()

    复杂度:对数。

    抛出:如果 comp 抛出。

  69. const_iterator find(const key_type & key) const;
  70. template<typename KeyType, typename KeyTypeKeyCompare> 
      const_iterator find(const KeyType & key, KeyTypeKeyCompare comp) const;

    要求:key 是一个值,使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 是划分的,其中 comp(nk, key) 暗示 !comp(key, nk),且 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:查找一个指向第一个键为 k 的元素的迭代器,如果不存在则返回 end()

    复杂度:对数。

    抛出:如果 comp 抛出。

  71. std::pair< iterator, iterator > equal_range(const key_type & key);
  72. template<typename KeyType, typename KeyTypeKeyCompare> 
      std::pair< iterator, iterator > 
      equal_range(const KeyType & key, KeyTypeKeyCompare comp);

    要求:key 是一个值,使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 是划分的,其中 comp(nk, key) 暗示 !comp(key, nk),且 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:查找包含所有键为 k 的元素的范围,或者一个空范围,该范围指示如果不存在键为 k 的元素,这些元素将插入的位置。

    复杂度:对数。

    抛出:如果 comp 抛出。

  73. std::pair< const_iterator, const_iterator > 
    equal_range(const key_type & key) const;
  74. template<typename KeyType, typename KeyTypeKeyCompare> 
      std::pair< const_iterator, const_iterator > 
      equal_range(const KeyType & key, KeyTypeKeyCompare comp) const;

    要求:key 是一个值,使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 是划分的,其中 comp(nk, key) 暗示 !comp(key, nk),且 nk 是插入到 *this 中的 value_type 的 key_type。

    效果:查找包含所有键为 k 的元素的范围,或者一个空范围,该范围指示如果不存在键为 k 的元素,这些元素将插入的位置。

    复杂度:对数。

    抛出:如果 comp 抛出。

  75. std::pair< iterator, iterator > 
    bounded_range(const key_type & lower_key, const key_type & upper_key, 
                  bool left_closed, bool right_closed);
  76. template<typename KeyType, typename KeyTypeKeyCompare> 
      std::pair< iterator, iterator > 
      bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                    KeyTypeKeyCompare comp, bool left_closed, bool right_closed);

    要求lower_key 是一个值,使得 *this 相对于 comp(nk, lower_key) 是划分的(如果 left_closed 为 true),否则相对于 !comp(lower_key, nk)。

    upper_key 是一个值,使得 *this 相对于 !comp(upper_key, nk) 进行分区(如果 right_closed 为 true),否则相对于 comp(nk, upper_key)。

    upper_key 不得根据 comp 排在 lower_key 之前 [comp(upper_key, lower_key) 应为 false]

    如果 lower_key 等价于 upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)],则 ('left_closed' || 'right_closed') 必须为 false。

    效果:返回具有以下标准的 pair。

    first = lower_bound(lower_key, comp) 如果 left_closed,否则 upper_bound(lower_key, comp)

    second = upper_bound(upper_key, comp) 如果 right_closed,否则 lower_bound(upper_key, comp)

    复杂度:对数。

    抛出:如果 comp 抛出。

    注意:与为 lower_key 和 upper_key 调用 upper_bound 和 lower_bound 相比,此函数可能更有效。

    注意:实验性功能,接口可能在未来版本中更改。

  77. std::pair< const_iterator, const_iterator > 
    bounded_range(const key_type & lower_key, const key_type & upper_key, 
                  bool left_closed, bool right_closed) const;
  78. template<typename KeyType, typename KeyTypeKeyCompare> 
      std::pair< const_iterator, const_iterator > 
      bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                    KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;

    要求lower_key 是一个值,使得 *this 相对于 comp(nk, lower_key) 是划分的(如果 left_closed 为 true),否则相对于 !comp(lower_key, nk)。

    upper_key 是一个值,使得 *this 相对于 !comp(upper_key, nk) 进行分区(如果 right_closed 为 true),否则相对于 comp(nk, upper_key)。

    upper_key 不得根据 comp 排在 lower_key 之前 [comp(upper_key, lower_key) 应为 false]

    如果 lower_key 等价于 upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)],则 ('left_closed' || 'right_closed') 必须为 false。

    效果:返回具有以下标准的 pair。

    first = lower_bound(lower_key, comp) 如果 left_closed,否则 upper_bound(lower_key, comp)

    second = upper_bound(upper_key, comp) 如果 right_closed,否则 lower_bound(upper_key, comp)

    复杂度:对数。

    抛出:如果 comp 抛出。

    注意:与为 lower_key 和 upper_key 调用 upper_bound 和 lower_bound 相比,此函数可能更有效。

    注意:实验性功能,接口可能在未来版本中更改。

  79. iterator iterator_to(reference value) noexcept;
  80. const_iterator iterator_to(const_reference value) const noexcept;
  81. pointer unlink_leftmost_without_rebalance() noexcept;

    效果:从容器中解除链接最左边的节点。

    复杂度:平均复杂度为常量时间。

    抛出:无。

    注意:此函数会破坏容器,容器只能用于后续的 unlink_leftmost_without_rebalance 调用。此函数通常用于实现容器的逐步受控销毁。

  82. void replace_node(iterator replace_this, reference with_this) noexcept;

    要求:replace_this 必须是 *this 的有效迭代器,并且 with_this 不能插入到任何容器中。

    效果:在容器中用 with_this 替换 replace_this 的位置。容器不需要重新平衡。

    复杂度:常量。

    抛出:无。

    注意:如果 with_this 与 replace_this 根据排序规则不相等,此函数将破坏容器的排序不变性。此函数比擦除和插入节点更快,因为它不需要重新平衡或比较。

  83. void remove_node(reference value) noexcept;

    效果:从容器中移除 "value"。

    抛出:无。

    复杂度:对数时间。

    注意:此静态函数仅可与非常量时间大小的容器以及有状态的比较函子一起使用。

    如果用户将此函数与常量时间大小容器或有状态比较函子一起调用,将产生编译错误。

  84. template<class ... Options2> void merge(treap_set< T, Options2... > & source);

    要求:"source" 容器的 Options 只能在比较函数上与 *this 不同。

    效果:尝试从 source 中提取每个元素,并使用 *this 的比较对象将其插入到 a 中。如果 a 中存在键与 source 中某个元素的键相等的元素,则该元素不会从 source 中提取。

    后置条件:指向 source 中已传输元素的指针和引用现在指向这些元素,但作为 *this 的成员。指向已传输元素的迭代器将继续指向它们的元素,但它们现在像 *this 中的迭代器一样工作,而不是像 source 中的迭代器。

    抛出:除非比较对象抛出,否则不抛出。

    复杂度:N log(a.size() + N)(N 为 source.size() 的值)。

  85. template<class ... Options2> 
      void merge(treap_multiset< T, Options2... > & source);

    要求:"source" 容器的 Options 只能在比较函数上与 *this 不同。

    效果:尝试从 source 中提取每个元素,并使用 *this 的比较对象将其插入到 a 中。如果 a 中存在键与 source 中某个元素的键相等的元素,则该元素不会从 source 中提取。

    后置条件:指向 source 中已传输元素的指针和引用现在指向这些元素,但作为 *this 的成员。指向已传输元素的迭代器将继续指向它们的元素,但它们现在像 *this 中的迭代器一样工作,而不是像 source 中的迭代器。

    抛出:除非比较对象抛出,否则不抛出。

    复杂度:N log(a.size() + N)(N 为 source.size() 的值)。

treap_set 公共静态函数

  1. static treap_set & container_from_end_iterator(iterator end_iterator) noexcept;
  2. static const treap_set & 
    container_from_end_iterator(const_iterator end_iterator) noexcept;
  3. static treap_set & container_from_iterator(iterator it) noexcept;
  4. static const treap_set & container_from_iterator(const_iterator it) noexcept;
  5. static iterator s_iterator_to(reference value) noexcept;
  6. static const_iterator s_iterator_to(const_reference value) noexcept;
  7. static void init_node(reference value) noexcept;

PrevUpHomeNext