23 Containers library [containers]

23.4 Associative containers [associative]

23.4.4 Class template map [map]

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.