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 multimap

boost::container::multimap

Synopsis

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

template<typename Key, typename T, typename Compare = std::less<Key>, 
         typename Allocator = new_allocator< std::pair< const Key, T> >, 
         typename MultiMapOptions = tree_assoc_defaults> 
class multimap {
public:
  // types
  typedef Key                                                              key_type;              
  typedef T                                                                mapped_type;           
  typedef std::pair< const Key, T >                                        value_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 std::pair< key_type, mapped_type >                               nonconst_value_type;   
  typedef implementation_defined                                           movable_value_type;    

  // construct/copy/destruct
  multimap();
  explicit multimap(const Compare &, 
                    const allocator_type & = allocator_type());
  explicit multimap(const allocator_type &);
  template<typename InputIterator> 
    multimap(InputIterator, InputIterator, const Compare & = Compare(), 
             const allocator_type & = allocator_type());
  template<typename InputIterator> 
    multimap(InputIterator, InputIterator, const allocator_type &);
  template<typename InputIterator> 
    multimap(ordered_range_t, InputIterator, InputIterator, 
             const Compare & = Compare(), 
             const allocator_type & = allocator_type());
  multimap(std::initializer_list< value_type >, const Compare & = Compare(), 
           const allocator_type & = allocator_type());
  multimap(std::initializer_list< value_type >, const allocator_type &);
  multimap(ordered_range_t, std::initializer_list< value_type >, 
           const Compare & = Compare(), 
           const allocator_type & = allocator_type());
  multimap(const multimap &);
  multimap(multimap &&);
  multimap(const multimap &, const allocator_type &);
  multimap(multimap &&, const allocator_type &);
  multimap & operator=(const multimap &);
  multimap & operator=(multimap &&) noexcept(condition);
  multimap & operator=(std::initializer_list< value_type >);

  // public member functions
  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() 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;
  size_type size() const;
  size_type max_size() const;
  template<class... Args> iterator emplace(Args &&...);
  template<class... Args> iterator emplace_hint(const_iterator, Args &&...);
  iterator insert(const value_type &);
  iterator insert(const nonconst_value_type &);
  iterator insert(nonconst_value_type &&);
  iterator insert(movable_value_type &&);
  iterator insert(const_iterator, const value_type &);
  iterator insert(const_iterator, const nonconst_value_type &);
  iterator insert(const_iterator, nonconst_value_type &&);
  iterator insert(const_iterator, movable_value_type &&);
  template<typename InputIterator> void insert(InputIterator, InputIterator);
  void insert(std::initializer_list< value_type >);
  iterator erase(const_iterator);
  size_type erase(const key_type &);
  iterator erase(const_iterator, const_iterator);
  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;
  void rebalance();

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

  // public data members
  void swap(multiset &x) noexcept(allocator_traits_type void clear;
};

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. The value_type stored by this container is the value_type is std::pair<const Key, T>.

Template Parameters

  1. typename Key

    is the key_type of the map

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

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

  4. typename Allocator = new_allocator< std::pair< const Key, T> >

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

  5. typename MultiMapOptions = tree_assoc_defaults

    is an packed option type generated using using boost::container::tree_assoc_options.

multimap public construct/copy/destruct

  1. multimap();

    Effects: Default constructs an empty multimap.

    Complexity: Constant.

  2. explicit multimap(const Compare & comp, 
                      const allocator_type & a = allocator_type());

    Effects: Constructs an empty multimap using the specified allocator.

    Complexity: Constant.

  3. explicit multimap(const allocator_type & a);

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

    Complexity: Constant.

  4. template<typename InputIterator> 
      multimap(InputIterator first, InputIterator last, 
               const Compare & comp = Compare(), 
               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.

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

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

  6. template<typename InputIterator> 
      multimap(ordered_range_t, InputIterator first, InputIterator last, 
               const Compare & comp = Compare(), 
               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.

    Note: Non-standard extension.

  7. multimap(std::initializer_list< value_type > il, 
             const Compare & comp = Compare(), 
             const allocator_type & a = allocator_type());

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

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

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

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

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

  9. multimap(ordered_range_t, std::initializer_list< value_type > il, 
             const Compare & comp = Compare(), 
             const allocator_type & a = allocator_type());

    Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the ordered 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.

  10. multimap(const multimap & x);

    Effects: Copy constructs a multimap.

    Complexity: Linear in x.size().

  11. multimap(multimap && x);

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

    Complexity: Constant.

    Postcondition: x is emptied.

  12. multimap(const multimap & x, const allocator_type & a);

    Effects: Copy constructs a multimap.

    Complexity: Linear in x.size().

  13. multimap(multimap && x, const allocator_type & a);

    Effects: Move constructs a multimap using the specified allocator. Constructs *this using x's resources. Complexity: Constant if a == x.get_allocator(), linear otherwise.

    Postcondition: x is emptied.

  14. multimap & operator=(const multimap & x);

    Effects: Makes *this a copy of x.

    Complexity: Linear in x.size().

  15. multimap & operator=(multimap && x) noexcept(condition);

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

    Complexity: Constant.

  16. multimap & operator=(std::initializer_list< value_type > il);

    Effects: Assign content of il to *this.

multimap public member functions

  1. allocator_type get_allocator() const;

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

    Complexity: Constant.

  2. stored_allocator_type & get_stored_allocator();

    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;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  4. iterator begin();

    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;

    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;

    Effects: Returns true if the container contains no elements.

    Throws: Nothing.

    Complexity: Constant.

  17. size_type size() const;

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

    Throws: Nothing.

    Complexity: Constant.

  18. size_type max_size() const;

    Effects: Returns the largest possible size of the container.

    Throws: Nothing.

    Complexity: Constant.

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

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

  21. iterator insert(const value_type & x);

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

    Complexity: Logarithmic.

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

  23. iterator insert(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.

  24. iterator insert(movable_value_type && x);

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

    Complexity: Logarithmic.

  25. 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 in general, but amortized constant if t is inserted right before p.

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

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

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

  29. 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)

  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 il.begin() to il.end())

  31. 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: Amortized constant time

  32. 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)

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

  34. key_compare key_comp() const;

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

    Complexity: Constant.

  35. value_compare value_comp() const;

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

    Complexity: Constant.

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

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

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

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

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

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

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

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

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

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

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

  45. void rebalance();

    Effects: Rebalances the tree. It's a no-op for Red-Black and AVL trees.

    Complexity: Linear

multimap friend functions

  1. friend bool operator==(const multimap & x, const multimap & 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 multimap & x, const multimap & 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 multimap & x, const multimap & 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 multimap & x, const multimap & 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 multimap & x, const multimap & 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 multimap & x, const multimap & 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(multimap & x, multimap & y);

    Effects: x.swap(y)

    Complexity: Constant.

multimap public public data members

  1. void swap(multiset &x) noexcept(allocator_traits_type void clear;

    Effects: x.swap(y)

    Complexity: Constant.

    Effects: Swaps the contents of *this and x.

    Throws: Nothing.

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

    Postcondition: size() == 0.

    Complexity: linear in size().


PrevUpHomeNext