[flat.map.overview]

# 23 Containers library [[containers]](./#containers)

## 23.6 Container adaptors [[container.adaptors]](container.adaptors#flat.map.overview)

### 23.6.8 Class template flat_map [[flat.map]](flat.map#overview)

#### 23.6.8.1 Overview [flat.map.overview]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16954)

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[.](#1.sentence-1)

flat_map supports iterators
that meet the *Cpp17InputIterator* requirements and
model the[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") concept ([[iterator.concept.random.access]](iterator.concept.random.access "24.3.4.13 Concept random_­access_­iterator"))[.](#1.sentence-2)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16967)

A flat_map meets all of the requirements
of a container ([[container.reqmts]](container.reqmts "23.2.2.2 Container requirements")) and
of a reversible container ([[container.rev.reqmts]](container.rev.reqmts "23.2.2.3 Reversible container requirements")),
plus the optional container requirements ([[container.opt.reqmts]](container.opt.reqmts "23.2.2.4 Optional container requirements"))[.](#2.sentence-1)

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

- [(2.1)](#2.1)

it does not meet the requirements related to node handles ([[container.node]](container.node "23.2.5 Node handles")),

- [(2.2)](#2.2)

it does not meet the requirements related to iterator invalidation, and

- [(2.3)](#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[.](#2.sentence-2)

[*Note [1](#note-1)*:

A flat_map does not meet the additional requirements of
an allocator-aware container ([[container.alloc.reqmts]](container.alloc.reqmts "23.2.2.5 Allocator-aware containers"))[.](#2.sentence-3)

â *end note*]

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16990)

A flat_map also provides most operations
described in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") for unique keys[.](#3.sentence-1)

This means that a flat_map supports
the a_uniq operations in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") but not the a_eq operations[.](#3.sentence-2)

For a flat_map<Key, T> the key_type is Key and
the value_type is pair<Key, T>[.](#3.sentence-3)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17000)

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[.](#4.sentence-1)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17005)

A flat_map maintains the following invariants:

- [(5.1)](#5.1)

it contains the same number of keys and values;

- [(5.2)](#5.2)

the keys are sorted with respect to the comparison object; and

- [(5.3)](#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[.](#5.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17018)

If any member function in [[flat.map.defn]](flat.map.defn "23.6.8.2 Definition") exits via an exception
the invariants are restored[.](#6.sentence-1)

[*Note [2](#note-2)*:

This can result in the flat_map being emptied[.](#6.sentence-2)

â *end note*]

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17025)

Any type C that meets the sequence container requirements ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers"))
can be used to instantiate flat_map,
as long asC​::​iterator meets the *Cpp17RandomAccessIterator* requirements and
invocations of
member functions C​::​size and C​::​max_size do not exit via an exception[.](#7.sentence-1)

In particular, vector ([[vector]](vector "23.3.13 Class template vector")) and deque ([[deque]](deque "23.3.5 Class template deque"))
can be used[.](#7.sentence-2)

[*Note [3](#note-3)*:

vector<bool> is not a sequence container[.](#7.sentence-3)

â *end note*]

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17039)

The program is ill-formed ifKey is not the same type as KeyContainer​::​value_type orT is not the same type as MappedContainer​::​value_type[.](#8.sentence-1)

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17044)

The effect of calling a constructor
that takes
both key_container_type and mapped_container_type arguments with
containers of different sizes is undefined[.](#9.sentence-1)

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17050)

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[.](#10.sentence-1)

[11](#11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17058)

The types iterator and const_iterator meet
the constexpr iterator requirements ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))[.](#11.sentence-1)
