Coverage Report

Created: 2024-09-23 06:29

/src/abseil-cpp/absl/container/flat_hash_map.h
Line
Count
Source (jump to first uncovered line)
1
// Copyright 2018 The Abseil Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      https://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14
//
15
// -----------------------------------------------------------------------------
16
// File: flat_hash_map.h
17
// -----------------------------------------------------------------------------
18
//
19
// An `absl::flat_hash_map<K, V>` is an unordered associative container of
20
// unique keys and associated values designed to be a more efficient replacement
21
// for `std::unordered_map`. Like `unordered_map`, search, insertion, and
22
// deletion of map elements can be done as an `O(1)` operation. However,
23
// `flat_hash_map` (and other unordered associative containers known as the
24
// collection of Abseil "Swiss tables") contain other optimizations that result
25
// in both memory and computation advantages.
26
//
27
// In most cases, your default choice for a hash map should be a map of type
28
// `flat_hash_map`.
29
//
30
// `flat_hash_map` is not exception-safe.
31
32
#ifndef ABSL_CONTAINER_FLAT_HASH_MAP_H_
33
#define ABSL_CONTAINER_FLAT_HASH_MAP_H_
34
35
#include <cstddef>
36
#include <memory>
37
#include <type_traits>
38
#include <utility>
39
40
#include "absl/algorithm/container.h"
41
#include "absl/base/attributes.h"
42
#include "absl/base/macros.h"
43
#include "absl/container/hash_container_defaults.h"
44
#include "absl/container/internal/container_memory.h"
45
#include "absl/container/internal/raw_hash_map.h"  // IWYU pragma: export
46
#include "absl/meta/type_traits.h"
47
48
namespace absl {
49
ABSL_NAMESPACE_BEGIN
50
namespace container_internal {
51
template <class K, class V>
52
struct FlatHashMapPolicy;
53
}  // namespace container_internal
54
55
// -----------------------------------------------------------------------------
56
// absl::flat_hash_map
57
// -----------------------------------------------------------------------------
58
//
59
// An `absl::flat_hash_map<K, V>` is an unordered associative container which
60
// has been optimized for both speed and memory footprint in most common use
61
// cases. Its interface is similar to that of `std::unordered_map<K, V>` with
62
// the following notable differences:
63
//
64
// * Requires keys that are CopyConstructible
65
// * Requires values that are MoveConstructible
66
// * Supports heterogeneous lookup, through `find()`, `operator[]()` and
67
//   `insert()`, provided that the map is provided a compatible heterogeneous
68
//   hashing function and equality operator. See below for details.
69
// * Invalidates any references and pointers to elements within the table after
70
//   `rehash()` and when the table is moved.
71
// * Contains a `capacity()` member function indicating the number of element
72
//   slots (open, deleted, and empty) within the hash map.
73
// * Returns `void` from the `erase(iterator)` overload.
74
//
75
// By default, `flat_hash_map` uses the `absl::Hash` hashing framework.
76
// All fundamental and Abseil types that support the `absl::Hash` framework have
77
// a compatible equality operator for comparing insertions into `flat_hash_map`.
78
// If your type is not yet supported by the `absl::Hash` framework, see
79
// absl/hash/hash.h for information on extending Abseil hashing to user-defined
80
// types.
81
//
82
// Using `absl::flat_hash_map` at interface boundaries in dynamically loaded
83
// libraries (e.g. .dll, .so) is unsupported due to way `absl::Hash` values may
84
// be randomized across dynamically loaded libraries.
85
//
86
// To achieve heterogeneous lookup for custom types either `Hash` and `Eq` type
87
// parameters can be used or `T` should have public inner types
88
// `absl_container_hash` and (optionally) `absl_container_eq`. In either case,
89
// `typename Hash::is_transparent` and `typename Eq::is_transparent` should be
90
// well-formed. Both types are basically functors:
91
// * `Hash` should support `size_t operator()(U val) const` that returns a hash
92
// for the given `val`.
93
// * `Eq` should support `bool operator()(U lhs, V rhs) const` that returns true
94
// if `lhs` is equal to `rhs`.
95
//
96
// In most cases `T` needs only to provide the `absl_container_hash`. In this
97
// case `std::equal_to<void>` will be used instead of `eq` part.
98
//
99
// NOTE: A `flat_hash_map` stores its value types directly inside its
100
// implementation array to avoid memory indirection. Because a `flat_hash_map`
101
// is designed to move data when rehashed, map values will not retain pointer
102
// stability. If you require pointer stability, or if your values are large,
103
// consider using `absl::flat_hash_map<Key, std::unique_ptr<Value>>` instead.
104
// If your types are not moveable or you require pointer stability for keys,
105
// consider `absl::node_hash_map`.
106
//
107
// Example:
108
//
109
//   // Create a flat hash map of three strings (that map to strings)
110
//   absl::flat_hash_map<std::string, std::string> ducks =
111
//     {{"a", "huey"}, {"b", "dewey"}, {"c", "louie"}};
112
//
113
//  // Insert a new element into the flat hash map
114
//  ducks.insert({"d", "donald"});
115
//
116
//  // Force a rehash of the flat hash map
117
//  ducks.rehash(0);
118
//
119
//  // Find the element with the key "b"
120
//  std::string search_key = "b";
121
//  auto result = ducks.find(search_key);
122
//  if (result != ducks.end()) {
123
//    std::cout << "Result: " << result->second << std::endl;
124
//  }
125
template <class K, class V, class Hash = DefaultHashContainerHash<K>,
126
          class Eq = DefaultHashContainerEq<K>,
127
          class Allocator = std::allocator<std::pair<const K, V>>>
128
class ABSL_ATTRIBUTE_OWNER flat_hash_map
129
    : public absl::container_internal::raw_hash_map<
130
          absl::container_internal::FlatHashMapPolicy<K, V>, Hash, Eq,
131
          Allocator> {
132
  using Base = typename flat_hash_map::raw_hash_map;
133
134
 public:
135
  // Constructors and Assignment Operators
136
  //
137
  // A flat_hash_map supports the same overload set as `std::unordered_map`
138
  // for construction and assignment:
139
  //
140
  // *  Default constructor
141
  //
142
  //    // No allocation for the table's elements is made.
143
  //    absl::flat_hash_map<int, std::string> map1;
144
  //
145
  // * Initializer List constructor
146
  //
147
  //   absl::flat_hash_map<int, std::string> map2 =
148
  //       {{1, "huey"}, {2, "dewey"}, {3, "louie"},};
149
  //
150
  // * Copy constructor
151
  //
152
  //   absl::flat_hash_map<int, std::string> map3(map2);
153
  //
154
  // * Copy assignment operator
155
  //
156
  //  // Hash functor and Comparator are copied as well
157
  //  absl::flat_hash_map<int, std::string> map4;
158
  //  map4 = map3;
159
  //
160
  // * Move constructor
161
  //
162
  //   // Move is guaranteed efficient
163
  //   absl::flat_hash_map<int, std::string> map5(std::move(map4));
164
  //
165
  // * Move assignment operator
166
  //
167
  //   // May be efficient if allocators are compatible
168
  //   absl::flat_hash_map<int, std::string> map6;
169
  //   map6 = std::move(map5);
170
  //
171
  // * Range constructor
172
  //
173
  //   std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}};
174
  //   absl::flat_hash_map<int, std::string> map7(v.begin(), v.end());
175
2
  flat_hash_map() {}
176
  using Base::Base;
177
178
  // flat_hash_map::begin()
179
  //
180
  // Returns an iterator to the beginning of the `flat_hash_map`.
181
  using Base::begin;
182
183
  // flat_hash_map::cbegin()
184
  //
185
  // Returns a const iterator to the beginning of the `flat_hash_map`.
186
  using Base::cbegin;
187
188
  // flat_hash_map::cend()
189
  //
190
  // Returns a const iterator to the end of the `flat_hash_map`.
191
  using Base::cend;
192
193
  // flat_hash_map::end()
194
  //
195
  // Returns an iterator to the end of the `flat_hash_map`.
196
  using Base::end;
197
198
  // flat_hash_map::capacity()
199
  //
200
  // Returns the number of element slots (assigned, deleted, and empty)
201
  // available within the `flat_hash_map`.
202
  //
203
  // NOTE: this member function is particular to `absl::flat_hash_map` and is
204
  // not provided in the `std::unordered_map` API.
205
  using Base::capacity;
206
207
  // flat_hash_map::empty()
208
  //
209
  // Returns whether or not the `flat_hash_map` is empty.
210
  using Base::empty;
211
212
  // flat_hash_map::max_size()
213
  //
214
  // Returns the largest theoretical possible number of elements within a
215
  // `flat_hash_map` under current memory constraints. This value can be thought
216
  // of the largest value of `std::distance(begin(), end())` for a
217
  // `flat_hash_map<K, V>`.
218
  using Base::max_size;
219
220
  // flat_hash_map::size()
221
  //
222
  // Returns the number of elements currently within the `flat_hash_map`.
223
  using Base::size;
224
225
  // flat_hash_map::clear()
226
  //
227
  // Removes all elements from the `flat_hash_map`. Invalidates any references,
228
  // pointers, or iterators referring to contained elements.
229
  //
230
  // NOTE: this operation may shrink the underlying buffer. To avoid shrinking
231
  // the underlying buffer call `erase(begin(), end())`.
232
  using Base::clear;
233
234
  // flat_hash_map::erase()
235
  //
236
  // Erases elements within the `flat_hash_map`. Erasing does not trigger a
237
  // rehash. Overloads are listed below.
238
  //
239
  // void erase(const_iterator pos):
240
  //
241
  //   Erases the element at `position` of the `flat_hash_map`, returning
242
  //   `void`.
243
  //
244
  //   NOTE: returning `void` in this case is different than that of STL
245
  //   containers in general and `std::unordered_map` in particular (which
246
  //   return an iterator to the element following the erased element). If that
247
  //   iterator is needed, simply post increment the iterator:
248
  //
249
  //     map.erase(it++);
250
  //
251
  // iterator erase(const_iterator first, const_iterator last):
252
  //
253
  //   Erases the elements in the open interval [`first`, `last`), returning an
254
  //   iterator pointing to `last`. The special case of calling
255
  //   `erase(begin(), end())` resets the reserved growth such that if
256
  //   `reserve(N)` has previously been called and there has been no intervening
257
  //   call to `clear()`, then after calling `erase(begin(), end())`, it is safe
258
  //   to assume that inserting N elements will not cause a rehash.
259
  //
260
  // size_type erase(const key_type& key):
261
  //
262
  //   Erases the element with the matching key, if it exists, returning the
263
  //   number of elements erased (0 or 1).
264
  using Base::erase;
265
266
  // flat_hash_map::insert()
267
  //
268
  // Inserts an element of the specified value into the `flat_hash_map`,
269
  // returning an iterator pointing to the newly inserted element, provided that
270
  // an element with the given key does not already exist. If rehashing occurs
271
  // due to the insertion, all iterators are invalidated. Overloads are listed
272
  // below.
273
  //
274
  // std::pair<iterator,bool> insert(const init_type& value):
275
  //
276
  //   Inserts a value into the `flat_hash_map`. Returns a pair consisting of an
277
  //   iterator to the inserted element (or to the element that prevented the
278
  //   insertion) and a bool denoting whether the insertion took place.
279
  //
280
  // std::pair<iterator,bool> insert(T&& value):
281
  // std::pair<iterator,bool> insert(init_type&& value):
282
  //
283
  //   Inserts a moveable value into the `flat_hash_map`. Returns a pair
284
  //   consisting of an iterator to the inserted element (or to the element that
285
  //   prevented the insertion) and a bool denoting whether the insertion took
286
  //   place.
287
  //
288
  // iterator insert(const_iterator hint, const init_type& value):
289
  // iterator insert(const_iterator hint, T&& value):
290
  // iterator insert(const_iterator hint, init_type&& value);
291
  //
292
  //   Inserts a value, using the position of `hint` as a non-binding suggestion
293
  //   for where to begin the insertion search. Returns an iterator to the
294
  //   inserted element, or to the existing element that prevented the
295
  //   insertion.
296
  //
297
  // void insert(InputIterator first, InputIterator last):
298
  //
299
  //   Inserts a range of values [`first`, `last`).
300
  //
301
  //   NOTE: Although the STL does not specify which element may be inserted if
302
  //   multiple keys compare equivalently, for `flat_hash_map` we guarantee the
303
  //   first match is inserted.
304
  //
305
  // void insert(std::initializer_list<init_type> ilist):
306
  //
307
  //   Inserts the elements within the initializer list `ilist`.
308
  //
309
  //   NOTE: Although the STL does not specify which element may be inserted if
310
  //   multiple keys compare equivalently within the initializer list, for
311
  //   `flat_hash_map` we guarantee the first match is inserted.
312
  using Base::insert;
313
314
  // flat_hash_map::insert_or_assign()
315
  //
316
  // Inserts an element of the specified value into the `flat_hash_map` provided
317
  // that a value with the given key does not already exist, or replaces it with
318
  // the element value if a key for that value already exists, returning an
319
  // iterator pointing to the newly inserted element.  If rehashing occurs due
320
  // to the insertion, all existing iterators are invalidated. Overloads are
321
  // listed below.
322
  //
323
  // pair<iterator, bool> insert_or_assign(const init_type& k, T&& obj):
324
  // pair<iterator, bool> insert_or_assign(init_type&& k, T&& obj):
325
  //
326
  //   Inserts/Assigns (or moves) the element of the specified key into the
327
  //   `flat_hash_map`.
328
  //
329
  // iterator insert_or_assign(const_iterator hint,
330
  //                           const init_type& k, T&& obj):
331
  // iterator insert_or_assign(const_iterator hint, init_type&& k, T&& obj):
332
  //
333
  //   Inserts/Assigns (or moves) the element of the specified key into the
334
  //   `flat_hash_map` using the position of `hint` as a non-binding suggestion
335
  //   for where to begin the insertion search.
336
  using Base::insert_or_assign;
337
338
  // flat_hash_map::emplace()
339
  //
340
  // Inserts an element of the specified value by constructing it in-place
341
  // within the `flat_hash_map`, provided that no element with the given key
342
  // already exists.
343
  //
344
  // The element may be constructed even if there already is an element with the
345
  // key in the container, in which case the newly constructed element will be
346
  // destroyed immediately. Prefer `try_emplace()` unless your key is not
347
  // copyable or moveable.
348
  //
349
  // If rehashing occurs due to the insertion, all iterators are invalidated.
350
  using Base::emplace;
351
352
  // flat_hash_map::emplace_hint()
353
  //
354
  // Inserts an element of the specified value by constructing it in-place
355
  // within the `flat_hash_map`, using the position of `hint` as a non-binding
356
  // suggestion for where to begin the insertion search, and only inserts
357
  // provided that no element with the given key already exists.
358
  //
359
  // The element may be constructed even if there already is an element with the
360
  // key in the container, in which case the newly constructed element will be
361
  // destroyed immediately. Prefer `try_emplace()` unless your key is not
362
  // copyable or moveable.
363
  //
364
  // If rehashing occurs due to the insertion, all iterators are invalidated.
365
  using Base::emplace_hint;
366
367
  // flat_hash_map::try_emplace()
368
  //
369
  // Inserts an element of the specified value by constructing it in-place
370
  // within the `flat_hash_map`, provided that no element with the given key
371
  // already exists. Unlike `emplace()`, if an element with the given key
372
  // already exists, we guarantee that no element is constructed.
373
  //
374
  // If rehashing occurs due to the insertion, all iterators are invalidated.
375
  // Overloads are listed below.
376
  //
377
  //   pair<iterator, bool> try_emplace(const key_type& k, Args&&... args):
378
  //   pair<iterator, bool> try_emplace(key_type&& k, Args&&... args):
379
  //
380
  // Inserts (via copy or move) the element of the specified key into the
381
  // `flat_hash_map`.
382
  //
383
  //   iterator try_emplace(const_iterator hint,
384
  //                        const key_type& k, Args&&... args):
385
  //   iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args):
386
  //
387
  // Inserts (via copy or move) the element of the specified key into the
388
  // `flat_hash_map` using the position of `hint` as a non-binding suggestion
389
  // for where to begin the insertion search.
390
  //
391
  // All `try_emplace()` overloads make the same guarantees regarding rvalue
392
  // arguments as `std::unordered_map::try_emplace()`, namely that these
393
  // functions will not move from rvalue arguments if insertions do not happen.
394
  using Base::try_emplace;
395
396
  // flat_hash_map::extract()
397
  //
398
  // Extracts the indicated element, erasing it in the process, and returns it
399
  // as a C++17-compatible node handle. Overloads are listed below.
400
  //
401
  // node_type extract(const_iterator position):
402
  //
403
  //   Extracts the key,value pair of the element at the indicated position and
404
  //   returns a node handle owning that extracted data.
405
  //
406
  // node_type extract(const key_type& x):
407
  //
408
  //   Extracts the key,value pair of the element with a key matching the passed
409
  //   key value and returns a node handle owning that extracted data. If the
410
  //   `flat_hash_map` does not contain an element with a matching key, this
411
  //   function returns an empty node handle.
412
  //
413
  // NOTE: when compiled in an earlier version of C++ than C++17,
414
  // `node_type::key()` returns a const reference to the key instead of a
415
  // mutable reference. We cannot safely return a mutable reference without
416
  // std::launder (which is not available before C++17).
417
  using Base::extract;
418
419
  // flat_hash_map::merge()
420
  //
421
  // Extracts elements from a given `source` flat hash map into this
422
  // `flat_hash_map`. If the destination `flat_hash_map` already contains an
423
  // element with an equivalent key, that element is not extracted.
424
  using Base::merge;
425
426
  // flat_hash_map::swap(flat_hash_map& other)
427
  //
428
  // Exchanges the contents of this `flat_hash_map` with those of the `other`
429
  // flat hash map.
430
  //
431
  // All iterators and references on the `flat_hash_map` remain valid, excepting
432
  // for the past-the-end iterator, which is invalidated.
433
  //
434
  // `swap()` requires that the flat hash map's hashing and key equivalence
435
  // functions be Swappable, and are exchanged using unqualified calls to
436
  // non-member `swap()`. If the map's allocator has
437
  // `std::allocator_traits<allocator_type>::propagate_on_container_swap::value`
438
  // set to `true`, the allocators are also exchanged using an unqualified call
439
  // to non-member `swap()`; otherwise, the allocators are not swapped.
440
  using Base::swap;
441
442
  // flat_hash_map::rehash(count)
443
  //
444
  // Rehashes the `flat_hash_map`, setting the number of slots to be at least
445
  // the passed value. If the new number of slots increases the load factor more
446
  // than the current maximum load factor
447
  // (`count` < `size()` / `max_load_factor()`), then the new number of slots
448
  // will be at least `size()` / `max_load_factor()`.
449
  //
450
  // To force a rehash, pass rehash(0).
451
  //
452
  // NOTE: unlike behavior in `std::unordered_map`, references are also
453
  // invalidated upon a `rehash()`.
454
  using Base::rehash;
455
456
  // flat_hash_map::reserve(count)
457
  //
458
  // Sets the number of slots in the `flat_hash_map` to the number needed to
459
  // accommodate at least `count` total elements without exceeding the current
460
  // maximum load factor, and may rehash the container if needed.
461
  using Base::reserve;
462
463
  // flat_hash_map::at()
464
  //
465
  // Returns a reference to the mapped value of the element with key equivalent
466
  // to the passed key.
467
  using Base::at;
468
469
  // flat_hash_map::contains()
470
  //
471
  // Determines whether an element with a key comparing equal to the given `key`
472
  // exists within the `flat_hash_map`, returning `true` if so or `false`
473
  // otherwise.
474
  using Base::contains;
475
476
  // flat_hash_map::count(const Key& key) const
477
  //
478
  // Returns the number of elements with a key comparing equal to the given
479
  // `key` within the `flat_hash_map`. note that this function will return
480
  // either `1` or `0` since duplicate keys are not allowed within a
481
  // `flat_hash_map`.
482
  using Base::count;
483
484
  // flat_hash_map::equal_range()
485
  //
486
  // Returns a closed range [first, last], defined by a `std::pair` of two
487
  // iterators, containing all elements with the passed key in the
488
  // `flat_hash_map`.
489
  using Base::equal_range;
490
491
  // flat_hash_map::find()
492
  //
493
  // Finds an element with the passed `key` within the `flat_hash_map`.
494
  using Base::find;
495
496
  // flat_hash_map::operator[]()
497
  //
498
  // Returns a reference to the value mapped to the passed key within the
499
  // `flat_hash_map`, performing an `insert()` if the key does not already
500
  // exist.
501
  //
502
  // If an insertion occurs and results in a rehashing of the container, all
503
  // iterators are invalidated. Otherwise iterators are not affected and
504
  // references are not invalidated. Overloads are listed below.
505
  //
506
  // T& operator[](const Key& key):
507
  //
508
  //   Inserts an init_type object constructed in-place if the element with the
509
  //   given key does not exist.
510
  //
511
  // T& operator[](Key&& key):
512
  //
513
  //   Inserts an init_type object constructed in-place provided that an element
514
  //   with the given key does not exist.
515
  using Base::operator[];
516
517
  // flat_hash_map::bucket_count()
518
  //
519
  // Returns the number of "buckets" within the `flat_hash_map`. Note that
520
  // because a flat hash map contains all elements within its internal storage,
521
  // this value simply equals the current capacity of the `flat_hash_map`.
522
  using Base::bucket_count;
523
524
  // flat_hash_map::load_factor()
525
  //
526
  // Returns the current load factor of the `flat_hash_map` (the average number
527
  // of slots occupied with a value within the hash map).
528
  using Base::load_factor;
529
530
  // flat_hash_map::max_load_factor()
531
  //
532
  // Manages the maximum load factor of the `flat_hash_map`. Overloads are
533
  // listed below.
534
  //
535
  // float flat_hash_map::max_load_factor()
536
  //
537
  //   Returns the current maximum load factor of the `flat_hash_map`.
538
  //
539
  // void flat_hash_map::max_load_factor(float ml)
540
  //
541
  //   Sets the maximum load factor of the `flat_hash_map` to the passed value.
542
  //
543
  //   NOTE: This overload is provided only for API compatibility with the STL;
544
  //   `flat_hash_map` will ignore any set load factor and manage its rehashing
545
  //   internally as an implementation detail.
546
  using Base::max_load_factor;
547
548
  // flat_hash_map::get_allocator()
549
  //
550
  // Returns the allocator function associated with this `flat_hash_map`.
551
  using Base::get_allocator;
552
553
  // flat_hash_map::hash_function()
554
  //
555
  // Returns the hashing function used to hash the keys within this
556
  // `flat_hash_map`.
557
  using Base::hash_function;
558
559
  // flat_hash_map::key_eq()
560
  //
561
  // Returns the function used for comparing keys equality.
562
  using Base::key_eq;
563
};
564
565
// erase_if(flat_hash_map<>, Pred)
566
//
567
// Erases all elements that satisfy the predicate `pred` from the container `c`.
568
// Returns the number of erased elements.
569
template <typename K, typename V, typename H, typename E, typename A,
570
          typename Predicate>
571
typename flat_hash_map<K, V, H, E, A>::size_type erase_if(
572
    flat_hash_map<K, V, H, E, A>& c, Predicate pred) {
573
  return container_internal::EraseIf(pred, &c);
574
}
575
576
// swap(flat_hash_map<>, flat_hash_map<>)
577
//
578
// Swaps the contents of two `flat_hash_map` containers.
579
//
580
// NOTE: we need to define this function template in order for
581
// `flat_hash_set::swap` to be called instead of `std::swap`. Even though we
582
// have `swap(raw_hash_set&, raw_hash_set&)` defined, that function requires a
583
// derived-to-base conversion, whereas `std::swap` is a function template so
584
// `std::swap` will be preferred by compiler.
585
template <typename K, typename V, typename H, typename E, typename A>
586
void swap(flat_hash_map<K, V, H, E, A>& x,
587
          flat_hash_map<K, V, H, E, A>& y) noexcept(noexcept(x.swap(y))) {
588
  x.swap(y);
589
}
590
591
namespace container_internal {
592
593
// c_for_each_fast(flat_hash_map<>, Function)
594
//
595
// Container-based version of the <algorithm> `std::for_each()` function to
596
// apply a function to a container's elements.
597
// There is no guarantees on the order of the function calls.
598
// Erasure and/or insertion of elements in the function is not allowed.
599
template <typename K, typename V, typename H, typename E, typename A,
600
          typename Function>
601
decay_t<Function> c_for_each_fast(const flat_hash_map<K, V, H, E, A>& c,
602
                                  Function&& f) {
603
  container_internal::ForEach(f, &c);
604
  return f;
605
}
606
template <typename K, typename V, typename H, typename E, typename A,
607
          typename Function>
608
decay_t<Function> c_for_each_fast(flat_hash_map<K, V, H, E, A>& c,
609
                                  Function&& f) {
610
  container_internal::ForEach(f, &c);
611
  return f;
612
}
613
template <typename K, typename V, typename H, typename E, typename A,
614
          typename Function>
615
decay_t<Function> c_for_each_fast(flat_hash_map<K, V, H, E, A>&& c,
616
                                  Function&& f) {
617
  container_internal::ForEach(f, &c);
618
  return f;
619
}
620
621
}  // namespace container_internal
622
623
namespace container_internal {
624
625
template <class K, class V>
626
struct FlatHashMapPolicy {
627
  using slot_policy = container_internal::map_slot_policy<K, V>;
628
  using slot_type = typename slot_policy::slot_type;
629
  using key_type = K;
630
  using mapped_type = V;
631
  using init_type = std::pair</*non const*/ key_type, mapped_type>;
632
633
  template <class Allocator, class... Args>
634
16
  static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
635
16
    slot_policy::construct(alloc, slot, std::forward<Args>(args)...);
636
16
  }
void absl::container_internal::FlatHashMapPolicy<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>::construct<std::__1::allocator<std::__1::pair<std::__1::basic_string_view<char, std::__1::char_traits<char> > const, absl::CommandLineFlag*> >, std::__1::piecewise_construct_t const&, std::__1::tuple<std::__1::basic_string_view<char, std::__1::char_traits<char> > const&&>, std::__1::tuple<absl::CommandLineFlag*&&> >(std::__1::allocator<std::__1::pair<std::__1::basic_string_view<char, std::__1::char_traits<char> > const, absl::CommandLineFlag*> >*, absl::container_internal::map_slot_type<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>*, std::__1::piecewise_construct_t const&, std::__1::tuple<std::__1::basic_string_view<char, std::__1::char_traits<char> > const&&>&&, std::__1::tuple<absl::CommandLineFlag*&&>&&)
Line
Count
Source
634
16
  static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
635
16
    slot_policy::construct(alloc, slot, std::forward<Args>(args)...);
636
16
  }
Unexecuted instantiation: void absl::container_internal::FlatHashMapPolicy<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>::construct<std::__1::allocator<std::__1::pair<std::__1::basic_string_view<char, std::__1::char_traits<char> > const, absl::CommandLineFlag*> >, std::__1::piecewise_construct_t const&, std::__1::tuple<std::__1::basic_string_view<char, std::__1::char_traits<char> >&&>, std::__1::tuple<absl::CommandLineFlag*&&> >(std::__1::allocator<std::__1::pair<std::__1::basic_string_view<char, std::__1::char_traits<char> > const, absl::CommandLineFlag*> >*, absl::container_internal::map_slot_type<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>*, std::__1::piecewise_construct_t const&, std::__1::tuple<std::__1::basic_string_view<char, std::__1::char_traits<char> >&&>&&, std::__1::tuple<absl::CommandLineFlag*&&>&&)
637
638
  // Returns std::true_type in case destroy is trivial.
639
  template <class Allocator>
640
0
  static auto destroy(Allocator* alloc, slot_type* slot) {
641
0
    return slot_policy::destroy(alloc, slot);
642
0
  }
643
644
  template <class Allocator>
645
  static auto transfer(Allocator* alloc, slot_type* new_slot,
646
0
                       slot_type* old_slot) {
647
0
    return slot_policy::transfer(alloc, new_slot, old_slot);
648
0
  }
Unexecuted instantiation: auto absl::container_internal::FlatHashMapPolicy<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>::transfer<std::__1::allocator<std::__1::pair<std::__1::basic_string_view<char, std::__1::char_traits<char> > const, absl::CommandLineFlag*> > >(std::__1::allocator<std::__1::pair<std::__1::basic_string_view<char, std::__1::char_traits<char> > const, absl::CommandLineFlag*> >*, absl::container_internal::map_slot_type<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>*, absl::container_internal::map_slot_type<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>*)
Unexecuted instantiation: auto absl::container_internal::FlatHashMapPolicy<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>::transfer<std::__1::allocator<char> >(std::__1::allocator<char>*, absl::container_internal::map_slot_type<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>*, absl::container_internal::map_slot_type<std::__1::basic_string_view<char, std::__1::char_traits<char> >, absl::CommandLineFlag*>*)
649
650
  template <class F, class... Args>
651
  static decltype(absl::container_internal::DecomposePair(
652
      std::declval<F>(), std::declval<Args>()...))
653
51
  apply(F&& f, Args&&... args) {
654
51
    return absl::container_internal::DecomposePair(std::forward<F>(f),
655
51
                                                   std::forward<Args>(args)...);
656
51
  }
_ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE12EqualElementIS6_EEJRSH_EEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSN_DpOSO_
Line
Count
Source
653
19
  apply(F&& f, Args&&... args) {
654
19
    return absl::container_internal::DecomposePair(std::forward<F>(f),
655
19
                                                   std::forward<Args>(args)...);
656
19
  }
_ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE19EmplaceDecomposableEJSH_EEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSL_DpOSM_
Line
Count
Source
653
16
  apply(F&& f, Args&&... args) {
654
16
    return absl::container_internal::DecomposePair(std::forward<F>(f),
655
16
                                                   std::forward<Args>(args)...);
656
16
  }
Unexecuted instantiation: _ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE11HashElementEJRSH_EEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSM_DpOSN_
_ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE11FindElementEJRSH_EEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSM_DpOSN_
Line
Count
Source
653
16
  apply(F&& f, Args&&... args) {
654
16
    return absl::container_internal::DecomposePair(std::forward<F>(f),
655
16
                                                   std::forward<Args>(args)...);
656
16
  }
Unexecuted instantiation: _ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE19EmplaceDecomposableEJNSF_IS6_S8_EEEEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSM_DpOSN_
Unexecuted instantiation: _ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE12EqualElementIS6_EEJRKSH_EEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSO_DpOSP_
Unexecuted instantiation: _ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_12raw_hash_setIS9_NS0_10StringHashENS0_8StringEqENS2_9allocatorINS2_4pairIKS6_S8_EEEEE11HashElementEJRKSH_EEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSN_DpOSO_
Unexecuted instantiation: _ZN4absl18container_internal17FlatHashMapPolicyINSt3__117basic_string_viewIcNS2_11char_traitsIcEEEEPNS_15CommandLineFlagEE5applyINS0_18hash_policy_traitsIS9_vE11HashElementINS0_10StringHashEEEJRNS2_4pairIKS6_S8_EEEEEDTclsr4absl18container_internalE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSK_DpOSL_
657
658
  template <class Hash>
659
0
  static constexpr HashSlotFn get_hash_slot_fn() {
660
0
    return memory_internal::IsLayoutCompatible<K, V>::value
661
0
               ? &TypeErasedApplyToSlotFn<Hash, K>
662
0
               : nullptr;
663
0
  }
664
665
  static size_t space_used(const slot_type*) { return 0; }
666
667
35
  static std::pair<const K, V>& element(slot_type* slot) { return slot->value; }
668
669
  static V& value(std::pair<const K, V>* kv) { return kv->second; }
670
  static const V& value(const std::pair<const K, V>* kv) { return kv->second; }
671
};
672
673
}  // namespace container_internal
674
675
namespace container_algorithm_internal {
676
677
// Specialization of trait in absl/algorithm/container.h
678
template <class Key, class T, class Hash, class KeyEqual, class Allocator>
679
struct IsUnorderedContainer<
680
    absl::flat_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {};
681
682
}  // namespace container_algorithm_internal
683
684
ABSL_NAMESPACE_END
685
}  // namespace absl
686
687
#endif  // ABSL_CONTAINER_FLAT_HASH_MAP_H_