[flat.multimap.overview] # 23 Containers library [[containers]](./#containers) ## 23.6 Container adaptors [[container.adaptors]](container.adaptors#flat.multimap.overview) ### 23.6.9 Class template flat_multimap [[flat.multimap]](flat.multimap#overview) #### 23.6.9.1 Overview [flat.multimap.overview] [1](#1) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18148) A flat_multimap is a container adaptor that provides an associative container interface that supports equivalent keys (i.e., possibly containing multiple copies of the same key value) and provides for fast retrieval of values of another type T based on the keys[.](#1.sentence-1) flat_multimap 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#L18161) A flat_multimap meets all of the requirements for a container ([[container.reqmts]](container.reqmts "23.2.2.2 Container requirements")) and for 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_multimap 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_multimap 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#L18183) A flat_multimap also provides most operations described in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") for equal keys[.](#3.sentence-1) This means that a flat_multimap supports the a_eq operations in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") but not the a_uniq operations[.](#3.sentence-2) For a flat_multimap the key_type is Key and the value_type is pair[.](#3.sentence-3) [4](#4) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18193) Except as otherwise noted, operations on flat_multimap are equivalent to those of flat_map, except that flat_multimap operations do not remove or replace elements with equal keys[.](#4.sentence-1) [*Example [1](#example-1)*: flat_multimap constructors and emplace do not erase non-unique elements after sorting them[.](#4.sentence-2) — *end example*] [5](#5) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18203) A flat_multimap 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#L18215) If any member function in [[flat.multimap.defn]](flat.multimap.defn "23.6.9.2 Definition") exits via an exception, the invariants are restored[.](#6.sentence-1) [*Note [2](#note-2)*: This can result in the flat_multimap being emptied[.](#6.sentence-2) — *end note*] [7](#7) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18222) Any type C that meets the sequence container requirements ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers")) can be used to instantiate flat_multimap, 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 is not a sequence container[.](#7.sentence-3) — *end note*] [8](#8) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18236) 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#L18241) The effect of calling a constructor that takes both key_container_type andmapped_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#L18247) The effect of calling a constructor or member function that takes a sorted_equivalent_t argument with a container, containers, or range that are not sorted with respect to key_comp() is undefined[.](#10.sentence-1) [11](#11) [#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18253) The types iterator and const_iterator meet the constexpr iterator requirements ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))[.](#11.sentence-1)