23 Containers library [containers]

23.4 Associative containers [associative]

23.4.5 Class template multimap [multimap]

23.4.5.1 Class template multimap overview [multimap.overview]

A multimap is an 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 ([container.requirements]), of an associative container ([associative.reqmts]), and of an allocator-aware container (Table [tab:containers.allocatoraware]). A multimap also provides most operations described in ([associative.reqmts]) for equal keys. This means that a multimap supports the a_eq operations in ([associative.reqmts]) but not the a_uniq operations. For a multimap<Key,T> the key_type is Key and the value_type is pair<const Key,T>. Descriptions are provided here only for operations on multimap that are not described in one of those tables or for operations where there is additional semantic information.

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair<const Key, T> > >
  class multimap {
  public:
    // types:
    typedef Key                                   key_type;
    typedef T                                     mapped_type;
    typedef pair<const Key,T>                     value_type;
    typedef Compare                               key_compare;
    typedef Allocator                             allocator_type;
    typedef value_type&                           reference;
    typedef const value_type&                     const_reference;
    typedef implementation-defined                iterator;       // see [container.requirements]
    typedef implementation-defined                const_iterator; // see [container.requirements]
    typedef implementation-defined                size_type;      // see [container.requirements]
    typedef implementation-defined                difference_type;// see [container.requirements]
    typedef typename allocator_traits<Allocator>::pointer           pointer;
    typedef typename allocator_traits<Allocator>::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    class value_compare {
    friend class multimap;
    protected:
      Compare comp;
      value_compare(Compare c) : comp(c) { }
    public:
      typedef bool result_type;
      typedef value_type first_argument_type;
      typedef value_type second_argument_type;
      bool operator()(const value_type& x, const value_type& y) const {
        return comp(x.first, y.first);
      }
    };

    // construct/copy/destroy:
    explicit multimap(const Compare& comp = Compare(),
                      const Allocator& = Allocator());
    template <class InputIterator>
      multimap(InputIterator first, InputIterator last,
               const Compare& comp = Compare(),
               const Allocator& = Allocator());
    multimap(const multimap<Key,T,Compare,Allocator>& x);
    multimap(multimap<Key,T,Compare,Allocator>&& x);
    explicit multimap(const Allocator&);
    multimap(const multimap&, const Allocator&);
    multimap(multimap&&, const Allocator&);
    multimap(initializer_list<value_type>,
      const Compare& = Compare(),
      const Allocator& = Allocator());
   ~multimap();
    multimap<Key,T,Compare,Allocator>&
      operator=(const multimap<Key,T,Compare,Allocator>& x);
    multimap<Key,T,Compare,Allocator>&
      operator=(multimap<Key,T,Compare,Allocator>&& x);
    multimap& operator=(initializer_list<value_type>);
    allocator_type get_allocator() const noexcept;

    // iterators:
    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;

    // capacity:
    bool           empty() const noexcept;
    size_type      size() const noexcept;
    size_type      max_size() const noexcept;

    // modifiers:
    template <class... Args> iterator emplace(Args&&... args);
    template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
    iterator insert(const value_type& x);
    template <class P> iterator insert(P&& x);
    iterator insert(const_iterator position, const value_type& x);
    template <class P> iterator insert(const_iterator position, P&& x);
    template <class InputIterator>
      void insert(InputIterator first, InputIterator last);
    void insert(initializer_list<value_type>);

    iterator  erase(const_iterator position);
    size_type erase(const key_type& x);
    iterator  erase(const_iterator first, const_iterator last);
    void swap(multimap<Key,T,Compare,Allocator>&);
    void clear() noexcept;

    // observers:
    key_compare    key_comp() const;
    value_compare  value_comp() const;

    // map operations:
    iterator       find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type      count(const key_type& x) const;

    iterator       lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator       upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;

    pair<iterator,iterator>
      equal_range(const key_type& x);
    pair<const_iterator,const_iterator>
      equal_range(const key_type& x) const;
  };

  template <class Key, class T, class Compare, class Allocator>
    bool operator==(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);

  // specialized algorithms:
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>& x,
              multimap<Key,T,Compare,Allocator>& y);
}

23.4.5.2 multimap constructors [multimap.cons]

explicit multimap(const Compare& comp = Compare(), const Allocator& = Allocator());

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

Complexity: Constant.

template <class InputIterator> multimap(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator());

Requires: If the iterator's dereference operator returns an lvalue or a const rvalue pair<key_type, mapped_type>, then both key_type and mapped_type shall be CopyConstructible.

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.

23.4.5.3 multimap modifiers [multimap.modifiers]

template <class P> iterator insert(P&& x); template <class P> iterator insert(const_iterator position, P&& x);

Requires: P shall be convertible to value_type.

If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g., if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type, mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.

23.4.5.4 multimap operations [multimap.ops]

iterator find(const key_type &x); const_iterator find(const key_type& x) const; iterator lower_bound(const key_type& x); const_iterator lower_bound(const key_type& x) const; pair<iterator, iterator> equal_range(const key_type& x); pair<const_iterator, const_iterator> equal_range(const key_type& x) const;

The find, lower_bound, upper_bound, and equal_range member functions each have two versions, one const and one non-const. In each case the behavior of the two versions is identical except that the const version returns a const_iterator and the non-const version an iterator ([associative.reqmts]).

23.4.5.5 multimap specialized algorithms [multimap.special]

template <class Key, class T, class Compare, class Allocator> void swap(multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y);

Effects:

x.swap(y);