23 Containers library [containers]

23.4 Associative containers [associative]

23.4.4 Class template map [map]

23.4.4.1 Class template map overview [map.overview]

A map is an associative container that supports unique keys (contains at most one of each key value) and provides for fast retrieval of values of another type T based on the keys. The map class supports bidirectional iterators.

A map satisfies all of the requirements of a container, of a reversible container ([container.requirements]), of an associative container ([associative.reqmts]), and of an allocator-aware container (Table [tab:containers.allocatoraware]). A map also provides most operations described in ([associative.reqmts]) for unique keys. This means that a map supports the a_uniq operations in ([associative.reqmts]) but not the a_eq operations. For a map<Key,T> the key_type is Key and the value_type is pair<const Key,T>. Descriptions are provided here only for operations on map 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 map {
  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 map;
    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);
      }
    };

    // [map.cons], construct/copy/destroy:
    explicit map(const Compare& comp = Compare(),
                 const Allocator& = Allocator());
    template <class InputIterator>
      map(InputIterator first, InputIterator last,
          const Compare& comp = Compare(), const Allocator& = Allocator());
    map(const map<Key,T,Compare,Allocator>& x);
    map(map<Key,T,Compare,Allocator>&& x);
    explicit map(const Allocator&);
    map(const map&, const Allocator&);
    map(map&&, const Allocator&);
    map(initializer_list<value_type>,
      const Compare& = Compare(),
      const Allocator& = Allocator());
   ~map();
    map<Key,T,Compare,Allocator>&
      operator=(const map<Key,T,Compare,Allocator>& x);
    map<Key,T,Compare,Allocator>&
      operator=(map<Key,T,Compare,Allocator>&& x);
    map& 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;

    // [map.access], element access:
    T& operator[](const key_type& x);
    T& operator[](key_type&& x);
    T&       at(const key_type& x);
    const T& at(const key_type& x) const;

    // [map.modifiers], modifiers:
    template <class... Args> pair<iterator, bool> emplace(Args&&... args);
    template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
    pair<iterator, bool> insert(const value_type& x);
    template <class P> pair<iterator, bool> insert(P&& x);
    iterator insert(const_iterator position, const value_type& x);
    template <class P>
      iterator insert(const_iterator position, P&&);
    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(map<Key,T,Compare,Allocator>&);
    void clear() noexcept;

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

    // [map.ops], 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 map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);

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

23.4.4.2 map constructors, copy, and assignment [map.cons]

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

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

Complexity: Constant.

template <class InputIterator> map(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 map 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.4.3 map element access [map.access]

T& operator[](const key_type& x);

Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.

Requires: key_type shall be CopyConstructible and mapped_type shall be DefaultConstructible.

Returns: A reference to the mapped_type corresponding to x in *this.

Complexity: logarithmic.

T& operator[](key_type&& x);

Effects: If there is no key equivalent to x in the map, inserts value_type(std::move(x), T()) into the map.

Requires: mapped_type shall be DefaultConstructible.

Returns: A reference to the mapped_type corresponding to x in *this.

Complexity: logarithmic.

T& at(const key_type& x); const T& at(const key_type& x) const;

Returns: A reference to the mapped_type corresponding to x in *this.

Throws: An exception object of type out_of_range if no such element is present.

Complexity: logarithmic.

23.4.4.4 map modifiers [map.modifiers]

template <class P> pair<iterator, bool> insert(P&& x); template <class P> pair<iterator, bool> insert(const_iterator position, P&& x); template <class InputIterator> void insert(InputIterator first, InputIterator last);

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.4.5 map operations [map.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; 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;

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

23.4.4.6 map specialized algorithms [map.special]

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

Effects:

x.swap(y);