//////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
+// (C) Copyright Ion Gaztanaga 2005-2013. 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)
//
#ifndef BOOST_CONTAINER_SET_HPP
#define BOOST_CONTAINER_SET_HPP
-#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+#if defined(_MSC_VER)
# pragma once
#endif
#include <functional>
#include <memory>
-#include <boost/move/move.hpp>
+#include <boost/move/utility_core.hpp>
+#include <boost/move/detail/move_helpers.hpp>
+#include <boost/move/traits.hpp>
#include <boost/container/detail/mpl.hpp>
#include <boost/container/detail/tree.hpp>
-#include <boost/move/move.hpp>
+#include <boost/move/utility_core.hpp>
#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
#include <boost/container/detail/preprocessor.hpp>
#endif
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+#include <initializer_list>
+#endif
-#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
-namespace boost {
-namespace container {
-#else
namespace boost {
namespace container {
-#endif
-/// @cond
-// Forward declarations of operators < and ==, needed for friend declaration.
-template <class T, class Pred, class A>
-inline bool operator==(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y);
-
-template <class T, class Pred, class A>
-inline bool operator<(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y);
-/// @endcond
+#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
//! A set is a kind of associative container that supports unique keys (contains at
//! most one of each key value) and provides for fast retrieval of the keys themselves.
//! A set satisfies all of the requirements of a container and of a reversible container
//! , and of an associative container. A set also provides most operations described in
//! for unique keys.
-#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
-template <class T, class Pred = std::less<T>, class A = std::allocator<T> >
+//!
+//! \tparam Key is the type to be inserted in the set, which is also the key_type
+//! \tparam Compare is the comparison functor used to order keys
+//! \tparam Allocator is the allocator to be used to allocate memory for this container
+//! \tparam SetOptions is an packed option type generated using using boost::container::tree_assoc_options.
+template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>, class SetOptions = tree_assoc_defaults >
#else
-template <class T, class Pred, class A>
+template <class Key, class Compare, class Allocator, class SetOptions>
#endif
class set
+ ///@cond
+ : public container_detail::tree
+ < Key, Key, container_detail::identity<Key>, Compare, Allocator, SetOptions>
+ ///@endcond
{
- /// @cond
+ #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
private:
BOOST_COPYABLE_AND_MOVABLE(set)
- typedef container_detail::rbtree<T, T,
- container_detail::identity<T>, Pred, A> tree_t;
- tree_t m_tree; // red-black tree representing set
- typedef typename container_detail::
- move_const_ref_type<T>::type insert_const_ref_type;
- /// @endcond
+ typedef container_detail::tree
+ < Key, Key, container_detail::identity<Key>, Compare, Allocator, SetOptions> base_t;
+ #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
public:
-
- // typedefs:
- typedef typename tree_t::key_type key_type;
- typedef typename tree_t::value_type value_type;
- typedef typename tree_t::pointer pointer;
- typedef typename tree_t::const_pointer const_pointer;
- typedef typename tree_t::reference reference;
- typedef typename tree_t::const_reference const_reference;
- typedef Pred key_compare;
- typedef Pred value_compare;
- typedef typename tree_t::iterator iterator;
- typedef typename tree_t::const_iterator const_iterator;
- typedef typename tree_t::reverse_iterator reverse_iterator;
- typedef typename tree_t::const_reverse_iterator const_reverse_iterator;
- typedef typename tree_t::size_type size_type;
- typedef typename tree_t::difference_type difference_type;
- typedef typename tree_t::allocator_type allocator_type;
- typedef typename tree_t::stored_allocator_type stored_allocator_type;
+ //////////////////////////////////////////////
+ //
+ // types
+ //
+ //////////////////////////////////////////////
+ typedef Key key_type;
+ typedef Key value_type;
+ typedef Compare key_compare;
+ typedef Compare value_compare;
+ typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
+ typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
+ typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
+ typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
+ typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
+ typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
+ typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
+ typedef Allocator allocator_type;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
+
+ //////////////////////////////////////////////
+ //
+ // construct/copy/destroy
+ //
+ //////////////////////////////////////////////
//! <b>Effects</b>: Default constructs an empty set.
//!
//! <b>Complexity</b>: Constant.
set()
- : m_tree()
+ : base_t()
{}
//! <b>Effects</b>: Constructs an empty set using the specified comparison object
//! and allocator.
//!
//! <b>Complexity</b>: Constant.
- explicit set(const Pred& comp,
+ explicit set(const Compare& comp,
const allocator_type& a = allocator_type())
- : m_tree(comp, a)
+ : base_t(comp, a)
+ {}
+
+ //! <b>Effects</b>: Constructs an empty set using the specified allocator object.
+ //!
+ //! <b>Complexity</b>: Constant.
+ explicit set(const allocator_type& a)
+ : base_t(a)
{}
//! <b>Effects</b>: Constructs an empty set using the specified comparison object and
//! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
//! comp and otherwise N logN, where N is last - first.
template <class InputIterator>
- set(InputIterator first, InputIterator last, const Pred& comp = Pred(),
+ set(InputIterator first, InputIterator last, const Compare& comp = Compare(),
const allocator_type& a = allocator_type())
- : m_tree(first, last, comp, a, true)
+ : base_t(true, first, last, comp, a)
{}
//! <b>Effects</b>: Constructs an empty set using the specified comparison object and
//! unique values.
//!
//! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: Non-standard extension.
template <class InputIterator>
set( ordered_unique_range_t, InputIterator first, InputIterator last
- , const Pred& comp = Pred(), const allocator_type& a = allocator_type())
- : m_tree(ordered_range, first, last, comp, a)
+ , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
+ : base_t(ordered_range, first, last, comp, a)
+ {}
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
+ //! allocator, and inserts elements from the range [il.begin(), il.end()).
+ //!
+ //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
+ //! comp and otherwise N logN, where N is il.begin() - il.end().
+ set(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
+ : base_t(true, il.begin(), il.end(), comp, a)
+ {}
+
+ //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
+ //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
+ //! is more efficient than the normal range creation for ordered ranges.
+ //!
+ //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
+ //! unique values.
+ //!
+ //! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: Non-standard extension.
+ set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
+ : base_t(ordered_range, il.begin(), il.end(), comp, a)
{}
+#endif
//! <b>Effects</b>: Copy constructs a set.
//!
//! <b>Complexity</b>: Linear in x.size().
set(const set& x)
- : m_tree(x.m_tree)
+ : base_t(static_cast<const base_t&>(x))
{}
//! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources.
//!
//! <b>Postcondition</b>: x is emptied.
set(BOOST_RV_REF(set) x)
- : m_tree(boost::move(x.m_tree))
+ : base_t(boost::move(static_cast<base_t&>(x)))
{}
//! <b>Effects</b>: Copy constructs a set using the specified allocator.
//!
//! <b>Complexity</b>: Linear in x.size().
set(const set& x, const allocator_type &a)
- : m_tree(x.m_tree, a)
+ : base_t(static_cast<const base_t&>(x), a)
{}
//! <b>Effects</b>: Move constructs a set using the specified allocator.
//!
//! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
set(BOOST_RV_REF(set) x, const allocator_type &a)
- : m_tree(boost::move(x.m_tree), a)
+ : base_t(boost::move(static_cast<base_t&>(x)), a)
{}
//! <b>Effects</b>: Makes *this a copy of x.
//!
//! <b>Complexity</b>: Linear in x.size().
set& operator=(BOOST_COPY_ASSIGN_REF(set) x)
- { m_tree = x.m_tree; return *this; }
+ { return static_cast<set&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
//! <b>Effects</b>: this->swap(x.get()).
//!
- //! <b>Complexity</b>: Constant.
+ //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
+ //! is false and (allocation throws or value_type's move constructor throws)
+ //!
+ //! <b>Complexity</b>: Constant if allocator_traits_type::
+ //! propagate_on_container_move_assignment is true or
+ //! this->get>allocator() == x.get_allocator(). Linear otherwise.
set& operator=(BOOST_RV_REF(set) x)
- { m_tree = boost::move(x.m_tree); return *this; }
+ BOOST_CONTAINER_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value)
+ { return static_cast<set&>(this->base_t::operator=(boost::move(static_cast<base_t&>(x)))); }
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ set& operator=(std::initializer_list<value_type> il)
+ {
+ this->clear();
+ insert(il.begin(), il.end());
+ return *this;
+ }
+#endif
- //! <b>Effects</b>: Returns the comparison object out
- //! of which a was constructed.
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+ //! <b>Effects</b>: Returns a copy of the Allocator that
+ //! was passed to the object's constructor.
//!
//! <b>Complexity</b>: Constant.
- key_compare key_comp() const
- { return m_tree.key_comp(); }
+ allocator_type get_allocator() const;
- //! <b>Effects</b>: Returns an object of value_compare constructed out
- //! of the comparison object.
+ //! <b>Effects</b>: Returns a reference to the internal allocator.
+ //!
+ //! <b>Throws</b>: Nothing
//!
//! <b>Complexity</b>: Constant.
- value_compare value_comp() const
- { return m_tree.key_comp(); }
+ //!
+ //! <b>Note</b>: Non-standard extension.
+ stored_allocator_type &get_stored_allocator();
- //! <b>Effects</b>: Returns a copy of the Allocator that
- //! was passed to the object's constructor.
+ //! <b>Effects</b>: Returns a reference to the internal allocator.
+ //!
+ //! <b>Throws</b>: Nothing
//!
//! <b>Complexity</b>: Constant.
- allocator_type get_allocator() const
- { return m_tree.get_allocator(); }
-
- 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>Note</b>: Non-standard extension.
+ const stored_allocator_type &get_stored_allocator() const;
//! <b>Effects</b>: Returns an iterator to the first element contained in the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant
- iterator begin()
- { return m_tree.begin(); }
+ iterator 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
- { return m_tree.begin(); }
+ const_iterator begin() const;
- //! <b>Effects</b>: Returns an iterator to the end of the container.
+ //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- iterator end()
- { return m_tree.end(); }
+ const_iterator cbegin() const;
- //! <b>Effects</b>: Returns a const_iterator to the end of the container.
+ //! <b>Effects</b>: Returns an iterator to the end of the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- const_iterator end() const
- { return m_tree.end(); }
+ iterator end();
- //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
- //! of the reversed container.
+ //! <b>Effects</b>: Returns a const_iterator to the end of the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- reverse_iterator rbegin()
- { return m_tree.rbegin(); }
+ const_iterator end() const;
- //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
- //! of the reversed container.
+ //! <b>Effects</b>: Returns a const_iterator to the end of the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- const_reverse_iterator rbegin() const
- { return m_tree.rbegin(); }
+ const_iterator cend() const;
- //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
+ //! <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 rend()
- { return m_tree.rend(); }
+ reverse_iterator rbegin();
- //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
+ //! <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 rend() const
- { return m_tree.rend(); }
+ const_reverse_iterator rbegin() const;
- //! <b>Effects</b>: Returns a const_iterator to the first element contained in the 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_iterator cbegin() const
- { return m_tree.cbegin(); }
+ const_reverse_iterator crbegin() const;
- //! <b>Effects</b>: Returns a const_iterator to the end of the container.
+ //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
+ //! of the reversed container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- const_iterator cend() const
- { return m_tree.cend(); }
+ reverse_iterator rend();
- //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
+ //! <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 crbegin() const
- { return m_tree.crbegin(); }
+ const_reverse_iterator rend() const;
//! <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 crend() const
- { return m_tree.crend(); }
+ const_reverse_iterator crend() const;
//! <b>Effects</b>: Returns true if the container contains no elements.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- bool empty() const
- { return m_tree.empty(); }
+ bool empty() const;
//! <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
- { return m_tree.size(); }
+ size_type size() const;
//! <b>Effects</b>: Returns the largest possible size of the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant.
- size_type max_size() const
- { return m_tree.max_size(); }
+ size_type max_size() const;
+ #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- //! <b>Effects</b>: Swaps the contents of *this and x.
+ #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+ //! <b>Effects</b>: Inserts an object x of type Key constructed with
+ //! std::forward<Args>(args)... if and only if there is
+ //! no element in the container with equivalent value.
+ //! and returns the iterator pointing to the
+ //! newly inserted element.
//!
- //! <b>Throws</b>: Nothing.
+ //! <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>: Constant.
- void swap(set& x)
- { m_tree.swap(x.m_tree); }
+ //! <b>Throws</b>: If memory allocation throws or
+ //! Key's in-place constructor throws.
+ //!
+ //! <b>Complexity</b>: Logarithmic.
+ template <class... Args>
+ std::pair<iterator,bool> emplace(Args&&... args)
+ { return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
+
+ //! <b>Effects</b>: Inserts an object of type Key constructed with
+ //! std::forward<Args>(args)... if and only if there is
+ //! no element in the container with equivalent value.
+ //! p is a hint pointing to where the insert
+ //! should start to search.
+ //!
+ //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
+ //!
+ //! <b>Complexity</b>: Logarithmic.
+ template <class... Args>
+ iterator emplace_hint(const_iterator p, Args&&... args)
+ { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
+
+ #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { return this->base_t::emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); }\
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint(const_iterator p \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { return this->base_t::emplace_hint_unique(p \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+ #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <b>Effects</b>: Inserts x if and only if there is no element in the container
//! with key equivalent to the key of x.
//!
//! points to the element with key equivalent to the key of x.
//!
//! <b>Complexity</b>: Logarithmic.
- std::pair<iterator,bool> insert(insert_const_ref_type x)
- { return priv_insert(x); }
-
- #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- std::pair<iterator,bool> insert(T &x)
- { return this->insert(const_cast<const T &>(x)); }
-
- template<class U>
- std::pair<iterator,bool> insert(const U &u
- , typename container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
- { return priv_insert(u); }
- #endif
+ std::pair<iterator, bool> insert(const value_type &x);
//! <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.
//! 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)
- { return m_tree.insert_unique(boost::move(x)); }
+ std::pair<iterator, bool> insert(value_type &&x);
+ #else
+ private:
+ typedef std::pair<iterator, bool> insert_return_pair;
+ public:
+ BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert)
+ #endif
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <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.
//!
//! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
//! is inserted right before p.
- iterator insert(const_iterator p, insert_const_ref_type x)
- { return priv_insert(p, x); }
-
- #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- iterator insert(const_iterator position, T &x)
- { return this->insert(position, const_cast<const T &>(x)); }
-
- template<class U>
- iterator insert( const_iterator position, const U &u
- , typename container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
- { return priv_insert(position, u); }
- #endif
+ iterator insert(const_iterator p, const value_type &x);
//! <b>Effects</b>: Inserts an element move constructed from x in the container.
//! p is a hint pointing to where the insert should start to search.
//! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
//!
//! <b>Complexity</b>: Logarithmic.
- iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
- { return m_tree.insert_unique(p, boost::move(x)); }
+ iterator insert(const_iterator p, value_type &&x);
+ #else
+ BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
+ #endif
//! <b>Requires</b>: first, last are not iterators into *this.
//!
//! <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)
- { m_tree.insert_unique(first, last); }
-
- #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
-
- //! <b>Effects</b>: Inserts an object x of type T constructed with
- //! std::forward<Args>(args)... if and only if there is
- //! no element in the container with equivalent value.
- //! and returns the iterator pointing to the
- //! newly inserted element.
- //!
- //! <b>Returns</b>: The bool component of the returned pair is true if and only
- //! 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>Throws</b>: If memory allocation throws or
- //! T's in-place constructor throws.
- //!
- //! <b>Complexity</b>: Logarithmic.
- template <class... Args>
- std::pair<iterator,bool> emplace(Args&&... args)
- { return m_tree.emplace_unique(boost::forward<Args>(args)...); }
-
- //! <b>Effects</b>: Inserts an object of type T constructed with
- //! std::forward<Args>(args)... if and only if there is
- //! no element in the container with equivalent value.
- //! p is a hint pointing to where the insert
- //! should start to search.
- //!
- //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
- //!
- //! <b>Complexity</b>: Logarithmic.
- template <class... Args>
- iterator emplace_hint(const_iterator hint, Args&&... args)
- { return m_tree.emplace_hint_unique(hint, boost::forward<Args>(args)...); }
-
- #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+ { this->base_t::insert_unique(first, last); }
- #define BOOST_PP_LOCAL_MACRO(n) \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { return m_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
- \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- iterator emplace_hint(const_iterator hint \
- BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { return m_tree.emplace_hint_unique(hint \
- BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ //! <b>Effects</b>: inserts each element from the range [il.begin(),il.end()) if and only
+ //! if there is no element with key equivalent to the key of that element.
//!
- #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
- #include BOOST_PP_LOCAL_ITERATE()
+ //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
+ void insert(std::initializer_list<value_type> il)
+ { this->base_t::insert_unique(il.begin(), il.end()); }
+#endif
- #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <b>Effects</b>: Erases the element pointed to by p.
//!
//! returns end().
//!
//! <b>Complexity</b>: Amortized constant time
- iterator erase(const_iterator p)
- { return m_tree.erase(p); }
+ iterator erase(const_iterator p);
//! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
//!
//! <b>Returns</b>: Returns the number of erased elements.
//!
//! <b>Complexity</b>: log(size()) + count(k)
- size_type erase(const key_type& x)
- { return m_tree.erase(x); }
+ size_type erase(const key_type& x);
//! <b>Effects</b>: Erases all the elements in the range [first, last).
//!
//! <b>Returns</b>: Returns last.
//!
//! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
- iterator erase(const_iterator first, const_iterator last)
- { return m_tree.erase(first, last); }
+ iterator erase(const_iterator first, const_iterator last);
+
+ //! <b>Effects</b>: Swaps the contents of *this and x.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ void swap(set& x);
//! <b>Effects</b>: erase(a.begin(),a.end()).
//!
//! <b>Postcondition</b>: size() == 0.
//!
//! <b>Complexity</b>: linear in size().
- void clear()
- { m_tree.clear(); }
+ void clear();
+
+ //! <b>Effects</b>: Returns the comparison object out
+ //! of which a was constructed.
+ //!
+ //! <b>Complexity</b>: Constant.
+ key_compare key_comp() const;
+
+ //! <b>Effects</b>: Returns an object of value_compare constructed out
+ //! of the comparison object.
+ //!
+ //! <b>Complexity</b>: Constant.
+ value_compare value_comp() const;
//! <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)
- { return m_tree.find(x); }
+ iterator find(const key_type& x);
- //! <b>Returns</b>: A const_iterator pointing to an element with the key
+ //! <b>Returns</b>: Allocator 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
- { return m_tree.find(x); }
+ const_iterator find(const key_type& x) const;
+
+ #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <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
- { return m_tree.find(x) == m_tree.end() ? 0 : 1; }
+ { return static_cast<size_type>(this->base_t::find(x) != this->base_t::cend()); }
+
+ //! <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)
+ { return static_cast<size_type>(this->base_t::find(x) != this->base_t::end()); }
+
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <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)
- { return m_tree.lower_bound(x); }
+ iterator lower_bound(const key_type& x);
- //! <b>Returns</b>: A const iterator pointing to the first element with key not
+ //! <b>Returns</b>: Allocator 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
- { return m_tree.lower_bound(x); }
+ const_iterator lower_bound(const key_type& x) const;
//! <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)
- { return m_tree.upper_bound(x); }
+ iterator upper_bound(const key_type& x);
- //! <b>Returns</b>: A const iterator pointing to the first element with key not
+ //! <b>Returns</b>: Allocator 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
- { return m_tree.upper_bound(x); }
+ const_iterator upper_bound(const key_type& x) const;
+
+ #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <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)
- { return m_tree.equal_range(x); }
+ std::pair<iterator,iterator> equal_range(const key_type& x)
+ { return this->base_t::lower_bound_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
- { return m_tree.equal_range(x); }
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
+ { return this->base_t::lower_bound_range(x); }
- /// @cond
- template <class K1, class C1, class A1>
- friend bool operator== (const set<K1,C1,A1>&, const set<K1,C1,A1>&);
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- template <class K1, class C1, class A1>
- friend bool operator< (const set<K1,C1,A1>&, const set<K1,C1,A1>&);
+ //! <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);
- private:
- std::pair<iterator, bool> priv_insert(const T &x)
- { return m_tree.insert_unique(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;
- iterator priv_insert(const_iterator p, const T &x)
- { return m_tree.insert_unique(p, x); }
+ //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
+ //!
+ //! <b>Complexity</b>: Linear
+ void rebalance();
- /// @endcond
-};
+ //! <b>Effects</b>: Returns true if x and y are equal
+ //!
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator==(const set& x, const set& y);
-template <class T, class Pred, class A>
-inline bool operator==(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y)
-{ return x.m_tree == y.m_tree; }
+ //! <b>Effects</b>: Returns true if x and y are unequal
+ //!
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator!=(const set& x, const set& y);
-template <class T, class Pred, class A>
-inline bool operator<(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y)
-{ return x.m_tree < y.m_tree; }
+ //! <b>Effects</b>: Returns true if x is less than y
+ //!
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator<(const set& x, const set& y);
-template <class T, class Pred, class A>
-inline bool operator!=(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y)
-{ return !(x == y); }
+ //! <b>Effects</b>: Returns true if x is greater than y
+ //!
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator>(const set& x, const set& y);
-template <class T, class Pred, class A>
-inline bool operator>(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y)
-{ return y < x; }
+ //! <b>Effects</b>: Returns true if x is equal or less than y
+ //!
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator<=(const set& x, const set& y);
-template <class T, class Pred, class A>
-inline bool operator<=(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y)
-{ return !(y < x); }
+ //! <b>Effects</b>: Returns true if x is equal or greater than y
+ //!
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator>=(const set& x, const set& y);
-template <class T, class Pred, class A>
-inline bool operator>=(const set<T,Pred,A>& x,
- const set<T,Pred,A>& y)
-{ return !(x < y); }
+ //! <b>Effects</b>: x.swap(y)
+ //!
+ //! <b>Complexity</b>: Constant.
+ friend void swap(set& x, set& y);
-template <class T, class Pred, class A>
-inline void swap(set<T,Pred,A>& x, set<T,Pred,A>& y)
-{ x.swap(y); }
+ #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+ #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
+ private:
+ template <class KeyType>
+ std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
+ { return this->base_t::insert_unique(::boost::forward<KeyType>(x)); }
+
+ template <class KeyType>
+ iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
+ { return this->base_t::insert_unique(p, ::boost::forward<KeyType>(x)); }
+ #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
+};
-/// @cond
+#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
} //namespace container {
-/*
+
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
-template <class T, class C, class A>
-struct has_trivial_destructor_after_move<boost::container::set<T, C, A> >
+template <class Key, class C, class SetOptions, class Allocator>
+struct has_trivial_destructor_after_move<boost::container::set<Key, C, Allocator, SetOptions> >
{
- static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
+ static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
};
-*/
-namespace container {
-// Forward declaration of operators < and ==, needed for friend declaration.
+namespace container {
-template <class T, class Pred, class A>
-inline bool operator==(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y);
+#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
-template <class T, class Pred, class A>
-inline bool operator<(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y);
-/// @endcond
+#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
//! A multiset is a kind of associative container that supports equivalent keys
//! (possibly contains multiple copies of the same key value) and provides for
//! A multiset satisfies all of the requirements of a container and of a reversible
//! container, and of an associative container). multiset also provides most operations
//! described for duplicate keys.
-#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
-template <class T, class Pred = std::less<T>, class A = std::allocator<T> >
+//!
+//! \tparam Key is the type to be inserted in the set, which is also the key_type
+//! \tparam Compare is the comparison functor used to order keys
+//! \tparam Allocator is the allocator to be used to allocate memory for this container
+//! \tparam MultiSetOptions is an packed option type generated using using boost::container::tree_assoc_options.
+template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>, class MultiSetOptions = tree_assoc_defaults >
#else
-template <class T, class Pred, class A>
+template <class Key, class Compare, class Allocator, class MultiSetOptions>
#endif
class multiset
-{
/// @cond
+ : public container_detail::tree
+ <Key, Key,container_detail::identity<Key>, Compare, Allocator, MultiSetOptions>
+ /// @endcond
+{
+ #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
private:
BOOST_COPYABLE_AND_MOVABLE(multiset)
- typedef container_detail::rbtree<T, T,
- container_detail::identity<T>, Pred, A> tree_t;
- tree_t m_tree; // red-black tree representing multiset
- typedef typename container_detail::
- move_const_ref_type<T>::type insert_const_ref_type;
- /// @endcond
+ typedef container_detail::tree
+ <Key, Key,container_detail::identity<Key>, Compare, Allocator, MultiSetOptions> base_t;
+ #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
public:
- // typedefs:
- typedef typename tree_t::key_type key_type;
- typedef typename tree_t::value_type value_type;
- typedef typename tree_t::pointer pointer;
- typedef typename tree_t::const_pointer const_pointer;
- typedef typename tree_t::reference reference;
- typedef typename tree_t::const_reference const_reference;
- typedef Pred key_compare;
- typedef Pred value_compare;
- typedef typename tree_t::iterator iterator;
- typedef typename tree_t::const_iterator const_iterator;
- typedef typename tree_t::reverse_iterator reverse_iterator;
- typedef typename tree_t::const_reverse_iterator const_reverse_iterator;
- typedef typename tree_t::size_type size_type;
- typedef typename tree_t::difference_type difference_type;
- typedef typename tree_t::allocator_type allocator_type;
- typedef typename tree_t::stored_allocator_type stored_allocator_type;
-
- //! <b>Effects</b>: Constructs an empty multiset using the specified comparison
- //! object and allocator.
- //!
- //! <b>Complexity</b>: Constant.
+ //////////////////////////////////////////////
+ //
+ // types
+ //
+ //////////////////////////////////////////////
+ typedef Key key_type;
+ typedef Key value_type;
+ typedef Compare key_compare;
+ typedef Compare value_compare;
+ typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
+ typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
+ typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
+ typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
+ typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
+ typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
+ typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
+ typedef Allocator allocator_type;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
+ typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
+
+ //////////////////////////////////////////////
+ //
+ // construct/copy/destroy
+ //
+ //////////////////////////////////////////////
+
+ //! @copydoc ::boost::container::set::set()
multiset()
- : m_tree()
+ : base_t()
{}
- //! <b>Effects</b>: Constructs an empty multiset using the specified comparison
- //! object and allocator.
- //!
- //! <b>Complexity</b>: Constant.
- explicit multiset(const Pred& comp,
+ //! @copydoc ::boost::container::set::set(const Compare&, const allocator_type&)
+ explicit multiset(const Compare& comp,
const allocator_type& a = allocator_type())
- : m_tree(comp, a)
+ : base_t(comp, a)
{}
- //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object
- //! and allocator, and inserts elements from the range [first ,last ).
- //!
- //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
- //! comp and otherwise N logN, where N is last - first.
+ //! @copydoc ::boost::container::set::set(const allocator_type&)
+ explicit multiset(const allocator_type& a)
+ : base_t(a)
+ {}
+
+ //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const Compare& comp, const allocator_type&)
template <class InputIterator>
multiset(InputIterator first, InputIterator last,
- const Pred& comp = Pred(),
+ const Compare& comp = Compare(),
const allocator_type& a = allocator_type())
- : m_tree(first, last, comp, a, false)
+ : base_t(false, first, last, comp, a)
{}
//! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and
//! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
//!
//! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: Non-standard extension.
template <class InputIterator>
- multiset( ordered_range_t ordered_range, InputIterator first, InputIterator last
- , const Pred& comp = Pred()
+ multiset( ordered_range_t, InputIterator first, InputIterator last
+ , const Compare& comp = Compare()
, const allocator_type& a = allocator_type())
- : m_tree(ordered_range, first, last, comp, a)
+ : base_t(ordered_range, first, last, comp, a)
{}
- //! <b>Effects</b>: Copy constructs a multiset.
- //!
- //! <b>Complexity</b>: Linear in x.size().
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
+ multiset(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
+ : base_t(false, il.begin(), il.end(), comp, a)
+ {}
+
+ //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
+ multiset(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
+ : base_t(ordered_range, il.begin(), il.end(), comp, a)
+ {}
+#endif
+
+
+ //! @copydoc ::boost::container::set::set(const set &)
multiset(const multiset& x)
- : m_tree(x.m_tree)
+ : base_t(static_cast<const base_t&>(x))
{}
- //! <b>Effects</b>: Move constructs a multiset. Constructs *this using x's resources.
- //!
- //! <b>Complexity</b>: Constant.
- //!
- //! <b>Postcondition</b>: x is emptied.
+ //! @copydoc ::boost::container::set(set &&)
multiset(BOOST_RV_REF(multiset) x)
- : m_tree(boost::move(x.m_tree))
+ : base_t(boost::move(static_cast<base_t&>(x)))
{}
- //! <b>Effects</b>: Copy constructs a multiset using the specified allocator.
- //!
- //! <b>Complexity</b>: Linear in x.size().
+ //! @copydoc ::boost::container::set(const set &, const allocator_type &)
multiset(const multiset& x, const allocator_type &a)
- : m_tree(x.m_tree, a)
+ : base_t(static_cast<const base_t&>(x), a)
{}
- //! <b>Effects</b>: Move constructs a multiset using the specified allocator.
- //! Constructs *this using x's resources.
- //!
- //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
- //!
- //! <b>Postcondition</b>: x is emptied.
+ //! @copydoc ::boost::container::set(set &&, const allocator_type &)
multiset(BOOST_RV_REF(multiset) x, const allocator_type &a)
- : m_tree(boost::move(x.m_tree), a)
+ : base_t(boost::move(static_cast<base_t&>(x)), a)
{}
- //! <b>Effects</b>: Makes *this a copy of x.
- //!
- //! <b>Complexity</b>: Linear in x.size().
+ //! @copydoc ::boost::container::set::operator=(const set &)
multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x)
- { m_tree = x.m_tree; return *this; }
+ { return static_cast<multiset&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
- //! <b>Effects</b>: this->swap(x.get()).
- //!
- //! <b>Complexity</b>: Constant.
+ //! @copydoc ::boost::container::set::operator=(set &&)
multiset& operator=(BOOST_RV_REF(multiset) x)
- { m_tree = boost::move(x.m_tree); return *this; }
+ { return static_cast<multiset&>(this->base_t::operator=(boost::move(static_cast<base_t&>(x)))); }
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ //! @copydoc ::boost::container::set::operator=(std::initializer_list<value_type>)
+ multiset& operator=(std::initializer_list<value_type> il)
+ {
+ this->clear();
+ insert(il.begin(), il.end());
+ return *this;
+ }
+#endif
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- //! <b>Effects</b>: Returns the comparison object out
- //! of which a was constructed.
- //!
- //! <b>Complexity</b>: Constant.
- key_compare key_comp() const
- { return m_tree.key_comp(); }
+ //! @copydoc ::boost::container::set::get_allocator()
+ allocator_type get_allocator() const;
- //! <b>Effects</b>: Returns an object of value_compare constructed out
- //! of the comparison object.
- //!
- //! <b>Complexity</b>: Constant.
- value_compare value_comp() const
- { return m_tree.key_comp(); }
+ //! @copydoc ::boost::container::set::get_stored_allocator()
+ stored_allocator_type &get_stored_allocator();
- //! <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
- { return m_tree.get_allocator(); }
+ //! @copydoc ::boost::container::set::get_stored_allocator() const
+ const stored_allocator_type &get_stored_allocator() const;
- const stored_allocator_type &get_stored_allocator() const
- { return m_tree.get_stored_allocator(); }
+ //! @copydoc ::boost::container::set::begin()
+ iterator begin();
- stored_allocator_type &get_stored_allocator()
- { return m_tree.get_stored_allocator(); }
+ //! @copydoc ::boost::container::set::begin() const
+ const_iterator begin() const;
- //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- iterator begin()
- { return m_tree.begin(); }
+ //! @copydoc ::boost::container::set::cbegin() const
+ const_iterator cbegin() const;
- //! <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
- { return m_tree.begin(); }
+ //! @copydoc ::boost::container::set::end()
+ iterator end() BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Returns an iterator to the end of the container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- iterator end()
- { return m_tree.end(); }
+ //! @copydoc ::boost::container::set::end() const
+ const_iterator end() const BOOST_CONTAINER_NOEXCEPT;
- //! <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 m_tree.end(); }
+ //! @copydoc ::boost::container::set::cend() const
+ const_iterator cend() const BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
- //! of the reversed container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- reverse_iterator rbegin()
- { return m_tree.rbegin(); }
+ //! @copydoc ::boost::container::set::rbegin()
+ reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
- //! of the reversed container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- const_reverse_iterator rbegin() const
- { return m_tree.rbegin(); }
+ //! @copydoc ::boost::container::set::rbegin() const
+ const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
- //! of the reversed container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- reverse_iterator rend()
- { return m_tree.rend(); }
+ //! @copydoc ::boost::container::set::crbegin() const
+ const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT;
- //! <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
- { return m_tree.rend(); }
+ //! @copydoc ::boost::container::set::rend()
+ reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT;
- //! <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.cbegin(); }
+ //! @copydoc ::boost::container::set::rend() const
+ const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Returns a const_iterator to the end of the container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- const_iterator cend() const
- { return m_tree.cend(); }
+ //! @copydoc ::boost::container::set::crend() const
+ const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
- //! of the reversed container.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- const_reverse_iterator crbegin() const
- { return m_tree.crbegin(); }
+ //! @copydoc ::boost::container::set::empty() const
+ bool empty() const;
- //! <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 crend() const
- { return m_tree.crend(); }
+ //! @copydoc ::boost::container::set::size() const
+ size_type size() const;
- //! <b>Effects</b>: Returns true if the container contains no elements.
- //!
- //! <b>Throws</b>: Nothing.
- //!
- //! <b>Complexity</b>: Constant.
- bool empty() const
- { return m_tree.empty(); }
+ //! @copydoc ::boost::container::set::max_size() const
+ size_type max_size() const;
- //! <b>Effects</b>: Returns the number of the elements contained in the container.
- //!
- //! <b>Throws</b>: Nothing.
+ #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+ #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+ //! <b>Effects</b>: Inserts an object of type Key constructed with
+ //! std::forward<Args>(args)... and returns the iterator pointing to the
+ //! newly inserted element.
//!
- //! <b>Complexity</b>: Constant.
- size_type size() const
- { return m_tree.size(); }
+ //! <b>Complexity</b>: Logarithmic.
+ template <class... Args>
+ iterator emplace(Args&&... args)
+ { return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
- //! <b>Effects</b>: Returns the largest possible size of the container.
+ //! <b>Effects</b>: Inserts an object of type Key constructed with
+ //! std::forward<Args>(args)...
//!
- //! <b>Throws</b>: Nothing.
+ //! <b>Returns</b>: An iterator pointing to the element with key equivalent
+ //! to the key of x.
//!
- //! <b>Complexity</b>: Constant.
- size_type max_size() const
- { return m_tree.max_size(); }
+ //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
+ //! is inserted right before p.
+ template <class... Args>
+ iterator emplace_hint(const_iterator p, Args&&... args)
+ { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
- //! <b>Effects</b>: Swaps the contents of *this and x.
- //!
- //! <b>Throws</b>: Nothing.
+ #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { return this->base_t::emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint(const_iterator p \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { return this->base_t::emplace_hint_equal(p \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
//!
- //! <b>Complexity</b>: Constant.
- void swap(multiset& x)
- { m_tree.swap(x.m_tree); }
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+ #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <b>Effects</b>: Inserts x and returns the iterator pointing to the
//! newly inserted element.
//!
//! <b>Complexity</b>: Logarithmic.
- iterator insert(insert_const_ref_type x)
- { return priv_insert(x); }
-
- #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- iterator insert(T &x)
- { return this->insert(const_cast<const T &>(x)); }
-
- template<class U>
- iterator insert(const U &u
- , typename container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
- { return priv_insert(u); }
- #endif
+ iterator insert(const value_type &x);
//! <b>Effects</b>: Inserts a copy of x in the container.
//!
//!
//! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
//! is inserted right before p.
- iterator insert(BOOST_RV_REF(value_type) x)
- { return m_tree.insert_equal(boost::move(x)); }
+ iterator insert(value_type &&x);
+ #else
+ BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert)
+ #endif
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <b>Effects</b>: Inserts a copy of x in the container.
//! p is a hint pointing to where the insert should start to search.
//!
//!
//! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
//! is inserted right before p.
- iterator insert(const_iterator p, insert_const_ref_type x)
- { return priv_insert(p, x); }
-
- #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- iterator insert(const_iterator position, T &x)
- { return this->insert(position, const_cast<const T &>(x)); }
-
- template<class U>
- iterator insert( const_iterator position, const U &u
- , typename container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
- { return priv_insert(position, u); }
- #endif
+ iterator insert(const_iterator p, const value_type &x);
//! <b>Effects</b>: Inserts a value move constructed from x in the container.
//! p is a hint pointing to where the insert should start to search.
//!
//! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
//! is inserted right before p.
- iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
- { return m_tree.insert_equal(p, boost::move(x)); }
+ iterator insert(const_iterator p, value_type &&x);
+ #else
+ BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
+ #endif
//! <b>Requires</b>: first, last are not iterators into *this.
//!
//! <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)
- { m_tree.insert_equal(first, last); }
+ { this->base_t::insert_equal(first, last); }
- #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ //! @copydoc ::boost::container::set::insert(std::initializer_list<value_type>)
+ void insert(std::initializer_list<value_type> il)
+ { this->base_t::insert_unique(il.begin(), il.end()); }
+#endif
- //! <b>Effects</b>: Inserts an object of type T constructed with
- //! std::forward<Args>(args)... and returns the iterator pointing to the
- //! newly inserted element.
- //!
- //! <b>Complexity</b>: Logarithmic.
- template <class... Args>
- iterator emplace(Args&&... args)
- { return m_tree.emplace_equal(boost::forward<Args>(args)...); }
+ #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- //! <b>Effects</b>: Inserts an object of type T constructed with
- //! std::forward<Args>(args)...
- //!
- //! <b>Returns</b>: An iterator pointing to the element with key equivalent
- //! to the key of x.
- //!
- //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
- //! is inserted right before p.
- template <class... Args>
- iterator emplace_hint(const_iterator hint, Args&&... args)
- { return m_tree.emplace_hint_equal(hint, boost::forward<Args>(args)...); }
+ //! @copydoc ::boost::container::set::erase(const_iterator)
+ iterator erase(const_iterator p);
- #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+ //! @copydoc ::boost::container::set::erase(const key_type&)
+ size_type erase(const key_type& x);
- #define BOOST_PP_LOCAL_MACRO(n) \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { return m_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
- \
- BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
- iterator emplace_hint(const_iterator hint \
- BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- { return m_tree.emplace_hint_equal(hint \
- BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
- //!
- #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
- #include BOOST_PP_LOCAL_ITERATE()
+ //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator)
+ iterator erase(const_iterator first, const_iterator last);
- #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+ //! @copydoc ::boost::container::set::swap
+ void swap(flat_multiset& x);
- //! <b>Effects</b>: Erases the element pointed to by p.
- //!
- //! <b>Returns</b>: Returns an iterator pointing to the element immediately
- //! following q prior to the element being erased. If no such element exists,
- //! returns end().
- //!
- //! <b>Complexity</b>: Amortized constant time
- iterator erase(const_iterator p)
- { return m_tree.erase(p); }
+ //! @copydoc ::boost::container::set::clear
+ void clear() BOOST_CONTAINER_NOEXCEPT;
- //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
- //!
- //! <b>Returns</b>: Returns the number of erased elements.
- //!
- //! <b>Complexity</b>: log(size()) + count(k)
- size_type erase(const key_type& x)
- { return m_tree.erase(x); }
+ //! @copydoc ::boost::container::set::key_comp
+ key_compare key_comp() const;
- //! <b>Effects</b>: Erases all the elements in the range [first, last).
- //!
- //! <b>Returns</b>: Returns last.
- //!
- //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
- iterator erase(const_iterator first, const_iterator last)
- { return m_tree.erase(first, last); }
+ //! @copydoc ::boost::container::set::value_comp
+ value_compare value_comp() const;
- //! <b>Effects</b>: erase(a.begin(),a.end()).
- //!
- //! <b>Postcondition</b>: size() == 0.
- //!
- //! <b>Complexity</b>: linear in size().
- void clear()
- { m_tree.clear(); }
+ //! @copydoc ::boost::container::set::find(const key_type& )
+ iterator find(const key_type& x);
- //! <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)
- { return m_tree.find(x); }
+ //! @copydoc ::boost::container::set::find(const key_type& ) const
+ const_iterator find(const key_type& x) const;
- //! <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
- { return m_tree.find(x); }
+ //! @copydoc ::boost::container::set::count(const key_type& ) const
+ size_type count(const key_type& x) const;
- //! <b>Returns</b>: The number of elements with key equivalent to x.
+ //! @copydoc ::boost::container::set::lower_bound(const key_type& )
+ iterator lower_bound(const key_type& x);
+
+ //! @copydoc ::boost::container::set::lower_bound(const key_type& ) const
+ const_iterator lower_bound(const key_type& x) const;
+
+ //! @copydoc ::boost::container::set::upper_bound(const key_type& )
+ iterator upper_bound(const key_type& x);
+
+ //! @copydoc ::boost::container::set::upper_bound(const key_type& ) const
+ const_iterator upper_bound(const key_type& x) const;
+
+ //! @copydoc ::boost::container::set::equal_range(const key_type& ) const
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
+
+ //! @copydoc ::boost::container::set::equal_range(const key_type& )
+ std::pair<iterator,iterator> equal_range(const key_type& x);
+
+ //! @copydoc ::boost::container::set::rebalance()
+ void rebalance();
+
+ //! <b>Effects</b>: Returns true if x and y are equal
//!
- //! <b>Complexity</b>: log(size())+count(k)
- size_type count(const key_type& x) const
- { return m_tree.count(x); }
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator==(const multiset& x, const multiset& y);
- //! <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>Effects</b>: Returns true if x and y are unequal
//!
- //! <b>Complexity</b>: Logarithmic
- iterator lower_bound(const key_type& x)
- { return m_tree.lower_bound(x); }
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator!=(const multiset& x, const multiset& y);
- //! <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>Effects</b>: Returns true if x is less than y
//!
- //! <b>Complexity</b>: Logarithmic
- const_iterator lower_bound(const key_type& x) const
- { return m_tree.lower_bound(x); }
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator<(const multiset& x, const multiset& y);
- //! <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>Effects</b>: Returns true if x is greater than y
//!
- //! <b>Complexity</b>: Logarithmic
- iterator upper_bound(const key_type& x)
- { return m_tree.upper_bound(x); }
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator>(const multiset& x, const multiset& y);
- //! <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>Effects</b>: Returns true if x is equal or less than y
//!
- //! <b>Complexity</b>: Logarithmic
- const_iterator upper_bound(const key_type& x) const
- { return m_tree.upper_bound(x); }
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator<=(const multiset& x, const multiset& y);
- //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
+ //! <b>Effects</b>: Returns true if x is equal or greater than y
//!
- //! <b>Complexity</b>: Logarithmic
- std::pair<iterator,iterator>
- equal_range(const key_type& x)
- { return m_tree.equal_range(x); }
+ //! <b>Complexity</b>: Linear to the number of elements in the container.
+ friend bool operator>=(const multiset& x, const multiset& y);
- //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
+ //! <b>Effects</b>: x.swap(y)
//!
- //! <b>Complexity</b>: Logarithmic
- std::pair<const_iterator, const_iterator>
- equal_range(const key_type& x) const
- { return m_tree.equal_range(x); }
+ //! <b>Complexity</b>: Constant.
+ friend void swap(multiset& x, multiset& y);
- /// @cond
- template <class K1, class C1, class A1>
- friend bool operator== (const multiset<K1,C1,A1>&,
- const multiset<K1,C1,A1>&);
- template <class K1, class C1, class A1>
- friend bool operator< (const multiset<K1,C1,A1>&,
- const multiset<K1,C1,A1>&);
+ #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+ #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
private:
- iterator priv_insert(const T &x)
- { return m_tree.insert_equal(x); }
+ template <class KeyType>
+ iterator priv_insert(BOOST_FWD_REF(KeyType) x)
+ { return this->base_t::insert_equal(::boost::forward<KeyType>(x)); }
- iterator priv_insert(const_iterator p, const T &x)
- { return m_tree.insert_equal(p, x); }
+ template <class KeyType>
+ iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
+ { return this->base_t::insert_equal(p, ::boost::forward<KeyType>(x)); }
- /// @endcond
+ #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
};
-template <class T, class Pred, class A>
-inline bool operator==(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y)
-{ return x.m_tree == y.m_tree; }
-
-template <class T, class Pred, class A>
-inline bool operator<(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y)
-{ return x.m_tree < y.m_tree; }
-
-template <class T, class Pred, class A>
-inline bool operator!=(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y)
-{ return !(x == y); }
-
-template <class T, class Pred, class A>
-inline bool operator>(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y)
-{ return y < x; }
-
-template <class T, class Pred, class A>
-inline bool operator<=(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y)
-{ return !(y < x); }
-
-template <class T, class Pred, class A>
-inline bool operator>=(const multiset<T,Pred,A>& x,
- const multiset<T,Pred,A>& y)
-{ return !(x < y); }
-
-template <class T, class Pred, class A>
-inline void swap(multiset<T,Pred,A>& x, multiset<T,Pred,A>& y)
-{ x.swap(y); }
-
-/// @cond
+#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
} //namespace container {
-/*
+
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
-template <class T, class C, class A>
-struct has_trivial_destructor_after_move<boost::container::multiset<T, C, A> >
+template <class Key, class C, class Allocator, class MultiSetOptions>
+struct has_trivial_destructor_after_move<boost::container::multiset<Key, C, Allocator, MultiSetOptions> >
{
- static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
+ static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
};
-*/
+
namespace container {
-/// @endcond
+#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
}}