1/**
2 * MIT License
3 *
4 * Copyright (c) 2017 Tessil
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24#ifndef TSL_ORDERED_MAP_H
25#define TSL_ORDERED_MAP_H
26
27
28#include <cstddef>
29#include <deque>
30#include <functional>
31#include <initializer_list>
32#include <memory>
33#include <type_traits>
34#include <utility>
35#include <vector>
36#include "ordered_hash.h"
37
38
39namespace tsl {
40
41
42/**
43 * Implementation of an hash map using open adressing with robin hood with backshift delete to resolve collisions.
44 *
45 * The particularity of this hash map is that it remembers the order in which the elements were added and
46 * provide a way to access the structure which stores these values through the 'values_container()' method.
47 * The used container is defined by ValueTypeContainer, by default a std::deque is used (grows faster) but
48 * a std::vector may be used. In this case the map provides a 'data()' method which give a direct access
49 * to the memory used to store the values (which can be usefull to communicate with C API's).
50 *
51 * The Key and T must be copy constructible and/or move constructible. To use `unordered_erase` they both
52 * must be swappable.
53 *
54 * The behaviour of the hash map is undefinded if the destructor of Key or T throws an exception.
55 *
56 * Iterators invalidation:
57 * - clear, operator=, reserve, rehash: always invalidate the iterators (also invalidate end()).
58 * - insert, emplace, emplace_hint, operator[]: when a std::vector is used as ValueTypeContainer
59 * and if size() < capacity(), only end().
60 * Otherwise all the iterators are invalidated if an insert occurs.
61 * - erase, unordered_erase: when a std::vector is used as ValueTypeContainer invalidate the iterator of
62 * the erased element and all the ones after the erased element (including end()).
63 * Otherwise all the iterators are invalidated if an erase occurs.
64 */
65template<class Key,
66 class T,
67 class Hash = std::hash<Key>,
68 class KeyEqual = std::equal_to<Key>,
69 class Allocator = std::allocator<std::pair<Key, T>>,
70 class ValueTypeContainer = std::deque<std::pair<Key, T>, Allocator>>
71class ordered_map {
72private:
73 template<typename U>
74 using has_is_transparent = tsl::detail_ordered_hash::has_is_transparent<U>;
75
76 class KeySelect {
77 public:
78 using key_type = Key;
79
80 const key_type& operator()(const std::pair<Key, T>& key_value) const noexcept {
81 return key_value.first;
82 }
83
84 key_type& operator()(std::pair<Key, T>& key_value) noexcept {
85 return key_value.first;
86 }
87 };
88
89 class ValueSelect {
90 public:
91 using value_type = T;
92
93 const value_type& operator()(const std::pair<Key, T>& key_value) const noexcept {
94 return key_value.second;
95 }
96
97 value_type& operator()(std::pair<Key, T>& key_value) noexcept {
98 return key_value.second;
99 }
100 };
101
102 using ht = detail_ordered_hash::ordered_hash<std::pair<Key, T>, KeySelect, ValueSelect,
103 Hash, KeyEqual, Allocator, ValueTypeContainer>;
104
105public:
106 using key_type = typename ht::key_type;
107 using mapped_type = T;
108 using value_type = typename ht::value_type;
109 using size_type = typename ht::size_type;
110 using difference_type = typename ht::difference_type;
111 using hasher = typename ht::hasher;
112 using key_equal = typename ht::key_equal;
113 using allocator_type = typename ht::allocator_type;
114 using reference = typename ht::reference;
115 using const_reference = typename ht::const_reference;
116 using pointer = typename ht::pointer;
117 using const_pointer = typename ht::const_pointer;
118 using iterator = typename ht::iterator;
119 using const_iterator = typename ht::const_iterator;
120 using reverse_iterator = typename ht::reverse_iterator;
121 using const_reverse_iterator = typename ht::const_reverse_iterator;
122
123 using values_container_type = typename ht::values_container_type;
124
125
126 /*
127 * Constructors
128 */
129 ordered_map(): ordered_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {
130 }
131
132 explicit ordered_map(size_type bucket_count,
133 const Hash& hash = Hash(),
134 const KeyEqual& equal = KeyEqual(),
135 const Allocator& alloc = Allocator()):
136 m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR)
137 {
138 }
139
140 ordered_map(size_type bucket_count,
141 const Allocator& alloc): ordered_map(bucket_count, Hash(), KeyEqual(), alloc)
142 {
143 }
144
145 ordered_map(size_type bucket_count,
146 const Hash& hash,
147 const Allocator& alloc): ordered_map(bucket_count, hash, KeyEqual(), alloc)
148 {
149 }
150
151 explicit ordered_map(const Allocator& alloc): ordered_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {
152 }
153
154 template<class InputIt>
155 ordered_map(InputIt first, InputIt last,
156 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
157 const Hash& hash = Hash(),
158 const KeyEqual& equal = KeyEqual(),
159 const Allocator& alloc = Allocator()): ordered_map(bucket_count, hash, equal, alloc)
160 {
161 insert(first, last);
162 }
163
164 template<class InputIt>
165 ordered_map(InputIt first, InputIt last,
166 size_type bucket_count,
167 const Allocator& alloc): ordered_map(first, last, bucket_count, Hash(), KeyEqual(), alloc)
168 {
169 }
170
171 template<class InputIt>
172 ordered_map(InputIt first, InputIt last,
173 size_type bucket_count,
174 const Hash& hash,
175 const Allocator& alloc): ordered_map(first, last, bucket_count, hash, KeyEqual(), alloc)
176 {
177 }
178
179 ordered_map(std::initializer_list<value_type> init,
180 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
181 const Hash& hash = Hash(),
182 const KeyEqual& equal = KeyEqual(),
183 const Allocator& alloc = Allocator()):
184 ordered_map(init.begin(), init.end(), bucket_count, hash, equal, alloc)
185 {
186 }
187
188 ordered_map(std::initializer_list<value_type> init,
189 size_type bucket_count,
190 const Allocator& alloc):
191 ordered_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
192 {
193 }
194
195 ordered_map(std::initializer_list<value_type> init,
196 size_type bucket_count,
197 const Hash& hash,
198 const Allocator& alloc):
199 ordered_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
200 {
201 }
202
203
204 ordered_map& operator=(std::initializer_list<value_type> ilist) {
205 m_ht.clear();
206
207 m_ht.reserve(ilist.size());
208 m_ht.insert(ilist.begin(), ilist.end());
209
210 return *this;
211 }
212
213 allocator_type get_allocator() const { return m_ht.get_allocator(); }
214
215
216
217 /*
218 * Iterators
219 */
220 iterator begin() noexcept { return m_ht.begin(); }
221 const_iterator begin() const noexcept { return m_ht.begin(); }
222 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
223
224 iterator end() noexcept { return m_ht.end(); }
225 const_iterator end() const noexcept { return m_ht.end(); }
226 const_iterator cend() const noexcept { return m_ht.cend(); }
227
228 reverse_iterator rbegin() noexcept { return m_ht.rbegin(); }
229 const_reverse_iterator rbegin() const noexcept { return m_ht.rbegin(); }
230 const_reverse_iterator rcbegin() const noexcept { return m_ht.rcbegin(); }
231
232 reverse_iterator rend() noexcept { return m_ht.rend(); }
233 const_reverse_iterator rend() const noexcept { return m_ht.rend(); }
234 const_reverse_iterator rcend() const noexcept { return m_ht.rcend(); }
235
236
237 /*
238 * Capacity
239 */
240 bool empty() const noexcept { return m_ht.empty(); }
241 size_type size() const noexcept { return m_ht.size(); }
242 size_type max_size() const noexcept { return m_ht.max_size(); }
243
244 /*
245 * Modifiers
246 */
247 void clear() noexcept { m_ht.clear(); }
248
249
250
251 std::pair<iterator, bool> insert(const value_type& value) { return m_ht.insert(value); }
252
253 template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr>
254 std::pair<iterator, bool> insert(P&& value) { return m_ht.emplace(std::forward<P>(value)); }
255
256 std::pair<iterator, bool> insert(value_type&& value) { return m_ht.insert(std::move(value)); }
257
258
259 iterator insert(const_iterator hint, const value_type& value) {
260 return m_ht.insert(hint, value);
261 }
262
263 template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr>
264 iterator insert(const_iterator hint, P&& value) {
265 return m_ht.emplace_hint(hint, std::forward<P>(value));
266 }
267
268 iterator insert(const_iterator hint, value_type&& value) {
269 return m_ht.insert(hint, std::move(value));
270 }
271
272
273 template<class InputIt>
274 void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
275 void insert(std::initializer_list<value_type> ilist) { m_ht.insert(ilist.begin(), ilist.end()); }
276
277
278
279
280 template<class M>
281 std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) {
282 return m_ht.insert_or_assign(k, std::forward<M>(obj));
283 }
284
285 template<class M>
286 std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
287 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
288 }
289
290
291 template<class M>
292 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj) {
293 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
294 }
295
296 template<class M>
297 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) {
298 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
299 }
300
301 /**
302 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
303 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
304 *
305 * Mainly here for compatibility with the std::unordered_map interface.
306 */
307 template<class... Args>
308 std::pair<iterator, bool> emplace(Args&&... args) { return m_ht.emplace(std::forward<Args>(args)...); }
309
310 /**
311 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value once.
312 * The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
313 *
314 * Mainly here for compatibility with the std::unordered_map interface.
315 */
316 template <class... Args>
317 iterator emplace_hint(const_iterator hint, Args&&... args) {
318 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
319 }
320
321
322
323
324 template<class... Args>
325 std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) {
326 return m_ht.try_emplace(k, std::forward<Args>(args)...);
327 }
328
329 template<class... Args>
330 std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
331 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
332 }
333
334 template<class... Args>
335 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) {
336 return m_ht.try_emplace(hint, k, std::forward<Args>(args)...);
337 }
338
339 template<class... Args>
340 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) {
341 return m_ht.try_emplace(hint, std::move(k), std::forward<Args>(args)...);
342 }
343
344
345
346
347 /**
348 * When erasing an element, the insert order will be preserved and no holes will be present in the container
349 * returned by 'values_container()'.
350 *
351 * The method is in O(n), if the order is not important 'unordered_erase(...)' method is faster with an O(1)
352 * average complexity.
353 */
354 iterator erase(iterator pos) { return m_ht.erase(pos); }
355
356 /**
357 * @copydoc erase(iterator pos)
358 */
359 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
360
361 /**
362 * @copydoc erase(iterator pos)
363 */
364 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
365
366 /**
367 * @copydoc erase(iterator pos)
368 */
369 size_type erase(const key_type& key) { return m_ht.erase(key); }
370
371 /**
372 * @copydoc erase(iterator pos)
373 *
374 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
375 * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
376 */
377 size_type erase(const key_type& key, std::size_t precalculated_hash) {
378 return m_ht.erase(key, precalculated_hash);
379 }
380
381 /**
382 * @copydoc erase(iterator pos)
383 *
384 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
385 * If so, K must be hashable and comparable to Key.
386 */
387 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
388 size_type erase(const K& key) { return m_ht.erase(key); }
389
390 /**
391 * @copydoc erase(const key_type& key, std::size_t precalculated_hash)
392 *
393 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
394 * If so, K must be hashable and comparable to Key.
395 */
396 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
397 size_type erase(const K& key, std::size_t precalculated_hash) {
398 return m_ht.erase(key, precalculated_hash);
399 }
400
401
402
403 void swap(ordered_map& other) { other.m_ht.swap(m_ht); }
404
405 /*
406 * Lookup
407 */
408 T& at(const Key& key) { return m_ht.at(key); }
409
410 /**
411 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
412 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
413 */
414 T& at(const Key& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); }
415
416
417 const T& at(const Key& key) const { return m_ht.at(key); }
418
419 /**
420 * @copydoc at(const Key& key, std::size_t precalculated_hash)
421 */
422 const T& at(const Key& key, std::size_t precalculated_hash) const { return m_ht.at(key, precalculated_hash); }
423
424
425 /**
426 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
427 * If so, K must be hashable and comparable to Key.
428 */
429 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
430 T& at(const K& key) { return m_ht.at(key); }
431
432 /**
433 * @copydoc at(const K& key)
434 *
435 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
436 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
437 */
438 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
439 T& at(const K& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); }
440
441 /**
442 * @copydoc at(const K& key)
443 */
444 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
445 const T& at(const K& key) const { return m_ht.at(key); }
446
447 /**
448 * @copydoc at(const K& key, std::size_t precalculated_hash)
449 */
450 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
451 const T& at(const K& key, std::size_t precalculated_hash) const { return m_ht.at(key, precalculated_hash); }
452
453
454
455 T& operator[](const Key& key) { return m_ht[key]; }
456 T& operator[](Key&& key) { return m_ht[std::move(key)]; }
457
458
459
460 size_type count(const Key& key) const { return m_ht.count(key); }
461
462 /**
463 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
464 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
465 */
466 size_type count(const Key& key, std::size_t precalculated_hash) const {
467 return m_ht.count(key, precalculated_hash);
468 }
469
470 /**
471 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
472 * If so, K must be hashable and comparable to Key.
473 */
474 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
475 size_type count(const K& key) const { return m_ht.count(key); }
476
477 /**
478 * @copydoc count(const K& key) const
479 *
480 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
481 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
482 */
483 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
484 size_type count(const K& key, std::size_t precalculated_hash) const {
485 return m_ht.count(key, precalculated_hash);
486 }
487
488
489
490 iterator find(const Key& key) { return m_ht.find(key); }
491
492 /**
493 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
494 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
495 */
496 iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
497
498 const_iterator find(const Key& key) const { return m_ht.find(key); }
499
500 /**
501 * @copydoc find(const Key& key, std::size_t precalculated_hash)
502 */
503 const_iterator find(const Key& key, std::size_t precalculated_hash) const {
504 return m_ht.find(key, precalculated_hash);
505 }
506
507 /**
508 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
509 * If so, K must be hashable and comparable to Key.
510 */
511 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
512 iterator find(const K& key) { return m_ht.find(key); }
513
514 /**
515 * @copydoc find(const K& key)
516 *
517 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
518 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
519 */
520 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
521 iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
522
523 /**
524 * @copydoc find(const K& key)
525 */
526 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
527 const_iterator find(const K& key) const { return m_ht.find(key); }
528
529 /**
530 * @copydoc find(const K& key)
531 *
532 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
533 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
534 */
535 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
536 const_iterator find(const K& key, std::size_t precalculated_hash) const {
537 return m_ht.find(key, precalculated_hash);
538 }
539
540
541
542 std::pair<iterator, iterator> equal_range(const Key& key) { return m_ht.equal_range(key); }
543
544 /**
545 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
546 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
547 */
548 std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) {
549 return m_ht.equal_range(key, precalculated_hash);
550 }
551
552 std::pair<const_iterator, const_iterator> equal_range(const Key& key) const { return m_ht.equal_range(key); }
553
554 /**
555 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
556 */
557 std::pair<const_iterator, const_iterator> equal_range(const Key& key, std::size_t precalculated_hash) const {
558 return m_ht.equal_range(key, precalculated_hash);
559 }
560
561 /**
562 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
563 * If so, K must be hashable and comparable to Key.
564 */
565 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
566 std::pair<iterator, iterator> equal_range(const K& key) { return m_ht.equal_range(key); }
567
568 /**
569 * @copydoc equal_range(const K& key)
570 *
571 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
572 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
573 */
574 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
575 std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) {
576 return m_ht.equal_range(key, precalculated_hash);
577 }
578
579 /**
580 * @copydoc equal_range(const K& key)
581 */
582 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
583 std::pair<const_iterator, const_iterator> equal_range(const K& key) const { return m_ht.equal_range(key); }
584
585 /**
586 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
587 */
588 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
589 std::pair<const_iterator, const_iterator> equal_range(const K& key, std::size_t precalculated_hash) const {
590 return m_ht.equal_range(key, precalculated_hash);
591 }
592
593
594
595 /*
596 * Bucket interface
597 */
598 size_type bucket_count() const { return m_ht.bucket_count(); }
599 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
600
601
602 /*
603 * Hash policy
604 */
605 float load_factor() const { return m_ht.load_factor(); }
606 float max_load_factor() const { return m_ht.max_load_factor(); }
607 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
608
609 void rehash(size_type count) { m_ht.rehash(count); }
610 void reserve(size_type count) { m_ht.reserve(count); }
611
612
613 /*
614 * Observers
615 */
616 hasher hash_function() const { return m_ht.hash_function(); }
617 key_equal key_eq() const { return m_ht.key_eq(); }
618
619
620
621 /*
622 * Other
623 */
624
625 /**
626 * Convert a const_iterator to an iterator.
627 */
628 iterator mutable_iterator(const_iterator pos) {
629 return m_ht.mutable_iterator(pos);
630 }
631
632 /**
633 * Requires index <= size().
634 *
635 * Return an iterator to the element at index. Return end() if index == size().
636 */
637 iterator nth(size_type index) { return m_ht.nth(index); }
638
639 /**
640 * @copydoc nth(size_type index)
641 */
642 const_iterator nth(size_type index) const { return m_ht.nth(index); }
643
644
645 /**
646 * Return const_reference to the first element. Requires the container to not be empty.
647 */
648 const_reference front() const { return m_ht.front(); }
649
650 /**
651 * Return const_reference to the last element. Requires the container to not be empty.
652 */
653 const_reference back() const { return m_ht.back(); }
654
655
656 /**
657 * Only available if ValueTypeContainer is a std::vector. Same as calling 'values_container().data()'.
658 */
659 template<class U = values_container_type, typename std::enable_if<tsl::detail_ordered_hash::is_vector<U>::value>::type* = nullptr>
660 const typename values_container_type::value_type* data() const noexcept { return m_ht.data(); }
661
662 /**
663 * Return the container in which the values are stored. The values are in the same order as the insertion order
664 * and are contiguous in the structure, no holes (size() == values_container().size()).
665 */
666 const values_container_type& values_container() const noexcept { return m_ht.values_container(); }
667
668 template<class U = values_container_type, typename std::enable_if<tsl::detail_ordered_hash::is_vector<U>::value>::type* = nullptr>
669 size_type capacity() const noexcept { return m_ht.capacity(); }
670
671 void shrink_to_fit() { m_ht.shrink_to_fit(); }
672
673
674
675 /**
676 * Insert the value before pos shifting all the elements on the right of pos (including pos) one position
677 * to the right.
678 *
679 * Amortized linear time-complexity in the distance between pos and end().
680 */
681 std::pair<iterator, bool> insert_at_position(const_iterator pos, const value_type& value) {
682 return m_ht.insert_at_position(pos, value);
683 }
684
685 /**
686 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
687 */
688 std::pair<iterator, bool> insert_at_position(const_iterator pos, value_type&& value) {
689 return m_ht.insert_at_position(pos, std::move(value));
690 }
691
692 /**
693 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
694 *
695 * Same as insert_at_position(pos, value_type(std::forward<Args>(args)...), mainly
696 * here for coherence.
697 */
698 template<class... Args>
699 std::pair<iterator, bool> emplace_at_position(const_iterator pos, Args&&... args) {
700 return m_ht.emplace_at_position(pos, std::forward<Args>(args)...);
701 }
702
703 /**
704 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
705 */
706 template<class... Args>
707 std::pair<iterator, bool> try_emplace_at_position(const_iterator pos, const key_type& k, Args&&... args) {
708 return m_ht.try_emplace_at_position(pos, k, std::forward<Args>(args)...);
709 }
710
711 /**
712 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
713 */
714 template<class... Args>
715 std::pair<iterator, bool> try_emplace_at_position(const_iterator pos, key_type&& k, Args&&... args) {
716 return m_ht.try_emplace_at_position(pos, std::move(k), std::forward<Args>(args)...);
717 }
718
719
720
721 void pop_back() { m_ht.pop_back(); }
722
723 /**
724 * Faster erase operation with an O(1) average complexity but it doesn't preserve the insertion order.
725 *
726 * If an erasure occurs, the last element of the map will take the place of the erased element.
727 */
728 iterator unordered_erase(iterator pos) { return m_ht.unordered_erase(pos); }
729
730 /**
731 * @copydoc unordered_erase(iterator pos)
732 */
733 iterator unordered_erase(const_iterator pos) { return m_ht.unordered_erase(pos); }
734
735 /**
736 * @copydoc unordered_erase(iterator pos)
737 */
738 size_type unordered_erase(const key_type& key) { return m_ht.unordered_erase(key); }
739
740 /**
741 * @copydoc unordered_erase(iterator pos)
742 *
743 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
744 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
745 */
746 size_type unordered_erase(const key_type& key, std::size_t precalculated_hash) {
747 return m_ht.unordered_erase(key, precalculated_hash);
748 }
749
750 /**
751 * @copydoc unordered_erase(iterator pos)
752 *
753 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
754 * If so, K must be hashable and comparable to Key.
755 */
756 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
757 size_type unordered_erase(const K& key) { return m_ht.unordered_erase(key); }
758
759 /**
760 * @copydoc unordered_erase(const K& key)
761 *
762 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
763 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
764 */
765 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
766 size_type unordered_erase(const K& key, std::size_t precalculated_hash) {
767 return m_ht.unordered_erase(key, precalculated_hash);
768 }
769
770
771
772 friend bool operator==(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht == rhs.m_ht; }
773 friend bool operator!=(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht != rhs.m_ht; }
774 friend bool operator<(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht < rhs.m_ht; }
775 friend bool operator<=(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht <= rhs.m_ht; }
776 friend bool operator>(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht > rhs.m_ht; }
777 friend bool operator>=(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht >= rhs.m_ht; }
778
779 friend void swap(ordered_map& lhs, ordered_map& rhs) { lhs.swap(rhs); }
780
781private:
782 ht m_ht;
783};
784
785} // end namespace tsl
786
787#endif
788