summaryrefslogtreecommitdiff
path: root/absl/container/flat_hash_map.h
blob: fcb70d861f39ce6a7f1dee21b384b7a7fe9d0d22 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
// Copyright 2018 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// -----------------------------------------------------------------------------
// File: flat_hash_map.h
// -----------------------------------------------------------------------------
//
// An `absl::flat_hash_map<K, V>` is an unordered associative container of
// unique keys and associated values designed to be a more efficient replacement
// for `std::unordered_map`. Like `unordered_map`, search, insertion, and
// deletion of map elements can be done as an `O(1)` operation. However,
// `flat_hash_map` (and other unordered associative containers known as the
// collection of Abseil "Swiss tables") contain other optimizations that result
// in both memory and computation advantages.
//
// In most cases, your default choice for a hash map should be a map of type
// `flat_hash_map`.

#ifndef ABSL_CONTAINER_FLAT_HASH_MAP_H_
#define ABSL_CONTAINER_FLAT_HASH_MAP_H_

#include <cstddef>
#include <new>
#include <type_traits>
#include <utility>

#include "absl/algorithm/container.h"
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/hash_function_defaults.h"  // IWYU pragma: export
#include "absl/container/internal/raw_hash_map.h"  // IWYU pragma: export
#include "absl/memory/memory.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace container_internal {
template <class K, class V>
struct FlatHashMapPolicy;
}  // namespace container_internal

// -----------------------------------------------------------------------------
// absl::flat_hash_map
// -----------------------------------------------------------------------------
//
// An `absl::flat_hash_map<K, V>` is an unordered associative container which
// has been optimized for both speed and memory footprint in most common use
// cases. Its interface is similar to that of `std::unordered_map<K, V>` with
// the following notable differences:
//
// * Requires keys that are CopyConstructible
// * Requires values that are MoveConstructible
// * Supports heterogeneous lookup, through `find()`, `operator[]()` and
//   `insert()`, provided that the map is provided a compatible heterogeneous
//   hashing function and equality operator.
// * Invalidates any references and pointers to elements within the table after
//   `rehash()`.
// * Contains a `capacity()` member function indicating the number of element
//   slots (open, deleted, and empty) within the hash map.
// * Returns `void` from the `erase(iterator)` overload.
//
// By default, `flat_hash_map` uses the `absl::Hash` hashing framework.
// All fundamental and Abseil types that support the `absl::Hash` framework have
// a compatible equality operator for comparing insertions into `flat_hash_map`.
// If your type is not yet supported by the `absl::Hash` framework, see
// absl/hash/hash.h for information on extending Abseil hashing to user-defined
// types.
//
// NOTE: A `flat_hash_map` stores its value types directly inside its
// implementation array to avoid memory indirection. Because a `flat_hash_map`
// is designed to move data when rehashed, map values will not retain pointer
// stability. If you require pointer stability, or if your values are large,
// consider using `absl::flat_hash_map<Key, std::unique_ptr<Value>>` instead.
// If your types are not moveable or you require pointer stability for keys,
// consider `absl::node_hash_map`.
//
// Example:
//
//   // Create a flat hash map of three strings (that map to strings)
//   absl::flat_hash_map<std::string, std::string> ducks =
//     {{"a", "huey"}, {"b", "dewey"}, {"c", "louie"}};
//
//  // Insert a new element into the flat hash map
//  ducks.insert({"d", "donald"});
//
//  // Force a rehash of the flat hash map
//  ducks.rehash(0);
//
//  // Find the element with the key "b"
//  std::string search_key = "b";
//  auto result = ducks.find(search_key);
//  if (result != ducks.end()) {
//    std::cout << "Result: " << result->second << std::endl;
//  }
template <class K, class V,
          class Hash = absl::container_internal::hash_default_hash<K>,
          class Eq = absl::container_internal::hash_default_eq<K>,
          class Allocator = std::allocator<std::pair<const K, V>>>
class flat_hash_map : public absl::container_internal::raw_hash_map<
                          absl::container_internal::FlatHashMapPolicy<K, V>,
                          Hash, Eq, Allocator> {
  using Base = typename flat_hash_map::raw_hash_map;

 public:
  // Constructors and Assignment Operators
  //
  // A flat_hash_map supports the same overload set as `std::unordered_map`
  // for construction and assignment:
  //
  // *  Default constructor
  //
  //    // No allocation for the table's elements is made.
  //    absl::flat_hash_map<int, std::string> map1;
  //
  // * Initializer List constructor
  //
  //   absl::flat_hash_map<int, std::string> map2 =
  //       {{1, "huey"}, {2, "dewey"}, {3, "louie"},};
  //
  // * Copy constructor
  //
  //   absl::flat_hash_map<int, std::string> map3(map2);
  //
  // * Copy assignment operator
  //
  //  // Hash functor and Comparator are copied as well
  //  absl::flat_hash_map<int, std::string> map4;
  //  map4 = map3;
  //
  // * Move constructor
  //
  //   // Move is guaranteed efficient
  //   absl::flat_hash_map<int, std::string> map5(std::move(map4));
  //
  // * Move assignment operator
  //
  //   // May be efficient if allocators are compatible
  //   absl::flat_hash_map<int, std::string> map6;
  //   map6 = std::move(map5);
  //
  // * Range constructor
  //
  //   std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}};
  //   absl::flat_hash_map<int, std::string> map7(v.begin(), v.end());
  flat_hash_map() {}
  using Base::Base;

  // flat_hash_map::begin()
  //
  // Returns an iterator to the beginning of the `flat_hash_map`.
  using Base::begin;

  // flat_hash_map::cbegin()
  //
  // Returns a const iterator to the beginning of the `flat_hash_map`.
  using Base::cbegin;

  // flat_hash_map::cend()
  //
  // Returns a const iterator to the end of the `flat_hash_map`.
  using Base::cend;

  // flat_hash_map::end()
  //
  // Returns an iterator to the end of the `flat_hash_map`.
  using Base::end;

  // flat_hash_map::capacity()
  //
  // Returns the number of element slots (assigned, deleted, and empty)
  // available within the `flat_hash_map`.
  //
  // NOTE: this member function is particular to `absl::flat_hash_map` and is
  // not provided in the `std::unordered_map` API.
  using Base::capacity;

  // flat_hash_map::empty()
  //
  // Returns whether or not the `flat_hash_map` is empty.
  using Base::empty;

  // flat_hash_map::max_size()
  //
  // Returns the largest theoretical possible number of elements within a
  // `flat_hash_map` under current memory constraints. This value can be thought
  // of the largest value of `std::distance(begin(), end())` for a
  // `flat_hash_map<K, V>`.
  using Base::max_size;

  // flat_hash_map::size()
  //
  // Returns the number of elements currently within the `flat_hash_map`.
  using Base::size;

  // flat_hash_map::clear()
  //
  // Removes all elements from the `flat_hash_map`. Invalidates any references,
  // pointers, or iterators referring to contained elements.
  //
  // NOTE: this operation may shrink the underlying buffer. To avoid shrinking
  // the underlying buffer call `erase(begin(), end())`.
  using Base::clear;

  // flat_hash_map::erase()
  //
  // Erases elements within the `flat_hash_map`. Erasing does not trigger a
  // rehash. Overloads are listed below.
  //
  // void erase(const_iterator pos):
  //
  //   Erases the element at `position` of the `flat_hash_map`, returning
  //   `void`.
  //
  //   NOTE: returning `void` in this case is different than that of STL
  //   containers in general and `std::unordered_map` in particular (which
  //   return an iterator to the element following the erased element). If that
  //   iterator is needed, simply post increment the iterator:
  //
  //     map.erase(it++);
  //
  // iterator erase(const_iterator first, const_iterator last):
  //
  //   Erases the elements in the open interval [`first`, `last`), returning an
  //   iterator pointing to `last`.
  //
  // size_type erase(const key_type& key):
  //
  //   Erases the element with the matching key, if it exists.
  using Base::erase;

  // flat_hash_map::insert()
  //
  // Inserts an element of the specified value into the `flat_hash_map`,
  // returning an iterator pointing to the newly inserted element, provided that
  // an element with the given key does not already exist. If rehashing occurs
  // due to the insertion, all iterators are invalidated. Overloads are listed
  // below.
  //
  // std::pair<iterator,bool> insert(const init_type& value):
  //
  //   Inserts a value into the `flat_hash_map`. Returns a pair consisting of an
  //   iterator to the inserted element (or to the element that prevented the
  //   insertion) and a bool denoting whether the insertion took place.
  //
  // std::pair<iterator,bool> insert(T&& value):
  // std::pair<iterator,bool> insert(init_type&& value):
  //
  //   Inserts a moveable value into the `flat_hash_map`. Returns a pair
  //   consisting of an iterator to the inserted element (or to the element that
  //   prevented the insertion) and a bool denoting whether the insertion took
  //   place.
  //
  // iterator insert(const_iterator hint, const init_type& value):
  // iterator insert(const_iterator hint, T&& value):
  // iterator insert(const_iterator hint, init_type&& value);
  //
  //   Inserts a value, using the position of `hint` as a non-binding suggestion
  //   for where to begin the insertion search. Returns an iterator to the
  //   inserted element, or to the existing element that prevented the
  //   insertion.
  //
  // void insert(InputIterator first, InputIterator last):
  //
  //   Inserts a range of values [`first`, `last`).
  //
  //   NOTE: Although the STL does not specify which element may be inserted if
  //   multiple keys compare equivalently, for `flat_hash_map` we guarantee the
  //   first match is inserted.
  //
  // void insert(std::initializer_list<init_type> ilist):
  //
  //   Inserts the elements within the initializer list `ilist`.
  //
  //   NOTE: Although the STL does not specify which element may be inserted if
  //   multiple keys compare equivalently within the initializer list, for
  //   `flat_hash_map` we guarantee the first match is inserted.
  using Base::insert;

  // flat_hash_map::insert_or_assign()
  //
  // Inserts an element of the specified value into the `flat_hash_map` provided
  // that a value with the given key does not already exist, or replaces it with
  // the element value if a key for that value already exists, returning an
  // iterator pointing to the newly inserted element.  If rehashing occurs due
  // to the insertion, all existing iterators are invalidated. Overloads are
  // listed below.
  //
  // pair<iterator, bool> insert_or_assign(const init_type& k, T&& obj):
  // pair<iterator, bool> insert_or_assign(init_type&& k, T&& obj):
  //
  //   Inserts/Assigns (or moves) the element of the specified key into the
  //   `flat_hash_map`.
  //
  // iterator insert_or_assign(const_iterator hint,
  //                           const init_type& k, T&& obj):
  // iterator insert_or_assign(const_iterator hint, init_type&& k, T&& obj):
  //
  //   Inserts/Assigns (or moves) the element of the specified key into the
  //   `flat_hash_map` using the position of `hint` as a non-binding suggestion
  //   for where to begin the insertion search.
  using Base::insert_or_assign;

  // flat_hash_map::emplace()
  //
  // Inserts an element of the specified value by constructing it in-place
  // within the `flat_hash_map`, provided that no element with the given key
  // already exists.
  //
  // The element may be constructed even if there already is an element with the
  // key in the container, in which case the newly constructed element will be
  // destroyed immediately. Prefer `try_emplace()` unless your key is not
  // copyable or moveable.
  //
  // If rehashing occurs due to the insertion, all iterators are invalidated.
  using Base::emplace;

  // flat_hash_map::emplace_hint()
  //
  // Inserts an element of the specified value by constructing it in-place
  // within the `flat_hash_map`, using the position of `hint` as a non-binding
  // suggestion for where to begin the insertion search, and only inserts
  // provided that no element with the given key already exists.
  //
  // The element may be constructed even if there already is an element with the
  // key in the container, in which case the newly constructed element will be
  // destroyed immediately. Prefer `try_emplace()` unless your key is not
  // copyable or moveable.
  //
  // If rehashing occurs due to the insertion, all iterators are invalidated.
  using Base::emplace_hint;

  // flat_hash_map::try_emplace()
  //
  // Inserts an element of the specified value by constructing it in-place
  // within the `flat_hash_map`, provided that no element with the given key
  // already exists. Unlike `emplace()`, if an element with the given key
  // already exists, we guarantee that no element is constructed.
  //
  // If rehashing occurs due to the insertion, all iterators are invalidated.
  // Overloads are listed below.
  //
  //   pair<iterator, bool> try_emplace(const key_type& k, Args&&... args):
  //   pair<iterator, bool> try_emplace(key_type&& k, Args&&... args):
  //
  // Inserts (via copy or move) the element of the specified key into the
  // `flat_hash_map`.
  //
  //   iterator try_emplace(const_iterator hint,
  //                        const init_type& k, Args&&... args):
  //   iterator try_emplace(const_iterator hint, init_type&& k, Args&&... args):
  //
  // Inserts (via copy or move) the element of the specified key into the
  // `flat_hash_map` using the position of `hint` as a non-binding suggestion
  // for where to begin the insertion search.
  //
  // All `try_emplace()` overloads make the same guarantees regarding rvalue
  // arguments as `std::unordered_map::try_emplace()`, namely that these
  // functions will not move from rvalue arguments if insertions do not happen.
  using Base::try_emplace;

  // flat_hash_map::extract()
  //
  // Extracts the indicated element, erasing it in the process, and returns it
  // as a C++17-compatible node handle. Overloads are listed below.
  //
  // node_type extract(const_iterator position):
  //
  //   Extracts the key,value pair of the element at the indicated position and
  //   returns a node handle owning that extracted data.
  //
  // node_type extract(const key_type& x):
  //
  //   Extracts the key,value pair of the element with a key matching the passed
  //   key value and returns a node handle owning that extracted data. If the
  //   `flat_hash_map` does not contain an element with a matching key, this
  //   function returns an empty node handle.
  using Base::extract;

  // flat_hash_map::merge()
  //
  // Extracts elements from a given `source` flat hash map into this
  // `flat_hash_map`. If the destination `flat_hash_map` already contains an
  // element with an equivalent key, that element is not extracted.
  using Base::merge;

  // flat_hash_map::swap(flat_hash_map& other)
  //
  // Exchanges the contents of this `flat_hash_map` with those of the `other`
  // flat hash map, avoiding invocation of any move, copy, or swap operations on
  // individual elements.
  //
  // All iterators and references on the `flat_hash_map` remain valid, excepting
  // for the past-the-end iterator, which is invalidated.
  //
  // `swap()` requires that the flat hash map's hashing and key equivalence
  // functions be Swappable, and are exchanged using unqualified calls to
  // non-member `swap()`. If the map's allocator has
  // `std::allocator_traits<allocator_type>::propagate_on_container_swap::value`
  // set to `true`, the allocators are also exchanged using an unqualified call
  // to non-member `swap()`; otherwise, the allocators are not swapped.
  using Base::swap;

  // flat_hash_map::rehash(count)
  //
  // Rehashes the `flat_hash_map`, setting the number of slots to be at least
  // the passed value. If the new number of slots increases the load factor more
  // than the current maximum load factor
  // (`count` < `size()` / `max_load_factor()`), then the new number of slots
  // will be at least `size()` / `max_load_factor()`.
  //
  // To force a rehash, pass rehash(0).
  //
  // NOTE: unlike behavior in `std::unordered_map`, references are also
  // invalidated upon a `rehash()`.
  using Base::rehash;

  // flat_hash_map::reserve(count)
  //
  // Sets the number of slots in the `flat_hash_map` to the number needed to
  // accommodate at least `count` total elements without exceeding the current
  // maximum load factor, and may rehash the container if needed.
  using Base::reserve;

  // flat_hash_map::at()
  //
  // Returns a reference to the mapped value of the element with key equivalent
  // to the passed key.
  using Base::at;

  // flat_hash_map::contains()
  //
  // Determines whether an element with a key comparing equal to the given `key`
  // exists within the `flat_hash_map`, returning `true` if so or `false`
  // otherwise.
  using Base::contains;

  // flat_hash_map::count(const Key& key) const
  //
  // Returns the number of elements with a key comparing equal to the given
  // `key` within the `flat_hash_map`. note that this function will return
  // either `1` or `0` since duplicate keys are not allowed within a
  // `flat_hash_map`.
  using Base::count;

  // flat_hash_map::equal_range()
  //
  // Returns a closed range [first, last], defined by a `std::pair` of two
  // iterators, containing all elements with the passed key in the
  // `flat_hash_map`.
  using Base::equal_range;

  // flat_hash_map::find()
  //
  // Finds an element with the passed `key` within the `flat_hash_map`.
  using Base::find;

  // flat_hash_map::operator[]()
  //
  // Returns a reference to the value mapped to the passed key within the
  // `flat_hash_map`, performing an `insert()` if the key does not already
  // exist.
  //
  // If an insertion occurs and results in a rehashing of the container, all
  // iterators are invalidated. Otherwise iterators are not affected and
  // references are not invalidated. Overloads are listed below.
  //
  // T& operator[](const Key& key):
  //
  //   Inserts an init_type object constructed in-place if the element with the
  //   given key does not exist.
  //
  // T& operator[](Key&& key):
  //
  //   Inserts an init_type object constructed in-place provided that an element
  //   with the given key does not exist.
  using Base::operator[];

  // flat_hash_map::bucket_count()
  //
  // Returns the number of "buckets" within the `flat_hash_map`. Note that
  // because a flat hash map contains all elements within its internal storage,
  // this value simply equals the current capacity of the `flat_hash_map`.
  using Base::bucket_count;

  // flat_hash_map::load_factor()
  //
  // Returns the current load factor of the `flat_hash_map` (the average number
  // of slots occupied with a value within the hash map).
  using Base::load_factor;

  // flat_hash_map::max_load_factor()
  //
  // Manages the maximum load factor of the `flat_hash_map`. Overloads are
  // listed below.
  //
  // float flat_hash_map::max_load_factor()
  //
  //   Returns the current maximum load factor of the `flat_hash_map`.
  //
  // void flat_hash_map::max_load_factor(float ml)
  //
  //   Sets the maximum load factor of the `flat_hash_map` to the passed value.
  //
  //   NOTE: This overload is provided only for API compatibility with the STL;
  //   `flat_hash_map` will ignore any set load factor and manage its rehashing
  //   internally as an implementation detail.
  using Base::max_load_factor;

  // flat_hash_map::get_allocator()
  //
  // Returns the allocator function associated with this `flat_hash_map`.
  using Base::get_allocator;

  // flat_hash_map::hash_function()
  //
  // Returns the hashing function used to hash the keys within this
  // `flat_hash_map`.
  using Base::hash_function;

  // flat_hash_map::key_eq()
  //
  // Returns the function used for comparing keys equality.
  using Base::key_eq;
};

// erase_if(flat_hash_map<>, Pred)
//
// Erases all elements that satisfy the predicate `pred` from the container `c`.
template <typename K, typename V, typename H, typename E, typename A,
          typename Predicate>
void erase_if(flat_hash_map<K, V, H, E, A>& c, Predicate pred) {
  container_internal::EraseIf(pred, &c);
}

namespace container_internal {

template <class K, class V>
struct FlatHashMapPolicy {
  using slot_policy = container_internal::map_slot_policy<K, V>;
  using slot_type = typename slot_policy::slot_type;
  using key_type = K;
  using mapped_type = V;
  using init_type = std::pair</*non const*/ key_type, mapped_type>;

  template <class Allocator, class... Args>
  static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
    slot_policy::construct(alloc, slot, std::forward<Args>(args)...);
  }

  template <class Allocator>
  static void destroy(Allocator* alloc, slot_type* slot) {
    slot_policy::destroy(alloc, slot);
  }

  template <class Allocator>
  static void transfer(Allocator* alloc, slot_type* new_slot,
                       slot_type* old_slot) {
    slot_policy::transfer(alloc, new_slot, old_slot);
  }

  template <class F, class... Args>
  static decltype(absl::container_internal::DecomposePair(
      std::declval<F>(), std::declval<Args>()...))
  apply(F&& f, Args&&... args) {
    return absl::container_internal::DecomposePair(std::forward<F>(f),
                                                   std::forward<Args>(args)...);
  }

  static size_t space_used(const slot_type*) { return 0; }

  static std::pair<const K, V>& element(slot_type* slot) { return slot->value; }

  static V& value(std::pair<const K, V>* kv) { return kv->second; }
  static const V& value(const std::pair<const K, V>* kv) { return kv->second; }
};

}  // namespace container_internal

namespace container_algorithm_internal {

// Specialization of trait in absl/algorithm/container.h
template <class Key, class T, class Hash, class KeyEqual, class Allocator>
struct IsUnorderedContainer<
    absl::flat_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {};

}  // namespace container_algorithm_internal

ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_CONTAINER_FLAT_HASH_MAP_H_