Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Class template flat_multiset

boost::container::flat_multiset

Synopsis

// In header: <boost/container/flat_set.hpp>

template<typename Key, typename Compare = std::less<Key>, 
         typename Allocator = std::allocator<Key> > 
class flat_multiset {
public:
  // types
  typedef Key                                                                key_type;       
  typedef Key                                                                value_type;     
  typedef Compare                                                            key_compare;    
  typedef Compare                                                            value_compare;  
  typedef ::boost::container::allocator_traits< Allocator >::pointer         pointer;        
  typedef ::boost::container::allocator_traits< Allocator >::const_pointer   const_pointer;  
  typedef ::boost::container::allocator_traits< Allocator >::reference       reference;      
  typedef ::boost::container::allocator_traits< Allocator >::const_reference const_reference;
  typedef ::boost::container::allocator_traits< Allocator >::size_type       size_type;      
  typedef ::boost::container::allocator_traits< Allocator >::difference_type difference_type;
  typedef Allocator                                                          allocator_type; 

  // construct/copy/destruct
  explicit flat_multiset();
  explicit flat_multiset(const Compare &, 
                         const allocator_type & = allocator_type());
  template<typename InputIterator> 
    flat_multiset(InputIterator, InputIterator, const Compare & = Compare(), 
                  const allocator_type & = allocator_type());
  template<typename InputIterator> 
    flat_multiset(ordered_range_t, InputIterator, InputIterator, 
                  const Compare & = Compare(), 
                  const allocator_type & = allocator_type());
  flat_multiset(const flat_multiset &);
  flat_multiset(BOOST_RV_REF(flat_multiset));
  flat_multiset(const flat_multiset &, const allocator_type &);
  flat_multiset(BOOST_RV_REF(flat_multiset), const allocator_type &);
  flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset));
  flat_multiset& operator=(BOOST_RV_REF(flat_multiset));

  // public member functions
  typedef BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type);
  typedef BOOST_CONTAINER_IMPDEF(tree_t::iterator);
  typedef BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const;
  typedef BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator);
  typedef BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const;
  allocator_type get_allocator() const;
  stored_allocator_type & get_stored_allocator();
  const stored_allocator_type & get_stored_allocator() const;
  iterator begin();
  const_iterator begin() const;
  const_iterator cbegin() const;
  iterator end();
  const_iterator end() const;
  const_iterator cend() const;
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;
  const_reverse_iterator crbegin() const;
  reverse_iterator rend();
  const_reverse_iterator rend() const;
  const_reverse_iterator crend() const;
  bool empty() const;
  size_type size() const;
  size_type max_size() const;
  size_type capacity() const;
  void reserve(size_type);
  void shrink_to_fit();
  template<class... Args> iterator emplace(Args &&...);
  template<class... Args> iterator emplace_hint(const_iterator, Args &&...);
  iterator insert(const value_type &);
  iterator insert(value_type &&);
   BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->);
  iterator insert(const_iterator, value_type &&);
   BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, 
                                          this->, const_iterator);
  const_iterator equal_range(const key_type &) const;
  std::pair< iterator, iterator > equal_range(const key_type &);

  // public data members
  const value_type & x;
};

Description

flat_multiset is a Sorted Associative Container that stores objects of type Key. flat_multiset is a Simple Associative Container, meaning that its value type, as well as its key type, is Key. flat_Multiset can store multiple copies of the same key value.

flat_multiset is similar to std::multiset but it's implemented like an ordered vector. This means that inserting a new element into a flat_multiset invalidates previous iterators and references

Erasing an element of a flat_multiset invalidates iterators and references pointing to elements that come after (their keys are equal or bigger) the erased element.

flat_multiset public construct/copy/destruct

  1. explicit flat_multiset();

    Effects: Default constructs an empty flat_multiset.

    Complexity: Constant.

  2. explicit flat_multiset(const Compare & comp, 
                           const allocator_type & a = allocator_type());
  3. template<typename InputIterator> 
      flat_multiset(InputIterator first, InputIterator last, 
                    const Compare & comp = Compare(), 
                    const allocator_type & a = allocator_type());
  4. template<typename InputIterator> 
      flat_multiset(ordered_range_t, InputIterator first, InputIterator last, 
                    const Compare & comp = Compare(), 
                    const allocator_type & a = allocator_type());

    Effects: Constructs an empty flat_multiset using the specified comparison object and allocator, and inserts elements from the ordered range [first ,last ). This function is more efficient than the normal range creation for ordered ranges.

    Requires: [first ,last) must be ordered according to the predicate.

    Complexity: Linear in N.

    Note: Non-standard extension.

  5. flat_multiset(const flat_multiset & x);

    Effects: Copy constructs a flat_multiset.

    Complexity: Linear in x.size().

  6. flat_multiset(BOOST_RV_REF(flat_multiset) mx);

    Effects: Move constructs a flat_multiset. Constructs *this using x's resources.

    Complexity: Constant.

    Postcondition: x is emptied.

  7. flat_multiset(const flat_multiset & x, const allocator_type & a);

    Effects: Copy constructs a flat_multiset using the specified allocator.

    Complexity: Linear in x.size().

  8. flat_multiset(BOOST_RV_REF(flat_multiset) mx, const allocator_type & a);

    Effects: Move constructs a flat_multiset using the specified allocator. Constructs *this using x's resources.

    Complexity: Constant if a == mx.get_allocator(), linear otherwise

  9. flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x);

    Effects: Makes *this a copy of x.

    Complexity: Linear in x.size().

  10. flat_multiset& operator=(BOOST_RV_REF(flat_multiset) mx);

    Effects: Makes *this a copy of x.

    Complexity: Linear in x.size().

flat_multiset public member functions

  1. typedef BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type);
  2. typedef BOOST_CONTAINER_IMPDEF(tree_t::iterator);
  3. typedef BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const;
  4. typedef BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator);
  5. typedef BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const;
  6. allocator_type get_allocator() const;

    Effects: Returns a copy of the Allocator that was passed to the object's constructor.

    Complexity: Constant.

  7. stored_allocator_type & get_stored_allocator();

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  8. const stored_allocator_type & get_stored_allocator() const;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  9. iterator begin();

    Effects: Returns an iterator to the first element contained in the container.

    Throws: Nothing.

    Complexity: Constant.

  10. const_iterator begin() const;

    Effects: Returns a const_iterator to the first element contained in the container.

    Throws: Nothing.

    Complexity: Constant.

  11. const_iterator cbegin() const;

    Effects: Returns a const_iterator to the first element contained in the container.

    Throws: Nothing.

    Complexity: Constant.

  12. iterator end();

    Effects: Returns an iterator to the end of the container.

    Throws: Nothing.

    Complexity: Constant.

  13. const_iterator end() const;

    Effects: Returns a const_iterator to the end of the container.

    Throws: Nothing.

    Complexity: Constant.

  14. const_iterator cend() const;

    Effects: Returns a const_iterator to the end of the container.

    Throws: Nothing.

    Complexity: Constant.

  15. reverse_iterator rbegin();

    Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

  16. const_reverse_iterator rbegin() const;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

  17. const_reverse_iterator crbegin() const;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

  18. reverse_iterator rend();

    Effects: Returns a reverse_iterator pointing to the end of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

  19. const_reverse_iterator rend() const;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

  20. const_reverse_iterator crend() const;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

  21. bool empty() const;

    Effects: Returns true if the container contains no elements.

    Throws: Nothing.

    Complexity: Constant.

  22. size_type size() const;

    Effects: Returns the number of the elements contained in the container.

    Throws: Nothing.

    Complexity: Constant.

  23. size_type max_size() const;

    Effects: Returns the largest possible size of the container.

    Throws: Nothing.

    Complexity: Constant.

  24. size_type capacity() const;

    Effects: Number of elements for which memory has been allocated. capacity() is always greater than or equal to size().

    Throws: Nothing.

    Complexity: Constant.

  25. void reserve(size_type count_);

    Effects: If n is less than or equal to capacity(), this call has no effect. Otherwise, it is a request for allocation of additional memory. If the request is successful, then capacity() is greater than or equal to n; otherwise, capacity() is unchanged. In either case, size() is unchanged.

    Throws: If memory allocation allocation throws or Key's copy constructor throws.

    Note: If capacity() is less than "count", iterators and references to to values might be invalidated.

  26. void shrink_to_fit();
    Effects: Tries to deallocate the excess of memory created

    Throws: If memory allocation throws, or Key's copy constructor throws.

    Complexity: Linear to size().

  27. template<class... Args> iterator emplace(Args &&... args);

    Effects: Inserts an object of type Key constructed with std::forward<Args>(args)... and returns the iterator pointing to the newly inserted element.

    Complexity: Logarithmic search time plus linear insertion to the elements with bigger keys than x.

    Note: If an element is inserted it might invalidate elements.

  28. template<class... Args> 
      iterator emplace_hint(const_iterator hint, Args &&... args);

    Effects: Inserts an object of type Key constructed with std::forward<Args>(args)... in the container. p is a hint pointing to where the insert should start to search.

    Returns: An iterator pointing to the element with key equivalent to the key of x.

    Complexity: Logarithmic search time (constant if x is inserted right before p) plus insertion linear to the elements with bigger keys than x.

    Note: If an element is inserted it might invalidate elements.

  29. iterator insert(const value_type & x);

    Effects: Inserts x and returns the iterator pointing to the newly inserted element.

    Complexity: Logarithmic search time plus linear insertion to the elements with bigger keys than x.

    Note: If an element is inserted it might invalidate elements.

  30. iterator insert(value_type && x);

    Effects: Inserts a new value_type move constructed from x and returns the iterator pointing to the newly inserted element.

    Complexity: Logarithmic search time plus linear insertion to the elements with bigger keys than x.

    Note: If an element is inserted it might invalidate elements.

  31.  BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, 
                                       this-> priv_insert);

    Effects: Inserts a copy of x in the container. p is a hint pointing to where the insert should start to search.

    Returns: An iterator pointing to the element with key equivalent to the key of x.

    Complexity: Logarithmic search time (constant if x is inserted right before p) plus insertion linear to the elements with bigger keys than x.

    Note: If an element is inserted it might invalidate elements.

  32. iterator insert(const_iterator position, value_type && x);

    Effects: Inserts a new value move constructed from x in the container. p is a hint pointing to where the insert should start to search.

    Returns: An iterator pointing to the element with key equivalent to the key of x.

    Complexity: Logarithmic search time (constant if x is inserted right before p) plus insertion linear to the elements with bigger keys than x.

    Note: If an element is inserted it might invalidate elements.

  33.  BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, 
                                            this-> priv_insert, const_iterator);

    Requires: first, last are not iterators into *this.

    Effects: inserts each element from the range [first,last) .

    Complexity: At most N log(size()+N) (N is the distance from first to last) search time plus N*size() insertion time.

    Note: If an element is inserted it might invalidate elements.

  34. const_iterator equal_range(const key_type & x) const;
  35. std::pair< iterator, iterator > equal_range(const key_type & x);

    Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).

    Complexity: Logarithmic


PrevUpHomeNext