Class template multimap

boost::container::multimap

Synopsis

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

template<typename Key, typename T, 
         typename Pred = std::less< std::pair< const Key, T> >, 
         typename A = std::allocator<T> > 
class multimap {
public:
  // types
  typedef tree_t::key_type                   key_type;                
  typedef tree_t::value_type                 value_type;              
  typedef tree_t::pointer                    pointer;                 
  typedef tree_t::const_pointer              const_pointer;           
  typedef tree_t::reference                  reference;               
  typedef tree_t::const_reference            const_reference;         
  typedef T                                  mapped_type;             
  typedef Pred                               key_compare;             
  typedef tree_t::iterator                   iterator;                
  typedef tree_t::const_iterator             const_iterator;          
  typedef tree_t::reverse_iterator           reverse_iterator;        
  typedef tree_t::const_reverse_iterator     const_reverse_iterator;  
  typedef tree_t::size_type                  size_type;               
  typedef tree_t::difference_type            difference_type;         
  typedef tree_t::allocator_type             allocator_type;          
  typedef tree_t::stored_allocator_type      stored_allocator_type;   
  typedef std::pair< key_type, mapped_type > nonconst_value_type;     
  typedef unspecified                        nonconst_impl_value_type;
  typedef value_compare_impl                 value_compare;           

  // construct/copy/destruct
  multimap();
  explicit multimap(const Pred &, const allocator_type & = allocator_type());
  template<typename InputIterator> 
    multimap(InputIterator, InputIterator, const Pred & = Pred(), 
             const allocator_type & = allocator_type());
  template<typename InputIterator> 
    multimap(ordered_range_t, InputIterator, InputIterator, 
             const Pred & = Pred(), 
             const allocator_type & = allocator_type());
  multimap(const multimap< Key, T, Pred, A > &);
  multimap(BOOST_RV_REF(multimap));
  multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap));
  multimap& operator=(BOOST_RV_REF(multimap));

  // public member functions
  key_compare key_comp() const;
  value_compare value_comp() const;
  allocator_type get_allocator() const;
  const stored_allocator_type & get_stored_allocator() const;
  stored_allocator_type & get_stored_allocator();
  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end() const;
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;
  reverse_iterator rend();
  const_reverse_iterator rend() const;
  bool empty() const;
  size_type size() const;
  size_type max_size() const;
  void swap(multimap &);
  iterator insert(const value_type &);
  iterator insert(const nonconst_value_type &);
  iterator insert(BOOST_RV_REF(nonconst_value_type));
  iterator insert(BOOST_RV_REF(nonconst_impl_value_type));
  iterator insert(iterator, const value_type &);
  iterator insert(iterator, const nonconst_value_type &);
  iterator insert(iterator, BOOST_RV_REF(nonconst_value_type));
  iterator insert(iterator, BOOST_RV_REF(nonconst_impl_value_type));
  template<typename InputIterator> void insert(InputIterator, InputIterator);
  template<class... Args> iterator emplace(Args &&...);
  template<class... Args> iterator emplace_hint(const_iterator, Args &&...);
  iterator erase(const_iterator);
  size_type erase(const key_type &);
  iterator erase(const_iterator, const_iterator);
  void clear();
  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 &);
  std::pair< iterator, iterator > equal_range(const key_type &);
  const_iterator upper_bound(const key_type &) const;
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) const;
};

Description

A 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 multimap class supports bidirectional iterators.

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

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

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

`multimap` public construct/copy/destruct

```
multimap();
```
Effects: Default constructs an empty multimap.

Complexity: Constant.

explicit multimap(const Pred & comp, 
                  const allocator_type & a = allocator_type());

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

Complexity: Constant.

```
template<typename InputIterator> 
  multimap(InputIterator first, InputIterator last, 
           const Pred & comp = Pred(), 
           const allocator_type & a = allocator_type());
```
Effects: Constructs an empty 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> 
  multimap(ordered_range_t ordered_range, InputIterator first, 
           InputIterator last, const Pred & comp = Pred(), 
           const allocator_type & a = allocator_type());
```
Effects: Constructs an empty 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.
```
multimap(const multimap< Key, T, Pred, A > & x);
```
Effects: Copy constructs a multimap.

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

Complexity: Construct.

Postcondition: x is emptied.
```
multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x);
```
Effects: Makes *this a copy of x.

Complexity: Linear in x.size().
```
multimap& operator=(BOOST_RV_REF(multimap) x);
```
Effects: this->swap(x.get()).

Complexity: Constant.

`multimap` public member functions

```
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.
```
allocator_type get_allocator() const;
```
Effects: Returns a copy of the Allocator that was passed to the object's constructor.

Complexity: Constant.

const stored_allocator_type & get_stored_allocator() const;

stored_allocator_type & get_stored_allocator();

```
iterator begin();
```
Effects: Returns an iterator to the first element contained in the container.

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

Complexity: Constant.
```
void swap(multimap & x);
```
Effects: Swaps the contents of *this and x.

Throws: Nothing.

Complexity: Constant.
```
iterator insert(const value_type & x);
```
Effects: Inserts x and returns the iterator pointing to the newly inserted element.

Complexity: Logarithmic.
```
iterator insert(const nonconst_value_type & x);
```
Effects: Inserts a new value constructed from x and returns the iterator pointing to the newly inserted element.

Complexity: Logarithmic.
```
iterator insert(BOOST_RV_REF(nonconst_value_type) x);
```
Effects: Inserts a new value move-constructed from x and returns the iterator pointing to the newly inserted element.

Complexity: Logarithmic.
```
iterator insert(BOOST_RV_REF(nonconst_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.
```
iterator insert(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 in general, but amortized constant if t is inserted right before p.
```
iterator insert(iterator position, const nonconst_value_type & x);
```
Effects: Inserts a new value 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 in general, but amortized constant if t is inserted right before p.
```
iterator insert(iterator position, BOOST_RV_REF(nonconst_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 in general, but amortized constant if t is inserted right before p.
```
iterator insert(iterator position, BOOST_RV_REF(nonconst_impl_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 in general, but amortized constant if t is inserted right before p.
```
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)
```
template<class... Args> iterator emplace(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 in general, but amortized constant if t is inserted right before p.
```
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 in general, but amortized constant if t is inserted right before p.
```
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: Amortized constant time
```
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: log(size()) + count(k)
```
iterator erase(const_iterator first, const_iterator last);
```
Effects: Erases all the elements in the range [first, last).

Returns: Returns last.

Complexity: log(size())+N where N is the distance from first to last.
```
void clear();
```
Effects: erase(a.begin(),a.end()).

Postcondition: size() == 0.

Complexity: linear in size().
```
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: A 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: 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
```
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
```
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
```
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
```
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