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 = new_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 >                  allocator_traits_type; 
  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;        
  typedef implementation_defined                                             stored_allocator_type; 
  typedef implementation_defined                                             iterator;              
  typedef implementation_defined                                             const_iterator;        
  typedef implementation_defined                                             reverse_iterator;      
  typedef implementation_defined                                             const_reverse_iterator;
  typedef implementation_defined                                             sequence_type;         

  // construct/copy/destruct
  explicit flat_multiset() noexcept(container_detail::is_nothrow_default_constructible< Allocator >::value &&container_detail::is_nothrow_default_constructible< Compare >::value));
  explicit flat_multiset(const Compare &);
  explicit flat_multiset(const allocator_type &);
  flat_multiset(const Compare &, const allocator_type &);
  template<typename InputIterator> flat_multiset(InputIterator, InputIterator);
  template<typename InputIterator> 
    flat_multiset(InputIterator, InputIterator, const allocator_type &);
  template<typename InputIterator> 
    flat_multiset(InputIterator, InputIterator, const Compare &);
  template<typename InputIterator> 
    flat_multiset(InputIterator, InputIterator, const Compare &, 
                  const allocator_type &);
  template<typename InputIterator> 
    flat_multiset(ordered_range_t, InputIterator, InputIterator);
  template<typename InputIterator> 
    flat_multiset(ordered_range_t, InputIterator, InputIterator, 
                  const Compare &);
  template<typename InputIterator> 
    flat_multiset(ordered_range_t, InputIterator, InputIterator, 
                  const Compare &, const allocator_type &);
  flat_multiset(std::initializer_list< value_type >);
  flat_multiset(std::initializer_list< value_type >, const allocator_type &);
  flat_multiset(std::initializer_list< value_type >, const Compare &);
  flat_multiset(std::initializer_list< value_type >, const Compare &, 
                const allocator_type &);
  flat_multiset(ordered_range_t, std::initializer_list< value_type >);
  flat_multiset(ordered_range_t, std::initializer_list< value_type >, 
                const Compare &);
  flat_multiset(ordered_range_t, std::initializer_list< value_type >, 
                const Compare &, const allocator_type &);
  flat_multiset(const flat_multiset &);
  flat_multiset(flat_multiset &&) noexcept(boost::container::container_detail::is_nothrow_move_constructible< Compare >::value));
  flat_multiset(const flat_multiset &, const allocator_type &);
  flat_multiset(flat_multiset &&, const allocator_type &);
  flat_multiset & operator=(const flat_multiset &);
  flat_multiset & 
  operator=(flat_multiset &&) noexcept((allocator_traits_type::propagate_on_container_move_assignment::value||allocator_traits_type::is_always_equal::value)&&boost::container::container_detail::is_nothrow_move_assignable< Compare >::value));
  flat_multiset & operator=(std::initializer_list< value_type >);

  // public member functions
  allocator_type get_allocator() const noexcept;
  stored_allocator_type & get_stored_allocator() noexcept;
  const stored_allocator_type & get_stored_allocator() const noexcept;
  iterator begin() noexcept;
  const_iterator begin() const;
  const_iterator cbegin() const noexcept;
  iterator end() noexcept;
  const_iterator end() const noexcept;
  const_iterator cend() const noexcept;
  reverse_iterator rbegin() noexcept;
  const_reverse_iterator rbegin() const noexcept;
  const_reverse_iterator crbegin() const noexcept;
  reverse_iterator rend() noexcept;
  const_reverse_iterator rend() const noexcept;
  const_reverse_iterator crend() const noexcept;
  bool empty() const noexcept;
  size_type size() const noexcept;
  size_type max_size() const noexcept;
  size_type capacity() const noexcept;
  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 &&);
  iterator insert(const_iterator, const value_type &);
  iterator insert(const_iterator, value_type &&);
  template<typename InputIterator> void insert(InputIterator, InputIterator);
  template<typename InputIterator> 
    void insert(ordered_range_t, InputIterator, InputIterator);
  void insert(std::initializer_list< value_type >);
  void insert(ordered_range_t, std::initializer_list< value_type >);
  template<typename C2> void merge(flat_multiset< Key, C2, Allocator > &);
  template<typename C2> void merge(flat_multiset< Key, C2, Allocator > &&);
  template<typename C2> void merge(flat_set< Key, C2, Allocator > &);
  template<typename C2> void merge(flat_set< Key, C2, Allocator > &&);
  iterator erase(const_iterator);
  size_type erase(const key_type &);
  iterator erase(const_iterator, const_iterator);
  void swap(flat_multiset &) noexcept(allocator_traits_type::is_always_equal::value &&boost::container::container_detail::is_nothrow_swappable< Compare >::value));
  void clear() noexcept;
  key_compare key_comp() const;
  value_compare value_comp() const;
  iterator find(const key_type &);
  const_iterator find(const key_type &) const;
  iterator nth(size_type) noexcept;
  const_iterator nth(size_type) const noexcept;
  size_type index_of(iterator) noexcept;
  size_type index_of(const_iterator) const noexcept;
  size_type count(const key_type &) const;
  iterator lower_bound(const key_type &);
  const_iterator lower_bound(const key_type &) const;
  iterator upper_bound(const key_type &);
  const_iterator upper_bound(const key_type &) const;
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) const;
  std::pair< iterator, iterator > equal_range(const key_type &);
  sequence_type extract_sequence();
  void adopt_sequence(sequence_type &&);
  void adopt_sequence(ordered_range_t, sequence_type &&);

  // friend functions
  friend bool operator==(const flat_multiset &, const flat_multiset &);
  friend bool operator!=(const flat_multiset &, const flat_multiset &);
  friend bool operator<(const flat_multiset &, const flat_multiset &);
  friend bool operator>(const flat_multiset &, const flat_multiset &);
  friend bool operator<=(const flat_multiset &, const flat_multiset &);
  friend bool operator>=(const flat_multiset &, const flat_multiset &);
  friend void swap(flat_multiset &, flat_multiset &);
};

Description

flat_multiset is a Sorted Associative Container that stores objects of type 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 invalidates iterators and references pointing to elements that come after (their keys are bigger) the erased element.

This container provides random-access iterators.

Template Parameters

  1. typename Key

    is the type to be inserted in the multiset, which is also the key_type

  2. typename Compare = std::less<Key>

    is the comparison functor used to order keys

  3. typename Allocator = new_allocator<Key>

    is the allocator to be used to allocate memory for this container

flat_multiset public construct/copy/destruct

  1. explicit flat_multiset() noexcept(container_detail::is_nothrow_default_constructible< Allocator >::value &&container_detail::is_nothrow_default_constructible< Compare >::value));

    Effects: Default constructs an empty container.

    Complexity: Constant.

  2. explicit flat_multiset(const Compare & comp);

    Effects: Constructs an empty container using the specified comparison object.

    Complexity: Constant.

  3. explicit flat_multiset(const allocator_type & a);

    Effects: Constructs an empty container using the specified allocator.

    Complexity: Constant.

  4. flat_multiset(const Compare & comp, const allocator_type & a);

    Effects: Constructs an empty container using the specified comparison object and allocator.

    Complexity: Constant.

  5. template<typename InputIterator> 
      flat_multiset(InputIterator first, InputIterator last);

    Effects: Constructs an empty container and inserts elements from the range [first ,last ).

    Complexity: Linear in N if the range [first ,last ) is already sorted using comp and otherwise N logN, where N is last - first.

  6. template<typename InputIterator> 
      flat_multiset(InputIterator first, InputIterator last, 
                    const allocator_type & a);

    Effects: Constructs an empty container using the specified allocator, and inserts elements from the range [first ,last ).

    Complexity: Linear in N if the range [first ,last ) is already sorted using comp and otherwise N logN, where N is last - first.

  7. template<typename InputIterator> 
      flat_multiset(InputIterator first, InputIterator last, const Compare & comp);

    Effects: Constructs an empty container using the specified comparison object and inserts elements from the range [first ,last ).

    Complexity: Linear in N if the range [first ,last ) is already sorted using comp and otherwise N logN, where N is last - first.

  8. template<typename InputIterator> 
      flat_multiset(InputIterator first, InputIterator last, const Compare & comp, 
                    const allocator_type & a);

    Effects: Constructs an empty container using the specified comparison object and allocator, and inserts elements from the range [first ,last ).

    Complexity: Linear in N if the range [first ,last ) is already sorted using comp and otherwise N logN, where N is last - first.

  9. template<typename InputIterator> 
      flat_multiset(ordered_range_t, InputIterator first, InputIterator last);

    Effects: Constructs an empty flat_multiset 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.

  10. template<typename InputIterator> 
      flat_multiset(ordered_range_t, InputIterator first, InputIterator last, 
                    const Compare & comp);

    Effects: Constructs an empty flat_multiset using the specified comparison object 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.

  11. template<typename InputIterator> 
      flat_multiset(ordered_range_t, InputIterator first, InputIterator last, 
                    const Compare & comp, const allocator_type & a);

    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.

  12. flat_multiset(std::initializer_list< value_type > il);

    Effects: Default constructs an empty container.

    Complexity: Constant.

  13. flat_multiset(std::initializer_list< value_type > il, 
                  const allocator_type & a);

    Effects: Constructs an empty container using the specified allocator, and inserts elements from the range [il.begin(), il.end()).

    Complexity: 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().

  14. flat_multiset(std::initializer_list< value_type > il, const Compare & comp);

    Effects: Constructs an empty container using the specified comparison object and inserts elements from the range [il.begin(), il.end()).

    Complexity: 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().

  15. flat_multiset(std::initializer_list< value_type > il, const Compare & comp, 
                  const allocator_type & a);

    Effects: Constructs an empty container using the specified comparison object and allocator, and inserts elements from the range [il.begin(), il.end()).

    Complexity: 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().

  16. flat_multiset(ordered_range_t, std::initializer_list< value_type > il);

    Effects: Constructs an empty containerand inserts elements from the ordered unique range [il.begin(), il.end()). This function is more efficient than the normal range creation for ordered ranges.

    Requires: [il.begin(), il.end()) must be ordered according to the predicate.

    Complexity: Linear in N.

    Note: Non-standard extension.

  17. flat_multiset(ordered_range_t, std::initializer_list< value_type > il, 
                  const Compare & comp);

    Effects: Constructs an empty container using the specified comparison object 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.

    Requires: [il.begin(), il.end()) must be ordered according to the predicate.

    Complexity: Linear in N.

    Note: Non-standard extension.

  18. flat_multiset(ordered_range_t, std::initializer_list< value_type > il, 
                  const Compare & comp, const allocator_type & a);

    Effects: Constructs an empty container 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.

    Requires: [il.begin(), il.end()) must be ordered according to the predicate.

    Complexity: Linear in N.

    Note: Non-standard extension.

  19. flat_multiset(const flat_multiset & x);

    Effects: Copy constructs the container.

    Complexity: Linear in x.size().

  20. flat_multiset(flat_multiset && x) noexcept(boost::container::container_detail::is_nothrow_move_constructible< Compare >::value));

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

    Complexity: Constant.

    Postcondition: x is emptied.

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

    Effects: Copy constructs a container using the specified allocator.

    Complexity: Linear in x.size().

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

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

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

  23. flat_multiset & operator=(const flat_multiset & x);

    Effects: Makes *this a copy of x.

    Complexity: Linear in x.size().

  24. flat_multiset & 
    operator=(flat_multiset && x) noexcept((allocator_traits_type::propagate_on_container_move_assignment::value||allocator_traits_type::is_always_equal::value)&&boost::container::container_detail::is_nothrow_move_assignable< Compare >::value));

    Throws: If allocator_traits_type::propagate_on_container_move_assignment is false and (allocation throws or value_type's move constructor throws)

    Complexity: Constant if allocator_traits_type:: propagate_on_container_move_assignment is true or this->get>allocator() == x.get_allocator(). Linear otherwise.

  25. flat_multiset & operator=(std::initializer_list< value_type > il);

    Effects: Copy all elements from il to *this.

    Complexity: Linear in il.size().

flat_multiset public member functions

  1. allocator_type get_allocator() const noexcept;

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

    Complexity: Constant.

  2. stored_allocator_type & get_stored_allocator() noexcept;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  3. const stored_allocator_type & get_stored_allocator() const noexcept;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  4. iterator begin() noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  5. const_iterator begin() const;

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

    Throws: Nothing.

    Complexity: Constant.

  6. const_iterator cbegin() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  7. iterator end() noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  8. const_iterator end() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  9. const_iterator cend() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  10. reverse_iterator rbegin() noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  11. const_reverse_iterator rbegin() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  12. const_reverse_iterator crbegin() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  13. reverse_iterator rend() noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  14. const_reverse_iterator rend() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  15. const_reverse_iterator crend() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  16. bool empty() const noexcept;

    Effects: Returns true if the container contains no elements.

    Throws: Nothing.

    Complexity: Constant.

  17. size_type size() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  18. size_type max_size() const noexcept;

    Effects: Returns the largest possible size of the container.

    Throws: Nothing.

    Complexity: Constant.

  19. size_type capacity() const noexcept;

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

    Throws: Nothing.

    Complexity: Constant.

  20. void reserve(size_type cnt);

    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 "cnt", iterators and references to to values might be invalidated.

  21. 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().

  22. 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.

  23. template<class... Args> 
      iterator emplace_hint(const_iterator p, 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.

  24. 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.

  25. 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.

  26. iterator insert(const_iterator p, const value_type & x);

    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.

  27. iterator insert(const_iterator p, 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.

  28. template<typename InputIterator> 
      void insert(InputIterator first, InputIterator last);

    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.

  29. template<typename InputIterator> 
      void insert(ordered_range_t, InputIterator first, InputIterator last);

    Requires: first, last are not iterators into *this and must be ordered according to the predicate.

    Effects: inserts each element from the range [first,last) .This function is more efficient than the normal range creation for ordered ranges.

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

    Note: Non-standard extension. If an element is inserted it might invalidate elements.

  30. void insert(std::initializer_list< value_type > il);

    Effects: inserts each element from the range [il.begin(), il.end()).

    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.

  31. void insert(ordered_range_t, std::initializer_list< value_type > il);

    Requires: Range [il.begin(), il.end()) must be ordered according to the predicate.

    Effects: inserts each element from the range [il.begin(), il.end()). This function is more efficient than the normal range creation for ordered ranges.

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

    Note: Non-standard extension. If an element is inserted it might invalidate elements.

  32. template<typename C2> void merge(flat_multiset< Key, C2, Allocator > & source);

    Requires: this->get_allocator() == source.get_allocator().

    Effects: Extracts each element in source and insert it into a using the comparison object of *this.

    Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.

    Throws: Nothing unless the comparison object throws.

    Complexity: N log(a.size() + N) (N has the value source.size())

  33. template<typename C2> 
      void merge(flat_multiset< Key, C2, Allocator > && source);

    Requires: this->get_allocator() == source.get_allocator().

    Effects: Extracts each element in source and insert it into a using the comparison object of *this.

    Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.

    Throws: Nothing unless the comparison object throws.

    Complexity: N log(a.size() + N) (N has the value source.size())

  34. template<typename C2> void merge(flat_set< Key, C2, Allocator > & source);

    Requires: this->get_allocator() == source.get_allocator().

    Effects: Extracts each element in source and insert it into a using the comparison object of *this.

    Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.

    Throws: Nothing unless the comparison object throws.

    Complexity: N log(a.size() + N) (N has the value source.size())

  35. template<typename C2> void merge(flat_set< Key, C2, Allocator > && source);

    Requires: this->get_allocator() == source.get_allocator().

    Effects: Extracts each element in source and insert it into a using the comparison object of *this.

    Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.

    Throws: Nothing unless the comparison object throws.

    Complexity: N log(a.size() + N) (N has the value source.size())

  36. iterator erase(const_iterator p);

    Effects: Erases the element pointed to by p.

    Returns: Returns an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists, returns end().

    Complexity: Linear to the elements with keys bigger than p

    Note: Invalidates elements with keys not less than the erased element.

  37. size_type erase(const key_type & x);

    Effects: Erases all elements in the container with key equivalent to x.

    Returns: Returns the number of erased elements.

    Complexity: Logarithmic search time plus erasure time linear to the elements with bigger keys.

  38. iterator erase(const_iterator first, const_iterator last);

    Effects: Erases all the elements in the range [first, last).

    Returns: Returns last.

    Complexity: size()*N where N is the distance from first to last.

    Complexity: Logarithmic search time plus erasure time linear to the elements with bigger keys.

  39. void swap(flat_multiset & x) noexcept(allocator_traits_type::is_always_equal::value &&boost::container::container_detail::is_nothrow_swappable< Compare >::value));

    Effects: Swaps the contents of *this and x.

    Throws: Nothing.

    Complexity: Constant.

  40. void clear() noexcept;

    Effects: erase(a.begin(),a.end()).

    Postcondition: size() == 0.

    Complexity: linear in size().

  41. key_compare key_comp() const;

    Effects: Returns the comparison object out of which a was constructed.

    Complexity: Constant.

  42. value_compare value_comp() const;

    Effects: Returns an object of value_compare constructed out of the comparison object.

    Complexity: Constant.

  43. iterator find(const key_type & x);

    Returns: An iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.

    Complexity: Logarithmic.

  44. const_iterator find(const key_type & x) const;

    Returns: A const_iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.

    Complexity: Logarithmic.

  45. iterator nth(size_type n) noexcept;

    Requires: size() >= n.

    Effects: Returns an iterator to the nth element from the beginning of the container. Returns end() if n == size().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  46. const_iterator nth(size_type n) const noexcept;

    Requires: size() >= n.

    Effects: Returns a const_iterator to the nth element from the beginning of the container. Returns end() if n == size().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  47. size_type index_of(iterator p) noexcept;

    Requires: begin() <= p <= end().

    Effects: Returns the index of the element pointed by p and size() if p == end().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  48. size_type index_of(const_iterator p) const noexcept;

    Requires: begin() <= p <= end().

    Effects: Returns the index of the element pointed by p and size() if p == end().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  49. size_type count(const key_type & x) const;

    Returns: The number of elements with key equivalent to x.

    Complexity: log(size())+count(k)

  50. iterator lower_bound(const key_type & x);

    Returns: An iterator pointing to the first element with key not less than k, or a.end() if such an element is not found.

    Complexity: Logarithmic

  51. const_iterator lower_bound(const key_type & x) const;

    Returns: A const iterator pointing to the first element with key not less than k, or a.end() if such an element is not found.

    Complexity: Logarithmic

  52. iterator upper_bound(const key_type & x);

    Returns: An iterator pointing to the first element with key not less than x, or end() if such an element is not found.

    Complexity: Logarithmic

  53. const_iterator upper_bound(const key_type & x) const;

    Returns: A const iterator pointing to the first element with key not less than x, or end() if such an element is not found.

    Complexity: Logarithmic

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

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

    Complexity: Logarithmic

  55. 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

  56. sequence_type extract_sequence();

    Effects: Extracts the internal sequence container.

    Complexity: Same as the move constructor of sequence_type, usually constant.

    Postcondition: this->empty()

    Throws: If secuence_type's move constructor throws

  57. void adopt_sequence(sequence_type && seq);

    Effects: Discards the internally hold sequence container and adopts the one passed externally using the move assignment.

    Complexity: Assuming O(1) move assignment, O(NlogN) with N = seq.size()

    Throws: If the comparison or the move constructor throws

  58. void adopt_sequence(ordered_range_t, sequence_type && seq);

    Requires: seq shall be ordered according to this->compare()

    Effects: Discards the internally hold sequence container and adopts the one passed externally using the move assignment.

    Complexity: Assuming O(1) move assignment, O(1)

    Throws: If the move assignment throws

flat_multiset friend functions

  1. friend bool operator==(const flat_multiset & x, const flat_multiset & y);

    Effects: Returns true if x and y are equal

    Complexity: Linear to the number of elements in the container.

  2. friend bool operator!=(const flat_multiset & x, const flat_multiset & y);

    Effects: Returns true if x and y are unequal

    Complexity: Linear to the number of elements in the container.

  3. friend bool operator<(const flat_multiset & x, const flat_multiset & y);

    Effects: Returns true if x is less than y

    Complexity: Linear to the number of elements in the container.

  4. friend bool operator>(const flat_multiset & x, const flat_multiset & y);

    Effects: Returns true if x is greater than y

    Complexity: Linear to the number of elements in the container.

  5. friend bool operator<=(const flat_multiset & x, const flat_multiset & y);

    Effects: Returns true if x is equal or less than y

    Complexity: Linear to the number of elements in the container.

  6. friend bool operator>=(const flat_multiset & x, const flat_multiset & y);

    Effects: Returns true if x is equal or greater than y

    Complexity: Linear to the number of elements in the container.

  7. friend void swap(flat_multiset & x, flat_multiset & y);

    Effects: x.swap(y)

    Complexity: Constant.


PrevUpHomeNext