1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_FLAT_MAP
11#define _LIBCPP_FLAT_MAP
12
13/*
14 Header <flat_map> synopsis
15
16#include <compare> // see [compare.syn]
17#include <initializer_list> // see [initializer.list.syn]
18
19namespace std {
20 struct sorted_unique_t { explicit sorted_unique_t() = default; };
21 inline constexpr sorted_unique_t sorted_unique{};
22
23 // [flat.map], class template flat_map
24 template<class Key, class T, class Compare = less<Key>,
25 class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
26 class flat_map {
27 public:
28 // types
29 using key_type = Key;
30 using mapped_type = T;
31 using value_type = pair<key_type, mapped_type>;
32 using key_compare = Compare;
33 using reference = pair<const key_type&, mapped_type&>;
34 using const_reference = pair<const key_type&, const mapped_type&>;
35 using size_type = size_t;
36 using difference_type = ptrdiff_t;
37 using iterator = implementation-defined; // see [container.requirements]
38 using const_iterator = implementation-defined; // see [container.requirements]
39 using reverse_iterator = std::reverse_iterator<iterator>;
40 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
41 using key_container_type = KeyContainer;
42 using mapped_container_type = MappedContainer;
43
44 class value_compare {
45 private:
46 key_compare comp; // exposition only
47 constexpr value_compare(key_compare c) : comp(c) { } // exposition only
48
49 public:
50 constexpr bool operator()(const_reference x, const_reference y) const {
51 return comp(x.first, y.first);
52 }
53 };
54
55 struct containers {
56 key_container_type keys;
57 mapped_container_type values;
58 };
59
60 // [flat.map.cons], constructors
61 constexpr flat_map() : flat_map(key_compare()) { }
62
63 constexpr flat_map(const flat_map&);
64 constexpr flat_map(flat_map&&);
65 constexpr flat_map& operator=(const flat_map&);
66 constexpr flat_map& operator=(flat_map&&);
67
68 constexpr explicit flat_map(const key_compare& comp)
69 : c(), compare(comp) { }
70
71 constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
72 const key_compare& comp = key_compare());
73
74 constexpr flat_map(sorted_unique_t, key_container_type key_cont,
75 mapped_container_type mapped_cont,
76 const key_compare& comp = key_compare());
77
78 template<class InputIterator>
79 constexpr flat_map(InputIterator first, InputIterator last,
80 const key_compare& comp = key_compare())
81 : c(), compare(comp) { insert(first, last); }
82
83 template<class InputIterator>
84 constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
85 const key_compare& comp = key_compare())
86 : c(), compare(comp) { insert(sorted_unique, first, last); }
87
88 template<container-compatible-range<value_type> R>
89 constexpr flat_map(from_range_t, R&& rg)
90 : flat_map(from_range, std::forward<R>(rg), key_compare()) { }
91 template<container-compatible-range<value_type> R>
92 constexpr flat_map(from_range_t, R&& rg, const key_compare& comp)
93 : flat_map(comp) { insert_range(std::forward<R>(rg)); }
94
95 constexpr flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare())
96 : flat_map(il.begin(), il.end(), comp) { }
97
98 constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
99 const key_compare& comp = key_compare())
100 : flat_map(sorted_unique, il.begin(), il.end(), comp) { }
101
102 // [flat.map.cons.alloc], constructors with allocators
103
104 template<class Alloc>
105 constexpr explicit flat_map(const Alloc& a);
106 template<class Alloc>
107 constexpr flat_map(const key_compare& comp, const Alloc& a);
108 template<class Alloc>
109 constexpr flat_map(const key_container_type& key_cont,
110 const mapped_container_type& mapped_cont,
111 const Alloc& a);
112 template<class Alloc>
113 constexpr flat_map(const key_container_type& key_cont,
114 const mapped_container_type& mapped_cont,
115 const key_compare& comp, const Alloc& a);
116 template<class Alloc>
117 constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
118 const mapped_container_type& mapped_cont, const Alloc& a);
119 template<class Alloc>
120 constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
121 const mapped_container_type& mapped_cont, const key_compare& comp,
122 const Alloc& a);
123 template<class Alloc>
124 constexpr flat_map(const flat_map&, const Alloc& a);
125 template<class Alloc>
126 constexpr flat_map(flat_map&&, const Alloc& a);
127 template<class InputIterator, class Alloc>
128 constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a);
129 template<class InputIterator, class Alloc>
130 constexpr flat_map(InputIterator first, InputIterator last,
131 const key_compare& comp, const Alloc& a);
132 template<class InputIterator, class Alloc>
133 constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
134 const Alloc& a);
135 template<class InputIterator, class Alloc>
136 constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
137 const key_compare& comp, const Alloc& a);
138 template<container-compatible-range<value_type> R, class Alloc>
139 constexpr flat_map(from_range_t, R&& rg, const Alloc& a);
140 template<container-compatible-range<value_type> R, class Alloc>
141 constexpr flat_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
142 template<class Alloc>
143 constexpr flat_map(initializer_list<value_type> il, const Alloc& a);
144 template<class Alloc>
145 constexpr flat_map(initializer_list<value_type> il, const key_compare& comp,
146 const Alloc& a);
147 template<class Alloc>
148 constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
149 template<class Alloc>
150 constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
151 const key_compare& comp, const Alloc& a);
152
153 constexpr flat_map& operator=(initializer_list<value_type>);
154
155 // iterators
156 constexpr iterator begin() noexcept;
157 constexpr const_iterator begin() const noexcept;
158 constexpr iterator end() noexcept;
159 constexpr const_iterator end() const noexcept;
160
161 constexpr reverse_iterator rbegin() noexcept;
162 constexpr const_reverse_iterator rbegin() const noexcept;
163 constexpr reverse_iterator rend() noexcept;
164 constexpr const_reverse_iterator rend() const noexcept;
165
166 constexpr const_iterator cbegin() const noexcept;
167 constexpr const_iterator cend() const noexcept;
168 constexpr const_reverse_iterator crbegin() const noexcept;
169 constexpr const_reverse_iterator crend() const noexcept;
170
171 // [flat.map.capacity], capacity
172 constexpr bool empty() const noexcept;
173 constexpr size_type size() const noexcept;
174 constexpr size_type max_size() const noexcept;
175
176 // [flat.map.access], element access
177 constexpr mapped_type& operator[](const key_type& x);
178 constexpr mapped_type& operator[](key_type&& x);
179 template<class K> constexpr mapped_type& operator[](K&& x);
180 constexpr mapped_type& at(const key_type& x);
181 constexpr const mapped_type& at(const key_type& x) const;
182 template<class K> constexpr mapped_type& at(const K& x);
183 template<class K> constexpr const mapped_type& at(const K& x) const;
184
185 // [flat.map.modifiers], modifiers
186 template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
187 template<class... Args>
188 constexpr iterator emplace_hint(const_iterator position, Args&&... args);
189
190 constexpr pair<iterator, bool> insert(const value_type& x)
191 { return emplace(x); }
192 constexpr pair<iterator, bool> insert(value_type&& x)
193 { return emplace(std::move(x)); }
194 constexpr iterator insert(const_iterator position, const value_type& x)
195 { return emplace_hint(position, x); }
196 constexpr iterator insert(const_iterator position, value_type&& x)
197 { return emplace_hint(position, std::move(x)); }
198
199 template<class P> constexpr pair<iterator, bool> insert(P&& x);
200 template<class P>
201 constexpr iterator insert(const_iterator position, P&&);
202 template<class InputIterator>
203 constexpr void insert(InputIterator first, InputIterator last);
204 template<class InputIterator>
205 constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
206 template<container-compatible-range<value_type> R>
207 constexpr void insert_range(R&& rg);
208 template<container-compatible-range<value_type> R>
209 constexpr void insert_range(sorted_unique_t, R&& rg);
210
211 constexpr void insert(initializer_list<value_type> il)
212 { insert(il.begin(), il.end()); }
213 constexpr void insert(sorted_unique_t, initializer_list<value_type> il)
214 { insert(sorted_unique, il.begin(), il.end()); }
215
216 constexpr containers extract() &&;
217 constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
218
219 template<class... Args>
220 constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
221 template<class... Args>
222 constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
223 template<class K, class... Args>
224 constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
225 template<class... Args>
226 constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
227 template<class... Args>
228 constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
229 template<class K, class... Args>
230 constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
231 template<class M>
232 constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
233 template<class M>
234 constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
235 template<class K, class M>
236 constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
237 template<class M>
238 constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
239 template<class M>
240 constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
241 template<class K, class M>
242 constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
243
244 constexpr iterator erase(iterator position);
245 constexpr iterator erase(const_iterator position);
246 constexpr size_type erase(const key_type& x);
247 template<class K> constexpr size_type erase(K&& x);
248 constexpr iterator erase(const_iterator first, const_iterator last);
249
250 constexpr void swap(flat_map& y) noexcept(see below);
251 constexpr void clear() noexcept;
252
253 // observers
254 constexpr key_compare key_comp() const;
255 constexpr value_compare value_comp() const;
256
257 constexpr const key_container_type& keys() const noexcept { return c.keys; }
258 constexpr const mapped_container_type& values() const noexcept { return c.values; }
259
260 // map operations
261 constexpr iterator find(const key_type& x);
262 constexpr const_iterator find(const key_type& x) const;
263 template<class K> constexpr iterator find(const K& x);
264 template<class K> constexpr const_iterator find(const K& x) const;
265
266 constexpr size_type count(const key_type& x) const;
267 template<class K> constexpr size_type count(const K& x) const;
268
269 constexpr bool contains(const key_type& x) const;
270 template<class K> constexpr bool contains(const K& x) const;
271
272 constexpr iterator lower_bound(const key_type& x);
273 constexpr const_iterator lower_bound(const key_type& x) const;
274 template<class K> constexpr iterator lower_bound(const K& x);
275 template<class K> constexpr const_iterator lower_bound(const K& x) const;
276
277 constexpr iterator upper_bound(const key_type& x);
278 constexpr const_iterator upper_bound(const key_type& x) const;
279 template<class K> constexpr iterator upper_bound(const K& x);
280 template<class K> constexpr const_iterator upper_bound(const K& x) const;
281
282 constexpr pair<iterator, iterator> equal_range(const key_type& x);
283 constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
284 template<class K> constexpr pair<iterator, iterator> equal_range(const K& x);
285 template<class K>
286 constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
287
288 friend constexpr bool operator==(const flat_map& x, const flat_map& y);
289
290 friend constexpr synth-three-way-result<value_type>
291 operator<=>(const flat_map& x, const flat_map& y);
292
293 friend constexpr void swap(flat_map& x, flat_map& y) noexcept(noexcept(x.swap(y)))
294 { x.swap(y); }
295
296 private:
297 containers c; // exposition only
298 key_compare compare; // exposition only
299
300 struct key-equiv { // exposition only
301 constexpr key-equiv(key_compare c) : comp(c) { }
302 constexpr bool operator()(const_reference x, const_reference y) const {
303 return !comp(x.first, y.first) && !comp(y.first, x.first);
304 }
305 key_compare comp;
306 };
307 };
308
309 template<class KeyContainer, class MappedContainer,
310 class Compare = less<typename KeyContainer::value_type>>
311 flat_map(KeyContainer, MappedContainer, Compare = Compare())
312 -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
313 Compare, KeyContainer, MappedContainer>;
314
315 template<class KeyContainer, class MappedContainer, class Allocator>
316 flat_map(KeyContainer, MappedContainer, Allocator)
317 -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
318 less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
319 template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
320 flat_map(KeyContainer, MappedContainer, Compare, Allocator)
321 -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
322 Compare, KeyContainer, MappedContainer>;
323
324 template<class KeyContainer, class MappedContainer,
325 class Compare = less<typename KeyContainer::value_type>>
326 flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare = Compare())
327 -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
328 Compare, KeyContainer, MappedContainer>;
329
330 template<class KeyContainer, class MappedContainer, class Allocator>
331 flat_map(sorted_unique_t, KeyContainer, MappedContainer, Allocator)
332 -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
333 less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
334 template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
335 flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare, Allocator)
336 -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
337 Compare, KeyContainer, MappedContainer>;
338
339 template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
340 flat_map(InputIterator, InputIterator, Compare = Compare())
341 -> flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
342
343 template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
344 flat_map(sorted_unique_t, InputIterator, InputIterator, Compare = Compare())
345 -> flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
346
347 template<ranges::input_range R, class Compare = less<range-key-type<R>>,
348 class Allocator = allocator<byte>>
349 flat_map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
350 -> flat_map<range-key-type<R>, range-mapped-type<R>, Compare,
351 vector<range-key-type<R>, alloc-rebind<Allocator, range-key-type<R>>>,
352 vector<range-mapped-type<R>, alloc-rebind<Allocator, range-mapped-type<R>>>>;
353
354 template<ranges::input_range R, class Allocator>
355 flat_map(from_range_t, R&&, Allocator)
356 -> flat_map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>,
357 vector<range-key-type<R>, alloc-rebind<Allocator, range-key-type<R>>>,
358 vector<range-mapped-type<R>, alloc-rebind<Allocator, range-mapped-type<R>>>>;
359
360 template<class Key, class T, class Compare = less<Key>>
361 flat_map(initializer_list<pair<Key, T>>, Compare = Compare())
362 -> flat_map<Key, T, Compare>;
363
364 template<class Key, class T, class Compare = less<Key>>
365 flat_map(sorted_unique_t, initializer_list<pair<Key, T>>, Compare = Compare())
366 -> flat_map<Key, T, Compare>;
367
368 template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
369 class Allocator>
370 struct uses_allocator<flat_map<Key, T, Compare, KeyContainer, MappedContainer>, Allocator>
371 : bool_constant<uses_allocator_v<KeyContainer, Allocator> &&
372 uses_allocator_v<MappedContainer, Allocator>> { };
373
374 // [flat.map.erasure], erasure for flat_map
375 template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
376 class Predicate>
377 typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
378 erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
379
380 struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };
381 inline constexpr sorted_equivalent_t sorted_equivalent{};
382
383 // [flat.multimap], class template flat_multimap
384 template<class Key, class T, class Compare = less<Key>,
385 class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
386 class flat_multimap {
387 public:
388 // types
389 using key_type = Key;
390 using mapped_type = T;
391 using value_type = pair<key_type, mapped_type>;
392 using key_compare = Compare;
393 using reference = pair<const key_type&, mapped_type&>;
394 using const_reference = pair<const key_type&, const mapped_type&>;
395 using size_type = size_t;
396 using difference_type = ptrdiff_t;
397 using iterator = implementation-defined; // see [container.requirements]
398 using const_iterator = implementation-defined; // see [container.requirements]
399 using reverse_iterator = std::reverse_iterator<iterator>;
400 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
401 using key_container_type = KeyContainer;
402 using mapped_container_type = MappedContainer;
403
404 class value_compare {
405 private:
406 key_compare comp; // exposition only
407 constexpr value_compare(key_compare c) : comp(c) { } // exposition only
408
409 public:
410 constexpr bool operator()(const_reference x, const_reference y) const {
411 return comp(x.first, y.first);
412 }
413 };
414
415 struct containers {
416 key_container_type keys;
417 mapped_container_type values;
418 };
419
420 // [flat.multimap.cons], constructors
421 constexpr flat_multimap() : flat_multimap(key_compare()) { }
422
423 constexpr flat_multimap(const flat_multimap&);
424 constexpr flat_multimap(flat_multimap&&);
425 constexpr flat_multimap& operator=(const flat_multimap&);
426 constexpr flat_multimap& operator=(flat_multimap&&);
427
428 constexpr explicit flat_multimap(const key_compare& comp)
429 : c(), compare(comp) { }
430
431 constexpr flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
432 const key_compare& comp = key_compare());
433
434 constexpr flat_multimap(sorted_equivalent_t,
435 key_container_type key_cont, mapped_container_type mapped_cont,
436 const key_compare& comp = key_compare());
437
438 template<class InputIterator>
439 constexpr flat_multimap(InputIterator first, InputIterator last,
440 const key_compare& comp = key_compare())
441 : c(), compare(comp)
442 { insert(first, last); }
443
444 template<class InputIterator>
445 constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
446 const key_compare& comp = key_compare())
447 : c(), compare(comp) { insert(sorted_equivalent, first, last); }
448
449 template<container-compatible-range<value_type> R>
450 constexpr flat_multimap(from_range_t, R&& rg)
451 : flat_multimap(from_range, std::forward<R>(rg), key_compare()) { }
452 template<container-compatible-range<value_type> R>
453 constexpr flat_multimap(from_range_t, R&& rg, const key_compare& comp)
454 : flat_multimap(comp) { insert_range(std::forward<R>(rg)); }
455
456 constexpr flat_multimap(initializer_list<value_type> il,
457 const key_compare& comp = key_compare())
458 : flat_multimap(il.begin(), il.end(), comp) { }
459
460 constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
461 const key_compare& comp = key_compare())
462 : flat_multimap(sorted_equivalent, il.begin(), il.end(), comp) { }
463
464 // [flat.multimap.cons.alloc], constructors with allocators
465
466 template<class Alloc>
467 constexpr explicit flat_multimap(const Alloc& a);
468 template<class Alloc>
469 constexpr flat_multimap(const key_compare& comp, const Alloc& a);
470 template<class Alloc>
471 constexpr flat_multimap(const key_container_type& key_cont,
472 const mapped_container_type& mapped_cont, const Alloc& a);
473 template<class Alloc>
474 constexpr flat_multimap(const key_container_type& key_cont,
475 const mapped_container_type& mapped_cont,
476 const key_compare& comp, const Alloc& a);
477 template<class Alloc>
478 constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
479 const mapped_container_type& mapped_cont, const Alloc& a);
480 template<class Alloc>
481 constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
482 const mapped_container_type& mapped_cont,
483 const key_compare& comp, const Alloc& a);
484 template<class Alloc>
485 constexpr flat_multimap(const flat_multimap&, const Alloc& a);
486 template<class Alloc>
487 constexpr flat_multimap(flat_multimap&&, const Alloc& a);
488 template<class InputIterator, class Alloc>
489 constexpr flat_multimap(InputIterator first, InputIterator last, const Alloc& a);
490 template<class InputIterator, class Alloc>
491 constexpr flat_multimap(InputIterator first, InputIterator last,
492 const key_compare& comp, const Alloc& a);
493 template<class InputIterator, class Alloc>
494 constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
495 const Alloc& a);
496 template<class InputIterator, class Alloc>
497 constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
498 const key_compare& comp, const Alloc& a);
499 template<container-compatible-range<value_type> R, class Alloc>
500 constexpr flat_multimap(from_range_t, R&& rg, const Alloc& a);
501 template<container-compatible-range<value_type> R, class Alloc>
502 constexpr flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
503 template<class Alloc>
504 constexpr flat_multimap(initializer_list<value_type> il, const Alloc& a);
505 template<class Alloc>
506 constexpr flat_multimap(initializer_list<value_type> il, const key_compare& comp,
507 const Alloc& a);
508 template<class Alloc>
509 constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
510 const Alloc& a);
511 template<class Alloc>
512 constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
513 const key_compare& comp, const Alloc& a);
514
515 flat_multimap& operator=(initializer_list<value_type>);
516
517 // iterators
518 constexpr iterator begin() noexcept;
519 constexpr const_iterator begin() const noexcept;
520 constexpr iterator end() noexcept;
521 constexpr const_iterator end() const noexcept;
522
523 constexpr reverse_iterator rbegin() noexcept;
524 constexpr const_reverse_iterator rbegin() const noexcept;
525 constexpr reverse_iterator rend() noexcept;
526 constexpr const_reverse_iterator rend() const noexcept;
527
528 constexpr const_iterator cbegin() const noexcept;
529 constexpr const_iterator cend() const noexcept;
530 constexpr const_reverse_iterator crbegin() const noexcept;
531 constexpr const_reverse_iterator crend() const noexcept;
532
533 // capacity
534 constexpr bool empty() const noexcept;
535 constexpr size_type size() const noexcept;
536 constexpr size_type max_size() const noexcept;
537
538 // modifiers
539 template<class... Args> constexpr iterator emplace(Args&&... args);
540 template<class... Args>
541 constexpr iterator emplace_hint(const_iterator position, Args&&... args);
542
543 constexpr iterator insert(const value_type& x)
544 { return emplace(x); }
545 constexpr iterator insert(value_type&& x)
546 { return emplace(std::move(x)); }
547 constexpr iterator insert(const_iterator position, const value_type& x)
548 { return emplace_hint(position, x); }
549 constexpr iterator insert(const_iterator position, value_type&& x)
550 { return emplace_hint(position, std::move(x)); }
551
552 template<class P> constexpr iterator insert(P&& x);
553 template<class P>
554 constexpr iterator insert(const_iterator position, P&&);
555 template<class InputIterator>
556 constexpr void insert(InputIterator first, InputIterator last);
557 template<class InputIterator>
558 constexpr void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
559 template<container-compatible-range<value_type> R>
560 constexpr void insert_range(R&& rg);
561 template<container-compatible-range<value_type> R>
562 constexpr void insert_range(sorted_equivalent_t, R&& rg);
563
564 constexpr void insert(initializer_list<value_type> il)
565 { insert(il.begin(), il.end()); }
566 constexpr void insert(sorted_equivalent_t, initializer_list<value_type> il)
567 { insert(sorted_equivalent, il.begin(), il.end()); }
568
569 constexpr containers extract() &&;
570 constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
571
572 constexpr iterator erase(iterator position);
573 constexpr iterator erase(const_iterator position);
574 constexpr size_type erase(const key_type& x);
575 template<class K> constexpr size_type erase(K&& x);
576 constexpr iterator erase(const_iterator first, const_iterator last);
577
578 constexpr void swap(flat_multimap&)
579 noexcept(is_nothrow_swappable_v<key_container_type> &&
580 is_nothrow_swappable_v<mapped_container_type> &&
581 is_nothrow_swappable_v<key_compare>);
582 constexpr void clear() noexcept;
583
584 // observers
585 constexpr key_compare key_comp() const;
586 constexpr value_compare value_comp() const;
587
588 constexpr const key_container_type& keys() const noexcept { return c.keys; }
589 constexpr const mapped_container_type& values() const noexcept { return c.values; }
590
591 // map operations
592 constexpr iterator find(const key_type& x);
593 constexpr const_iterator find(const key_type& x) const;
594 template<class K> constexpr iterator find(const K& x);
595 template<class K> constexpr const_iterator find(const K& x) const;
596
597 constexpr size_type count(const key_type& x) const;
598 template<class K> constexpr size_type count(const K& x) const;
599
600 constexpr bool contains(const key_type& x) const;
601 template<class K> constexpr bool contains(const K& x) const;
602
603 constexpr iterator lower_bound(const key_type& x);
604 constexpr const_iterator lower_bound(const key_type& x) const;
605 template<class K> constexpr iterator lower_bound(const K& x);
606 template<class K> constexpr const_iterator lower_bound(const K& x) const;
607
608 constexpr iterator upper_bound(const key_type& x);
609 constexpr const_iterator upper_bound(const key_type& x) const;
610 template<class K> constexpr iterator upper_bound(const K& x);
611 template<class K> constexpr const_iterator upper_bound(const K& x) const;
612
613 constexpr pair<iterator, iterator> equal_range(const key_type& x);
614 constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
615 template<class K>
616 constexpr pair<iterator, iterator> equal_range(const K& x);
617 template<class K>
618 constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
619
620 friend constexpr bool operator==(const flat_multimap& x, const flat_multimap& y);
621
622 friend constexpr synth-three-way-result<value_type>
623 operator<=>(const flat_multimap& x, const flat_multimap& y);
624
625 friend constexpr void swap(flat_multimap& x, flat_multimap& y)
626 noexcept(noexcept(x.swap(y)))
627 { x.swap(y); }
628
629 private:
630 containers c; // exposition only
631 key_compare compare; // exposition only
632 };
633
634 template<class KeyContainer, class MappedContainer,
635 class Compare = less<typename KeyContainer::value_type>>
636 flat_multimap(KeyContainer, MappedContainer, Compare = Compare())
637 -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
638 Compare, KeyContainer, MappedContainer>;
639
640 template<class KeyContainer, class MappedContainer, class Allocator>
641 flat_multimap(KeyContainer, MappedContainer, Allocator)
642 -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
643 less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
644 template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
645 flat_multimap(KeyContainer, MappedContainer, Compare, Allocator)
646 -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
647 Compare, KeyContainer, MappedContainer>;
648
649 template<class KeyContainer, class MappedContainer,
650 class Compare = less<typename KeyContainer::value_type>>
651 flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare = Compare())
652 -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
653 Compare, KeyContainer, MappedContainer>;
654
655 template<class KeyContainer, class MappedContainer, class Allocator>
656 flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Allocator)
657 -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
658 less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
659 template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
660 flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare, Allocator)
661 -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
662 Compare, KeyContainer, MappedContainer>;
663
664 template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
665 flat_multimap(InputIterator, InputIterator, Compare = Compare())
666 -> flat_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
667
668 template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
669 flat_multimap(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())
670 -> flat_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
671
672 template<ranges::input_range R, class Compare = less<range-key-type<R>>,
673 class Allocator = allocator<byte>>
674 flat_multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
675 -> flat_multimap<range-key-type<R>, range-mapped-type<R>, Compare,
676 vector<range-key-type<R>,
677 alloc-rebind<Allocator, range-key-type<R>>>,
678 vector<range-mapped-type<R>,
679 alloc-rebind<Allocator, range-mapped-type<R>>>>;
680
681 template<ranges::input_range R, class Allocator>
682 flat_multimap(from_range_t, R&&, Allocator)
683 -> flat_multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>,
684 vector<range-key-type<R>,
685 alloc-rebind<Allocator, range-key-type<R>>>,
686 vector<range-mapped-type<R>,
687 alloc-rebind<Allocator, range-mapped-type<R>>>>;
688
689 template<class Key, class T, class Compare = less<Key>>
690 flat_multimap(initializer_list<pair<Key, T>>, Compare = Compare())
691 -> flat_multimap<Key, T, Compare>;
692
693 template<class Key, class T, class Compare = less<Key>>
694 flat_multimap(sorted_equivalent_t, initializer_list<pair<Key, T>>, Compare = Compare())
695 -> flat_multimap<Key, T, Compare>;
696
697 template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
698 class Allocator>
699 struct uses_allocator<flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>,
700 Allocator>
701 : bool_constant<uses_allocator_v<KeyContainer, Allocator> &&
702 uses_allocator_v<MappedContainer, Allocator>> { };
703
704 // [flat.multimap.erasure], erasure for flat_multimap
705 template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
706 class Predicate>
707 typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
708 erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
709*/
710
711#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
712# include <__cxx03/__config>
713#else
714# include <__config>
715
716# if _LIBCPP_STD_VER >= 23
717# include <__flat_map/flat_map.h>
718# include <__flat_map/flat_multimap.h>
719# include <__flat_map/sorted_equivalent.h>
720# include <__flat_map/sorted_unique.h>
721# endif
722
723// for feature-test macros
724# include <version>
725
726// standard required includes
727
728// [iterator.range]
729# include <__iterator/access.h>
730# include <__iterator/data.h>
731# include <__iterator/empty.h>
732# include <__iterator/reverse_access.h>
733# include <__iterator/size.h>
734
735// [flat.map.syn]
736# include <compare>
737# include <initializer_list>
738
739# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
740# pragma GCC system_header
741# endif
742#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
743
744#endif // _LIBCPP_FLAT_MAP