Chris@16: ////////////////////////////////////////////////////////////////////////////// Chris@16: // Chris@16: // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost Chris@16: // Software License, Version 1.0. (See accompanying file Chris@16: // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) Chris@16: // Chris@16: // See http://www.boost.org/libs/container for documentation. Chris@16: // Chris@16: ////////////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: #ifndef BOOST_CONTAINER_FLAT_SET_HPP Chris@16: #define BOOST_CONTAINER_FLAT_SET_HPP Chris@16: Chris@16: #if defined(_MSC_VER) Chris@16: # pragma once Chris@16: #endif Chris@16: Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: namespace boost { Chris@16: namespace container { Chris@16: Chris@16: /// @cond Chris@16: // Forward declarations of operators < and ==, needed for friend declaration. Chris@16: Chris@16: #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED Chris@16: template , class Allocator = std::allocator > Chris@16: #else Chris@16: template Chris@16: #endif Chris@16: class flat_set; Chris@16: Chris@16: template Chris@16: inline bool operator==(const flat_set& x, Chris@16: const flat_set& y); Chris@16: Chris@16: template Chris@16: inline bool operator<(const flat_set& x, Chris@16: const flat_set& y); Chris@16: /// @endcond Chris@16: Chris@16: //! flat_set is a Sorted Associative Container that stores objects of type Key. Chris@16: //! It is also a Unique Associative Container, meaning that no two elements are the same. Chris@16: //! Chris@16: //! flat_set is similar to std::set but it's implemented like an ordered vector. Chris@16: //! This means that inserting a new element into a flat_set invalidates Chris@16: //! previous iterators and references Chris@16: //! Chris@16: //! Erasing an element of a flat_set invalidates iterators and references Chris@16: //! pointing to elements that come after (their keys are bigger) the erased element. Chris@16: //! Chris@16: //! This container provides random-access iterators. Chris@16: #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED Chris@16: template , class Allocator = std::allocator > Chris@16: #else Chris@16: template Chris@16: #endif Chris@16: class flat_set Chris@16: { Chris@16: /// @cond Chris@16: private: Chris@16: BOOST_COPYABLE_AND_MOVABLE(flat_set) Chris@16: typedef container_detail::flat_tree, Compare, Allocator> tree_t; Chris@16: tree_t m_flat_tree; // flat tree representing flat_set Chris@16: /// @endcond Chris@16: Chris@16: public: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // types Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: typedef Key key_type; Chris@16: typedef Key value_type; Chris@16: typedef Compare key_compare; Chris@16: typedef Compare value_compare; Chris@16: typedef typename ::boost::container::allocator_traits::pointer pointer; Chris@16: typedef typename ::boost::container::allocator_traits::const_pointer const_pointer; Chris@16: typedef typename ::boost::container::allocator_traits::reference reference; Chris@16: typedef typename ::boost::container::allocator_traits::const_reference const_reference; Chris@16: typedef typename ::boost::container::allocator_traits::size_type size_type; Chris@16: typedef typename ::boost::container::allocator_traits::difference_type difference_type; Chris@16: typedef Allocator allocator_type; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator; Chris@16: Chris@16: public: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // construct/copy/destroy Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Effects: Default constructs an empty flat_set. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: explicit flat_set() Chris@16: : m_flat_tree() Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty flat_set using the specified Chris@16: //! comparison object and allocator. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: explicit flat_set(const Compare& comp, Chris@16: const allocator_type& a = allocator_type()) Chris@16: : m_flat_tree(comp, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty flat_set using the specified allocator. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: explicit flat_set(const allocator_type& a) Chris@16: : m_flat_tree(a) Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty set using the specified comparison object and Chris@16: //! allocator, and inserts elements from the range [first ,last ). Chris@16: //! Chris@16: //! Complexity: Linear in N if the range [first ,last ) is already sorted using Chris@16: //! comp and otherwise N logN, where N is last - first. Chris@16: template Chris@16: flat_set(InputIterator first, InputIterator last, Chris@16: const Compare& comp = Compare(), Chris@16: const allocator_type& a = allocator_type()) Chris@16: : m_flat_tree(true, first, last, comp, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty flat_set using the specified comparison object and Chris@16: //! allocator, and inserts elements from the ordered unique range [first ,last). This function Chris@16: //! is more efficient than the normal range creation for ordered ranges. Chris@16: //! Chris@16: //! Requires: [first ,last) must be ordered according to the predicate and must be Chris@16: //! unique values. Chris@16: //! Chris@16: //! Complexity: Linear in N. Chris@16: //! Chris@16: //! Note: Non-standard extension. Chris@16: template Chris@16: flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, Chris@16: const Compare& comp = Compare(), Chris@16: const allocator_type& a = allocator_type()) Chris@16: : m_flat_tree(ordered_range, first, last, comp, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Copy constructs a set. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_set(const flat_set& x) Chris@16: : m_flat_tree(x.m_flat_tree) Chris@16: {} Chris@16: Chris@16: //! Effects: Move constructs a set. Constructs *this using x's resources. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Postcondition: x is emptied. Chris@16: flat_set(BOOST_RV_REF(flat_set) mx) Chris@16: : m_flat_tree(boost::move(mx.m_flat_tree)) Chris@16: {} Chris@16: Chris@16: //! Effects: Copy constructs a set using the specified allocator. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_set(const flat_set& x, const allocator_type &a) Chris@16: : m_flat_tree(x.m_flat_tree, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Move constructs a set using the specified allocator. Chris@16: //! Constructs *this using x's resources. Chris@16: //! Chris@16: //! Complexity: Constant if a == mx.get_allocator(), linear otherwise Chris@16: flat_set(BOOST_RV_REF(flat_set) mx, const allocator_type &a) Chris@16: : m_flat_tree(boost::move(mx.m_flat_tree), a) Chris@16: {} Chris@16: Chris@16: //! Effects: Makes *this a copy of x. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_set& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x) Chris@16: { m_flat_tree = x.m_flat_tree; return *this; } Chris@16: Chris@16: //! Effects: Makes *this a copy of the previous value of xx. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_set& operator=(BOOST_RV_REF(flat_set) mx) Chris@16: { m_flat_tree = boost::move(mx.m_flat_tree); return *this; } Chris@16: Chris@16: //! Effects: Returns a copy of the Allocator that Chris@16: //! was passed to the object's constructor. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.get_allocator(); } Chris@16: Chris@16: //! Effects: Returns a reference to the internal allocator. Chris@16: //! Chris@16: //! Throws: Nothing Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Note: Non-standard extension. Chris@16: stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.get_stored_allocator(); } Chris@16: Chris@16: //! Effects: Returns a reference to the internal allocator. Chris@16: //! Chris@16: //! Throws: Nothing Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Note: Non-standard extension. Chris@16: const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.get_stored_allocator(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // iterators Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Effects: Returns an iterator to the first element contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: iterator begin() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.begin(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the first element contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator begin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.begin(); } Chris@16: Chris@16: //! Effects: Returns an iterator to the end of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: iterator end() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.end(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the end of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator end() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.end(); } Chris@16: Chris@16: //! Effects: Returns a reverse_iterator pointing to the beginning Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rbegin(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the beginning Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rbegin(); } Chris@16: Chris@16: //! Effects: Returns a reverse_iterator pointing to the end Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rend(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the end Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rend(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the first element contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.cbegin(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the end of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator cend() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.cend(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the beginning Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.crbegin(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the end Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.crend(); } Chris@16: Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // capacity Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Effects: Returns true if the container contains no elements. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: bool empty() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.empty(); } Chris@16: Chris@16: //! Effects: Returns the number of the elements contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: size_type size() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.size(); } Chris@16: Chris@16: //! Effects: Returns the largest possible size of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: size_type max_size() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.max_size(); } Chris@16: Chris@16: //! Effects: Number of elements for which memory has been allocated. Chris@16: //! capacity() is always greater than or equal to size(). Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: size_type capacity() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.capacity(); } Chris@16: Chris@16: //! Effects: If n is less than or equal to capacity(), this call has no Chris@16: //! effect. Otherwise, it is a request for allocation of additional memory. Chris@16: //! If the request is successful, then capacity() is greater than or equal to Chris@16: //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. Chris@16: //! Chris@16: //! Throws: If memory allocation allocation throws or Key's copy constructor throws. Chris@16: //! Chris@16: //! Note: If capacity() is less than "cnt", iterators and references to Chris@16: //! to values might be invalidated. Chris@16: void reserve(size_type cnt) Chris@16: { m_flat_tree.reserve(cnt); } Chris@16: Chris@16: //! Effects: Tries to deallocate the excess of memory created Chris@16: // with previous allocations. The size of the vector is unchanged Chris@16: //! Chris@16: //! Throws: If memory allocation throws, or Key's copy constructor throws. Chris@16: //! Chris@16: //! Complexity: Linear to size(). Chris@16: void shrink_to_fit() Chris@16: { m_flat_tree.shrink_to_fit(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // modifiers Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) Chris@16: Chris@16: //! Effects: Inserts an object x of type Key constructed with Chris@16: //! std::forward(args)... if and only if there is no element in the container Chris@16: //! with key equivalent to the key of x. Chris@16: //! Chris@16: //! Returns: The bool component of the returned pair is true if and only Chris@16: //! if the insertion takes place, and the iterator component of the pair Chris@16: //! points to the element with key equivalent to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus linear insertion Chris@16: //! to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: template Chris@16: std::pair emplace(Args&&... args) Chris@16: { return m_flat_tree.emplace_unique(boost::forward(args)...); } Chris@16: Chris@16: //! Effects: Inserts an object of type Key constructed with Chris@16: //! std::forward(args)... in the container if and only if there is Chris@16: //! no element in the container with key equivalent to the key of x. Chris@16: //! p is a hint pointing to where the insert should start to search. Chris@16: //! Chris@16: //! Returns: An iterator pointing to the element with key equivalent Chris@16: //! to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time (constant if x is inserted Chris@16: //! right before p) plus insertion linear to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: template Chris@16: iterator emplace_hint(const_iterator hint, Args&&... args) Chris@16: { return m_flat_tree.emplace_hint_unique(hint, boost::forward(args)...); } Chris@16: Chris@16: #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING Chris@16: Chris@16: #define BOOST_PP_LOCAL_MACRO(n) \ Chris@16: BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ Chris@16: std::pair emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ Chris@16: { return m_flat_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ Chris@16: \ Chris@16: BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ Chris@16: iterator emplace_hint(const_iterator hint \ Chris@16: BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ Chris@16: { return m_flat_tree.emplace_hint_unique \ Chris@16: (hint BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ Chris@16: //! Chris@16: #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) Chris@16: #include BOOST_PP_LOCAL_ITERATE() Chris@16: Chris@16: #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING Chris@16: Chris@16: #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) Chris@16: //! Effects: Inserts x if and only if there is no element in the container Chris@16: //! with key equivalent to the key of x. Chris@16: //! Chris@16: //! Returns: The bool component of the returned pair is true if and only Chris@16: //! if the insertion takes place, and the iterator component of the pair Chris@16: //! points to the element with key equivalent to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus linear insertion Chris@16: //! to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: std::pair insert(const value_type &x); Chris@16: Chris@16: //! Effects: Inserts a new value_type move constructed from the pair if and Chris@16: //! only if there is no element in the container with key equivalent to the key of x. Chris@16: //! Chris@16: //! Returns: The bool component of the returned pair is true if and only Chris@16: //! if the insertion takes place, and the iterator component of the pair Chris@16: //! points to the element with key equivalent to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus linear insertion Chris@16: //! to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: std::pair insert(value_type &&x); Chris@16: #else Chris@16: private: Chris@16: typedef std::pair insert_return_pair; Chris@16: public: Chris@16: BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert) Chris@16: #endif Chris@16: Chris@16: #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) Chris@16: //! Effects: Inserts a copy of x in the container if and only if there is Chris@16: //! no element in the container with key equivalent to the key of x. Chris@16: //! p is a hint pointing to where the insert should start to search. Chris@16: //! Chris@16: //! Returns: An iterator pointing to the element with key equivalent Chris@16: //! to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time (constant if x is inserted Chris@16: //! right before p) plus insertion linear to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: iterator insert(const_iterator p, const value_type &x); Chris@16: Chris@16: //! Effects: Inserts an element move constructed from x in the container. Chris@16: //! p is a hint pointing to where the insert should start to search. Chris@16: //! Chris@16: //! Returns: An iterator pointing to the element with key equivalent to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time (constant if x is inserted Chris@16: //! right before p) plus insertion linear to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: iterator insert(const_iterator position, value_type &&x); Chris@16: #else Chris@16: BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator) Chris@16: #endif Chris@16: Chris@16: //! Requires: first, last are not iterators into *this. Chris@16: //! Chris@16: //! Effects: inserts each element from the range [first,last) if and only Chris@16: //! if there is no element with key equivalent to the key of that element. Chris@16: //! Chris@16: //! Complexity: At most N log(size()+N) (N is the distance from first to last) Chris@16: //! search time plus N*size() insertion time. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: template Chris@16: void insert(InputIterator first, InputIterator last) Chris@16: { m_flat_tree.insert_unique(first, last); } Chris@16: Chris@16: //! Requires: first, last are not iterators into *this and Chris@16: //! must be ordered according to the predicate and must be Chris@16: //! unique values. Chris@16: //! Chris@16: //! Effects: inserts each element from the range [first,last) .This function Chris@16: //! is more efficient than the normal range creation for ordered ranges. Chris@16: //! Chris@16: //! Complexity: At most N log(size()+N) (N is the distance from first to last) Chris@16: //! search time plus N*size() insertion time. Chris@16: //! Chris@16: //! Note: Non-standard extension. If an element is inserted it might invalidate elements. Chris@16: template Chris@16: void insert(ordered_unique_range_t, InputIterator first, InputIterator last) Chris@16: { m_flat_tree.insert_unique(ordered_unique_range, first, last); } Chris@16: Chris@16: //! Effects: Erases the element pointed to by position. Chris@16: //! Chris@16: //! Returns: Returns an iterator pointing to the element immediately Chris@16: //! following q prior to the element being erased. If no such element exists, Chris@16: //! returns end(). Chris@16: //! Chris@16: //! Complexity: Linear to the elements with keys bigger than position Chris@16: //! Chris@16: //! Note: Invalidates elements with keys Chris@16: //! not less than the erased element. Chris@16: iterator erase(const_iterator position) Chris@16: { return m_flat_tree.erase(position); } Chris@16: Chris@16: //! Effects: Erases all elements in the container with key equivalent to x. Chris@16: //! Chris@16: //! Returns: Returns the number of erased elements. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus erasure time Chris@16: //! linear to the elements with bigger keys. Chris@16: size_type erase(const key_type& x) Chris@16: { return m_flat_tree.erase(x); } Chris@16: Chris@16: //! Effects: Erases all the elements in the range [first, last). Chris@16: //! Chris@16: //! Returns: Returns last. Chris@16: //! Chris@16: //! Complexity: size()*N where N is the distance from first to last. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus erasure time Chris@16: //! linear to the elements with bigger keys. Chris@16: iterator erase(const_iterator first, const_iterator last) Chris@16: { return m_flat_tree.erase(first, last); } Chris@16: Chris@16: //! Effects: Swaps the contents of *this and x. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: void swap(flat_set& x) Chris@16: { m_flat_tree.swap(x.m_flat_tree); } Chris@16: Chris@16: //! Effects: erase(a.begin(),a.end()). Chris@16: //! Chris@16: //! Postcondition: size() == 0. Chris@16: //! Chris@16: //! Complexity: linear in size(). Chris@16: void clear() BOOST_CONTAINER_NOEXCEPT Chris@16: { m_flat_tree.clear(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // observers Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Effects: Returns the comparison object out Chris@16: //! of which a was constructed. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: key_compare key_comp() const Chris@16: { return m_flat_tree.key_comp(); } Chris@16: Chris@16: //! Effects: Returns an object of value_compare constructed out Chris@16: //! of the comparison object. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: value_compare value_comp() const Chris@16: { return m_flat_tree.key_comp(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // set operations Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Returns: An iterator pointing to an element with the key Chris@16: //! equivalent to x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic. Chris@16: iterator find(const key_type& x) Chris@16: { return m_flat_tree.find(x); } Chris@16: Chris@16: //! Returns: Allocator const_iterator pointing to an element with the key Chris@16: //! equivalent to x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic.s Chris@16: const_iterator find(const key_type& x) const Chris@16: { return m_flat_tree.find(x); } Chris@16: Chris@16: //! Returns: The number of elements with key equivalent to x. Chris@16: //! Chris@16: //! Complexity: log(size())+count(k) Chris@16: size_type count(const key_type& x) const Chris@16: { return static_cast(m_flat_tree.find(x) != m_flat_tree.end()); } Chris@16: Chris@16: //! Returns: An iterator pointing to the first element with key not less Chris@16: //! than k, or a.end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: iterator lower_bound(const key_type& x) Chris@16: { return m_flat_tree.lower_bound(x); } Chris@16: Chris@16: //! Returns: Allocator const iterator pointing to the first element with key not Chris@16: //! less than k, or a.end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: const_iterator lower_bound(const key_type& x) const Chris@16: { return m_flat_tree.lower_bound(x); } Chris@16: Chris@16: //! Returns: An iterator pointing to the first element with key not less Chris@16: //! than x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: iterator upper_bound(const key_type& x) Chris@16: { return m_flat_tree.upper_bound(x); } Chris@16: Chris@16: //! Returns: Allocator const iterator pointing to the first element with key not Chris@16: //! less than x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: const_iterator upper_bound(const key_type& x) const Chris@16: { return m_flat_tree.upper_bound(x); } Chris@16: Chris@16: //! Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: std::pair equal_range(const key_type& x) const Chris@16: { return m_flat_tree.equal_range(x); } Chris@16: Chris@16: //! Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: std::pair equal_range(const key_type& x) Chris@16: { return m_flat_tree.equal_range(x); } Chris@16: Chris@16: /// @cond Chris@16: template Chris@16: friend bool operator== (const flat_set&, const flat_set&); Chris@16: Chris@16: template Chris@16: friend bool operator< (const flat_set&, const flat_set&); Chris@16: Chris@16: private: Chris@16: template Chris@16: std::pair priv_insert(BOOST_FWD_REF(KeyType) x) Chris@16: { return m_flat_tree.insert_unique(::boost::forward(x)); } Chris@16: Chris@16: template Chris@16: iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x) Chris@16: { return m_flat_tree.insert_unique(p, ::boost::forward(x)); } Chris@16: /// @endcond Chris@16: }; Chris@16: Chris@16: template Chris@16: inline bool operator==(const flat_set& x, Chris@16: const flat_set& y) Chris@16: { return x.m_flat_tree == y.m_flat_tree; } Chris@16: Chris@16: template Chris@16: inline bool operator<(const flat_set& x, Chris@16: const flat_set& y) Chris@16: { return x.m_flat_tree < y.m_flat_tree; } Chris@16: Chris@16: template Chris@16: inline bool operator!=(const flat_set& x, Chris@16: const flat_set& y) Chris@16: { return !(x == y); } Chris@16: Chris@16: template Chris@16: inline bool operator>(const flat_set& x, Chris@16: const flat_set& y) Chris@16: { return y < x; } Chris@16: Chris@16: template Chris@16: inline bool operator<=(const flat_set& x, Chris@16: const flat_set& y) Chris@16: { return !(y < x); } Chris@16: Chris@16: template Chris@16: inline bool operator>=(const flat_set& x, Chris@16: const flat_set& y) Chris@16: { return !(x < y); } Chris@16: Chris@16: template Chris@16: inline void swap(flat_set& x, flat_set& y) Chris@16: { x.swap(y); } Chris@16: Chris@16: /// @cond Chris@16: Chris@16: } //namespace container { Chris@16: Chris@16: //!has_trivial_destructor_after_move<> == true_type Chris@16: //!specialization for optimizations Chris@16: template Chris@16: struct has_trivial_destructor_after_move > Chris@16: { Chris@16: static const bool value = has_trivial_destructor_after_move::value &&has_trivial_destructor_after_move::value; Chris@16: }; Chris@16: Chris@16: namespace container { Chris@16: Chris@16: // Forward declaration of operators < and ==, needed for friend declaration. Chris@16: Chris@16: #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED Chris@16: template , class Allocator = std::allocator > Chris@16: #else Chris@16: template Chris@16: #endif Chris@16: class flat_multiset; Chris@16: Chris@16: template Chris@16: inline bool operator==(const flat_multiset& x, Chris@16: const flat_multiset& y); Chris@16: Chris@16: template Chris@16: inline bool operator<(const flat_multiset& x, Chris@16: const flat_multiset& y); Chris@16: /// @endcond Chris@16: Chris@16: //! flat_multiset is a Sorted Associative Container that stores objects of type Key. Chris@16: //! Chris@16: //! flat_multiset can store multiple copies of the same key value. Chris@16: //! Chris@16: //! flat_multiset is similar to std::multiset but it's implemented like an ordered vector. Chris@16: //! This means that inserting a new element into a flat_multiset invalidates Chris@16: //! previous iterators and references Chris@16: //! Chris@16: //! Erasing an element invalidates iterators and references Chris@16: //! pointing to elements that come after (their keys are bigger) the erased element. Chris@16: //! Chris@16: //! This container provides random-access iterators. Chris@16: #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED Chris@16: template , class Allocator = std::allocator > Chris@16: #else Chris@16: template Chris@16: #endif Chris@16: class flat_multiset Chris@16: { Chris@16: /// @cond Chris@16: private: Chris@16: BOOST_COPYABLE_AND_MOVABLE(flat_multiset) Chris@16: typedef container_detail::flat_tree, Compare, Allocator> tree_t; Chris@16: tree_t m_flat_tree; // flat tree representing flat_multiset Chris@16: /// @endcond Chris@16: Chris@16: public: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // types Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: typedef Key key_type; Chris@16: typedef Key value_type; Chris@16: typedef Compare key_compare; Chris@16: typedef Compare value_compare; Chris@16: typedef typename ::boost::container::allocator_traits::pointer pointer; Chris@16: typedef typename ::boost::container::allocator_traits::const_pointer const_pointer; Chris@16: typedef typename ::boost::container::allocator_traits::reference reference; Chris@16: typedef typename ::boost::container::allocator_traits::const_reference const_reference; Chris@16: typedef typename ::boost::container::allocator_traits::size_type size_type; Chris@16: typedef typename ::boost::container::allocator_traits::difference_type difference_type; Chris@16: typedef Allocator allocator_type; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator; Chris@16: typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator; Chris@16: Chris@16: //! Effects: Default constructs an empty flat_multiset. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: explicit flat_multiset() Chris@16: : m_flat_tree() Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty flat_multiset using the specified Chris@16: //! comparison object and allocator. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: explicit flat_multiset(const Compare& comp, Chris@16: const allocator_type& a = allocator_type()) Chris@16: : m_flat_tree(comp, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty flat_multiset using the specified allocator. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: explicit flat_multiset(const allocator_type& a) Chris@16: : m_flat_tree(a) Chris@16: {} Chris@16: Chris@16: template Chris@16: flat_multiset(InputIterator first, InputIterator last, Chris@16: const Compare& comp = Compare(), Chris@16: const allocator_type& a = allocator_type()) Chris@16: : m_flat_tree(false, first, last, comp, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Constructs an empty flat_multiset using the specified comparison object and Chris@16: //! allocator, and inserts elements from the ordered range [first ,last ). This function Chris@16: //! is more efficient than the normal range creation for ordered ranges. Chris@16: //! Chris@16: //! Requires: [first ,last) must be ordered according to the predicate. Chris@16: //! Chris@16: //! Complexity: Linear in N. Chris@16: //! Chris@16: //! Note: Non-standard extension. Chris@16: template Chris@16: flat_multiset(ordered_range_t, InputIterator first, InputIterator last, Chris@16: const Compare& comp = Compare(), Chris@16: const allocator_type& a = allocator_type()) Chris@16: : m_flat_tree(ordered_range, first, last, comp, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Copy constructs a flat_multiset. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_multiset(const flat_multiset& x) Chris@16: : m_flat_tree(x.m_flat_tree) Chris@16: {} Chris@16: Chris@16: //! Effects: Move constructs a flat_multiset. Constructs *this using x's resources. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Postcondition: x is emptied. Chris@16: flat_multiset(BOOST_RV_REF(flat_multiset) mx) Chris@16: : m_flat_tree(boost::move(mx.m_flat_tree)) Chris@16: {} Chris@16: Chris@16: //! Effects: Copy constructs a flat_multiset using the specified allocator. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_multiset(const flat_multiset& x, const allocator_type &a) Chris@16: : m_flat_tree(x.m_flat_tree, a) Chris@16: {} Chris@16: Chris@16: //! Effects: Move constructs a flat_multiset using the specified allocator. Chris@16: //! Constructs *this using x's resources. Chris@16: //! Chris@16: //! Complexity: Constant if a == mx.get_allocator(), linear otherwise Chris@16: flat_multiset(BOOST_RV_REF(flat_multiset) mx, const allocator_type &a) Chris@16: : m_flat_tree(boost::move(mx.m_flat_tree), a) Chris@16: {} Chris@16: Chris@16: //! Effects: Makes *this a copy of x. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x) Chris@16: { m_flat_tree = x.m_flat_tree; return *this; } Chris@16: Chris@16: //! Effects: Makes *this a copy of x. Chris@16: //! Chris@16: //! Complexity: Linear in x.size(). Chris@16: flat_multiset& operator=(BOOST_RV_REF(flat_multiset) mx) Chris@16: { m_flat_tree = boost::move(mx.m_flat_tree); return *this; } Chris@16: Chris@16: //! Effects: Returns a copy of the Allocator that Chris@16: //! was passed to the object's constructor. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.get_allocator(); } Chris@16: Chris@16: //! Effects: Returns a reference to the internal allocator. Chris@16: //! Chris@16: //! Throws: Nothing Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Note: Non-standard extension. Chris@16: stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.get_stored_allocator(); } Chris@16: Chris@16: //! Effects: Returns a reference to the internal allocator. Chris@16: //! Chris@16: //! Throws: Nothing Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Note: Non-standard extension. Chris@16: const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.get_stored_allocator(); } Chris@16: Chris@16: //! Effects: Returns an iterator to the first element contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: iterator begin() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.begin(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the first element contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator begin() const Chris@16: { return m_flat_tree.begin(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the first element contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.cbegin(); } Chris@16: Chris@16: //! Effects: Returns an iterator to the end of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: iterator end() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.end(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the end of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator end() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.end(); } Chris@16: Chris@16: //! Effects: Returns a const_iterator to the end of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_iterator cend() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.cend(); } Chris@16: Chris@16: //! Effects: Returns a reverse_iterator pointing to the beginning Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rbegin(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the beginning Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rbegin(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the beginning Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.crbegin(); } Chris@16: Chris@16: //! Effects: Returns a reverse_iterator pointing to the end Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rend(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the end Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.rend(); } Chris@16: Chris@16: //! Effects: Returns a const_reverse_iterator pointing to the end Chris@16: //! of the reversed container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.crend(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // capacity Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Effects: Returns true if the container contains no elements. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: bool empty() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.empty(); } Chris@16: Chris@16: //! Effects: Returns the number of the elements contained in the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: size_type size() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.size(); } Chris@16: Chris@16: //! Effects: Returns the largest possible size of the container. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: size_type max_size() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.max_size(); } Chris@16: Chris@16: //! Effects: Number of elements for which memory has been allocated. Chris@16: //! capacity() is always greater than or equal to size(). Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: size_type capacity() const BOOST_CONTAINER_NOEXCEPT Chris@16: { return m_flat_tree.capacity(); } Chris@16: Chris@16: //! Effects: If n is less than or equal to capacity(), this call has no Chris@16: //! effect. Otherwise, it is a request for allocation of additional memory. Chris@16: //! If the request is successful, then capacity() is greater than or equal to Chris@16: //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. Chris@16: //! Chris@16: //! Throws: If memory allocation allocation throws or Key's copy constructor throws. Chris@16: //! Chris@16: //! Note: If capacity() is less than "cnt", iterators and references to Chris@16: //! to values might be invalidated. Chris@16: void reserve(size_type cnt) Chris@16: { m_flat_tree.reserve(cnt); } Chris@16: Chris@16: //! Effects: Tries to deallocate the excess of memory created Chris@16: // with previous allocations. The size of the vector is unchanged Chris@16: //! Chris@16: //! Throws: If memory allocation throws, or Key's copy constructor throws. Chris@16: //! Chris@16: //! Complexity: Linear to size(). Chris@16: void shrink_to_fit() Chris@16: { m_flat_tree.shrink_to_fit(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // modifiers Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) Chris@16: Chris@16: //! Effects: Inserts an object of type Key constructed with Chris@16: //! std::forward(args)... and returns the iterator pointing to the Chris@16: //! newly inserted element. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus linear insertion Chris@16: //! to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: template Chris@16: iterator emplace(Args&&... args) Chris@16: { return m_flat_tree.emplace_equal(boost::forward(args)...); } Chris@16: Chris@16: //! Effects: Inserts an object of type Key constructed with Chris@16: //! std::forward(args)... in the container. Chris@16: //! p is a hint pointing to where the insert should start to search. Chris@16: //! Chris@16: //! Returns: An iterator pointing to the element with key equivalent Chris@16: //! to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time (constant if x is inserted Chris@16: //! right before p) plus insertion linear to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: template Chris@16: iterator emplace_hint(const_iterator hint, Args&&... args) Chris@16: { return m_flat_tree.emplace_hint_equal(hint, boost::forward(args)...); } Chris@16: Chris@16: #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING Chris@16: Chris@16: #define BOOST_PP_LOCAL_MACRO(n) \ Chris@16: BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ Chris@16: iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ Chris@16: { return m_flat_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ Chris@16: \ Chris@16: BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ Chris@16: iterator emplace_hint(const_iterator hint \ Chris@16: BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ Chris@16: { return m_flat_tree.emplace_hint_equal \ Chris@16: (hint BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ Chris@16: //! Chris@16: #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) Chris@16: #include BOOST_PP_LOCAL_ITERATE() Chris@16: Chris@16: #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING Chris@16: Chris@16: #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) Chris@16: //! Effects: Inserts x and returns the iterator pointing to the Chris@16: //! newly inserted element. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus linear insertion Chris@16: //! to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: iterator insert(const value_type &x); Chris@16: Chris@16: //! Effects: Inserts a new value_type move constructed from x Chris@16: //! and returns the iterator pointing to the newly inserted element. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus linear insertion Chris@16: //! to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: iterator insert(value_type &&x); Chris@16: #else Chris@16: BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert) Chris@16: #endif Chris@16: Chris@16: #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) Chris@16: //! Effects: Inserts a copy of x in the container. Chris@16: //! p is a hint pointing to where the insert should start to search. Chris@16: //! Chris@16: //! Returns: An iterator pointing to the element with key equivalent Chris@16: //! to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time (constant if x is inserted Chris@16: //! right before p) plus insertion linear to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: iterator insert(const_iterator p, const value_type &x); Chris@16: Chris@16: //! Effects: Inserts a new value move constructed from x in the container. Chris@16: //! p is a hint pointing to where the insert should start to search. Chris@16: //! Chris@16: //! Returns: An iterator pointing to the element with key equivalent Chris@16: //! to the key of x. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time (constant if x is inserted Chris@16: //! right before p) plus insertion linear to the elements with bigger keys than x. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: iterator insert(const_iterator position, value_type &&x); Chris@16: #else Chris@16: BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator) Chris@16: #endif Chris@16: Chris@16: //! Requires: first, last are not iterators into *this. Chris@16: //! Chris@16: //! Effects: inserts each element from the range [first,last) . Chris@16: //! Chris@16: //! Complexity: At most N log(size()+N) (N is the distance from first to last) Chris@16: //! search time plus N*size() insertion time. Chris@16: //! Chris@16: //! Note: If an element is inserted it might invalidate elements. Chris@16: template Chris@16: void insert(InputIterator first, InputIterator last) Chris@16: { m_flat_tree.insert_equal(first, last); } Chris@16: Chris@16: //! Requires: first, last are not iterators into *this and Chris@16: //! must be ordered according to the predicate. Chris@16: //! Chris@16: //! Effects: inserts each element from the range [first,last) .This function Chris@16: //! is more efficient than the normal range creation for ordered ranges. Chris@16: //! Chris@16: //! Complexity: At most N log(size()+N) (N is the distance from first to last) Chris@16: //! search time plus N*size() insertion time. Chris@16: //! Chris@16: //! Note: Non-standard extension. If an element is inserted it might invalidate elements. Chris@16: template Chris@16: void insert(ordered_range_t, InputIterator first, InputIterator last) Chris@16: { m_flat_tree.insert_equal(ordered_range, first, last); } Chris@16: Chris@16: //! Effects: Erases the element pointed to by position. Chris@16: //! Chris@16: //! Returns: Returns an iterator pointing to the element immediately Chris@16: //! following q prior to the element being erased. If no such element exists, Chris@16: //! returns end(). Chris@16: //! Chris@16: //! Complexity: Linear to the elements with keys bigger than position Chris@16: //! Chris@16: //! Note: Invalidates elements with keys Chris@16: //! not less than the erased element. Chris@16: iterator erase(const_iterator position) Chris@16: { return m_flat_tree.erase(position); } Chris@16: Chris@16: //! Effects: Erases all elements in the container with key equivalent to x. Chris@16: //! Chris@16: //! Returns: Returns the number of erased elements. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus erasure time Chris@16: //! linear to the elements with bigger keys. Chris@16: size_type erase(const key_type& x) Chris@16: { return m_flat_tree.erase(x); } Chris@16: Chris@16: //! Effects: Erases all the elements in the range [first, last). Chris@16: //! Chris@16: //! Returns: Returns last. Chris@16: //! Chris@16: //! Complexity: size()*N where N is the distance from first to last. Chris@16: //! Chris@16: //! Complexity: Logarithmic search time plus erasure time Chris@16: //! linear to the elements with bigger keys. Chris@16: iterator erase(const_iterator first, const_iterator last) Chris@16: { return m_flat_tree.erase(first, last); } Chris@16: Chris@16: //! Effects: Swaps the contents of *this and x. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: void swap(flat_multiset& x) Chris@16: { m_flat_tree.swap(x.m_flat_tree); } Chris@16: Chris@16: //! Effects: erase(a.begin(),a.end()). Chris@16: //! Chris@16: //! Postcondition: size() == 0. Chris@16: //! Chris@16: //! Complexity: linear in size(). Chris@16: void clear() BOOST_CONTAINER_NOEXCEPT Chris@16: { m_flat_tree.clear(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // observers Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Effects: Returns the comparison object out Chris@16: //! of which a was constructed. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: key_compare key_comp() const Chris@16: { return m_flat_tree.key_comp(); } Chris@16: Chris@16: //! Effects: Returns an object of value_compare constructed out Chris@16: //! of the comparison object. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: value_compare value_comp() const Chris@16: { return m_flat_tree.key_comp(); } Chris@16: Chris@16: ////////////////////////////////////////////// Chris@16: // Chris@16: // set operations Chris@16: // Chris@16: ////////////////////////////////////////////// Chris@16: Chris@16: //! Returns: An iterator pointing to an element with the key Chris@16: //! equivalent to x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic. Chris@16: iterator find(const key_type& x) Chris@16: { return m_flat_tree.find(x); } Chris@16: Chris@16: //! Returns: Allocator const_iterator pointing to an element with the key Chris@16: //! equivalent to x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic.s Chris@16: const_iterator find(const key_type& x) const Chris@16: { return m_flat_tree.find(x); } Chris@16: Chris@16: //! Returns: The number of elements with key equivalent to x. Chris@16: //! Chris@16: //! Complexity: log(size())+count(k) Chris@16: size_type count(const key_type& x) const Chris@16: { return m_flat_tree.count(x); } Chris@16: Chris@16: //! Returns: An iterator pointing to the first element with key not less Chris@16: //! than k, or a.end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: iterator lower_bound(const key_type& x) Chris@16: { return m_flat_tree.lower_bound(x); } Chris@16: Chris@16: //! Returns: Allocator const iterator pointing to the first element with key not Chris@16: //! less than k, or a.end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: const_iterator lower_bound(const key_type& x) const Chris@16: { return m_flat_tree.lower_bound(x); } Chris@16: Chris@16: //! Returns: An iterator pointing to the first element with key not less Chris@16: //! than x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: iterator upper_bound(const key_type& x) Chris@16: { return m_flat_tree.upper_bound(x); } Chris@16: Chris@16: //! Returns: Allocator const iterator pointing to the first element with key not Chris@16: //! less than x, or end() if such an element is not found. Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: const_iterator upper_bound(const key_type& x) const Chris@16: { return m_flat_tree.upper_bound(x); } Chris@16: Chris@16: //! Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: std::pair equal_range(const key_type& x) const Chris@16: { return m_flat_tree.equal_range(x); } Chris@16: Chris@16: //! Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). Chris@16: //! Chris@16: //! Complexity: Logarithmic Chris@16: std::pair equal_range(const key_type& x) Chris@16: { return m_flat_tree.equal_range(x); } Chris@16: Chris@16: /// @cond Chris@16: template Chris@16: friend bool operator== (const flat_multiset&, Chris@16: const flat_multiset&); Chris@16: template Chris@16: friend bool operator< (const flat_multiset&, Chris@16: const flat_multiset&); Chris@16: private: Chris@16: template Chris@16: iterator priv_insert(BOOST_FWD_REF(KeyType) x) Chris@16: { return m_flat_tree.insert_equal(::boost::forward(x)); } Chris@16: Chris@16: template Chris@16: iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x) Chris@16: { return m_flat_tree.insert_equal(p, ::boost::forward(x)); } Chris@16: /// @endcond Chris@16: }; Chris@16: Chris@16: template Chris@16: inline bool operator==(const flat_multiset& x, Chris@16: const flat_multiset& y) Chris@16: { return x.m_flat_tree == y.m_flat_tree; } Chris@16: Chris@16: template Chris@16: inline bool operator<(const flat_multiset& x, Chris@16: const flat_multiset& y) Chris@16: { return x.m_flat_tree < y.m_flat_tree; } Chris@16: Chris@16: template Chris@16: inline bool operator!=(const flat_multiset& x, Chris@16: const flat_multiset& y) Chris@16: { return !(x == y); } Chris@16: Chris@16: template Chris@16: inline bool operator>(const flat_multiset& x, Chris@16: const flat_multiset& y) Chris@16: { return y < x; } Chris@16: Chris@16: template Chris@16: inline bool operator<=(const flat_multiset& x, Chris@16: const flat_multiset& y) Chris@16: { return !(y < x); } Chris@16: Chris@16: template Chris@16: inline bool operator>=(const flat_multiset& x, Chris@16: const flat_multiset& y) Chris@16: { return !(x < y); } Chris@16: Chris@16: template Chris@16: inline void swap(flat_multiset& x, flat_multiset& y) Chris@16: { x.swap(y); } Chris@16: Chris@16: /// @cond Chris@16: Chris@16: } //namespace container { Chris@16: Chris@16: //!has_trivial_destructor_after_move<> == true_type Chris@16: //!specialization for optimizations Chris@16: template Chris@16: struct has_trivial_destructor_after_move > Chris@16: { Chris@16: static const bool value = has_trivial_destructor_after_move::value && has_trivial_destructor_after_move::value; Chris@16: }; Chris@16: Chris@16: namespace container { Chris@16: Chris@16: /// @endcond Chris@16: Chris@16: }} Chris@16: Chris@16: #include Chris@16: Chris@16: #endif /* BOOST_CONTAINER_FLAT_SET_HPP */