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);
}
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.
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.
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]).
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);