24 Containers library [containers]

A flat_map is a container adaptor that provides an associative container interface that supports unique keys (i.e., contains at most one of each key value) and provides for fast retrieval of values of another type T based on the keys.

flat_map supports iterators that meet the Cpp17InputIterator requirements and model the random_access_iterator concept ([iterator.concept.random.access]).

A flat_map meets all of the requirements of a container ([container.reqmts]) and of a reversible container ([container.rev.reqmts]), plus the optional container requirements ([container.opt.reqmts]).

flat_map meets the requirements of an associative container ([associative.reqmts]), except that:

• (2.1)
  it does not meet the requirements related to node handles ([container.node]),
• (2.2)
  it does not meet the requirements related to iterator invalidation, and
• (2.3)
  the time complexity of the operations that insert or erase a single element from the map is linear, including the ones that take an insertion position iterator.

A flat_map also provides most operations described in [associative.reqmts] for unique keys.

This means that a flat_map supports the a_uniq operations in [associative.reqmts] but not the a_eq operations.

For a flat_map<Key, T> the key_type is Key and the value_type is pair<Key, T>.

Descriptions are provided here only for operations on flat_map that are not described in one of those sets of requirements or for operations where there is additional semantic information.

A flat_map maintains the following invariants:

• (5.1)
  it contains the same number of keys and values;
• (5.2)
  the keys are sorted with respect to the comparison object; and
• (5.3)
  the value at offset off within the value container is the value associated with the key at offset off within the key container.

If any member function in [flat.map.defn] exits via an exception the invariants are restored.

Any type C that meets the sequence container requirements ([sequence.reqmts]) can be used to instantiate flat_map, as long as C​::​iterator meets the Cpp17RandomAccessIterator requirements and invocations of member functions C​::​size and C​::​max_size do not exit via an exception.

In particular, vector ([vector]) and deque ([deque]) can be used.

The program is ill-formed if Key is not the same type as KeyContainer​::​value_type or T is not the same type as MappedContainer​::​value_type.

The effect of calling a constructor that takes both key_container_type and mapped_container_type arguments with containers of different sizes is undefined.

The effect of calling a constructor or member function that takes a sorted_unique_t argument with a container, containers, or range that is not sorted with respect to key_comp(), or that contains equal elements, is undefined.