diff options
Diffstat (limited to 'boost/container/flat_set.hpp')
| -rw-r--r-- | boost/container/flat_set.hpp | 625 |
1 files changed, 352 insertions, 273 deletions
diff --git a/boost/container/flat_set.hpp b/boost/container/flat_set.hpp index f36730972e..09c95eb2f5 100644 --- a/boost/container/flat_set.hpp +++ b/boost/container/flat_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) // @@ -45,31 +45,31 @@ template <class T, class Pred, class A> class flat_set; template <class T, class Pred, class A> -inline bool operator==(const flat_set<T,Pred,A>& x, +inline bool operator==(const flat_set<T,Pred,A>& x, const flat_set<T,Pred,A>& y); template <class T, class Pred, class A> -inline bool operator<(const flat_set<T,Pred,A>& x, +inline bool operator<(const flat_set<T,Pred,A>& x, const flat_set<T,Pred,A>& y); /// @endcond -//! flat_set is a Sorted Associative Container that stores objects of type Key. -//! flat_set is a Simple Associative Container, meaning that its value type, -//! as well as its key type, is Key. It is also a Unique Associative Container, -//! meaning that no two elements are the same. -//! +//! flat_set is a Sorted Associative Container that stores objects of type Key. +//! flat_set is a Simple Associative Container, meaning that its value type, +//! as well as its key type, is Key. It is also a Unique Associative Container, +//! meaning that no two elements are the same. +//! //! flat_set is similar to std::set but it's implemented like an ordered vector. //! This means that inserting a new element into a flat_set invalidates //! previous iterators and references //! -//! Erasing an element of a flat_set invalidates iterators and references +//! Erasing an element of a flat_set invalidates iterators and references //! pointing to elements that come after (their keys are bigger) the erased element. #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 flat_set +class flat_set { /// @cond private: @@ -100,227 +100,245 @@ class flat_set typedef typename tree_t::allocator_type allocator_type; typedef typename tree_t::stored_allocator_type stored_allocator_type; - //! <b>Effects</b>: Defatuls constructs an empty flat_map. - //! + //! <b>Effects</b>: Default constructs an empty flat_set. + //! //! <b>Complexity</b>: Constant. explicit flat_set() : m_flat_tree() {} - //! <b>Effects</b>: Constructs an empty flat_map using the specified + //! <b>Effects</b>: Constructs an empty flat_set using the specified //! comparison object and allocator. - //! + //! //! <b>Complexity</b>: Constant. explicit flat_set(const Pred& comp, const allocator_type& a = allocator_type()) : m_flat_tree(comp, a) {} - //! <b>Effects</b>: Constructs an empty map 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> - flat_set(InputIterator first, InputIterator last, + flat_set(InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_flat_tree(comp, a) + : m_flat_tree(comp, a) { m_flat_tree.insert_unique(first, last); } - //! <b>Effects</b>: Constructs an empty flat_set using the specified comparison object and + //! <b>Effects</b>: Constructs an empty flat_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. + //! + //! <b>Note</b>: Non-standard extension. template <class InputIterator> - flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, + flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_flat_tree(ordered_range, first, last, comp, a) + : m_flat_tree(ordered_range, first, last, comp, a) {} - //! <b>Effects</b>: Copy constructs a map. - //! + //! <b>Effects</b>: Copy constructs a set. + //! //! <b>Complexity</b>: Linear in x.size(). - flat_set(const flat_set<T,Pred,A>& x) - : m_flat_tree(x.m_flat_tree) {} + flat_set(const flat_set& x) + : m_flat_tree(x.m_flat_tree) + {} - //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources. - //! - //! <b>Complexity</b>: Construct. - //! + //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources. + //! + //! <b>Complexity</b>: Constant. + //! //! <b>Postcondition</b>: x is emptied. - flat_set(BOOST_RV_REF(flat_set) mx) + flat_set(BOOST_RV_REF(flat_set) mx) : m_flat_tree(boost::move(mx.m_flat_tree)) {} + //! <b>Effects</b>: Copy constructs a set using the specified allocator. + //! + //! <b>Complexity</b>: Linear in x.size(). + flat_set(const flat_set& x, const allocator_type &a) + : m_flat_tree(x.m_flat_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 == mx.get_allocator(), linear otherwise + flat_set(BOOST_RV_REF(flat_set) mx, const allocator_type &a) + : m_flat_tree(boost::move(mx.m_flat_tree), a) + {} + //! <b>Effects</b>: Makes *this a copy of x. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - flat_set<T,Pred,A>& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x) + flat_set& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x) { m_flat_tree = x.m_flat_tree; return *this; } - //! <b>Effects</b>: Makes *this a copy of x. - //! + //! <b>Effects</b>: Makes *this a copy of the previous value of xx. + //! //! <b>Complexity</b>: Linear in x.size(). - flat_set<T,Pred,A>& operator=(BOOST_RV_REF(flat_set) mx) + flat_set& operator=(BOOST_RV_REF(flat_set) mx) { m_flat_tree = boost::move(mx.m_flat_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_flat_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_flat_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_flat_tree.get_allocator(); } - const stored_allocator_type &get_stored_allocator() const + const stored_allocator_type &get_stored_allocator() const { return m_flat_tree.get_stored_allocator(); } stored_allocator_type &get_stored_allocator() { return m_flat_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_flat_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_flat_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 cbegin() const + const_iterator cbegin() const { return m_flat_tree.cbegin(); } //! <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_flat_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_flat_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 cend() const + const_iterator cend() const { return m_flat_tree.cend(); } - //! <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_flat_tree.rbegin(); } + reverse_iterator rbegin() + { return m_flat_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_flat_tree.rbegin(); } + const_reverse_iterator rbegin() const + { return m_flat_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 crbegin() const - { return m_flat_tree.crbegin(); } + const_reverse_iterator crbegin() const + { return m_flat_tree.crbegin(); } //! <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() { return m_flat_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_flat_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 crend() const + const_reverse_iterator crend() const { return m_flat_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_flat_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_flat_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_flat_tree.max_size(); } //! <b>Effects</b>: Swaps the contents of *this and x. @@ -331,10 +349,10 @@ class flat_set void swap(flat_set& x) { m_flat_tree.swap(x.m_flat_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. //! @@ -342,7 +360,7 @@ class flat_set //! to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - 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) @@ -357,7 +375,7 @@ class flat_set //! <b>Effects</b>: Inserts a new value_type move constructed from the pair 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. //! @@ -365,10 +383,10 @@ class flat_set //! to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) + std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) { return m_flat_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. //! @@ -379,7 +397,7 @@ class flat_set //! right before p) plus insertion linear to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - 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) @@ -400,12 +418,12 @@ class flat_set //! right before p) plus insertion linear to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - iterator insert(const_iterator position, BOOST_RV_REF(value_type) x) + iterator insert(const_iterator position, BOOST_RV_REF(value_type) x) { return m_flat_tree.insert_unique(position, 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) @@ -413,16 +431,31 @@ class flat_set //! //! <b>Note</b>: If an element is inserted it might invalidate elements. template <class InputIterator> - void insert(InputIterator first, InputIterator last) + void insert(InputIterator first, InputIterator last) { m_flat_tree.insert_unique(first, last); } + //! <b>Requires</b>: first, last are not iterators into *this and + //! must be ordered according to the predicate and must be + //! unique values. + //! + //! <b>Effects</b>: inserts each element from the range [first,last) .This function + //! is more efficient than the normal range creation for ordered ranges. + //! + //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) + //! search time plus N*size() insertion time. + //! + //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements. + template <class InputIterator> + void insert(ordered_unique_range_t, InputIterator first, InputIterator last) + { m_flat_tree.insert_unique(ordered_unique_range, 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 no element in the container + //! std::forward<Args>(args)... 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. //! @@ -435,7 +468,7 @@ class flat_set { return m_flat_tree.emplace_unique(boost::forward<Args>(args)...); } //! <b>Effects</b>: Inserts an object of type T constructed with - //! std::forward<Args>(args)... in the container if and only if there is + //! std::forward<Args>(args)... 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. //! @@ -471,14 +504,14 @@ class flat_set //! <b>Effects</b>: Erases the element pointed to by position. //! //! <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>: Linear to the elements with keys bigger than position //! //! <b>Note</b>: Invalidates elements with keys //! not less than the erased element. - iterator erase(const_iterator position) + iterator erase(const_iterator position) { return m_flat_tree.erase(position); } //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. @@ -487,7 +520,7 @@ class flat_set //! //! <b>Complexity</b>: Logarithmic search time plus erasure time //! linear to the elements with bigger keys. - size_type erase(const key_type& x) + size_type erase(const key_type& x) { return m_flat_tree.erase(x); } //! <b>Effects</b>: Erases all the elements in the range [first, last). @@ -498,7 +531,7 @@ class flat_set //! //! <b>Complexity</b>: Logarithmic search time plus erasure time //! linear to the elements with bigger keys. - iterator erase(const_iterator first, const_iterator last) + iterator erase(const_iterator first, const_iterator last) { return m_flat_tree.erase(first, last); } //! <b>Effects</b>: erase(a.begin(),a.end()). @@ -506,7 +539,7 @@ class flat_set //! <b>Postcondition</b>: size() == 0. //! //! <b>Complexity</b>: linear in size(). - void clear() + void clear() { m_flat_tree.clear(); } //! <b>Effects</b>: Tries to deallocate the excess of memory created @@ -522,34 +555,34 @@ class flat_set //! 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_flat_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.s - const_iterator find(const key_type& x) const + const_iterator find(const key_type& x) const { return m_flat_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_flat_tree.find(x) == m_flat_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_flat_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_flat_tree.lower_bound(x); } //! <b>Returns</b>: An iterator pointing to the first element with key not less @@ -563,42 +596,42 @@ class flat_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_flat_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<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_flat_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<iterator,iterator> - equal_range(const key_type& x) + std::pair<iterator,iterator> + equal_range(const key_type& x) { return m_flat_tree.equal_range(x); } //! <b>Effects</b>: Number of elements for which memory has been allocated. //! capacity() is always greater than or equal to size(). - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - size_type capacity() const + size_type capacity() const { return m_flat_tree.capacity(); } //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no //! effect. Otherwise, it is a request for allocation of additional memory. //! If the request is successful, then capacity() is greater than or equal to //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. - //! + //! //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws. //! //! <b>Note</b>: If capacity() is less than "count", iterators and references to //! to values might be invalidated. - void reserve(size_type count) + void reserve(size_type count) { m_flat_tree.reserve(count); } /// @cond @@ -609,46 +642,46 @@ class flat_set friend bool operator< (const flat_set<K1,C1,A1>&, const flat_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_flat_tree.insert_unique(x); } - iterator priv_insert(const_iterator p, const T &x) + iterator priv_insert(const_iterator p, const T &x) { return m_flat_tree.insert_unique(p, x); } /// @endcond }; template <class T, class Pred, class A> -inline bool operator==(const flat_set<T,Pred,A>& x, - const flat_set<T,Pred,A>& y) +inline bool operator==(const flat_set<T,Pred,A>& x, + const flat_set<T,Pred,A>& y) { return x.m_flat_tree == y.m_flat_tree; } template <class T, class Pred, class A> -inline bool operator<(const flat_set<T,Pred,A>& x, - const flat_set<T,Pred,A>& y) +inline bool operator<(const flat_set<T,Pred,A>& x, + const flat_set<T,Pred,A>& y) { return x.m_flat_tree < y.m_flat_tree; } template <class T, class Pred, class A> -inline bool operator!=(const flat_set<T,Pred,A>& x, - const flat_set<T,Pred,A>& y) +inline bool operator!=(const flat_set<T,Pred,A>& x, + const flat_set<T,Pred,A>& y) { return !(x == y); } template <class T, class Pred, class A> -inline bool operator>(const flat_set<T,Pred,A>& x, - const flat_set<T,Pred,A>& y) +inline bool operator>(const flat_set<T,Pred,A>& x, + const flat_set<T,Pred,A>& y) { return y < x; } template <class T, class Pred, class A> -inline bool operator<=(const flat_set<T,Pred,A>& x, - const flat_set<T,Pred,A>& y) +inline bool operator<=(const flat_set<T,Pred,A>& x, + const flat_set<T,Pred,A>& y) { return !(y < x); } template <class T, class Pred, class A> -inline bool operator>=(const flat_set<T,Pred,A>& x, - const flat_set<T,Pred,A>& y) +inline bool operator>=(const flat_set<T,Pred,A>& x, + const flat_set<T,Pred,A>& y) { return !(x < y); } template <class T, class Pred, class A> -inline void swap(flat_set<T,Pred,A>& x, flat_set<T,Pred,A>& y) +inline void swap(flat_set<T,Pred,A>& x, flat_set<T,Pred,A>& y) { x.swap(y); } /// @cond @@ -675,31 +708,31 @@ template <class T, class Pred, class A> class flat_multiset; template <class T, class Pred, class A> -inline bool operator==(const flat_multiset<T,Pred,A>& x, +inline bool operator==(const flat_multiset<T,Pred,A>& x, const flat_multiset<T,Pred,A>& y); template <class T, class Pred, class A> -inline bool operator<(const flat_multiset<T,Pred,A>& x, +inline bool operator<(const flat_multiset<T,Pred,A>& x, const flat_multiset<T,Pred,A>& y); /// @endcond -//! flat_multiset is a Sorted Associative Container that stores objects of type Key. -//! flat_multiset is a Simple Associative Container, meaning that its value type, +//! flat_multiset is a Sorted Associative Container that stores objects of type Key. +//! flat_multiset is a Simple Associative Container, meaning that its value type, //! as well as its key type, is Key. //! flat_Multiset can store multiple copies of the same key value. -//! +//! //! flat_multiset is similar to std::multiset but it's implemented like an ordered vector. //! This means that inserting a new element into a flat_multiset invalidates //! previous iterators and references //! -//! Erasing an element of a flat_multiset invalidates iterators and references +//! Erasing an element of a flat_multiset invalidates iterators and references //! pointing to elements that come after (their keys are equal or bigger) the erased element. #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 flat_multiset +class flat_multiset { /// @cond private: @@ -729,8 +762,8 @@ class flat_multiset typedef typename tree_t::allocator_type allocator_type; typedef typename tree_t::stored_allocator_type stored_allocator_type; - //! <b>Effects</b>: Defatuls constructs an empty flat_map. - //! + //! <b>Effects</b>: Default constructs an empty flat_multiset. + //! //! <b>Complexity</b>: Constant. explicit flat_multiset() : m_flat_tree() @@ -744,187 +777,219 @@ class flat_multiset flat_multiset(InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_flat_tree(comp, a) + : m_flat_tree(comp, a) { m_flat_tree.insert_equal(first, last); } - //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and + //! <b>Effects</b>: Constructs an empty flat_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. + //! + //! <b>Note</b>: Non-standard extension. template <class InputIterator> flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) - : m_flat_tree(ordered_range, first, last, comp, a) + : m_flat_tree(ordered_range, first, last, comp, a) {} - flat_multiset(const flat_multiset<T,Pred,A>& x) - : m_flat_tree(x.m_flat_tree) {} + //! <b>Effects</b>: Copy constructs a flat_multiset. + //! + //! <b>Complexity</b>: Linear in x.size(). + flat_multiset(const flat_multiset& x) + : m_flat_tree(x.m_flat_tree) + {} + + //! <b>Effects</b>: Move constructs a flat_multiset. Constructs *this using x's resources. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Postcondition</b>: x is emptied. + flat_multiset(BOOST_RV_REF(flat_multiset) mx) + : m_flat_tree(boost::move(mx.m_flat_tree)) + {} + + //! <b>Effects</b>: Copy constructs a flat_multiset using the specified allocator. + //! + //! <b>Complexity</b>: Linear in x.size(). + flat_multiset(const flat_multiset& x, const allocator_type &a) + : m_flat_tree(x.m_flat_tree, a) + {} - flat_multiset(BOOST_RV_REF(flat_multiset) x) - : m_flat_tree(boost::move(x.m_flat_tree)) + //! <b>Effects</b>: Move constructs a flat_multiset using the specified allocator. + //! Constructs *this using x's resources. + //! + //! <b>Complexity</b>: Constant if a == mx.get_allocator(), linear otherwise + flat_multiset(BOOST_RV_REF(flat_multiset) mx, const allocator_type &a) + : m_flat_tree(boost::move(mx.m_flat_tree), a) {} - flat_multiset<T,Pred,A>& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x) + //! <b>Effects</b>: Makes *this a copy of x. + //! + //! <b>Complexity</b>: Linear in x.size(). + flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x) { m_flat_tree = x.m_flat_tree; return *this; } - flat_multiset<T,Pred,A>& operator=(BOOST_RV_REF(flat_multiset) mx) + //! <b>Effects</b>: Makes *this a copy of x. + //! + //! <b>Complexity</b>: Linear in x.size(). + flat_multiset& operator=(BOOST_RV_REF(flat_multiset) mx) { m_flat_tree = boost::move(mx.m_flat_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_flat_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_flat_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_flat_tree.get_allocator(); } - const stored_allocator_type &get_stored_allocator() const + const stored_allocator_type &get_stored_allocator() const { return m_flat_tree.get_stored_allocator(); } stored_allocator_type &get_stored_allocator() { return m_flat_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_flat_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_flat_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 cbegin() const + const_iterator cbegin() const { return m_flat_tree.cbegin(); } //! <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_flat_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_flat_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 cend() const + const_iterator cend() const { return m_flat_tree.cend(); } - //! <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_flat_tree.rbegin(); } + reverse_iterator rbegin() + { return m_flat_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_flat_tree.rbegin(); } + const_reverse_iterator rbegin() const + { return m_flat_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 crbegin() const - { return m_flat_tree.crbegin(); } + const_reverse_iterator crbegin() const + { return m_flat_tree.crbegin(); } //! <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() { return m_flat_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_flat_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 crend() const + const_reverse_iterator crend() const { return m_flat_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_flat_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_flat_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_flat_tree.max_size(); } //! <b>Effects</b>: Swaps the contents of *this and x. @@ -936,13 +1001,13 @@ class flat_multiset { m_flat_tree.swap(x.m_flat_tree); } //! <b>Effects</b>: Inserts x and returns the iterator pointing to the - //! newly inserted element. + //! newly inserted element. //! //! <b>Complexity</b>: Logarithmic search time plus linear insertion //! to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - 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) @@ -955,13 +1020,13 @@ class flat_multiset #endif //! <b>Effects</b>: Inserts a new value_type move constructed from x - //! and returns the iterator pointing to the newly inserted element. + //! and returns the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic search time plus linear insertion //! to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - iterator insert(BOOST_RV_REF(value_type) x) + iterator insert(BOOST_RV_REF(value_type) x) { return m_flat_tree.insert_equal(boost::move(x)); } //! <b>Effects</b>: Inserts a copy of x in the container. @@ -974,7 +1039,7 @@ class flat_multiset //! right before p) plus insertion linear to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - 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) @@ -997,7 +1062,7 @@ class flat_multiset //! right before p) plus insertion linear to the elements with bigger keys than x. //! //! <b>Note</b>: If an element is inserted it might invalidate elements. - iterator insert(const_iterator position, BOOST_RV_REF(value_type) x) + iterator insert(const_iterator position, BOOST_RV_REF(value_type) x) { return m_flat_tree.insert_equal(position, boost::move(x)); } //! <b>Requires</b>: first, last are not iterators into *this. @@ -1009,14 +1074,28 @@ class flat_multiset //! //! <b>Note</b>: If an element is inserted it might invalidate elements. template <class InputIterator> - void insert(InputIterator first, InputIterator last) + void insert(InputIterator first, InputIterator last) { m_flat_tree.insert_equal(first, last); } + //! <b>Requires</b>: first, last are not iterators into *this and + //! must be ordered according to the predicate. + //! + //! <b>Effects</b>: inserts each element from the range [first,last) .This function + //! is more efficient than the normal range creation for ordered ranges. + //! + //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) + //! search time plus N*size() insertion time. + //! + //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements. + template <class InputIterator> + void insert(ordered_range_t, InputIterator first, InputIterator last) + { m_flat_tree.insert_equal(ordered_range, 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 search time plus linear insertion //! to the elements with bigger keys than x. @@ -1062,14 +1141,14 @@ class flat_multiset //! <b>Effects</b>: Erases the element pointed to by position. //! //! <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>: Linear to the elements with keys bigger than position //! //! <b>Note</b>: Invalidates elements with keys //! not less than the erased element. - iterator erase(const_iterator position) + iterator erase(const_iterator position) { return m_flat_tree.erase(position); } //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. @@ -1078,7 +1157,7 @@ class flat_multiset //! //! <b>Complexity</b>: Logarithmic search time plus erasure time //! linear to the elements with bigger keys. - size_type erase(const key_type& x) + size_type erase(const key_type& x) { return m_flat_tree.erase(x); } //! <b>Effects</b>: Erases all the elements in the range [first, last). @@ -1089,7 +1168,7 @@ class flat_multiset //! //! <b>Complexity</b>: Logarithmic search time plus erasure time //! linear to the elements with bigger keys. - iterator erase(const_iterator first, const_iterator last) + iterator erase(const_iterator first, const_iterator last) { return m_flat_tree.erase(first, last); } //! <b>Effects</b>: erase(a.begin(),a.end()). @@ -1097,7 +1176,7 @@ class flat_multiset //! <b>Postcondition</b>: size() == 0. //! //! <b>Complexity</b>: linear in size(). - void clear() + void clear() { m_flat_tree.clear(); } //! <b>Effects</b>: Tries to deallocate the excess of memory created @@ -1113,34 +1192,34 @@ class flat_multiset //! 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_flat_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.s - const_iterator find(const key_type& x) const + const_iterator find(const key_type& x) const { return m_flat_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_flat_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_flat_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_flat_tree.lower_bound(x); } //! <b>Returns</b>: An iterator pointing to the first element with key not less @@ -1154,42 +1233,42 @@ class flat_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_flat_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<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_flat_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<iterator,iterator> - equal_range(const key_type& x) + std::pair<iterator,iterator> + equal_range(const key_type& x) { return m_flat_tree.equal_range(x); } //! <b>Effects</b>: Number of elements for which memory has been allocated. //! capacity() is always greater than or equal to size(). - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - size_type capacity() const + size_type capacity() const { return m_flat_tree.capacity(); } //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no //! effect. Otherwise, it is a request for allocation of additional memory. //! If the request is successful, then capacity() is greater than or equal to //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. - //! + //! //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws. //! //! <b>Note</b>: If capacity() is less than "count", iterators and references to //! to values might be invalidated. - void reserve(size_type count) + void reserve(size_type count) { m_flat_tree.reserve(count); } /// @cond @@ -1200,46 +1279,46 @@ class flat_multiset friend bool operator< (const flat_multiset<K1,C1,A1>&, const flat_multiset<K1,C1,A1>&); private: - iterator priv_insert(const T &x) + iterator priv_insert(const T &x) { return m_flat_tree.insert_equal(x); } - iterator priv_insert(const_iterator p, const T &x) + iterator priv_insert(const_iterator p, const T &x) { return m_flat_tree.insert_equal(p, x); } /// @endcond }; template <class T, class Pred, class A> -inline bool operator==(const flat_multiset<T,Pred,A>& x, - const flat_multiset<T,Pred,A>& y) +inline bool operator==(const flat_multiset<T,Pred,A>& x, + const flat_multiset<T,Pred,A>& y) { return x.m_flat_tree == y.m_flat_tree; } template <class T, class Pred, class A> -inline bool operator<(const flat_multiset<T,Pred,A>& x, - const flat_multiset<T,Pred,A>& y) +inline bool operator<(const flat_multiset<T,Pred,A>& x, + const flat_multiset<T,Pred,A>& y) { return x.m_flat_tree < y.m_flat_tree; } template <class T, class Pred, class A> -inline bool operator!=(const flat_multiset<T,Pred,A>& x, - const flat_multiset<T,Pred,A>& y) +inline bool operator!=(const flat_multiset<T,Pred,A>& x, + const flat_multiset<T,Pred,A>& y) { return !(x == y); } template <class T, class Pred, class A> -inline bool operator>(const flat_multiset<T,Pred,A>& x, - const flat_multiset<T,Pred,A>& y) +inline bool operator>(const flat_multiset<T,Pred,A>& x, + const flat_multiset<T,Pred,A>& y) { return y < x; } template <class T, class Pred, class A> -inline bool operator<=(const flat_multiset<T,Pred,A>& x, - const flat_multiset<T,Pred,A>& y) +inline bool operator<=(const flat_multiset<T,Pred,A>& x, + const flat_multiset<T,Pred,A>& y) { return !(y < x); } template <class T, class Pred, class A> -inline bool operator>=(const flat_multiset<T,Pred,A>& x, - const flat_multiset<T,Pred,A>& y) +inline bool operator>=(const flat_multiset<T,Pred,A>& x, + const flat_multiset<T,Pred,A>& y) { return !(x < y); } template <class T, class Pred, class A> -inline void swap(flat_multiset<T,Pred,A>& x, flat_multiset<T,Pred,A>& y) +inline void swap(flat_multiset<T,Pred,A>& x, flat_multiset<T,Pred,A>& y) { x.swap(y); } /// @cond |