...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::intrusive::sgtree
// In header: <boost/intrusive/sgtree.hpp> template<typename T, class ... Options> class sgtree { public: // types typedef ValueTraits value_traits; typedef implementation_defined::pointer pointer; typedef implementation_defined::const_pointer const_pointer; typedef implementation_defined::value_type value_type; typedef implementation_defined::key_type key_type; typedef implementation_defined::key_of_value key_of_value; 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::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::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; typedef implementation_defined insert_commit_data; // public member functions sgtree(); explicit sgtree(const key_compare &, const value_traits & = value_traits()); template<typename Iterator> sgtree(bool, Iterator, Iterator, const key_compare & = key_compare(), const value_traits & = value_traits()); sgtree(sgtree &&); sgtree & operator=(sgtree &&); ~sgtree(); 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(sgtree &); template<typename Cloner, typename Disposer> void clone_from(const sgtree &, Cloner, Disposer); template<typename Cloner, typename Disposer> void clone_from(sgtree &&, Cloner, Disposer); iterator insert_equal(reference); iterator insert_equal(const_iterator, reference); template<typename Iterator> void insert_equal(Iterator, Iterator); std::pair< iterator, bool > insert_unique(reference); iterator insert_unique(const_iterator, reference); template<typename KeyType, typename KeyTypeKeyCompare> std::pair< iterator BOOST_INTRUSIVE_I bool > insert_unique_check(const KeyType &, KeyTypeKeyCompare, insert_commit_data &); template<typename KeyType, typename KeyTypeKeyCompare> std::pair< iterator, bool > insert_unique_check(const_iterator, const KeyType &, KeyTypeKeyCompare, insert_commit_data &); std::pair< iterator, bool > insert_unique_check(const key_type &, insert_commit_data &); std::pair< iterator, bool > insert_unique_check(const_iterator, const key_type &, insert_commit_data &); iterator insert_unique_commit(reference, const insert_commit_data &) noexcept; template<typename Iterator> void insert_unique(Iterator, Iterator); 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; template<typename T, class ... Options2> void merge_unique(sgtree< T, Options2... > &); while(it ! = itend); template<typename T, class ... Options2> void merge_equal(sgtree< T, Options2... > &); while(it ! = itend); 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; void rebalance() noexcept; iterator rebalance_subtree(iterator) noexcept; float balance_factor() const noexcept; void balance_factor(float) noexcept; // public static functions static sgtree & container_from_end_iterator(iterator) noexcept; static const sgtree & container_from_end_iterator(const_iterator) noexcept; static sgtree & container_from_iterator(iterator) noexcept; static const sgtree & 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; static const bool floating_point; static const bool stateful_value_traits; };
The class template sgtree is an intrusive scapegoat tree container, that is used to construct intrusive sg_set and sg_multiset containers. The no-throw guarantee holds only, if the value_compare object doesn't throw.
The template parameter T
is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.
The container supports the following options: base_hook<>/member_hook<>/value_traits<>
, floating_point<>
, size_type<>
and compare<>
.
sgtree
public member functionssgtree();
Effects: Constructs an empty container.
Complexity: Constant.
Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor of the key_compare object throws. Basic guarantee.
explicit sgtree(const key_compare & cmp, const value_traits & v_traits = value_traits());
template<typename Iterator> sgtree(bool unique, Iterator b, Iterator e, const key_compare & cmp = key_compare(), const value_traits & v_traits = value_traits());
sgtree(sgtree && x);
Effects: Constructs a container moving resources from another container. Internal comparison object and value traits are move constructed and nodes belonging to x (except the node representing the "end") are linked to *this.
Complexity: Constant.
Throws: If value_traits::node_traits::node's move constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the move constructor of the comparison objet throws.
sgtree & operator=(sgtree && x);
Effects: Equivalent to swap
~sgtree();
Effects: Detaches all elements from this. The objects in the set are not deleted (i.e. no destructors are called), but the nodes according to the value_traits template parameter are reinitialized and thus can be reused.
Complexity: Linear to elements contained in *this.
Throws: Nothing.
iterator begin() noexcept;
Effects: Returns an iterator pointing to the beginning of the container.
Complexity: Constant.
Throws: Nothing.
const_iterator begin() const noexcept;
Effects: Returns a const_iterator pointing to the beginning of the container.
Complexity: Constant.
Throws: Nothing.
const_iterator cbegin() const noexcept;
Effects: Returns a const_iterator pointing to the beginning of the container.
Complexity: Constant.
Throws: Nothing.
iterator end() noexcept;
Effects: Returns an iterator pointing to the end of the container.
Complexity: Constant.
Throws: Nothing.
const_iterator end() const noexcept;
Effects: Returns a const_iterator pointing to the end of the container.
Complexity: Constant.
Throws: Nothing.
const_iterator cend() const noexcept;
Effects: Returns a const_iterator pointing to the end of the container.
Complexity: Constant.
Throws: Nothing.
reverse_iterator rbegin() noexcept;
Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.
Complexity: Constant.
Throws: Nothing.
const_reverse_iterator rbegin() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.
Complexity: Constant.
Throws: Nothing.
const_reverse_iterator crbegin() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.
Complexity: Constant.
Throws: Nothing.
reverse_iterator rend() noexcept;
Effects: Returns a reverse_iterator pointing to the end of the reversed container.
Complexity: Constant.
Throws: Nothing.
const_reverse_iterator rend() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.
Complexity: Constant.
Throws: Nothing.
const_reverse_iterator crend() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.
Complexity: Constant.
Throws: Nothing.
iterator root() noexcept;
Effects: Returns a iterator pointing to the root node of the container or end() if not present.
Complexity: Constant.
Throws: Nothing.
const_iterator root() const noexcept;
Effects: Returns a const_iterator pointing to the root node of the container or cend() if not present.
Complexity: Constant.
Throws: Nothing.
const_iterator croot() const noexcept;
Effects: Returns a const_iterator pointing to the root node of the container or cend() if not present.
Complexity: Constant.
Throws: Nothing.
key_compare key_comp() const;
Effects: Returns the key_compare object used by the container.
Complexity: Constant.
Throws: If key_compare copy-constructor throws.
value_compare value_comp() const;
Effects: Returns the value_compare object used by the container.
Complexity: Constant.
Throws: If value_compare copy-constructor throws.
bool empty() const noexcept;
Effects: Returns true if the container is empty.
Complexity: Constant.
Throws: Nothing.
size_type size() const noexcept;
Effects: Returns the number of elements stored in the container.
Complexity: Linear to elements contained in *this if constant-time size option is disabled. Constant time otherwise.
Throws: Nothing.
void swap(sgtree & other);
Effects: Swaps the contents of two containers.
Complexity: Constant.
Throws: If the comparison functor's swap call throws.
template<typename Cloner, typename Disposer> void clone_from(const sgtree & src, Cloner cloner, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.
Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(const_reference ) and inserts them on *this. Copies the predicate from the source container.
If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).
Complexity: Linear to erased plus inserted elements.
Throws: If cloner throws or predicate copy assignment throws. Basic guarantee. Additional notes: it also copies the alpha factor from the source container.
template<typename Cloner, typename Disposer> void clone_from(sgtree && src, Cloner cloner, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.
Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(reference) and inserts them on *this. Copies the predicate from the source container.
If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).
Complexity: Linear to erased plus inserted elements.
Throws: If cloner throws or predicate copy assignment throws. Basic guarantee.
Note: This version can modify the source container, useful to implement move semantics. Additional notes: it also copies the alpha factor from the source container.
iterator insert_equal(reference value);
iterator insert_equal(const_iterator hint, reference value);
template<typename Iterator> void insert_equal(Iterator b, Iterator e);
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Inserts a each element of a range into the container before the upper bound of the key of each element.
Complexity: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().
Throws: If the comparison functor call throws.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
std::pair< iterator, bool > insert_unique(reference value);
iterator insert_unique(const_iterator hint, reference value);
template<typename KeyType, typename KeyTypeKeyCompare> std::pair< iterator BOOST_INTRUSIVE_I bool > insert_unique_check(const KeyType & key, KeyTypeKeyCompare comp, insert_commit_data & commit_data);
template<typename KeyType, typename KeyTypeKeyCompare> std::pair< iterator, bool > insert_unique_check(const_iterator hint, const KeyType & key, KeyTypeKeyCompare comp, insert_commit_data & commit_data);
std::pair< iterator, bool > insert_unique_check(const key_type & key, insert_commit_data & commit_data);
std::pair< iterator, bool > insert_unique_check(const_iterator hint, const key_type & key, insert_commit_data & commit_data);
iterator insert_unique_commit(reference value, const insert_commit_data & commit_data) noexcept;
Requires: value must be an lvalue of type value_type. commit_data must have been obtained from a previous call to "insert_check". No objects should have been inserted or erased from the container between the "insert_check" that filled "commit_data" and the call to "insert_commit".
Effects: Inserts the value in the container using the information obtained from the "commit_data" that a previous "insert_check" filled.
Returns: An iterator to the newly inserted object.
Complexity: Constant time.
Throws: Nothing.
Notes: This function has only sense if a "insert_check" has been previously executed to fill "commit_data". No value should be inserted or erased between the "insert_check" and "insert_commit" calls.
template<typename Iterator> void insert_unique(Iterator b, Iterator e);
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Tries to insert each element of a range into the container.
Complexity: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().
Throws: If the comparison functor call throws.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
iterator insert_before(const_iterator pos, reference value) noexcept;
Requires: value must be an lvalue, "pos" must be a valid iterator (or end) and must be the succesor of value once inserted according to the predicate
Effects: Inserts x into the container before "pos".
Complexity: Constant time.
Throws: Nothing.
Note: This function does not check preconditions so if "pos" is not the successor of "value" container ordering invariant will be broken. This is a low-level function to be used only for performance reasons by advanced users.
void push_back(reference value) noexcept;
Requires: value must be an lvalue, and it must be no less than the greatest inserted key
Effects: Inserts x into the container in the last position.
Complexity: Constant time.
Throws: Nothing.
Note: This function does not check preconditions so if value is less than the greatest inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.
void push_front(reference value) noexcept;
Requires: value must be an lvalue, and it must be no greater than the minimum inserted key
Effects: Inserts x into the container in the first position.
Complexity: Constant time.
Throws: Nothing.
Note: This function does not check preconditions so if value is greater than the minimum inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.
iterator erase(const_iterator i) noexcept;
iterator erase(const_iterator b, const_iterator e) noexcept;
size_type erase(const key_type & key);
template<typename KeyType, typename KeyTypeKeyCompare> size_type erase(const KeyType & key, KeyTypeKeyCompare comp);
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this
.
Effects: Erases all the elements with the given key. according to the comparison functor "comp".
Returns: The number of erased elements.
Complexity: O(log(size() + N).
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
template<typename Disposer> iterator erase_and_dispose(const_iterator i, Disposer disposer) noexcept;
template<typename Disposer> iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) noexcept;
template<typename Disposer> size_type erase_and_dispose(const key_type & key, Disposer disposer);
template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> size_type erase_and_dispose(const KeyType & key, KeyTypeKeyCompare comp, Disposer disposer);
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk) and nk the key_type of a value_type inserted into *this
.
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases all the elements with the given key. according to the comparison functor "comp". Disposer::operator()(pointer) is called for the removed elements.
Returns: The number of erased elements.
Complexity: O(log(size() + N).
Throws: Nothing.
Note: Invalidates the iterators to the erased elements.
void clear() noexcept;
Effects: Erases all of the elements.
Complexity: Linear to the number of elements on the container. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
template<typename Disposer> void clear_and_dispose(Disposer disposer) noexcept;
Effects: Erases all of the elements calling disposer(p) for each node to be erased. Complexity: Average complexity for is at most O(log(size() + N)), where N is the number of elements in the container.
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased elements. Calls N times to disposer functor.
template<typename T, class ... Options2> void merge_unique(sgtree< T, Options2... > &);
Requires: "source" container's Options can only can differ in the comparison function from *this.
Effects: Attempts to extract each element in source and insert it into a using the comparison object of *this. If there is an element in a with key equivalent to the key of an element from source, then that element is not extracted from source.
Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.
Throws: Nothing unless the comparison object throws.
Complexity: N log(a.size() + N) (N has the value source.size())
while(it ! = itend);
template<typename T, class ... Options2> void merge_equal(sgtree< T, Options2... > &);
Requires: "source" container's Options can only can differ in the comparison function from *this.
Effects: Extracts each element in source and insert it into a using the comparison object of *this.
Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.
Throws: Nothing unless the comparison object throws.
Complexity: N log(a.size() + N) (N has the value source.size())
while(it ! = itend);
size_type count(const key_type & key) const;
template<typename KeyType, typename KeyTypeKeyCompare> size_type count(const KeyType & key, KeyTypeKeyCompare comp) const;
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this
.
Effects: Returns the number of contained elements with the given key
Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given key.
Throws: If comp
throws.
iterator lower_bound(const key_type & key);
template<typename KeyType, typename KeyTypeKeyCompare> iterator lower_bound(const KeyType & key, KeyTypeKeyCompare comp);
const_iterator lower_bound(const key_type & key) const;
template<typename KeyType, typename KeyTypeKeyCompare> const_iterator lower_bound(const KeyType & key, KeyTypeKeyCompare comp) const;
iterator upper_bound(const key_type & key);
template<typename KeyType, typename KeyTypeKeyCompare> iterator upper_bound(const KeyType & key, KeyTypeKeyCompare comp);
Requires: key is a value such that *this
is partitioned with respect to !comp(key, nk), with nk the key_type of a value_type inserted into *this
.
Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.
Complexity: Logarithmic.
Throws: If comp
throws.
const_iterator upper_bound(const key_type & key) const;
template<typename KeyType, typename KeyTypeKeyCompare> const_iterator upper_bound(const KeyType & key, KeyTypeKeyCompare comp) const;
Requires: key is a value such that *this
is partitioned with respect to !comp(key, nk), with nk the key_type of a value_type inserted into *this
.
Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.
Complexity: Logarithmic.
Throws: If comp
throws.
iterator find(const key_type & key);
template<typename KeyType, typename KeyTypeKeyCompare> iterator find(const KeyType & key, KeyTypeKeyCompare comp);
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this
.
Effects: Finds an iterator to the first element whose key is k or end() if that element does not exist.
Complexity: Logarithmic.
Throws: If comp
throws.
const_iterator find(const key_type & key) const;
template<typename KeyType, typename KeyTypeKeyCompare> const_iterator find(const KeyType & key, KeyTypeKeyCompare comp) const;
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), and nk the key_type of a value_type inserted into *this
.
Effects: Finds an iterator to the first element whose key is k or end() if that element does not exist.
Complexity: Logarithmic.
Throws: If comp
throws.
std::pair< iterator, iterator > equal_range(const key_type & key);
template<typename KeyType, typename KeyTypeKeyCompare> std::pair< iterator, iterator > equal_range(const KeyType & key, KeyTypeKeyCompare comp);
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this
.
Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.
Complexity: Logarithmic.
Throws: If comp
throws.
std::pair< const_iterator, const_iterator > equal_range(const key_type & key) const;
template<typename KeyType, typename KeyTypeKeyCompare> std::pair< const_iterator, const_iterator > equal_range(const KeyType & key, KeyTypeKeyCompare comp) const;
Requires: key is a value such that *this
is partitioned with respect to comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), with nk the key_type of a value_type inserted into *this
.
Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.
Complexity: Logarithmic.
Throws: If comp
throws.
std::pair< iterator, iterator > bounded_range(const key_type & lower_key, const key_type & upper_key, bool left_closed, bool right_closed);
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);
Requires: lower_key
is a value such that *this
is partitioned with respect to comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise.
upper_key
is a value such that *this
is partitioned with respect to !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise.
upper_key
shall not precede lower_key
according to comp [comp(upper_key, lower_key) shall be false]
If lower_key
is equivalent to upper_key
[!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.
Effects: Returns an a pair with the following criteria:
first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
Complexity: Logarithmic.
Throws: If comp
throws.
Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.
Note: Experimental function, the interface might change in future releases.
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;
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;
Requires: lower_key
is a value such that *this
is partitioned with respect to comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise.
upper_key
is a value such that *this
is partitioned with respect to !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise.
upper_key
shall not precede lower_key
according to comp [comp(upper_key, lower_key) shall be false]
If lower_key
is equivalent to upper_key
[!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then ('left_closed' || 'right_closed') must be false.
Effects: Returns an a pair with the following criteria:
first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
Complexity: Logarithmic.
Throws: If comp
throws.
Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.
Note: Experimental function, the interface might change in future releases.
iterator iterator_to(reference value) noexcept;
const_iterator iterator_to(const_reference value) const noexcept;
pointer unlink_leftmost_without_rebalance() noexcept;
Effects: Unlinks the leftmost node from the container.
Complexity: Average complexity is constant time.
Throws: Nothing.
Notes: This function breaks the container and the container can only be used for more unlink_leftmost_without_rebalance calls. This function is normally used to achieve a step by step controlled destruction of the container.
void replace_node(iterator replace_this, reference with_this) noexcept;
Requires: replace_this must be a valid iterator of *this and with_this must not be inserted in any container.
Effects: Replaces replace_this in its position in the container with with_this. The container does not need to be rebalanced.
Complexity: Constant.
Throws: Nothing.
Note: This function will break container ordering invariants if with_this is not equivalent to *replace_this according to the ordering rules. This function is faster than erasing and inserting the node, since no rebalancing or comparison is needed.
void remove_node(reference value) noexcept;
Effects: removes "value" from the container.
Throws: Nothing.
Complexity: Logarithmic time.
Note: This static function is only usable with non-constant time size containers that have stateless comparison functors.
If the user calls this function with a constant time size container or stateful comparison functor a compilation error will be issued.
void rebalance() noexcept;
Effects: Rebalances the tree.
Throws: Nothing.
Complexity: Linear.
iterator rebalance_subtree(iterator root) noexcept;
Requires: old_root is a node of a tree.
Effects: Rebalances the subtree rooted at old_root.
Returns: The new root of the subtree.
Throws: Nothing.
Complexity: Linear to the elements in the subtree.
float balance_factor() const noexcept;
Returns: The balance factor (alpha) used in this tree
Throws: Nothing.
Complexity: Constant.
void balance_factor(float new_alpha) noexcept;
Requires: new_alpha must be a value between 0.5 and 1.0
Effects: Establishes a new balance factor (alpha) and rebalances the tree if the new balance factor is stricter (less) than the old factor.
Throws: Nothing.
Complexity: Linear to the elements in the subtree.
sgtree
public static functionsstatic sgtree & container_from_end_iterator(iterator end_iterator) noexcept;
static const sgtree & container_from_end_iterator(const_iterator end_iterator) noexcept;
static sgtree & container_from_iterator(iterator it) noexcept;
static const sgtree & container_from_iterator(const_iterator it) noexcept;
static iterator s_iterator_to(reference value) noexcept;
static const_iterator s_iterator_to(const_reference value) noexcept;
static void init_node(reference value) noexcept;