diff options
Diffstat (limited to 'boost/container/set.hpp')
| -rw-r--r-- | boost/container/set.hpp | 560 |
1 files changed, 296 insertions, 264 deletions
diff --git a/boost/container/set.hpp b/boost/container/set.hpp index b25e7013fc..09ada20033 100644 --- a/boost/container/set.hpp +++ b/boost/container/set.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2011. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // @@ -42,32 +42,32 @@ namespace container { /// @cond // Forward declarations of operators < and ==, needed for friend declaration. template <class T, class Pred, class A> -inline bool operator==(const set<T,Pred,A>& x, +inline bool operator==(const set<T,Pred,A>& x, const set<T,Pred,A>& y); template <class T, class Pred, class A> -inline bool operator<(const set<T,Pred,A>& x, +inline bool operator<(const set<T,Pred,A>& x, const set<T,Pred,A>& y); /// @endcond -//! A set is a kind of associative container that supports unique keys (contains at -//! most one of each key value) and provides for fast retrieval of the keys themselves. -//! Class set supports bidirectional iterators. -//! -//! A set satisfies all of the requirements of a container and of a reversible container -//! , and of an associative container. A set also provides most operations described in +//! A set is a kind of associative container that supports unique keys (contains at +//! most one of each key value) and provides for fast retrieval of the keys themselves. +//! Class set supports bidirectional iterators. +//! +//! A set satisfies all of the requirements of a container and of a reversible container +//! , and of an associative container. A set also provides most operations described in //! for unique keys. #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED template <class T, class Pred = std::less<T>, class A = std::allocator<T> > #else template <class T, class Pred, class A> #endif -class set +class set { /// @cond private: BOOST_COPYABLE_AND_MOVABLE(set) - typedef container_detail::rbtree<T, T, + typedef container_detail::rbtree<T, T, container_detail::identity<T>, Pred, A> tree_t; tree_t m_tree; // red-black tree representing set typedef typename container_detail:: @@ -95,225 +95,240 @@ class set typedef typename tree_t::stored_allocator_type stored_allocator_type; //! <b>Effects</b>: Default constructs an empty set. - //! + //! //! <b>Complexity</b>: Constant. set() : m_tree() {} - //! <b>Effects</b>: Constructs an empty set using the specified comparison object + //! <b>Effects</b>: Constructs an empty set using the specified comparison object //! and allocator. - //! + //! //! <b>Complexity</b>: Constant. explicit set(const Pred& comp, const allocator_type& a = allocator_type()) : m_tree(comp, a) {} - //! <b>Effects</b>: Constructs an empty set using the specified comparison object and + //! <b>Effects</b>: Constructs an empty set using the specified comparison object and //! allocator, and inserts elements from the range [first ,last ). - //! - //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using //! comp and otherwise N logN, where N is last - first. template <class InputIterator> set(InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_tree(first, last, comp, a, true) + : m_tree(first, last, comp, a, true) {} - //! <b>Effects</b>: Constructs an empty set using the specified comparison object and + //! <b>Effects</b>: Constructs an empty set using the specified comparison object and //! allocator, and inserts elements from the ordered unique range [first ,last). This function //! is more efficient than the normal range creation for ordered ranges. //! //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be //! unique values. - //! + //! //! <b>Complexity</b>: Linear in N. template <class InputIterator> set( ordered_unique_range_t, InputIterator first, InputIterator last , const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_tree(ordered_range, first, last, comp, a) + : m_tree(ordered_range, first, last, comp, a) {} //! <b>Effects</b>: Copy constructs a set. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - set(const set& x) + set(const set& x) : m_tree(x.m_tree) {} //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources. - //! - //! <b>Complexity</b>: Construct. - //! + //! + //! <b>Complexity</b>: Constant. + //! //! <b>Postcondition</b>: x is emptied. - set(BOOST_RV_REF(set) x) + set(BOOST_RV_REF(set) x) : m_tree(boost::move(x.m_tree)) {} + //! <b>Effects</b>: Copy constructs a set using the specified allocator. + //! + //! <b>Complexity</b>: Linear in x.size(). + set(const set& x, const allocator_type &a) + : m_tree(x.m_tree, a) + {} + + //! <b>Effects</b>: Move constructs a set using the specified allocator. + //! Constructs *this using x's resources. + //! + //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. + set(BOOST_RV_REF(set) x, const allocator_type &a) + : m_tree(boost::move(x.m_tree), a) + {} + //! <b>Effects</b>: Makes *this a copy of x. - //! + //! //! <b>Complexity</b>: Linear in x.size(). set& operator=(BOOST_COPY_ASSIGN_REF(set) x) { m_tree = x.m_tree; return *this; } //! <b>Effects</b>: this->swap(x.get()). - //! + //! //! <b>Complexity</b>: Constant. set& operator=(BOOST_RV_REF(set) x) { m_tree = boost::move(x.m_tree); return *this; } //! <b>Effects</b>: Returns the comparison object out //! of which a was constructed. - //! + //! //! <b>Complexity</b>: Constant. - key_compare key_comp() const + key_compare key_comp() const { return m_tree.key_comp(); } //! <b>Effects</b>: Returns an object of value_compare constructed out //! of the comparison object. - //! + //! //! <b>Complexity</b>: Constant. - value_compare value_comp() const + value_compare value_comp() const { return m_tree.key_comp(); } //! <b>Effects</b>: Returns a copy of the Allocator that //! was passed to the object's constructor. - //! + //! //! <b>Complexity</b>: Constant. - allocator_type get_allocator() const + allocator_type get_allocator() const { return m_tree.get_allocator(); } - const stored_allocator_type &get_stored_allocator() const + const stored_allocator_type &get_stored_allocator() const { return m_tree.get_stored_allocator(); } stored_allocator_type &get_stored_allocator() { return m_tree.get_stored_allocator(); } //! <b>Effects</b>: Returns an iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant - iterator begin() + iterator begin() { return m_tree.begin(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator begin() const + const_iterator begin() const { return m_tree.begin(); } //! <b>Effects</b>: Returns an iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - iterator end() + iterator end() { return m_tree.end(); } //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator end() const + const_iterator end() const { return m_tree.end(); } - //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reverse_iterator rbegin() - { return m_tree.rbegin(); } + reverse_iterator rbegin() + { return m_tree.rbegin(); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin() const - { return m_tree.rbegin(); } + const_reverse_iterator rbegin() const + { return m_tree.rbegin(); } //! <b>Effects</b>: Returns a reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reverse_iterator rend() + reverse_iterator rend() { return m_tree.rend(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const + const_reverse_iterator rend() const { return m_tree.rend(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cbegin() const + const_iterator cbegin() const { return m_tree.cbegin(); } //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cend() const + const_iterator cend() const { return m_tree.cend(); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const - { return m_tree.crbegin(); } + const_reverse_iterator crbegin() const + { return m_tree.crbegin(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const + const_reverse_iterator crend() const { return m_tree.crend(); } //! <b>Effects</b>: Returns true if the container contains no elements. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - bool empty() const + bool empty() const { return m_tree.empty(); } //! <b>Effects</b>: Returns the number of the elements contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - size_type size() const + size_type size() const { return m_tree.size(); } //! <b>Effects</b>: Returns the largest possible size of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - size_type max_size() const + size_type max_size() const { return m_tree.max_size(); } //! <b>Effects</b>: Swaps the contents of *this and x. @@ -324,15 +339,15 @@ class set void swap(set& x) { m_tree.swap(x.m_tree); } - //! <b>Effects</b>: Inserts x if and only if there is no element in the container + //! <b>Effects</b>: Inserts x if and only if there is no element in the container //! with key equivalent to the key of x. //! - //! <b>Returns</b>: The bool component of the returned pair is true if and only + //! <b>Returns</b>: The bool component of the returned pair is true if and only //! if the insertion takes place, and the iterator component of the pair //! points to the element with key equivalent to the key of x. //! //! <b>Complexity</b>: Logarithmic. - std::pair<iterator,bool> insert(insert_const_ref_type x) + std::pair<iterator,bool> insert(insert_const_ref_type x) { return priv_insert(x); } #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -345,18 +360,18 @@ class set { return priv_insert(u); } #endif - //! <b>Effects</b>: Move constructs a new value from x if and only if there is + //! <b>Effects</b>: Move constructs a new value from x if and only if there is //! no element in the container with key equivalent to the key of x. //! - //! <b>Returns</b>: The bool component of the returned pair is true if and only + //! <b>Returns</b>: The bool component of the returned pair is true if and only //! if the insertion takes place, and the iterator component of the pair //! points to the element with key equivalent to the key of x. //! //! <b>Complexity</b>: Logarithmic. - std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) + std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) { return m_tree.insert_unique(boost::move(x)); } - //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is + //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is //! no element in the container with key equivalent to the key of x. //! p is a hint pointing to where the insert should start to search. //! @@ -365,7 +380,7 @@ class set //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator p, insert_const_ref_type x) + iterator insert(const_iterator p, insert_const_ref_type x) { return priv_insert(p, x); } #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -384,28 +399,28 @@ class set //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) + iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) { return m_tree.insert_unique(p, boost::move(x)); } //! <b>Requires</b>: first, last are not iterators into *this. //! - //! <b>Effects</b>: inserts each element from the range [first,last) if and only + //! <b>Effects</b>: inserts each element from the range [first,last) if and only //! if there is no element with key equivalent to the key of that element. //! //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) template <class InputIterator> - void insert(InputIterator first, InputIterator last) + void insert(InputIterator first, InputIterator last) { m_tree.insert_unique(first, last); } #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts an object x of type T constructed with - //! std::forward<Args>(args)... if and only if there is + //! std::forward<Args>(args)... if and only if there is //! no element in the container with equivalent value. //! and returns the iterator pointing to the //! newly inserted element. //! - //! <b>Returns</b>: The bool component of the returned pair is true if and only + //! <b>Returns</b>: The bool component of the returned pair is true if and only //! if the insertion takes place, and the iterator component of the pair //! points to the element with key equivalent to the key of x. //! @@ -418,7 +433,7 @@ class set { return m_tree.emplace_unique(boost::forward<Args>(args)...); } //! <b>Effects</b>: Inserts an object of type T constructed with - //! std::forward<Args>(args)... if and only if there is + //! std::forward<Args>(args)... if and only if there is //! no element in the container with equivalent value. //! p is a hint pointing to where the insert //! should start to search. @@ -451,11 +466,11 @@ class set //! <b>Effects</b>: Erases the element pointed to by p. //! //! <b>Returns</b>: Returns an iterator pointing to the element immediately - //! following q prior to the element being erased. If no such element exists, + //! following q prior to the element being erased. If no such element exists, //! returns end(). //! //! <b>Complexity</b>: Amortized constant time - iterator erase(const_iterator p) + iterator erase(const_iterator p) { return m_tree.erase(p); } //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. @@ -463,7 +478,7 @@ class set //! <b>Returns</b>: Returns the number of erased elements. //! //! <b>Complexity</b>: log(size()) + count(k) - size_type erase(const key_type& x) + size_type erase(const key_type& x) { return m_tree.erase(x); } //! <b>Effects</b>: Erases all the elements in the range [first, last). @@ -471,7 +486,7 @@ class set //! <b>Returns</b>: Returns last. //! //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. - iterator erase(const_iterator first, const_iterator last) + iterator erase(const_iterator first, const_iterator last) { return m_tree.erase(first, last); } //! <b>Effects</b>: erase(a.begin(),a.end()). @@ -479,41 +494,41 @@ class set //! <b>Postcondition</b>: size() == 0. //! //! <b>Complexity</b>: linear in size(). - void clear() + void clear() { m_tree.clear(); } //! <b>Returns</b>: An iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - iterator find(const key_type& x) + iterator find(const key_type& x) { return m_tree.find(x); } //! <b>Returns</b>: A const_iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - const_iterator find(const key_type& x) const + const_iterator find(const key_type& x) const { return m_tree.find(x); } //! <b>Returns</b>: The number of elements with key equivalent to x. //! //! <b>Complexity</b>: log(size())+count(k) - size_type count(const key_type& x) const + size_type count(const key_type& x) const { return m_tree.find(x) == m_tree.end() ? 0 : 1; } //! <b>Returns</b>: An iterator pointing to the first element with key not less //! than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator lower_bound(const key_type& x) + iterator lower_bound(const key_type& x) { return m_tree.lower_bound(x); } //! <b>Returns</b>: A const iterator pointing to the first element with key not //! less than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator lower_bound(const key_type& x) const + const_iterator lower_bound(const key_type& x) const { return m_tree.lower_bound(x); } //! <b>Returns</b>: An iterator pointing to the first element with key not less @@ -527,21 +542,21 @@ class set //! less than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator upper_bound(const key_type& x) const + const_iterator upper_bound(const key_type& x) const { return m_tree.upper_bound(x); } //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<iterator,iterator> - equal_range(const key_type& x) + std::pair<iterator,iterator> + equal_range(const key_type& x) { return m_tree.equal_range(x); } //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<const_iterator, const_iterator> - equal_range(const key_type& x) const + std::pair<const_iterator, const_iterator> + equal_range(const key_type& x) const { return m_tree.equal_range(x); } /// @cond @@ -552,47 +567,47 @@ class set friend bool operator< (const set<K1,C1,A1>&, const set<K1,C1,A1>&); private: - std::pair<iterator, bool> priv_insert(const T &x) + std::pair<iterator, bool> priv_insert(const T &x) { return m_tree.insert_unique(x); } - iterator priv_insert(const_iterator p, const T &x) + iterator priv_insert(const_iterator p, const T &x) { return m_tree.insert_unique(p, x); } /// @endcond }; template <class T, class Pred, class A> -inline bool operator==(const set<T,Pred,A>& x, - const set<T,Pred,A>& y) +inline bool operator==(const set<T,Pred,A>& x, + const set<T,Pred,A>& y) { return x.m_tree == y.m_tree; } template <class T, class Pred, class A> -inline bool operator<(const set<T,Pred,A>& x, - const set<T,Pred,A>& y) +inline bool operator<(const set<T,Pred,A>& x, + const set<T,Pred,A>& y) { return x.m_tree < y.m_tree; } template <class T, class Pred, class A> -inline bool operator!=(const set<T,Pred,A>& x, - const set<T,Pred,A>& y) +inline bool operator!=(const set<T,Pred,A>& x, + const set<T,Pred,A>& y) { return !(x == y); } template <class T, class Pred, class A> -inline bool operator>(const set<T,Pred,A>& x, - const set<T,Pred,A>& y) +inline bool operator>(const set<T,Pred,A>& x, + const set<T,Pred,A>& y) { return y < x; } template <class T, class Pred, class A> -inline bool operator<=(const set<T,Pred,A>& x, - const set<T,Pred,A>& y) +inline bool operator<=(const set<T,Pred,A>& x, + const set<T,Pred,A>& y) { return !(y < x); } template <class T, class Pred, class A> -inline bool operator>=(const set<T,Pred,A>& x, - const set<T,Pred,A>& y) +inline bool operator>=(const set<T,Pred,A>& x, + const set<T,Pred,A>& y) { return !(x < y); } template <class T, class Pred, class A> -inline void swap(set<T,Pred,A>& x, set<T,Pred,A>& y) +inline void swap(set<T,Pred,A>& x, set<T,Pred,A>& y) { x.swap(y); } /// @cond @@ -612,32 +627,32 @@ namespace container { // Forward declaration of operators < and ==, needed for friend declaration. template <class T, class Pred, class A> -inline bool operator==(const multiset<T,Pred,A>& x, +inline bool operator==(const multiset<T,Pred,A>& x, const multiset<T,Pred,A>& y); template <class T, class Pred, class A> -inline bool operator<(const multiset<T,Pred,A>& x, +inline bool operator<(const multiset<T,Pred,A>& x, const multiset<T,Pred,A>& y); /// @endcond -//! A multiset is a kind of associative container that supports equivalent keys -//! (possibly contains multiple copies of the same key value) and provides for +//! A multiset is a kind of associative container that supports equivalent keys +//! (possibly contains multiple copies of the same key value) and provides for //! fast retrieval of the keys themselves. Class multiset supports bidirectional iterators. -//! -//! A multiset satisfies all of the requirements of a container and of a reversible -//! container, and of an associative container). multiset also provides most operations +//! +//! A multiset satisfies all of the requirements of a container and of a reversible +//! container, and of an associative container). multiset also provides most operations //! described for duplicate keys. #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED template <class T, class Pred = std::less<T>, class A = std::allocator<T> > #else template <class T, class Pred, class A> #endif -class multiset +class multiset { /// @cond private: BOOST_COPYABLE_AND_MOVABLE(multiset) - typedef container_detail::rbtree<T, T, + typedef container_detail::rbtree<T, T, container_detail::identity<T>, Pred, A> tree_t; tree_t m_tree; // red-black tree representing multiset typedef typename container_detail:: @@ -666,7 +681,7 @@ class multiset //! <b>Effects</b>: Constructs an empty multiset using the specified comparison //! object and allocator. - //! + //! //! <b>Complexity</b>: Constant. multiset() : m_tree() @@ -674,7 +689,7 @@ class multiset //! <b>Effects</b>: Constructs an empty multiset using the specified comparison //! object and allocator. - //! + //! //! <b>Complexity</b>: Constant. explicit multiset(const Pred& comp, const allocator_type& a = allocator_type()) @@ -683,209 +698,226 @@ class multiset //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object //! and allocator, and inserts elements from the range [first ,last ). - //! - //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using //! comp and otherwise N logN, where N is last - first. template <class InputIterator> multiset(InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_tree(first, last, comp, a, false) + : m_tree(first, last, comp, a, false) {} - //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and + //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and //! allocator, and inserts elements from the ordered range [first ,last ). This function //! is more efficient than the normal range creation for ordered ranges. //! //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. - //! + //! //! <b>Complexity</b>: Linear in N. template <class InputIterator> multiset( ordered_range_t ordered_range, InputIterator first, InputIterator last , const Pred& comp = Pred() , const allocator_type& a = allocator_type()) - : m_tree(ordered_range, first, last, comp, a) + : m_tree(ordered_range, first, last, comp, a) {} //! <b>Effects</b>: Copy constructs a multiset. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - multiset(const multiset& x) + multiset(const multiset& x) : m_tree(x.m_tree) {} //! <b>Effects</b>: Move constructs a multiset. Constructs *this using x's resources. - //! - //! <b>Complexity</b>: Construct. - //! + //! + //! <b>Complexity</b>: Constant. + //! //! <b>Postcondition</b>: x is emptied. - multiset(BOOST_RV_REF(multiset) x) + multiset(BOOST_RV_REF(multiset) x) : m_tree(boost::move(x.m_tree)) {} + //! <b>Effects</b>: Copy constructs a multiset using the specified allocator. + //! + //! <b>Complexity</b>: Linear in x.size(). + multiset(const multiset& x, const allocator_type &a) + : m_tree(x.m_tree, a) + {} + + //! <b>Effects</b>: Move constructs a multiset using the specified allocator. + //! Constructs *this using x's resources. + //! + //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. + //! + //! <b>Postcondition</b>: x is emptied. + multiset(BOOST_RV_REF(multiset) x, const allocator_type &a) + : m_tree(boost::move(x.m_tree), a) + {} + //! <b>Effects</b>: Makes *this a copy of x. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x) + multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x) { m_tree = x.m_tree; return *this; } //! <b>Effects</b>: this->swap(x.get()). - //! + //! //! <b>Complexity</b>: Constant. - multiset& operator=(BOOST_RV_REF(multiset) x) + multiset& operator=(BOOST_RV_REF(multiset) x) { m_tree = boost::move(x.m_tree); return *this; } //! <b>Effects</b>: Returns the comparison object out //! of which a was constructed. - //! + //! //! <b>Complexity</b>: Constant. - key_compare key_comp() const + key_compare key_comp() const { return m_tree.key_comp(); } //! <b>Effects</b>: Returns an object of value_compare constructed out //! of the comparison object. - //! + //! //! <b>Complexity</b>: Constant. - value_compare value_comp() const + value_compare value_comp() const { return m_tree.key_comp(); } //! <b>Effects</b>: Returns a copy of the Allocator that //! was passed to the object's constructor. - //! + //! //! <b>Complexity</b>: Constant. - allocator_type get_allocator() const + allocator_type get_allocator() const { return m_tree.get_allocator(); } - const stored_allocator_type &get_stored_allocator() const + const stored_allocator_type &get_stored_allocator() const { return m_tree.get_stored_allocator(); } stored_allocator_type &get_stored_allocator() { return m_tree.get_stored_allocator(); } //! <b>Effects</b>: Returns an iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - iterator begin() + iterator begin() { return m_tree.begin(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator begin() const + const_iterator begin() const { return m_tree.begin(); } //! <b>Effects</b>: Returns an iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - iterator end() + iterator end() { return m_tree.end(); } //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator end() const + const_iterator end() const { return m_tree.end(); } - //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reverse_iterator rbegin() - { return m_tree.rbegin(); } + reverse_iterator rbegin() + { return m_tree.rbegin(); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin() const - { return m_tree.rbegin(); } + const_reverse_iterator rbegin() const + { return m_tree.rbegin(); } //! <b>Effects</b>: Returns a reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reverse_iterator rend() + reverse_iterator rend() { return m_tree.rend(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const + const_reverse_iterator rend() const { return m_tree.rend(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cbegin() const + const_iterator cbegin() const { return m_tree.cbegin(); } //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cend() const + const_iterator cend() const { return m_tree.cend(); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const - { return m_tree.crbegin(); } + const_reverse_iterator crbegin() const + { return m_tree.crbegin(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const + const_reverse_iterator crend() const { return m_tree.crend(); } //! <b>Effects</b>: Returns true if the container contains no elements. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - bool empty() const + bool empty() const { return m_tree.empty(); } //! <b>Effects</b>: Returns the number of the elements contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - size_type size() const + size_type size() const { return m_tree.size(); } //! <b>Effects</b>: Returns the largest possible size of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - size_type max_size() const + size_type max_size() const { return m_tree.max_size(); } //! <b>Effects</b>: Swaps the contents of *this and x. @@ -897,10 +929,10 @@ class multiset { m_tree.swap(x.m_tree); } //! <b>Effects</b>: Inserts x and returns the iterator pointing to the - //! newly inserted element. + //! newly inserted element. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(insert_const_ref_type x) + iterator insert(insert_const_ref_type x) { return priv_insert(x); } #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -920,7 +952,7 @@ class multiset //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(BOOST_RV_REF(value_type) x) + iterator insert(BOOST_RV_REF(value_type) x) { return m_tree.insert_equal(boost::move(x)); } //! <b>Effects</b>: Inserts a copy of x in the container. @@ -931,7 +963,7 @@ class multiset //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator p, insert_const_ref_type x) + iterator insert(const_iterator p, insert_const_ref_type x) { return priv_insert(p, x); } #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -952,7 +984,7 @@ class multiset //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) + iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) { return m_tree.insert_equal(p, boost::move(x)); } //! <b>Requires</b>: first, last are not iterators into *this. @@ -961,14 +993,14 @@ class multiset //! //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) template <class InputIterator> - void insert(InputIterator first, InputIterator last) + void insert(InputIterator first, InputIterator last) { m_tree.insert_equal(first, last); } #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts an object of type T constructed with //! std::forward<Args>(args)... and returns the iterator pointing to the - //! newly inserted element. + //! newly inserted element. //! //! <b>Complexity</b>: Logarithmic. template <class... Args> @@ -1008,11 +1040,11 @@ class multiset //! <b>Effects</b>: Erases the element pointed to by p. //! //! <b>Returns</b>: Returns an iterator pointing to the element immediately - //! following q prior to the element being erased. If no such element exists, + //! following q prior to the element being erased. If no such element exists, //! returns end(). //! //! <b>Complexity</b>: Amortized constant time - iterator erase(const_iterator p) + iterator erase(const_iterator p) { return m_tree.erase(p); } //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. @@ -1020,7 +1052,7 @@ class multiset //! <b>Returns</b>: Returns the number of erased elements. //! //! <b>Complexity</b>: log(size()) + count(k) - size_type erase(const key_type& x) + size_type erase(const key_type& x) { return m_tree.erase(x); } //! <b>Effects</b>: Erases all the elements in the range [first, last). @@ -1036,41 +1068,41 @@ class multiset //! <b>Postcondition</b>: size() == 0. //! //! <b>Complexity</b>: linear in size(). - void clear() + void clear() { m_tree.clear(); } //! <b>Returns</b>: An iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - iterator find(const key_type& x) + iterator find(const key_type& x) { return m_tree.find(x); } //! <b>Returns</b>: A const iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - const_iterator find(const key_type& x) const + const_iterator find(const key_type& x) const { return m_tree.find(x); } //! <b>Returns</b>: The number of elements with key equivalent to x. //! //! <b>Complexity</b>: log(size())+count(k) - size_type count(const key_type& x) const + size_type count(const key_type& x) const { return m_tree.count(x); } //! <b>Returns</b>: An iterator pointing to the first element with key not less //! than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator lower_bound(const key_type& x) + iterator lower_bound(const key_type& x) { return m_tree.lower_bound(x); } //! <b>Returns</b>: A const iterator pointing to the first element with key not //! less than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator lower_bound(const key_type& x) const + const_iterator lower_bound(const key_type& x) const { return m_tree.lower_bound(x); } //! <b>Returns</b>: An iterator pointing to the first element with key not less @@ -1084,21 +1116,21 @@ class multiset //! less than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator upper_bound(const key_type& x) const + const_iterator upper_bound(const key_type& x) const { return m_tree.upper_bound(x); } //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<iterator,iterator> - equal_range(const key_type& x) + std::pair<iterator,iterator> + equal_range(const key_type& x) { return m_tree.equal_range(x); } //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<const_iterator, const_iterator> - equal_range(const key_type& x) const + std::pair<const_iterator, const_iterator> + equal_range(const key_type& x) const { return m_tree.equal_range(x); } /// @cond @@ -1109,47 +1141,47 @@ class multiset friend bool operator< (const multiset<K1,C1,A1>&, const multiset<K1,C1,A1>&); private: - iterator priv_insert(const T &x) + iterator priv_insert(const T &x) { return m_tree.insert_equal(x); } - iterator priv_insert(const_iterator p, const T &x) + iterator priv_insert(const_iterator p, const T &x) { return m_tree.insert_equal(p, x); } /// @endcond }; template <class T, class Pred, class A> -inline bool operator==(const multiset<T,Pred,A>& x, - const multiset<T,Pred,A>& y) +inline bool operator==(const multiset<T,Pred,A>& x, + const multiset<T,Pred,A>& y) { return x.m_tree == y.m_tree; } template <class T, class Pred, class A> -inline bool operator<(const multiset<T,Pred,A>& x, - const multiset<T,Pred,A>& y) +inline bool operator<(const multiset<T,Pred,A>& x, + const multiset<T,Pred,A>& y) { return x.m_tree < y.m_tree; } template <class T, class Pred, class A> -inline bool operator!=(const multiset<T,Pred,A>& x, - const multiset<T,Pred,A>& y) +inline bool operator!=(const multiset<T,Pred,A>& x, + const multiset<T,Pred,A>& y) { return !(x == y); } template <class T, class Pred, class A> -inline bool operator>(const multiset<T,Pred,A>& x, - const multiset<T,Pred,A>& y) +inline bool operator>(const multiset<T,Pred,A>& x, + const multiset<T,Pred,A>& y) { return y < x; } template <class T, class Pred, class A> -inline bool operator<=(const multiset<T,Pred,A>& x, - const multiset<T,Pred,A>& y) +inline bool operator<=(const multiset<T,Pred,A>& x, + const multiset<T,Pred,A>& y) { return !(y < x); } template <class T, class Pred, class A> -inline bool operator>=(const multiset<T,Pred,A>& x, - const multiset<T,Pred,A>& y) +inline bool operator>=(const multiset<T,Pred,A>& x, + const multiset<T,Pred,A>& y) { return !(x < y); } template <class T, class Pred, class A> -inline void swap(multiset<T,Pred,A>& x, multiset<T,Pred,A>& y) +inline void swap(multiset<T,Pred,A>& x, multiset<T,Pred,A>& y) { x.swap(y); } /// @cond |