diff options
Diffstat (limited to 'boost/container/map.hpp')
| -rw-r--r-- | boost/container/map.hpp | 628 |
1 files changed, 370 insertions, 258 deletions
diff --git a/boost/container/map.hpp b/boost/container/map.hpp index 8f7ecd42b3..91cbd35429 100644 --- a/boost/container/map.hpp +++ b/boost/container/map.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) // @@ -47,20 +47,20 @@ namespace container { /// @cond // Forward declarations of operators == and <, needed for friend declarations. template <class Key, class T, class Pred, class A> -inline bool operator==(const map<Key,T,Pred,A>& x, +inline bool operator==(const map<Key,T,Pred,A>& x, const map<Key,T,Pred,A>& y); template <class Key, class T, class Pred, class A> -inline bool operator<(const map<Key,T,Pred,A>& x, +inline bool operator<(const map<Key,T,Pred,A>& x, const map<Key,T,Pred,A>& y); /// @endcond -//! A map is a kind of associative container that supports unique keys (contains at -//! most one of each key value) and provides for fast retrieval of values of another +//! A map is a kind of associative container that supports unique keys (contains at +//! most one of each key value) and provides for fast retrieval of values of another //! type T based on the keys. The map class supports bidirectional iterators. -//! -//! A map satisfies all of the requirements of a container and of a reversible -//! container and of an associative container. For a +//! +//! A map satisfies all of the requirements of a container and of a reversible +//! container and of an associative container. For a //! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>. //! //! Pred is the ordering function for Keys (e.g. <i>std::less<Key></i>). @@ -72,15 +72,15 @@ template <class Key, class T, class Pred = std::less< std::pair< const Key, T> > #else template <class Key, class T, class Pred, class A> #endif -class map +class map { /// @cond private: BOOST_COPYABLE_AND_MOVABLE(map) - typedef container_detail::rbtree<Key, - std::pair<const Key, T>, - container_detail::select1st< std::pair<const Key, T> >, - Pred, + typedef container_detail::rbtree<Key, + std::pair<const Key, T>, + container_detail::select1st< std::pair<const Key, T> >, + Pred, A> tree_t; tree_t m_tree; // red-black tree representing map @@ -112,7 +112,7 @@ class map /// @cond class value_compare_impl : public Pred, - public std::binary_function<value_type, value_type, bool> + public std::binary_function<value_type, value_type, bool> { friend class map<Key,T,Pred,A>; protected : @@ -126,7 +126,7 @@ class map typedef value_compare_impl value_compare; //! <b>Effects</b>: Default constructs an empty map. - //! + //! //! <b>Complexity</b>: Constant. map() : m_tree() @@ -135,9 +135,9 @@ class map BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } - //! <b>Effects</b>: Constructs an empty map using the specified comparison object + //! <b>Effects</b>: Constructs an empty map using the specified comparison object //! and allocator. - //! + //! //! <b>Complexity</b>: Constant. explicit map(const Pred& comp, const allocator_type& a = allocator_type()) @@ -147,204 +147,261 @@ class map BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } - //! <b>Effects</b>: Constructs an empty map using the specified comparison object and + //! <b>Effects</b>: Constructs an empty map 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> map(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) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } - //! <b>Effects</b>: Constructs an empty map using the specified comparison object and + //! <b>Effects</b>: Constructs an empty map 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> map( 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) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } //! <b>Effects</b>: Copy constructs a map. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - map(const map<Key,T,Pred,A>& x) + map(const map& x) : m_tree(x.m_tree) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources. - //! - //! <b>Complexity</b>: Construct. - //! + //! + //! <b>Complexity</b>: Constant. + //! //! <b>Postcondition</b>: x is emptied. - map(BOOST_RV_REF(map) x) + map(BOOST_RV_REF(map) x) : m_tree(boost::move(x.m_tree)) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + } + + //! <b>Effects</b>: Copy constructs a map using the specified allocator. + //! + //! <b>Complexity</b>: Linear in x.size(). + map(const map& x, const allocator_type &a) + : m_tree(x.m_tree, a) + { + //Allocator type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + } + + //! <b>Effects</b>: Move constructs a map using the specified allocator. + //! Constructs *this using x's resources. + //! + //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise. + //! + //! <b>Postcondition</b>: x is emptied. + map(BOOST_RV_REF(map) x, const allocator_type &a) + : m_tree(boost::move(x.m_tree), a) + { + //Allocator type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } //! <b>Effects</b>: Makes *this a copy of x. - //! + //! //! <b>Complexity</b>: Linear in x.size(). map& operator=(BOOST_COPY_ASSIGN_REF(map) x) { m_tree = x.m_tree; return *this; } //! <b>Effects</b>: this->swap(x.get()). - //! + //! //! <b>Complexity</b>: Constant. map& operator=(BOOST_RV_REF(map) 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 value_compare(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 this->cbegin(); } + + //! <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 { 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 + { return this->cend(); } + + //! <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 cend() 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() + 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 this->crbegin(); } + + //! <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 + const_reverse_iterator crbegin() 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 + { return this->crend(); } + + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const + const_reverse_iterator crend() const { return m_tree.rend(); } //! <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(); } #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - //! Effects: If there is no key equivalent to x in the map, inserts + //! Effects: If there is no key equivalent to x in the map, inserts //! value_type(x, T()) into the map. - //! + //! //! Returns: A reference to the mapped_type corresponding to x in *this. - //! + //! //! Complexity: Logarithmic. mapped_type& operator[](const key_type &k); - //! Effects: If there is no key equivalent to x in the map, inserts + //! Effects: If there is no key equivalent to x in the map, inserts //! value_type(boost::move(x), T()) into the map (the key is move-constructed) - //! + //! //! Returns: A reference to the mapped_type corresponding to x in *this. - //! + //! //! Complexity: Logarithmic. mapped_type& operator[](key_type &&k); #else @@ -383,62 +440,62 @@ class map void swap(map& 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(const value_type& x) + std::pair<iterator,bool> insert(const value_type& x) { return m_tree.insert_unique(x); } - //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if + //! <b>Effects</b>: Inserts a new value_type created 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. //! //! <b>Complexity</b>: Logarithmic. - std::pair<iterator,bool> insert(const nonconst_value_type& x) + std::pair<iterator,bool> insert(const nonconst_value_type& x) { return m_tree.insert_unique(x); } //! <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. //! //! <b>Complexity</b>: Logarithmic. - std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x) + std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x) { return m_tree.insert_unique(boost::move(x)); } //! <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. //! //! <b>Complexity</b>: Logarithmic. - std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_impl_value_type) x) + std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_impl_value_type) x) { return m_tree.insert_unique(boost::move(x)); } - //! <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. //! @@ -450,7 +507,7 @@ class map iterator insert(iterator position, const value_type& x) { return m_tree.insert_unique(position, x); } - //! <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. //! p is a hint pointing to where the insert should start to search. //! @@ -462,7 +519,7 @@ class map iterator insert(iterator position, BOOST_RV_REF(nonconst_value_type) x) { return m_tree.insert_unique(position, boost::move(x)); } - //! <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. //! p is a hint pointing to where the insert should start to search. //! @@ -494,22 +551,22 @@ class map //! <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)... 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 an equivalent key. //! p is a hint pointing to where the insert should start to search. //! - //! <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. //! @@ -520,7 +577,7 @@ class map { return m_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 an equivalent key. //! p is a hint pointing to where the insert should start to search. //! @@ -554,11 +611,11 @@ class map //! <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>: Amortized constant time - iterator erase(const_iterator position) + iterator erase(const_iterator position) { return m_tree.erase(position); } //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. @@ -566,7 +623,7 @@ class map //! <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). @@ -582,67 +639,67 @@ class map //! <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 //! than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator upper_bound(const key_type& x) + iterator upper_bound(const key_type& x) { return m_tree.upper_bound(x); } //! <b>Returns</b>: A const iterator pointing to the first element with key not //! 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 @@ -666,7 +723,7 @@ class map return (*i).second; } - mapped_type& priv_subscript(BOOST_RV_REF(key_type) mk) + mapped_type& priv_subscript(BOOST_RV_REF(key_type) mk) { key_type &k = mk; //we can optimize this @@ -684,37 +741,37 @@ class map }; template <class Key, class T, class Pred, class A> -inline bool operator==(const map<Key,T,Pred,A>& x, - const map<Key,T,Pred,A>& y) +inline bool operator==(const map<Key,T,Pred,A>& x, + const map<Key,T,Pred,A>& y) { return x.m_tree == y.m_tree; } template <class Key, class T, class Pred, class A> -inline bool operator<(const map<Key,T,Pred,A>& x, - const map<Key,T,Pred,A>& y) +inline bool operator<(const map<Key,T,Pred,A>& x, + const map<Key,T,Pred,A>& y) { return x.m_tree < y.m_tree; } template <class Key, class T, class Pred, class A> -inline bool operator!=(const map<Key,T,Pred,A>& x, - const map<Key,T,Pred,A>& y) +inline bool operator!=(const map<Key,T,Pred,A>& x, + const map<Key,T,Pred,A>& y) { return !(x == y); } template <class Key, class T, class Pred, class A> -inline bool operator>(const map<Key,T,Pred,A>& x, - const map<Key,T,Pred,A>& y) +inline bool operator>(const map<Key,T,Pred,A>& x, + const map<Key,T,Pred,A>& y) { return y < x; } template <class Key, class T, class Pred, class A> -inline bool operator<=(const map<Key,T,Pred,A>& x, - const map<Key,T,Pred,A>& y) +inline bool operator<=(const map<Key,T,Pred,A>& x, + const map<Key,T,Pred,A>& y) { return !(y < x); } template <class Key, class T, class Pred, class A> -inline bool operator>=(const map<Key,T,Pred,A>& x, - const map<Key,T,Pred,A>& y) +inline bool operator>=(const map<Key,T,Pred,A>& x, + const map<Key,T,Pred,A>& y) { return !(x < y); } template <class Key, class T, class Pred, class A> -inline void swap(map<Key,T,Pred,A>& x, map<Key,T,Pred,A>& y) +inline void swap(map<Key,T,Pred,A>& x, map<Key,T,Pred,A>& y) { x.swap(y); } /// @cond @@ -722,11 +779,11 @@ inline void swap(map<Key,T,Pred,A>& x, map<Key,T,Pred,A>& y) // Forward declaration of operators < and ==, needed for friend declaration. template <class Key, class T, class Pred, class A> -inline bool operator==(const multimap<Key,T,Pred,A>& x, +inline bool operator==(const multimap<Key,T,Pred,A>& x, const multimap<Key,T,Pred,A>& y); template <class Key, class T, class Pred, class A> -inline bool operator<(const multimap<Key,T,Pred,A>& x, +inline bool operator<(const multimap<Key,T,Pred,A>& x, const multimap<Key,T,Pred,A>& y); } //namespace container { @@ -743,14 +800,14 @@ namespace container { /// @endcond -//! A multimap is a kind of associative container that supports equivalent keys -//! (possibly containing multiple copies of the same key value) and provides for +//! A multimap is a kind of associative container that supports equivalent keys +//! (possibly containing multiple copies of the same key value) and provides for //! fast retrieval of values of another type T based on the keys. The multimap class //! supports bidirectional iterators. -//! -//! A multimap satisfies all of the requirements of a container and of a reversible -//! container and of an associative container. For a -//! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>. +//! +//! A multimap satisfies all of the requirements of a container and of a reversible +//! container and of an associative container. For a +//! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>. //! //! Pred is the ordering function for Keys (e.g. <i>std::less<Key></i>). //! @@ -761,15 +818,15 @@ template <class Key, class T, class Pred = std::less< std::pair< const Key, T> > #else template <class Key, class T, class Pred, class A> #endif -class multimap +class multimap { /// @cond private: BOOST_COPYABLE_AND_MOVABLE(multimap) - typedef container_detail::rbtree<Key, - std::pair<const Key, T>, - container_detail::select1st< std::pair<const Key, T> >, - Pred, + typedef container_detail::rbtree<Key, + std::pair<const Key, T>, + container_detail::select1st< std::pair<const Key, T> >, + Pred, A> tree_t; tree_t m_tree; // red-black tree representing map typedef typename container_detail:: @@ -802,7 +859,7 @@ class multimap /// @cond class value_compare_impl : public Pred, - public std::binary_function<value_type, value_type, bool> + public std::binary_function<value_type, value_type, bool> { friend class multimap<Key,T,Pred,A>; protected : @@ -816,7 +873,7 @@ class multimap typedef value_compare_impl value_compare; //! <b>Effects</b>: Default constructs an empty multimap. - //! + //! //! <b>Complexity</b>: Constant. multimap() : m_tree() @@ -827,195 +884,250 @@ class multimap //! <b>Effects</b>: Constructs an empty multimap using the specified comparison //! object and allocator. - //! + //! //! <b>Complexity</b>: Constant. explicit multimap(const Pred& comp, const allocator_type& a = allocator_type()) : m_tree(comp, a) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } //! <b>Effects</b>: Constructs an empty multimap 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> multimap(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) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } - //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and + //! <b>Effects</b>: Constructs an empty multimap 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> multimap(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 multimap. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - multimap(const multimap<Key,T,Pred,A>& x) + multimap(const multimap& x) : m_tree(x.m_tree) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources. - //! - //! <b>Complexity</b>: Construct. - //! + //! + //! <b>Complexity</b>: Constant. + //! //! <b>Postcondition</b>: x is emptied. - multimap(BOOST_RV_REF(multimap) x) + multimap(BOOST_RV_REF(multimap) x) : m_tree(boost::move(x.m_tree)) { //Allocator type must be std::pair<CONST Key, T> - BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + } + + //! <b>Effects</b>: Copy constructs a multimap. + //! + //! <b>Complexity</b>: Linear in x.size(). + multimap(const multimap& x, const allocator_type &a) + : m_tree(x.m_tree, a) + { + //Allocator type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); + } + + //! <b>Effects</b>: Move constructs a multimap 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. + multimap(BOOST_RV_REF(multimap) x, const allocator_type &a) + : m_tree(boost::move(x.m_tree), a) + { + //Allocator type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename A::value_type>::value)); } //! <b>Effects</b>: Makes *this a copy of x. - //! + //! //! <b>Complexity</b>: Linear in x.size(). - multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x) + multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x) { m_tree = x.m_tree; return *this; } //! <b>Effects</b>: this->swap(x.get()). - //! + //! //! <b>Complexity</b>: Constant. - multimap& operator=(BOOST_RV_REF(multimap) x) + multimap& operator=(BOOST_RV_REF(multimap) 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 value_compare(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 this->cbegin(); } + + //! <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 { 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 + { return this->cend(); } + + //! <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 cend() 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() + 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 this->crbegin(); } + + //! <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 + const_reverse_iterator crbegin() 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 + { return this->crend(); } + + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const + const_reverse_iterator crend() const { return m_tree.rend(); } //! <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. @@ -1027,31 +1139,31 @@ class multimap { 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(const value_type& x) + iterator insert(const value_type& x) { return m_tree.insert_equal(x); } - //! <b>Effects</b>: Inserts a new value constructed from x and returns - //! the iterator pointing to the newly inserted element. + //! <b>Effects</b>: Inserts a new value constructed from x and returns + //! the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(const nonconst_value_type& x) + iterator insert(const nonconst_value_type& x) { return m_tree.insert_equal(x); } - //! <b>Effects</b>: Inserts a new value move-constructed from x and returns - //! the iterator pointing to the newly inserted element. + //! <b>Effects</b>: Inserts a new value move-constructed from x and returns + //! the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(BOOST_RV_REF(nonconst_value_type) x) + iterator insert(BOOST_RV_REF(nonconst_value_type) x) { return m_tree.insert_equal(boost::move(x)); } - //! <b>Effects</b>: Inserts a new value move-constructed from x and returns - //! the iterator pointing to the newly inserted element. + //! <b>Effects</b>: Inserts a new value move-constructed from x and returns + //! the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(BOOST_RV_REF(nonconst_impl_value_type) x) + iterator insert(BOOST_RV_REF(nonconst_impl_value_type) x) { return m_tree.insert_equal(boost::move(x)); } //! <b>Effects</b>: Inserts a copy of x in the container. @@ -1104,7 +1216,7 @@ class multimap //! //! <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) @@ -1156,11 +1268,11 @@ class multimap //! <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>: Amortized constant time - iterator erase(const_iterator position) + iterator erase(const_iterator position) { return m_tree.erase(position); } //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. @@ -1168,7 +1280,7 @@ class multimap //! <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). @@ -1184,68 +1296,68 @@ class multimap //! <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 //! than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator upper_bound(const key_type& x) + iterator upper_bound(const key_type& x) { 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>Returns</b>: A const iterator pointing to the first element with key not //! 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<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 @@ -1260,37 +1372,37 @@ class multimap }; template <class Key, class T, class Pred, class A> -inline bool operator==(const multimap<Key,T,Pred,A>& x, - const multimap<Key,T,Pred,A>& y) +inline bool operator==(const multimap<Key,T,Pred,A>& x, + const multimap<Key,T,Pred,A>& y) { return x.m_tree == y.m_tree; } template <class Key, class T, class Pred, class A> -inline bool operator<(const multimap<Key,T,Pred,A>& x, - const multimap<Key,T,Pred,A>& y) +inline bool operator<(const multimap<Key,T,Pred,A>& x, + const multimap<Key,T,Pred,A>& y) { return x.m_tree < y.m_tree; } template <class Key, class T, class Pred, class A> -inline bool operator!=(const multimap<Key,T,Pred,A>& x, - const multimap<Key,T,Pred,A>& y) +inline bool operator!=(const multimap<Key,T,Pred,A>& x, + const multimap<Key,T,Pred,A>& y) { return !(x == y); } template <class Key, class T, class Pred, class A> -inline bool operator>(const multimap<Key,T,Pred,A>& x, - const multimap<Key,T,Pred,A>& y) +inline bool operator>(const multimap<Key,T,Pred,A>& x, + const multimap<Key,T,Pred,A>& y) { return y < x; } template <class Key, class T, class Pred, class A> -inline bool operator<=(const multimap<Key,T,Pred,A>& x, - const multimap<Key,T,Pred,A>& y) +inline bool operator<=(const multimap<Key,T,Pred,A>& x, + const multimap<Key,T,Pred,A>& y) { return !(y < x); } template <class Key, class T, class Pred, class A> -inline bool operator>=(const multimap<Key,T,Pred,A>& x, - const multimap<Key,T,Pred,A>& y) +inline bool operator>=(const multimap<Key,T,Pred,A>& x, + const multimap<Key,T,Pred,A>& y) { return !(x < y); } template <class Key, class T, class Pred, class A> -inline void swap(multimap<Key,T,Pred,A>& x, multimap<Key,T,Pred,A>& y) +inline void swap(multimap<Key,T,Pred,A>& x, multimap<Key,T,Pred,A>& y) { x.swap(y); } /// @cond |