Class template flat_multimap

boost::container::flat_multimap

Synopsis

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

template<typename Key, typename T, typename Compare = std::less<Key>, 
         typename Allocator = std::allocator< std::pair< Key, T> > > 
class flat_multimap {
public:
  // types
  typedef Key                                                              key_type;              
  typedef T                                                                mapped_type;           
  typedef std::pair< Key, T >                                              value_type;            
  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                                           value_compare;         
  typedef Compare                                                          key_compare;           
  typedef implementation_defined                                           iterator;              
  typedef implementation_defined                                           const_iterator;        
  typedef implementation_defined                                           reverse_iterator;      
  typedef implementation_defined                                           const_reverse_iterator;
  typedef implementation_defined                                           movable_value_type;    

  // construct/copy/destruct
  flat_multimap();
  explicit flat_multimap(const Compare &, 
                         const allocator_type & = allocator_type());
  explicit flat_multimap(const allocator_type &);
  template<typename InputIterator> 
    flat_multimap(InputIterator, InputIterator, const Compare & = Compare(), 
                  const allocator_type & = allocator_type());
  template<typename InputIterator> 
    flat_multimap(ordered_range_t, InputIterator, InputIterator, 
                  const Compare & = Compare(), 
                  const allocator_type & = allocator_type());
  flat_multimap(const flat_multimap &);
  flat_multimap(flat_multimap &&);
  flat_multimap(const flat_multimap &, const allocator_type &);
  flat_multimap(flat_multimap &&, const allocator_type &);
  flat_multimap & operator=(const flat_multimap &);
  flat_multimap & 
  operator=(flat_multimap &&) noexcept(allocator_traits_type::propagate_on_container_move_assignment::value));

  // 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 noexcept;
  iterator end() noexcept;
  const_iterator end() const noexcept;
  reverse_iterator rbegin() noexcept;
  const_reverse_iterator rbegin() const noexcept;
  reverse_iterator rend() noexcept;
  const_reverse_iterator rend() const noexcept;
  const_iterator cbegin() const noexcept;
  const_iterator cend() const noexcept;
  const_reverse_iterator crbegin() 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(impl_value_type &&);
  iterator insert(const_iterator, const value_type &);
  iterator insert(const_iterator, value_type &&);
  iterator insert(const_iterator, impl_value_type &&);
  template<typename InputIterator> void insert(InputIterator, InputIterator);
  template<typename InputIterator> 
    void insert(ordered_range_t, InputIterator, InputIterator);
  iterator erase(const_iterator);
  size_type erase(const key_type &);
  iterator erase(const_iterator, const_iterator);
  void swap(flat_multimap &);
  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;
  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< iterator, iterator > equal_range(const key_type &);
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) const;

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

Description

A flat_multimap is a kind of associative container that supports equivalent keys (possibly containing multiple copies of the same key value) and provides for fast retrieval of values of another type T based on the keys. The flat_multimap class supports random-access iterators.

A flat_multimap satisfies all of the requirements of a container and of a reversible container and of an associative container. For a flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T> (unlike std::multimap<Key, T> which value_type is std::pair<const Key, T>).

Compare is the ordering function for Keys (e.g. std::less<Key>).

Allocator is the allocator to allocate the value_types (e.g. allocator< std::pair<Key, T> >).

flat_multimap is similar to std::multimap but it's implemented like an ordered vector. This means that inserting a new element into a flat_map 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

```
typename Key
```
is the key_type of the map
```
typename T
```
```
typename Compare = std::less<Key>
```
is the ordering function for Keys (e.g. std::less<Key>).
```
typename Allocator = std::allocator< std::pair< Key, T> >
```
is the allocator to allocate the value_types (e.g. allocator< std::pair<Key, T> > ).

`flat_multimap` public construct/copy/destruct

```
flat_multimap();
```
Effects: Default constructs an empty flat_map.

Complexity: Constant.

explicit flat_multimap(const Compare & comp, 
                       const allocator_type & a = allocator_type());

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

Complexity: Constant.

```
explicit flat_multimap(const allocator_type & a);
```
Effects: Constructs an empty flat_multimap using the specified allocator.

Complexity: Constant.
```
template<typename InputIterator> 
  flat_multimap(InputIterator first, InputIterator last, 
                const Compare & comp = Compare(), 
                const allocator_type & a = allocator_type());
```
Effects: Constructs an empty flat_multimap 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.
```
template<typename InputIterator> 
  flat_multimap(ordered_range_t, InputIterator first, InputIterator last, 
                const Compare & comp = Compare(), 
                const allocator_type & a = allocator_type());
```
Effects: Constructs an empty flat_multimap using the specified comparison object and allocator, and inserts elements from the ordered range [first ,last). This function is more efficient than the normal range creation for ordered ranges.

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

Complexity: Linear in N.

Note: Non-standard extension.
```
flat_multimap(const flat_multimap & x);
```
Effects: Copy constructs a flat_multimap.

Complexity: Linear in x.size().
```
flat_multimap(flat_multimap && x);
```
Effects: Move constructs a flat_multimap. Constructs *this using x's resources.

Complexity: Constant.

Postcondition: x is emptied.
```
flat_multimap(const flat_multimap & x, const allocator_type & a);
```
Effects: Copy constructs a flat_multimap using the specified allocator.

Complexity: Linear in x.size().
```
flat_multimap(flat_multimap && x, const allocator_type & a);
```
Effects: Move constructs a flat_multimap using the specified allocator. Constructs *this using x's resources.

Complexity: Constant if a == x.get_allocator(), linear otherwise.
```
flat_multimap & operator=(const flat_multimap & x);
```
Effects: Makes *this a copy of x.

Complexity: Linear in x.size().

flat_multimap & 
operator=(flat_multimap && x) noexcept(allocator_traits_type::propagate_on_container_move_assignment::value));

Effects: this->swap(x.get()).

Complexity: Constant.

`flat_multimap` public member functions

```
allocator_type get_allocator() const noexcept;
```
Effects: Returns a copy of the Allocator that was passed to the object's constructor.

Complexity: Constant.
```
stored_allocator_type & get_stored_allocator() noexcept;
```
Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.
```
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.
```
iterator begin() noexcept;
```
Effects: Returns an iterator to the first element contained in the container.

Throws: Nothing.

Complexity: Constant.
```
const_iterator begin() const noexcept;
```
Effects: Returns a const_iterator to the first element contained in the container.

Throws: Nothing.

Complexity: Constant.
```
iterator end() noexcept;
```
Effects: Returns an iterator to the end of the container.

Throws: Nothing.

Complexity: Constant.
```
const_iterator end() const noexcept;
```
Effects: Returns a const_iterator to the end of the container.

Throws: Nothing.

Complexity: Constant.
```
reverse_iterator rbegin() noexcept;
```
Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator rbegin() const noexcept;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
reverse_iterator rend() noexcept;
```
Effects: Returns a reverse_iterator pointing to the end of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator rend() const noexcept;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cbegin() const noexcept;
```
Effects: Returns a const_iterator to the first element contained in the container.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cend() const noexcept;
```
Effects: Returns a const_iterator to the end of the container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator crbegin() const noexcept;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator crend() const noexcept;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
bool empty() const noexcept;
```
Effects: Returns true if the container contains no elements.

Throws: Nothing.

Complexity: Constant.
```
size_type size() const noexcept;
```
Effects: Returns the number of the elements contained in the container.

Throws: Nothing.

Complexity: Constant.
```
size_type max_size() const noexcept;
```
Effects: Returns the largest possible size of the container.

Throws: Nothing.

Complexity: Constant.
```
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.
```
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 T's copy constructor throws.

Note: If capacity() is less than "cnt", iterators and references to to values might be invalidated.
```
void shrink_to_fit();
```
Effects: Tries to deallocate the excess of memory created
Throws: If memory allocation throws, or T's copy constructor throws.

Complexity: Linear to size().
```
template<class... Args> iterator emplace(Args &&... args);
```
Effects: Inserts an object of type T 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.
```
template<class... Args> 
  iterator emplace_hint(const_iterator hint, Args &&... args);
```
Effects: Inserts an object of type T 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 time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.
```
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.
```
iterator insert(value_type && x);
```
Effects: Inserts a new value 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.
```
iterator insert(impl_value_type && x);
```
Effects: Inserts a new value 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.
```
iterator insert(const_iterator position, 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 time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.
```
iterator insert(const_iterator position, value_type && x);
```
Effects: Inserts a 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 time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.
```
iterator insert(const_iterator position, impl_value_type && x);
```
Effects: Inserts a 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 time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.
```
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.
```
template<typename InputIterator> 
  void insert(ordered_range_t, InputIterator first, InputIterator last);
```
Requires: first, last are not iterators into *this.

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

Effects: inserts each element from the range [first,last) if and only if there is no element with key equivalent to the key of that element. 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: If an element is inserted it might invalidate elements.

Note: Non-standard extension.
```
iterator erase(const_iterator position);
```
Effects: Erases the element pointed to by position.

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 position

Note: Invalidates elements with keys not less than the erased element.
```
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.
```
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.
```
void swap(flat_multimap & x);
```
Effects: Swaps the contents of *this and x.

Throws: Nothing.

Complexity: Constant.
```
void clear() noexcept;
```
Effects: erase(a.begin(),a.end()).

Postcondition: size() == 0.

Complexity: linear in size().
```
key_compare key_comp() const;
```
Effects: Returns the comparison object out of which a was constructed.

Complexity: Constant.
```
value_compare value_comp() const;
```
Effects: Returns an object of value_compare constructed out of the comparison object.

Complexity: Constant.
```
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.
```
const_iterator find(const key_type & x) const;
```
Returns: An const_iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.

Complexity: Logarithmic.
```
size_type count(const key_type & x) const;
```
Returns: The number of elements with key equivalent to x.

Complexity: log(size())+count(k)
```
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
```
const_iterator lower_bound(const key_type & x) const;
```
Returns: Allocator 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
```
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
```
const_iterator upper_bound(const key_type & x) const;
```
Returns: Allocator const iterator pointing to the first element with key not less than x, or end() if such an element is not found.

Complexity: Logarithmic
```
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
```
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

`flat_multimap` friend functions

```
friend bool operator==(const flat_multimap & x, const flat_multimap & y);
```
Effects: Returns true if x and y are equal

Complexity: Linear to the number of elements in the container.
```
friend bool operator!=(const flat_multimap & x, const flat_multimap & y);
```
Effects: Returns true if x and y are unequal

Complexity: Linear to the number of elements in the container.
```
friend bool operator<(const flat_multimap & x, const flat_multimap & y);
```
Effects: Returns true if x is less than y

Complexity: Linear to the number of elements in the container.
```
friend bool operator>(const flat_multimap & x, const flat_multimap & y);
```
Effects: Returns true if x is greater than y

Complexity: Linear to the number of elements in the container.
```
friend bool operator<=(const flat_multimap & x, const flat_multimap & y);
```
Effects: Returns true if x is equal or less than y

Complexity: Linear to the number of elements in the container.
```
friend bool operator>=(const flat_multimap & x, const flat_multimap & y);
```
Effects: Returns true if x is equal or greater than y

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

friend void swap(flat_multimap & x, flat_multimap & y);

Effects: x.swap(y)

Complexity: Constant.

Boost C++ Libraries