Embedded Template Library 1.0
Loading...
Searching...
No Matches
unordered_map.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2016 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_UNORDERED_MAP_INCLUDED
32#define ETL_UNORDERED_MAP_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "utility.h"
39#include "pool.h"
40#include "array.h"
42#include "hash.h"
43#include "type_traits.h"
44#include "nth_type.h"
45#include "parameter_type.h"
46#include "nullptr.h"
47#include "vector.h"
48#include "error_handler.h"
49#include "exception.h"
50#include "debug_count.h"
51#include "iterator.h"
52#include "placement_new.h"
53#include "initializer_list.h"
54
56
57#include <stddef.h>
58
59//*****************************************************************************
63//*****************************************************************************
64
65namespace etl
66{
67 //***************************************************************************
70 //***************************************************************************
80
81 //***************************************************************************
84 //***************************************************************************
86 {
87 public:
88
90 : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:full", ETL_UNORDERED_MAP_FILE_ID"A"), file_name_, line_number_)
91 {
92 }
93 };
94
95 //***************************************************************************
98 //***************************************************************************
100 {
101 public:
102
104 : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:range", ETL_UNORDERED_MAP_FILE_ID"B"), file_name_, line_number_)
105 {}
106 };
107
108 //***************************************************************************
111 //***************************************************************************
113 {
114 public:
115
117 : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:iterator", ETL_UNORDERED_MAP_FILE_ID"C"), file_name_, line_number_)
118 {
119 }
120 };
121
122 //***************************************************************************
126 //***************************************************************************
127 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
129 {
130 public:
131
132 typedef ETL_OR_STD::pair<const TKey, T> value_type;
133
134 typedef TKey key_type;
135 typedef T mapped_type;
136 typedef THash hasher;
137 typedef TKeyEqual key_equal;
138 typedef value_type& reference;
139 typedef const value_type& const_reference;
140#if ETL_USING_CPP11
141 typedef value_type&& rvalue_reference;
142#endif
143 typedef value_type* pointer;
144 typedef const value_type* const_pointer;
145 typedef size_t size_type;
146
149#if ETL_USING_CPP11
151#endif
153 typedef const mapped_type& const_mapped_reference;
154
155 typedef etl::forward_link<0> link_t; // Default link.
156
157 // The nodes that store the elements.
158 // The nodes that store the elements.
159 struct node_t : public link_t
160 {
161 node_t(const_reference key_value_pair_)
162 : key_value_pair(key_value_pair_)
163 {
164 }
165
166 value_type key_value_pair;
167 };
168
169 friend bool operator ==(const node_t& lhs, const node_t& rhs)
170 {
171 return (lhs.key_value_pair.first == rhs.key_value_pair.first) &&
172 (lhs.key_value_pair.second == rhs.key_value_pair.second);
173 }
174
175 friend bool operator !=(const node_t& lhs, const node_t& rhs)
176 {
177 return !(lhs == rhs);
178 }
179
180 protected:
181
183 typedef etl::ipool pool_t;
184
185 public:
186
187 // Local iterators iterate over one bucket.
188 typedef typename bucket_t::iterator local_iterator;
189 typedef typename bucket_t::const_iterator const_local_iterator;
190
191 //*********************************************************************
192 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, T>
193 {
194 public:
195
197 typedef typename iunordered_map::key_type key_type;
199 typedef typename iunordered_map::hasher hasher;
200 typedef typename iunordered_map::key_equal key_equal;
201 typedef typename iunordered_map::reference reference;
202 typedef typename iunordered_map::const_reference const_reference;
203 typedef typename iunordered_map::pointer pointer;
204 typedef typename iunordered_map::const_pointer const_pointer;
205 typedef typename iunordered_map::size_type size_type;
206
207 friend class iunordered_map;
208 friend class const_iterator;
209
210 //*********************************
211 iterator()
212 {
213 }
214
215 //*********************************
216 iterator(const iterator& other)
217 : pbuckets_end(other.pbuckets_end)
218 , pbucket(other.pbucket)
219 , inode(other.inode)
220 {
221 }
222
223 //*********************************
225 {
226 ++inode;
227
228 // The end of this node list?
229 if (inode == pbucket->end())
230 {
231 // Search for the next non-empty bucket.
232 ++pbucket;
233 while ((pbucket != pbuckets_end) && (pbucket->empty()))
234 {
235 ++pbucket;
236 }
237
238 // If not past the end, get the first node in the bucket.
239 if (pbucket != pbuckets_end)
240 {
241 inode = pbucket->begin();
242 }
243 }
244
245 return *this;
246 }
247
248 //*********************************
250 {
251 iterator temp(*this);
252 operator++();
253 return temp;
254 }
255
256 //*********************************
258 {
259 pbuckets_end = other.pbuckets_end;
260 pbucket = other.pbucket;
261 inode = other.inode;
262 return *this;
263 }
264
265 //*********************************
266 reference operator *() const
267 {
268 return inode->key_value_pair;
269 }
270
271 //*********************************
272 pointer operator &() const
273 {
274 return &(inode->key_value_pair);
275 }
276
277 //*********************************
278 pointer operator ->() const
279 {
280 return &(inode->key_value_pair);
281 }
282
283 //*********************************
284 friend bool operator == (const iterator& lhs, const iterator& rhs)
285 {
286 return lhs.compare(rhs);
287 }
288
289 //*********************************
290 friend bool operator != (const iterator& lhs, const iterator& rhs)
291 {
292 return !(lhs == rhs);
293 }
294
295 private:
296
297 //*********************************
299 : pbuckets_end(pbuckets_end_)
300 , pbucket(pbucket_)
301 , inode(inode_)
302 {
303 }
304
305 //*********************************
306 bool compare(const iterator& rhs) const
307 {
308 return rhs.inode == inode;
309 }
310
311 //*********************************
312 bucket_t& get_bucket()
313 {
314 return *pbucket;
315 }
316
317 //*********************************
318 bucket_t* get_bucket_list_iterator()
319 {
320 return pbucket;
321 }
322
323 //*********************************
324 local_iterator get_local_iterator()
325 {
326 return inode;
327 }
328
329 bucket_t* pbuckets_end;
330 bucket_t* pbucket;
331 local_iterator inode;
332 };
333
334 //*********************************************************************
335 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>
336 {
337 public:
338
340 typedef typename iunordered_map::key_type key_type;
342 typedef typename iunordered_map::hasher hasher;
343 typedef typename iunordered_map::key_equal key_equal;
344 typedef typename iunordered_map::reference reference;
345 typedef typename iunordered_map::const_reference const_reference;
346 typedef typename iunordered_map::pointer pointer;
347 typedef typename iunordered_map::const_pointer const_pointer;
348 typedef typename iunordered_map::size_type size_type;
349
350 friend class iunordered_map;
351 friend class iterator;
352
353 //*********************************
355 {
356 }
357
358 //*********************************
360 : pbuckets_end(other.pbuckets_end)
361 , pbucket(other.pbucket)
362 , inode(other.inode)
363 {
364 }
365
366 //*********************************
368 : pbuckets_end(other.pbuckets_end)
369 , pbucket(other.pbucket)
370 , inode(other.inode)
371 {
372 }
373
374 //*********************************
376 {
377 ++inode;
378
379 // The end of this node list?
380 if (inode == pbucket->end())
381 {
382 // Search for the next non-empty bucket.
383 ++pbucket;
384 while ((pbucket != pbuckets_end) && (pbucket->empty()))
385 {
386 ++pbucket;
387 }
388
389 // If not past the end, get the first node in the bucket.
390 if (pbucket != pbuckets_end)
391 {
392 inode = pbucket->begin();
393 }
394 }
395
396 return *this;
397 }
398
399 //*********************************
401 {
402 const_iterator temp(*this);
403 operator++();
404 return temp;
405 }
406
407 //*********************************
409 {
410 pbuckets_end = other.pbuckets_end;
411 pbucket = other.pbucket;
412 inode = other.inode;
413 return *this;
414 }
415
416 //*********************************
417 const_reference operator *() const
418 {
419 return inode->key_value_pair;
420 }
421
422 //*********************************
423 const_pointer operator &() const
424 {
425 return &(inode->key_value_pair);
426 }
427
428 //*********************************
429 const_pointer operator ->() const
430 {
431 return &(inode->key_value_pair);
432 }
433
434 //*********************************
435 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
436 {
437 return lhs.compare(rhs);
438 }
439
440 //*********************************
441 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
442 {
443 return !(lhs == rhs);
444 }
445
446 private:
447
448 //*********************************
450 : pbuckets_end(pbuckets_end_)
451 , pbucket(pbucket_)
452 , inode(inode_)
453 {
454 }
455
456 //*********************************
457 bool compare(const const_iterator& rhs) const
458 {
459 return rhs.inode == inode;
460 }
461
462 //*********************************
463 bucket_t& get_bucket()
464 {
465 return *pbucket;
466 }
467
468 //*********************************
469 bucket_t* get_bucket_list_iterator()
470 {
471 return pbucket;
472 }
473
474 //*********************************
475 local_iterator get_local_iterator()
476 {
477 return inode;
478 }
479
480 bucket_t* pbuckets_end;
481 bucket_t* pbucket;
482 local_iterator inode;
483 };
484
485 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
486
487 //*********************************************************************
490 //*********************************************************************
492 {
493 return iterator((pbuckets + number_of_buckets), first, first->begin());
494 }
495
496 //*********************************************************************
499 //*********************************************************************
501 {
502 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
503 }
504
505 //*********************************************************************
508 //*********************************************************************
510 {
511 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
512 }
513
514 //*********************************************************************
517 //*********************************************************************
518 local_iterator begin(size_t i)
519 {
520 return pbuckets[i].begin();
521 }
522
523 //*********************************************************************
526 //*********************************************************************
527 const_local_iterator begin(size_t i) const
528 {
529 return pbuckets[i].cbegin();
530 }
531
532 //*********************************************************************
535 //*********************************************************************
536 const_local_iterator cbegin(size_t i) const
537 {
538 return pbuckets[i].cbegin();
539 }
540
541 //*********************************************************************
544 //*********************************************************************
546 {
547 return iterator((pbuckets + number_of_buckets), last, last->end());
548 }
549
550 //*********************************************************************
553 //*********************************************************************
555 {
556 return const_iterator((pbuckets + number_of_buckets), last, last->end());
557 }
558
559 //*********************************************************************
562 //*********************************************************************
564 {
565 return const_iterator((pbuckets + number_of_buckets), last, last->end());
566 }
567
568 //*********************************************************************
571 //*********************************************************************
572 local_iterator end(size_t i)
573 {
574 return pbuckets[i].end();
575 }
576
577 //*********************************************************************
580 //*********************************************************************
581 const_local_iterator end(size_t i) const
582 {
583 return pbuckets[i].cend();
584 }
585
586 //*********************************************************************
589 //*********************************************************************
590 const_local_iterator cend(size_t i) const
591 {
592 return pbuckets[i].cend();
593 }
594
595 //*********************************************************************
598 //*********************************************************************
600 {
601 return key_hash_function(key) % number_of_buckets;
602 }
603
604#if ETL_USING_CPP11
605 //*********************************************************************
608 //*********************************************************************
610 size_type get_bucket_index(const K& key) const
611 {
612 return key_hash_function(key) % number_of_buckets;
613 }
614#endif
615
616 //*********************************************************************
619 //*********************************************************************
621 {
622 size_t index = bucket(key);
623
624 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
625 }
626
627#if ETL_USING_CPP11
628 //*********************************************************************
631 //*********************************************************************
633 size_type bucket_size(const K& key) const
634 {
635 size_t index = bucket(key);
636
637 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
638 }
639#endif
640
641 //*********************************************************************
644 //*********************************************************************
646 {
647 return number_of_buckets;
648 }
649
650 //*********************************************************************
653 //*********************************************************************
655 {
656 return number_of_buckets;
657 }
658
659#if ETL_USING_CPP11
660 //*********************************************************************
664 //*********************************************************************
665 mapped_reference operator [](rvalue_key_reference key)
666 {
667 // Find the bucket.
668 bucket_t* pbucket = pbuckets + get_bucket_index(key);
669
670 // Find the first node in the bucket.
671 local_iterator inode = pbucket->begin();
672
673 // Walk the list looking for the right one.
674 while (inode != pbucket->end())
675 {
676 // Equal keys?
677 if (key_equal_function(key, inode->key_value_pair.first))
678 {
679 // Found a match.
680 return inode->key_value_pair.second;
681 }
682 else
683 {
684 ++inode;
685 }
686 }
687
688 // Doesn't exist, so add a new one.
689 // Get a new node.
690 node_t* node = allocate_data_node();
691 node->clear();
692 ::new ((void*)etl::addressof(node->key_value_pair.first)) key_type(etl::move(key));
693 ::new ((void*)etl::addressof(node->key_value_pair.second)) mapped_type();
694 ETL_INCREMENT_DEBUG_COUNT;
695
696 pbucket->insert_after(pbucket->before_begin(), *node);
697
698 adjust_first_last_markers_after_insert(pbucket);
699
700 return pbucket->begin()->key_value_pair.second;
701 }
702#endif
703
704 //*********************************************************************
708 //*********************************************************************
710 {
711 // Find the bucket.
712 bucket_t* pbucket = pbuckets + get_bucket_index(key);
713
714 // Find the first node in the bucket.
715 local_iterator inode = pbucket->begin();
716
717 // Walk the list looking for the right one.
718 while (inode != pbucket->end())
719 {
720 // Equal keys?
721 if (key_equal_function(key, inode->key_value_pair.first))
722 {
723 // Found a match.
724 return inode->key_value_pair.second;
725 }
726 else
727 {
728 ++inode;
729 }
730 }
731
732 // Doesn't exist, so add a new one.
733 // Get a new node.
734 node_t* node = allocate_data_node();
735 node->clear();
736 ::new ((void*)etl::addressof(node->key_value_pair.first)) key_type(key);
737 ::new ((void*)etl::addressof(node->key_value_pair.second)) mapped_type();
738 ETL_INCREMENT_DEBUG_COUNT;
739
740 pbucket->insert_after(pbucket->before_begin(), *node);
741
742 adjust_first_last_markers_after_insert(pbucket);
743
744 return pbucket->begin()->key_value_pair.second;
745 }
746
747#if ETL_USING_CPP11
748 //*********************************************************************
752 //*********************************************************************
754 mapped_reference operator [](const K& key)
755 {
756 // Find the bucket.
757 bucket_t* pbucket = pbuckets + get_bucket_index(key);
758
759 // Find the first node in the bucket.
760 local_iterator inode = pbucket->begin();
761
762 // Walk the list looking for the right one.
763 while (inode != pbucket->end())
764 {
765 // Equal keys?
766 if (key_equal_function(key, inode->key_value_pair.first))
767 {
768 // Found a match.
769 return inode->key_value_pair.second;
770 }
771 else
772 {
773 ++inode;
774 }
775 }
776
777 // Doesn't exist, so add a new one.
778 // Get a new node.
779 node_t* node = allocate_data_node();
780 node->clear();
781 ::new ((void*)etl::addressof(node->key_value_pair.first)) key_type(key);
782 ::new ((void*)etl::addressof(node->key_value_pair.second)) mapped_type();
783 ETL_INCREMENT_DEBUG_COUNT;
784
785 pbucket->insert_after(pbucket->before_begin(), *node);
786
787 adjust_first_last_markers_after_insert(pbucket);
788
789 return pbucket->begin()->key_value_pair.second;
790 }
791#endif
792
793 //*********************************************************************
798 //*********************************************************************
800 {
801 // Find the bucket.
802 bucket_t* pbucket = pbuckets + get_bucket_index(key);
803
804 // Find the first node in the bucket.
805 local_iterator inode = pbucket->begin();
806
807 // Walk the list looking for the right one.
808 while (inode != pbucket->end())
809 {
810 // Equal keys?
811 if (key_equal_function(key, inode->key_value_pair.first))
812 {
813 // Found a match.
814 return inode->key_value_pair.second;
815 }
816 else
817 {
818 ++inode;
819 }
820 }
821
822 // Doesn't exist.
823 ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
824
825 return begin()->second;
826 }
827
828 //*********************************************************************
833 //*********************************************************************
835 {
836 // Find the bucket.
837 bucket_t* pbucket = pbuckets + get_bucket_index(key);
838
839 // Find the first node in the bucket.
840 local_iterator inode = pbucket->begin();
841
842 // Walk the list looking for the right one.
843 while (inode != pbucket->end())
844 {
845 // Equal keys?
846 if (key_equal_function(key, inode->key_value_pair.first))
847 {
848 // Found a match.
849 return inode->key_value_pair.second;
850 }
851 else
852 {
853 ++inode;
854 }
855 }
856
857 // Doesn't exist.
858 ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
859
860 return begin()->second;
861 }
862
863#if ETL_USING_CPP11
864 //*********************************************************************
869 //*********************************************************************
871 mapped_reference at(const K& key)
872 {
873 // Find the bucket.
874 bucket_t* pbucket = pbuckets + get_bucket_index(key);
875
876 // Find the first node in the bucket.
877 local_iterator inode = pbucket->begin();
878
879 // Walk the list looking for the right one.
880 while (inode != pbucket->end())
881 {
882 // Equal keys?
883 if (key_equal_function(key, inode->key_value_pair.first))
884 {
885 // Found a match.
886 return inode->key_value_pair.second;
887 }
888 else
889 {
890 ++inode;
891 }
892 }
893
894 // Doesn't exist.
895 ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
896
897 return begin()->second;
898 }
899#endif
900
901#if ETL_USING_CPP11
902 //*********************************************************************
907 //*********************************************************************
908 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
909 const_mapped_reference at(const K& key) const
910 {
911 // Find the bucket.
912 bucket_t* pbucket = pbuckets + get_bucket_index(key);
913
914 // Find the first node in the bucket.
915 local_iterator inode = pbucket->begin();
916
917 // Walk the list looking for the right one.
918 while (inode != pbucket->end())
919 {
920 // Equal keys?
921 if (key_equal_function(key, inode->key_value_pair.first))
922 {
923 // Found a match.
924 return inode->key_value_pair.second;
925 }
926 else
927 {
928 ++inode;
929 }
930 }
931
932 // Doesn't exist.
933 ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
934
935 return begin()->second;
936 }
937#endif
938
939 //*********************************************************************
945 //*********************************************************************
946 template <typename TIterator>
948 {
949#if ETL_IS_DEBUG_BUILD
950 difference_type d = etl::distance(first_, last_);
951 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_map_iterator));
952 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_map_full));
953#endif
954
955 clear();
956
957 while (first_ != last_)
958 {
959 insert(*first_);
960 ++first_;
961 }
962 }
963
964 //*********************************************************************
968 //*********************************************************************
969 ETL_OR_STD::pair<iterator, bool> insert(const_reference key_value_pair)
970 {
971 ETL_OR_STD::pair<iterator, bool> result(end(), false);
972
973 ETL_ASSERT(!full(), ETL_ERROR(unordered_map_full));
974
975 const key_type& key = key_value_pair.first;
976
977 // Get the hash index.
978 size_t index = get_bucket_index(key);
979
980 // Get the bucket & bucket iterator.
981 bucket_t* pbucket = pbuckets + index;
982 bucket_t& bucket = *pbucket;
983
984 // The first one in the bucket?
985 if (bucket.empty())
986 {
987 // Get a new node.
988 node_t* node = allocate_data_node();
989 node->clear();
990 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(key_value_pair);
991 ETL_INCREMENT_DEBUG_COUNT;
992
993 // Just add the pointer to the bucket;
994 bucket.insert_after(bucket.before_begin(), *node);
995
996 adjust_first_last_markers_after_insert(pbucket);
997
998 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
999 result.second = true;
1000 }
1001 else
1002 {
1003 // Step though the bucket looking for a place to insert.
1004 local_iterator inode_previous = bucket.before_begin();
1005 local_iterator inode = bucket.begin();
1006
1007 while (inode != bucket.end())
1008 {
1009 // Do we already have this key?
1010 if (key_equal_function(inode->key_value_pair.first, key))
1011 {
1012 break;
1013 }
1014
1016 ++inode;
1017 }
1018
1019 // Not already there?
1020 if (inode == bucket.end())
1021 {
1022 // Get a new node.
1023 node_t* node = allocate_data_node();
1024 node->clear();
1025 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(key_value_pair);
1026 ETL_INCREMENT_DEBUG_COUNT;
1027
1028 // Add the node to the end of the bucket;
1029 bucket.insert_after(inode_previous, *node);
1030 adjust_first_last_markers_after_insert(&bucket);
1032
1033 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
1034 result.second = true;
1035 }
1036 }
1037
1038 return result;
1039 }
1040
1041#if ETL_USING_CPP11
1042 //*********************************************************************
1046 //*********************************************************************
1047 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key_value_pair)
1048 {
1049 ETL_OR_STD::pair<iterator, bool> result(end(), false);
1050
1051 ETL_ASSERT(!full(), ETL_ERROR(unordered_map_full));
1052
1053 const key_type& key = key_value_pair.first;
1054
1055 // Get the hash index.
1056 size_t index = get_bucket_index(key);
1057
1058 // Get the bucket & bucket iterator.
1059 bucket_t* pbucket = pbuckets + index;
1060 bucket_t& bucket = *pbucket;
1061
1062 // The first one in the bucket?
1063 if (bucket.empty())
1064 {
1065 // Get a new node.
1066 node_t* node = allocate_data_node();
1067 node->clear();
1068 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(etl::move(key_value_pair));
1069 ETL_INCREMENT_DEBUG_COUNT;
1070
1071 // Just add the pointer to the bucket;
1072 bucket.insert_after(bucket.before_begin(), *node);
1073
1074 adjust_first_last_markers_after_insert(pbucket);
1075
1076 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
1077 result.second = true;
1078 }
1079 else
1080 {
1081 // Step though the bucket looking for a place to insert.
1082 local_iterator inode_previous = bucket.before_begin();
1083 local_iterator inode = bucket.begin();
1084
1085 while (inode != bucket.end())
1086 {
1087 // Do we already have this key?
1088 if (key_equal_function(inode->key_value_pair.first, key))
1089 {
1090 break;
1091 }
1092
1093 ++inode_previous;
1094 ++inode;
1095 }
1096
1097 // Not already there?
1098 if (inode == bucket.end())
1099 {
1100 // Get a new node.
1101 node_t* node = allocate_data_node();
1102 node->clear();
1103 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(etl::move(key_value_pair));
1104 ETL_INCREMENT_DEBUG_COUNT;
1105
1106 // Add the node to the end of the bucket;
1107 bucket.insert_after(inode_previous, *node);
1108 adjust_first_last_markers_after_insert(&bucket);
1109 ++inode_previous;
1110
1111 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
1112 result.second = true;
1113 }
1114 }
1115
1116 return result;
1117 }
1118#endif
1119
1120 //*********************************************************************
1125 //*********************************************************************
1126 iterator insert(const_iterator, const_reference key_value_pair)
1127 {
1128 return insert(key_value_pair).first;
1129 }
1130
1131#if ETL_USING_CPP11
1132 //*********************************************************************
1137 //*********************************************************************
1138 iterator insert(const_iterator, rvalue_reference key_value_pair)
1139 {
1140 return insert(etl::move(key_value_pair)).first;
1141 }
1142#endif
1143
1144 //*********************************************************************
1150 //*********************************************************************
1151 template <class TIterator>
1153 {
1154 while (first_ != last_)
1155 {
1156 insert(*first_);
1157 ++first_;
1158 }
1159 }
1160
1161 //*********************************************************************
1165 //*********************************************************************
1167 {
1168 size_t n = 0UL;
1169 size_t index = get_bucket_index(key);
1170
1171 bucket_t& bucket = pbuckets[index];
1172
1173 local_iterator iprevious = bucket.before_begin();
1174 local_iterator icurrent = bucket.begin();
1175
1176 // Search for the key, if we have it.
1177 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key_value_pair.first, key)))
1178 {
1179 ++iprevious;
1180 ++icurrent;
1181 }
1182
1183 // Did we find it?
1184 if (icurrent != bucket.end())
1185 {
1186 delete_data_node(iprevious, icurrent, bucket);
1187 n = 1;
1188 }
1189
1190 return n;
1191 }
1192
1193#if ETL_USING_CPP11
1194 //*********************************************************************
1198 //*********************************************************************
1200 size_t erase(const K& key)
1201 {
1202 size_t n = 0UL;
1203 size_t index = get_bucket_index(key);
1204
1205 bucket_t& bucket = pbuckets[index];
1206
1207 local_iterator iprevious = bucket.before_begin();
1208 local_iterator icurrent = bucket.begin();
1209
1210 // Search for the key, if we have it.
1211 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key_value_pair.first, key)))
1212 {
1213 ++iprevious;
1214 ++icurrent;
1215 }
1216
1217 // Did we find it?
1218 if (icurrent != bucket.end())
1219 {
1220 delete_data_node(iprevious, icurrent, bucket);
1221 n = 1;
1222 }
1223
1224 return n;
1225 }
1226#endif
1227
1228 //*********************************************************************
1231 //*********************************************************************
1233 {
1234 // Make a note of the next one.
1235 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
1236 ++inext;
1237
1238 bucket_t& bucket = ielement.get_bucket();
1239 local_iterator iprevious = bucket.before_begin();
1240 local_iterator icurrent = ielement.get_local_iterator();
1241
1242 // Find the node previous to the one we're interested in.
1243 while (iprevious->etl_next != &*icurrent)
1244 {
1245 ++iprevious;
1246 }
1247
1248 delete_data_node(iprevious, icurrent, bucket);
1249
1250 return inext;
1251 }
1252
1253 //*********************************************************************
1259 //*********************************************************************
1261 {
1262 // Erasing everything?
1263 if ((first_ == begin()) && (last_ == end()))
1264 {
1265 clear();
1266 return end();
1267 }
1268
1269 // Get the starting point.
1270 bucket_t* pbucket = first_.get_bucket_list_iterator();
1271 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
1272 local_iterator iprevious = pbucket->before_begin();
1273 local_iterator icurrent = first_.get_local_iterator();
1274 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
1275
1276 // Find the node previous to the first one.
1277 while (iprevious->etl_next != &*icurrent)
1278 {
1279 ++iprevious;
1280 }
1281
1282 // Remember the item before the first erased one.
1283 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
1284
1285 // Until we reach the end.
1286 while ((icurrent != iend) || (pbucket != pend_bucket))
1287 {
1288 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
1289
1290 // Have we not reached the end?
1291 if ((icurrent != iend) || (pbucket != pend_bucket))
1292 {
1293 // At the end of this bucket?
1294 if ((icurrent == pbucket->end()))
1295 {
1296 // Find the next non-empty one.
1297 do
1298 {
1299 ++pbucket;
1300 } while (pbucket->empty());
1301
1302 iprevious = pbucket->before_begin();
1303 icurrent = pbucket->begin();
1304 }
1305 }
1306 }
1307
1308 return ++ibefore_erased;
1309 }
1310
1311 //*************************************************************************
1313 //*************************************************************************
1314 void clear()
1315 {
1316 initialise();
1317 }
1318
1319 //*********************************************************************
1323 //*********************************************************************
1324 size_t count(const_key_reference key) const
1325 {
1326 return (find(key) == end()) ? 0 : 1;
1327 }
1328
1329#if ETL_USING_CPP11
1330 //*********************************************************************
1334 //*********************************************************************
1336 size_t count(const K& key) const
1337 {
1338 return (find(key) == end()) ? 0 : 1;
1339 }
1340#endif
1341
1342 //*********************************************************************
1346 //*********************************************************************
1348 {
1349 size_t index = get_bucket_index(key);
1350
1351 bucket_t* pbucket = pbuckets + index;
1352 bucket_t& bucket = *pbucket;
1353
1354 // Is the bucket not empty?
1355 if (!bucket.empty())
1356 {
1357 // Step though the list until we find the end or an equivalent key.
1358 local_iterator inode = bucket.begin();
1359 local_iterator iend = bucket.end();
1360
1361 while (inode != iend)
1362 {
1363 // Do we have this one?
1364 if (key_equal_function(key, inode->key_value_pair.first))
1365 {
1366 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1367 }
1368
1369 ++inode;
1370 }
1371 }
1372
1373 return end();
1374 }
1375
1376 //*********************************************************************
1380 //*********************************************************************
1382 {
1383 size_t index = get_bucket_index(key);
1384
1385 bucket_t* pbucket = pbuckets + index;
1386 bucket_t& bucket = *pbucket;
1387
1388 // Is the bucket not empty?
1389 if (!bucket.empty())
1390 {
1391 // Step though the list until we find the end or an equivalent key.
1392 local_iterator inode = bucket.begin();
1393 local_iterator iend = bucket.end();
1394
1395 while (inode != iend)
1396 {
1397 // Do we have this one?
1398 if (key_equal_function(key, inode->key_value_pair.first))
1399 {
1400 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1401 }
1402
1403 ++inode;
1404 }
1405 }
1406
1407 return end();
1408 }
1409
1410#if ETL_USING_CPP11
1411 //*********************************************************************
1415 //*********************************************************************
1417 iterator find(const K& key)
1418 {
1419 size_t index = get_bucket_index(key);
1420
1421 bucket_t* pbucket = pbuckets + index;
1422 bucket_t& bucket = *pbucket;
1423
1424 // Is the bucket not empty?
1425 if (!bucket.empty())
1426 {
1427 // Step though the list until we find the end or an equivalent key.
1428 local_iterator inode = bucket.begin();
1429 local_iterator iend = bucket.end();
1430
1431 while (inode != iend)
1432 {
1433 // Do we have this one?
1434 if (key_equal_function(key, inode->key_value_pair.first))
1435 {
1436 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1437 }
1438
1439 ++inode;
1440 }
1441 }
1442
1443 return end();
1444 }
1445#endif
1446
1447#if ETL_USING_CPP11
1448 //*********************************************************************
1452 //*********************************************************************
1453 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
1454 const_iterator find(const K& key) const
1455 {
1456 size_t index = get_bucket_index(key);
1457
1458 bucket_t* pbucket = pbuckets + index;
1459 bucket_t& bucket = *pbucket;
1460
1461 // Is the bucket not empty?
1462 if (!bucket.empty())
1463 {
1464 // Step though the list until we find the end or an equivalent key.
1465 local_iterator inode = bucket.begin();
1466 local_iterator iend = bucket.end();
1467
1468 while (inode != iend)
1469 {
1470 // Do we have this one?
1471 if (key_equal_function(key, inode->key_value_pair.first))
1472 {
1473 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1474 }
1475
1476 ++inode;
1477 }
1478 }
1479
1480 return end();
1481 }
1482#endif
1483
1484 //*********************************************************************
1491 //*********************************************************************
1492 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
1493 {
1494 iterator f = find(key);
1495 iterator l = f;
1496
1497 if (l != end())
1498 {
1499 ++l;
1500 }
1501
1502 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1503 }
1504
1505 //*********************************************************************
1512 //*********************************************************************
1513 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
1514 {
1515 const_iterator f = find(key);
1516 const_iterator l = f;
1517
1518 if (l != end())
1519 {
1520 ++l;
1521 }
1522
1523 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1524 }
1525
1526#if ETL_USING_CPP11
1527 //*********************************************************************
1534 //*********************************************************************
1536 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
1537 {
1538 iterator f = find(key);
1539 iterator l = f;
1540
1541 if (l != end())
1542 {
1543 ++l;
1544 }
1545
1546 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1547 }
1548#endif
1549
1550#if ETL_USING_CPP11
1551 //*********************************************************************
1558 //*********************************************************************
1559 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
1560 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1561 {
1562 const_iterator f = find(key);
1563 const_iterator l = f;
1564
1565 if (l != end())
1566 {
1567 ++l;
1568 }
1569
1570 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1571 }
1572#endif
1573
1574 //*************************************************************************
1576 //*************************************************************************
1578 {
1579 return pnodepool->size();
1580 }
1581
1582 //*************************************************************************
1584 //*************************************************************************
1586 {
1587 return pnodepool->max_size();
1588 }
1589
1590 //*************************************************************************
1592 //*************************************************************************
1594 {
1595 return pnodepool->max_size();
1596 }
1597
1598 //*************************************************************************
1600 //*************************************************************************
1601 bool empty() const
1602 {
1603 return pnodepool->empty();
1604 }
1605
1606 //*************************************************************************
1608 //*************************************************************************
1609 bool full() const
1610 {
1611 return pnodepool->full();
1612 }
1613
1614 //*************************************************************************
1617 //*************************************************************************
1618 size_t available() const
1619 {
1620 return pnodepool->available();
1621 }
1622
1623 //*************************************************************************
1626 //*************************************************************************
1627 float load_factor() const
1628 {
1629 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1630 }
1631
1632 //*************************************************************************
1635 //*************************************************************************
1637 {
1638 return key_hash_function;
1639 }
1640
1641 //*************************************************************************
1644 //*************************************************************************
1646 {
1647 return key_equal_function;
1648 }
1649
1650 //*************************************************************************
1652 //*************************************************************************
1654 {
1655 // Skip if doing self assignment
1656 if (this != &rhs)
1657 {
1658 key_hash_function = rhs.hash_function();
1659 key_equal_function = rhs.key_eq();
1660 assign(rhs.cbegin(), rhs.cend());
1661 }
1662
1663 return *this;
1664 }
1665#if ETL_USING_CPP11
1666 //*************************************************************************
1668 //*************************************************************************
1670 {
1671 // Skip if doing self assignment
1672 if (this != &rhs)
1673 {
1674 clear();
1675 key_hash_function = rhs.hash_function();
1676 key_equal_function = rhs.key_eq();
1677 this->move(rhs.begin(), rhs.end());
1678 }
1679
1680 return *this;
1681 }
1682#endif
1683
1684 //*************************************************************************
1686 //*************************************************************************
1688 {
1689 return find(key) != end();
1690 }
1691
1692#if ETL_USING_CPP11
1693 //*************************************************************************
1695 //*************************************************************************
1697 bool contains(const K& key) const
1698 {
1699 return find(key) != end();
1700 }
1701#endif
1702
1703 protected:
1704
1705 //*********************************************************************
1707 //*********************************************************************
1709 : pnodepool(&node_pool_)
1710 , pbuckets(pbuckets_)
1711 , number_of_buckets(number_of_buckets_)
1712 , first(pbuckets)
1713 , last(pbuckets)
1714 , key_hash_function(key_hash_function_)
1715 , key_equal_function(key_equal_function_)
1716 {
1717 }
1718
1719 //*********************************************************************
1721 //*********************************************************************
1723 {
1724 if (!empty())
1725 {
1726 // For each bucket...
1727 for (size_t i = 0UL; i < number_of_buckets; ++i)
1728 {
1729 bucket_t& bucket = pbuckets[i];
1730
1731 if (!bucket.empty())
1732 {
1733 // For each item in the bucket...
1734 local_iterator it = bucket.begin();
1735
1736 while (it != bucket.end())
1737 {
1738 // Destroy the value contents.
1739 it->key_value_pair.~value_type();
1740 ETL_DECREMENT_DEBUG_COUNT;
1741
1742 ++it;
1743 }
1744
1745 // Now it's safe to clear the bucket.
1746 bucket.clear();
1747 }
1748 }
1749
1750 // Now it's safe to clear the entire pool in one go.
1751 pnodepool->release_all();
1752 }
1753
1754 first = pbuckets;
1755 last = first;
1756 }
1757
1758#if ETL_USING_CPP11
1759 //*************************************************************************
1761 //*************************************************************************
1762 void move(iterator b, iterator e)
1763 {
1764 while (b != e)
1765 {
1766 iterator temp = b;
1767 ++temp;
1768 insert(etl::move(*b));
1769 b = temp;
1770 }
1771 }
1772#endif
1773
1774 private:
1775
1776 //*************************************************************************
1778 //*************************************************************************
1779 node_t* allocate_data_node()
1780 {
1781 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1782 return (pnodepool->*func)();
1783 }
1784
1785 //*********************************************************************
1787 //*********************************************************************
1788 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1789 {
1790 if (size() == 1)
1791 {
1792 first = pbucket;
1793 last = pbucket;
1794 }
1795 else
1796 {
1797 if (pbucket < first)
1798 {
1799 first = pbucket;
1800 }
1801 else if (pbucket > last)
1802 {
1803 last = pbucket;
1804 }
1805 }
1806 }
1807
1808 //*********************************************************************
1810 //*********************************************************************
1811 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1812 {
1813 if (empty())
1814 {
1815 first = pbuckets;
1816 last = pbuckets;
1817 }
1818 else
1819 {
1820 if (pbucket == first)
1821 {
1822 // We erased the first so, we need to search again from where we erased.
1823 while (first->empty())
1824 {
1825 ++first;
1826 }
1827 }
1828 else if (pbucket == last)
1829 {
1830 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1831 pbucket = first;
1832 bucket_t* pend = last;
1833
1834 last = first;
1835
1836 while (pbucket != pend)
1837 {
1838 if (!pbucket->empty())
1839 {
1840 last = pbucket;
1841 }
1842
1843 ++pbucket;
1844 }
1845 }
1846 }
1847 }
1848
1849 //*********************************************************************
1851 //*********************************************************************
1852 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1853 {
1854 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1855 icurrent->key_value_pair.~value_type(); // Destroy the value.
1856 pnodepool->release(&*icurrent); // Release it back to the pool.
1857 adjust_first_last_markers_after_erase(&bucket);
1858 ETL_DECREMENT_DEBUG_COUNT;
1859
1860 return inext;
1861 }
1862
1863 // Disable copy construction.
1864 iunordered_map(const iunordered_map&);
1865
1867 pool_t* pnodepool;
1868
1870 bucket_t* pbuckets;
1871
1873 const size_t number_of_buckets;
1874
1876 bucket_t* first;
1877 bucket_t* last;
1878
1880 hasher key_hash_function;
1881
1883 key_equal key_equal_function;
1884
1886 ETL_DECLARE_DEBUG_COUNT;
1887
1888 //*************************************************************************
1890 //*************************************************************************
1891#if defined(ETL_POLYMORPHIC_UNORDERED_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1892 public:
1893 virtual ~iunordered_map()
1894 {
1895 }
1896#else
1897 protected:
1899 {
1900 }
1901#endif
1902 };
1903
1904 //***************************************************************************
1910 //***************************************************************************
1911 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1914 {
1915 const bool sizes_match = (lhs.size() == rhs.size());
1916 bool elements_match = true;
1917
1919
1920 if (sizes_match)
1921 {
1922 itr_t l_begin = lhs.begin();
1923 itr_t l_end = lhs.end();
1924
1925 while ((l_begin != l_end) && elements_match)
1926 {
1927 const TKey key = l_begin->first;
1928 const T l_value = l_begin->second;
1929
1930 // See if the lhs key exists in the rhs.
1931 ETL_OR_STD::pair<itr_t, itr_t> range = rhs.equal_range(key);
1932
1933 if (range.first != rhs.end())
1934 {
1935 // See if the values match
1936 const T r_value = range.first->second;
1937
1939 }
1940 else
1941 {
1942 elements_match = false;
1943 }
1944
1945 ++l_begin;
1946 }
1947 }
1948
1949 return (sizes_match && elements_match);
1950 }
1951
1952 //***************************************************************************
1958 //***************************************************************************
1959 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1965
1966 //*************************************************************************
1968 //*************************************************************************
1969 template <typename TKey, typename TValue, const size_t MAX_SIZE_, const size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
1970 class unordered_map : public etl::iunordered_map<TKey, TValue, THash, TKeyEqual>
1971 {
1972 private:
1973
1975
1976 public:
1977
1978 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1979 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1980
1981 //*************************************************************************
1983 //*************************************************************************
1984 unordered_map(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1985 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1986 {
1987 }
1988
1989 //*************************************************************************
1991 //*************************************************************************
1993 : base(node_pool, buckets, MAX_BUCKETS_, other.hash_function(), other.key_eq())
1994 {
1995 base::assign(other.cbegin(), other.cend());
1996 }
1997
1998#if ETL_USING_CPP11
1999 //*************************************************************************
2001 //*************************************************************************
2003 : base(node_pool, buckets, MAX_BUCKETS_, other.hash_function(), other.key_eq())
2004 {
2005 if (this != &other)
2006 {
2007 base::move(other.begin(), other.end());
2008 }
2009 }
2010#endif
2011
2012 //*************************************************************************
2017 //*************************************************************************
2018 template <typename TIterator>
2020 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
2021 {
2022 base::assign(first_, last_);
2023 }
2024
2025#if ETL_HAS_INITIALIZER_LIST
2026 //*************************************************************************
2028 //*************************************************************************
2029 unordered_map(std::initializer_list<ETL_OR_STD::pair<TKey, TValue>> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
2030 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
2031 {
2032 base::assign(init.begin(), init.end());
2033 }
2034#endif
2035
2036 //*************************************************************************
2038 //*************************************************************************
2040 {
2041 base::initialise();
2042 }
2043
2044 //*************************************************************************
2046 //*************************************************************************
2048 {
2049 base::operator=(rhs);
2050 return *this;
2051 }
2052
2053#if ETL_USING_CPP11
2054 //*************************************************************************
2056 //*************************************************************************
2058 {
2059 base::operator=(etl::move(rhs));
2060 return *this;
2061 }
2062#endif
2063
2064 private:
2065
2068
2070 typename base::bucket_t buckets[MAX_BUCKETS_];
2071 };
2072
2073 //*************************************************************************
2075 //*************************************************************************
2076#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2077 template <typename... TPairs>
2078 unordered_map(TPairs...) -> unordered_map<typename etl::nth_type_t<0, TPairs...>::first_type,
2079 typename etl::nth_type_t<0, TPairs...>::second_type,
2080 sizeof...(TPairs)>;
2081#endif
2082
2083 //*************************************************************************
2085 //*************************************************************************
2086#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2087 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... TPairs>
2088 constexpr auto make_unordered_map(TPairs&&... pairs) -> etl::unordered_map<TKey, T, sizeof...(TPairs), sizeof...(TPairs), THash, TKeyEqual>
2089 {
2090 return { etl::forward<TPairs>(pairs)... };
2091 }
2092#endif
2093}
2094
2095#endif
Definition unordered_map.h:336
Definition unordered_map.h:193
A templated unordered_map implementation that uses a fixed size buffer.
Definition unordered_map.h:1971
unordered_map(const unordered_map &other)
Copy constructor.
Definition unordered_map.h:1992
unordered_map(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_map.h:1984
~unordered_map()
Destructor.
Definition unordered_map.h:2039
unordered_map(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_map.h:2019
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
ETL_CONSTEXPR17 etl::enable_if<!etl::is_same< T, etl::nullptr_t >::value, T >::type * addressof(T &t)
Definition addressof.h:52
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:301
bool empty() const
Definition ipool.h:310
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:319
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:293
Definition ipool.h:102
float load_factor() const
Definition unordered_map.h:1627
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_map.h:1260
size_type get_bucket_index(const_key_reference key) const
Definition unordered_map.h:599
iterator begin()
Definition unordered_map.h:491
void initialise()
Initialise the unordered_map.
Definition unordered_map.h:1722
const_iterator find(const_key_reference key) const
Definition unordered_map.h:1381
size_type size() const
Gets the size of the unordered_map.
Definition unordered_map.h:1577
const_local_iterator cend(size_t i) const
Definition unordered_map.h:590
~iunordered_map()
Destructor.
Definition unordered_map.h:1898
iterator end()
Definition unordered_map.h:545
size_t available() const
Definition unordered_map.h:1618
local_iterator end(size_t i)
Definition unordered_map.h:572
hasher hash_function() const
Definition unordered_map.h:1636
const_local_iterator cbegin(size_t i) const
Definition unordered_map.h:536
local_iterator begin(size_t i)
Definition unordered_map.h:518
const_local_iterator end(size_t i) const
Definition unordered_map.h:581
iunordered_map & operator=(const iunordered_map &rhs)
Assignment operator.
Definition unordered_map.h:1653
size_type bucket_size(const_key_reference key) const
Definition unordered_map.h:620
void insert(TIterator first_, TIterator last_)
Definition unordered_map.h:1152
size_type max_bucket_count() const
Definition unordered_map.h:645
const_iterator end() const
Definition unordered_map.h:554
mapped_reference operator[](const_key_reference key)
Definition unordered_map.h:709
bool full() const
Checks to see if the unordered_map is full.
Definition unordered_map.h:1609
size_t count(const_key_reference key) const
Definition unordered_map.h:1324
iterator find(const_key_reference key)
Definition unordered_map.h:1347
bool contains(const_key_reference key) const
Check if the unordered_map contains the key.
Definition unordered_map.h:1687
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition unordered_map.h:1513
const_iterator begin() const
Definition unordered_map.h:500
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition unordered_map.h:1492
void clear()
Clears the unordered_map.
Definition unordered_map.h:1314
iterator erase(const_iterator ielement)
Definition unordered_map.h:1232
iunordered_map(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_map.h:1708
const_local_iterator begin(size_t i) const
Definition unordered_map.h:527
bool empty() const
Checks to see if the unordered_map is empty.
Definition unordered_map.h:1601
key_equal key_eq() const
Definition unordered_map.h:1645
mapped_reference at(const_key_reference key)
Definition unordered_map.h:799
size_t erase(const_key_reference key)
Definition unordered_map.h:1166
const key_type & const_key_reference
Defines the parameter types.
Definition unordered_map.h:148
size_type capacity() const
Gets the maximum possible size of the unordered_map.
Definition unordered_map.h:1593
size_type bucket_count() const
Definition unordered_map.h:654
const_iterator cend() const
Definition unordered_map.h:563
iterator insert(const_iterator, const_reference key_value_pair)
Definition unordered_map.h:1126
const_mapped_reference at(const_key_reference key) const
Definition unordered_map.h:834
size_type max_size() const
Gets the maximum possible size of the unordered_map.
Definition unordered_map.h:1585
ETL_OR_STD::pair< iterator, bool > insert(const_reference key_value_pair)
Definition unordered_map.h:969
void assign(TIterator first_, TIterator last_)
Definition unordered_map.h:947
const_iterator cbegin() const
Definition unordered_map.h:509
Definition unordered_map.h:129
Definition unordered_map.h:72
Definition unordered_map.h:86
Definition unordered_map.h:113
Definition unordered_map.h:100
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_map.h:160
pair holds two objects of arbitrary type
Definition utility.h:164
T1 first
first is a copy of the first object
Definition utility.h:168
T2 second
second is a copy of the second object
Definition utility.h:169