Embedded Template Library 1.0
flat_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) 2015 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_FLAT_MAP_INCLUDED
32#define ETL_FLAT_MAP_INCLUDED
33
34#include "platform.h"
35#include "reference_flat_map.h"
36#include "pool.h"
37#include "placement_new.h"
38#include "nth_type.h"
39#include "utility.h"
40#include "type_traits.h"
41#include "initializer_list.h"
42
44
45//*****************************************************************************
53//*****************************************************************************
54
55namespace etl
56{
57 //***************************************************************************
61 //***************************************************************************
62 template <typename TKey, typename TMapped, typename TKeyCompare = etl::less<TKey> >
63 class iflat_map : private etl::ireference_flat_map<TKey, TMapped, TKeyCompare>
64 {
65 private:
66
68 typedef typename refmap_t::lookup_t lookup_t;
69 typedef etl::ipool storage_t;
70
71 public:
72
73 typedef ETL_OR_STD::pair<const TKey, TMapped> value_type;
74 typedef TKey key_type;
75 typedef TMapped mapped_type;
76 typedef TKeyCompare key_compare;
77 typedef value_type& reference;
78 typedef const value_type& const_reference;
79#if ETL_USING_CPP11
80 typedef value_type&& rvalue_reference;
81#endif
82 typedef value_type* pointer;
83 typedef const value_type* const_pointer;
84 typedef size_t size_type;
85
86 typedef const key_type& const_key_reference;
87#if ETL_USING_CPP11
88 typedef key_type&& rvalue_key_reference;
89#endif
90 typedef mapped_type& mapped_reference;
91 typedef const mapped_type& const_mapped_reference;
92
93 typedef typename refmap_t::iterator iterator;
95
96 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
97 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
98 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
99
100 private:
101
102 //*********************************************************************
104 //*********************************************************************
105 class compare
106 {
107 public:
108
109 bool operator ()(const value_type& element, key_type key) const
110 {
111 return comp(element.first, key);
112 }
113
114 bool operator ()(key_type key, const value_type& element) const
115 {
116 return comp(key, element.first);
117 }
118
119 key_compare comp;
120 };
121
122 public:
123
124 //*********************************************************************
127 //*********************************************************************
129 {
130 return refmap_t::begin();
131 }
132
133 //*********************************************************************
136 //*********************************************************************
138 {
139 return refmap_t::begin();
140 }
141
142 //*********************************************************************
145 //*********************************************************************
147 {
148 return refmap_t::end();
149 }
150
151 //*********************************************************************
154 //*********************************************************************
156 {
157 return refmap_t::end();
158 }
159
160 //*********************************************************************
163 //*********************************************************************
165 {
166 return refmap_t::cbegin();
167 }
168
169 //*********************************************************************
172 //*********************************************************************
174 {
175 return refmap_t::cend();
176 }
177
178 //*********************************************************************
181 //*********************************************************************
182 reverse_iterator rbegin()
183 {
184 return refmap_t::rbegin();
185 }
186
187 //*********************************************************************
190 //*********************************************************************
191 const_reverse_iterator rbegin() const
192 {
193 return refmap_t::rbegin();
194 }
195
196 //*********************************************************************
199 //*********************************************************************
200 reverse_iterator rend()
201 {
202 return refmap_t::rend();
203 }
204
205 //*********************************************************************
208 //*********************************************************************
209 const_reverse_iterator rend() const
210 {
211 return refmap_t::rend();
212 }
213
214 //*********************************************************************
217 //*********************************************************************
218 const_reverse_iterator crbegin() const
219 {
220 return refmap_t::crbegin();
221 }
222
223 //*********************************************************************
226 //*********************************************************************
227 const_reverse_iterator crend() const
228 {
229 return refmap_t::crend();
230 }
231
232#if ETL_USING_CPP11
233 //*********************************************************************
237 //*********************************************************************
238 mapped_reference operator [](rvalue_key_reference key)
239 {
240 iterator i_element = lower_bound(key);
241
242 // Doesn't already exist?
243 if ((i_element == end()) || compare(key, i_element->first))
244 {
245 insert_default_value(i_element, etl::move(key));
246 }
247
248 return i_element->second;
249 }
250#endif
251
252 //*********************************************************************
256 //*********************************************************************
257 mapped_reference operator [](const_key_reference key)
258 {
259 iterator i_element = lower_bound(key);
260
261 // Doesn't already exist?
262 if ((i_element == end()) || compare(key, i_element->first))
263 {
264 insert_default_value(i_element, key);
265 }
266
267 return i_element->second;
268 }
269
270 //*********************************************************************
275 //*********************************************************************
276 mapped_reference at(const_key_reference key)
277 {
278 return refmap_t::at(key);
279 }
280
281#if ETL_USING_CPP11
282 //*********************************************************************
283 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
284 mapped_reference at(const K& key)
285 {
286 return refmap_t::at(key);
287 }
288#endif
289
290 //*********************************************************************
295 //*********************************************************************
296 const_mapped_reference at(const_key_reference key) const
297 {
298 return refmap_t::at(key);
299 }
300
301#if ETL_USING_CPP11
302 //*********************************************************************
303 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
304 const_mapped_reference at(const K& key) const
305 {
306 return refmap_t::at(key);
307 }
308#endif
309
310 //*********************************************************************
316 //*********************************************************************
317 template <typename TIterator>
318 void assign(TIterator first, TIterator last)
319 {
320#if ETL_IS_DEBUG_BUILD
321 difference_type d = etl::distance(first, last);
322 ETL_ASSERT(d <= difference_type(capacity()), ETL_ERROR(flat_map_full));
323#endif
324
325 clear();
326
327 while (first != last)
328 {
329 insert(*first);
330 ++first;
331 }
332 }
333
334 //*********************************************************************
338 //*********************************************************************
339 ETL_OR_STD::pair<iterator, bool> insert(const_reference value)
340 {
341 iterator i_element = lower_bound(value.first);
342
343 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
344
345 // Doesn't already exist?
346 if ((i_element == end()) || compare(value.first, i_element->first))
347 {
348 result = insert_value(i_element, value);
349 }
350
351 return result;
352 }
353
354#if ETL_USING_CPP11
355 //*********************************************************************
359 //*********************************************************************
360 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference value)
361 {
362 iterator i_element = lower_bound(value.first);
363
364 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
365
366 // Doesn't already exist?
367 if ((i_element == end()) || compare(value.first, i_element->first))
368 {
369 //result = insert_value(i_element, etl::move(value.first), etl::move(value.second));
370 result = insert_value(i_element, etl::move(value));
371 }
372
373 return result;
374 }
375#endif
376
377 //*********************************************************************
382 //*********************************************************************
383 iterator insert(const_iterator /*position*/, const_reference value)
384 {
385 return insert(value).first;
386 }
387
388#if ETL_USING_CPP11
389 //*********************************************************************
394 //*********************************************************************
395 iterator insert(const_iterator /*position*/, rvalue_reference value)
396 {
397 return insert(etl::move(value)).first;
398 }
399#endif
400
401 //*********************************************************************
407 //*********************************************************************
408 template <class TIterator>
409 void insert(TIterator first, TIterator last)
410 {
411 while (first != last)
412 {
413 insert(*first);
414 ++first;
415 }
416 }
417
418 //*************************************************************************
420 //*************************************************************************
421 ETL_OR_STD::pair<iterator, bool> emplace(const value_type& value)
422 {
423 return emplace(value.first, value.second);
424 }
425
426#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
427 //*************************************************************************
429 //*************************************************************************
430 template <typename ... Args>
431 ETL_OR_STD::pair<iterator, bool> emplace(const_key_reference key, Args && ... args)
432 {
433 ETL_ASSERT(!full(), ETL_ERROR(flat_map_full));
434
435 // Create it.
436 value_type* pvalue = storage.allocate<value_type>();
437 ::new ((void*)etl::addressof(pvalue->first)) key_type(key);
438 ::new ((void*)etl::addressof(pvalue->second)) mapped_type(etl::forward<Args>(args)...);
439
440 iterator i_element = lower_bound(key);
441
442 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
443
444 // Doesn't already exist?
445 if ((i_element == end()) || compare(key, i_element->first))
446 {
447 ETL_INCREMENT_DEBUG_COUNT
448 result = refmap_t::insert_at(i_element, *pvalue);
449 }
450 else
451 {
452 pvalue->~value_type();
453 storage.release(pvalue);
454 }
455
456 return result;
457 }
458
459#else
460
461 //*************************************************************************
463 //*************************************************************************
464 template <typename T1>
465 ETL_OR_STD::pair<iterator, bool> emplace(const_key_reference key, const T1& value1)
466 {
467 ETL_ASSERT(!full(), ETL_ERROR(flat_map_full));
468
469 // Create it.
470 value_type* pvalue = storage.allocate<value_type>();
471 ::new ((void*)etl::addressof(pvalue->first)) key_type(key);
472 ::new ((void*)etl::addressof(pvalue->second)) mapped_type(value1);
473
474 iterator i_element = lower_bound(key);
475
476 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
477
478 // Doesn't already exist?
479 if ((i_element == end()) || compare(key, i_element->first))
480 {
481 ETL_INCREMENT_DEBUG_COUNT
482 result = refmap_t::insert_at(i_element, *pvalue);
483 }
484 else
485 {
486 pvalue->~value_type();
487 storage.release(pvalue);
488 }
489
490 return result;
491 }
492
493 //*************************************************************************
495 //*************************************************************************
496 template <typename T1, typename T2>
497 ETL_OR_STD::pair<iterator, bool> emplace(const_key_reference key, const T1& value1, const T2& value2)
498 {
499 ETL_ASSERT(!full(), ETL_ERROR(flat_map_full));
500
501 // Create it.
502 value_type* pvalue = storage.allocate<value_type>();
503 ::new ((void*)etl::addressof(pvalue->first)) key_type(key);
504 ::new ((void*)etl::addressof(pvalue->second)) mapped_type(value1, value2);
505
506 iterator i_element = lower_bound(key);
507
508 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
509
510 // Doesn't already exist?
511 if ((i_element == end()) || compare(key, i_element->first))
512 {
513 ETL_INCREMENT_DEBUG_COUNT
514 result = refmap_t::insert_at(i_element, *pvalue);
515 }
516 else
517 {
518 pvalue->~value_type();
519 storage.release(pvalue);
520 }
521
522 return result;
523 }
524
525 //*************************************************************************
527 //*************************************************************************
528 template <typename T1, typename T2, typename T3>
529 ETL_OR_STD::pair<iterator, bool> emplace(const_key_reference key, const T1& value1, const T2& value2, const T3& value3)
530 {
531 ETL_ASSERT(!full(), ETL_ERROR(flat_map_full));
532
533 // Create it.
534 value_type* pvalue = storage.allocate<value_type>();
535 ::new ((void*)etl::addressof(pvalue->first)) key_type(key);
536 ::new ((void*)etl::addressof(pvalue->second)) mapped_type(value1, value2, value3);
537
538 iterator i_element = lower_bound(key);
539
540 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
541
542 // Doesn't already exist?
543 if ((i_element == end()) || compare(key, i_element->first))
544 {
545 ETL_INCREMENT_DEBUG_COUNT
546 result = refmap_t::insert_at(i_element, *pvalue);
547 }
548 else
549 {
550 pvalue->~value_type();
551 storage.release(pvalue);
552 }
553
554 return result;
555 }
556
557 //*************************************************************************
559 //*************************************************************************
560 template <typename T1, typename T2, typename T3, typename T4>
561 ETL_OR_STD::pair<iterator, bool> emplace(const_key_reference key, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
562 {
563 ETL_ASSERT(!full(), ETL_ERROR(flat_map_full));
564
565 // Create it.
566 value_type* pvalue = storage.allocate<value_type>();
567 ::new ((void*)etl::addressof(pvalue->first)) key_type(key);
568 ::new ((void*)etl::addressof(pvalue->second)) mapped_type(value1, value2, value3, value4);
569
570 iterator i_element = lower_bound(key);
571
572 ETL_OR_STD::pair<iterator, bool> result(i_element, false);
573
574 // Doesn't already exist?
575 if ((i_element == end()) || compare(key, i_element->first))
576 {
577 ETL_INCREMENT_DEBUG_COUNT
578 result = refmap_t::insert_at(i_element, *pvalue);
579 }
580 else
581 {
582 pvalue->~value_type();
583 storage.release(pvalue);
584 }
585
586 return result;
587 }
588
589#endif
590
591 //*********************************************************************
595 //*********************************************************************
596 size_t erase(const_key_reference key)
597 {
598 iterator i_element = find(key);
599
600 if (i_element == end())
601 {
602 return 0;
603 }
604 else
605 {
606 i_element->~value_type();
607 storage.release(etl::addressof(*i_element));
608 refmap_t::erase(i_element);
609 ETL_DECREMENT_DEBUG_COUNT;
610 return 1;
611 }
612 }
613
614#if ETL_USING_CPP11
615 //*********************************************************************
616 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
617 size_t erase(K&& key)
618 {
619 iterator i_element = find(etl::forward<K>(key));
620
621 if (i_element == end())
622 {
623 return 0;
624 }
625 else
626 {
627 i_element->~value_type();
628 storage.release(etl::addressof(*i_element));
629 refmap_t::erase(i_element);
630 ETL_DECREMENT_DEBUG_COUNT;
631 return 1;
632 }
633 }
634#endif
635
636 //*********************************************************************
639 //*********************************************************************
641 {
642 i_element->~value_type();
643 storage.release(etl::addressof(*i_element));
644 ETL_DECREMENT_DEBUG_COUNT
645 return refmap_t::erase(i_element);
646 }
647
648 //*********************************************************************
651 //*********************************************************************
653 {
654 i_element->~value_type();
655 storage.release(etl::addressof(*i_element));
656 ETL_DECREMENT_DEBUG_COUNT
657 return refmap_t::erase(i_element);
658 }
659
660 //*********************************************************************
666 //*********************************************************************
668 {
669 const_iterator itr = first;
670
671 while (itr != last)
672 {
673 itr->~value_type();
674 storage.release(etl::addressof(*itr));
675 ++itr;
676 ETL_DECREMENT_DEBUG_COUNT
677 }
678
679 return refmap_t::erase(first, last);
680 }
681
682 //*************************************************************************
684 //*************************************************************************
685 void clear()
686 {
688 {
689 storage.release_all();
690 }
691 else
692 {
693 iterator itr = begin();
694
695 while (itr != end())
696 {
697 itr->~value_type();
698 storage.release(etl::addressof(*itr));
699 ++itr;
700 }
701 }
702
703 ETL_RESET_DEBUG_COUNT
705 }
706
707 //*********************************************************************
711 //*********************************************************************
712 iterator find(const_key_reference key)
713 {
714 return refmap_t::find(key);
715 }
716
717#if ETL_USING_CPP11
718 //*********************************************************************
719 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
720 iterator find(const K& key)
721 {
722 return refmap_t::find(key);
723 }
724#endif
725
726 //*********************************************************************
730 //*********************************************************************
731 const_iterator find(const_key_reference key) const
732 {
733 return refmap_t::find(key);
734 }
735
736#if ETL_USING_CPP11
737 //*********************************************************************
738 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
739 const_iterator find(const K& key) const
740 {
741 return refmap_t::find(key);
742 }
743#endif
744
745 //*********************************************************************
749 //*********************************************************************
750 size_t count(const_key_reference key) const
751 {
752 return refmap_t::count(key);
753 }
754
755#if ETL_USING_CPP11
756 //*********************************************************************
757 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
758 size_t count(const K& key) const
759 {
760 return refmap_t::count(key);
761 }
762#endif
763
764 //*********************************************************************
768 //*********************************************************************
769 iterator lower_bound(const_key_reference key)
770 {
771 return refmap_t::lower_bound(key);
772 }
773
774#if ETL_USING_CPP11
775 //*********************************************************************
776 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
777 iterator lower_bound(const K& key)
778 {
779 return refmap_t::lower_bound(key);
780 }
781#endif
782
783 //*********************************************************************
787 //*********************************************************************
788 const_iterator lower_bound(const_key_reference key) const
789 {
790 return refmap_t::lower_bound(key);
791 }
792
793#if ETL_USING_CPP11
794 //*********************************************************************
795 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
796 const_iterator lower_bound(const K& key) const
797 {
798 return refmap_t::lower_bound(key);
799 }
800#endif
801
802 //*********************************************************************
806 //*********************************************************************
807 iterator upper_bound(const_key_reference key)
808 {
809 return refmap_t::upper_bound(key);
810 }
811
812#if ETL_USING_CPP11
813 //*********************************************************************
814 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
815 iterator upper_bound(const K& key)
816 {
817 return refmap_t::upper_bound(key);
818 }
819#endif
820
821 //*********************************************************************
825 //*********************************************************************
826 const_iterator upper_bound(const_key_reference key) const
827 {
828 return refmap_t::upper_bound(key);
829 }
830
831#if ETL_USING_CPP11
832 //*********************************************************************
833 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
834 const_iterator upper_bound(const K& key) const
835 {
836 return refmap_t::upper_bound(key);
837 }
838#endif
839
840 //*********************************************************************
844 //*********************************************************************
845 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
846 {
847 return refmap_t::equal_range(key);
848 }
849
850#if ETL_USING_CPP11
851 //*********************************************************************
852 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
853 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
854 {
855 return refmap_t::equal_range(key);
856 }
857#endif
858
859 //*********************************************************************
863 //*********************************************************************
864 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
865 {
866 return refmap_t::equal_range(key);
867 }
868
869#if ETL_USING_CPP11
870 //*********************************************************************
871 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
872 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
873 {
874 return refmap_t::equal_range(key);
875 }
876#endif
877
878 //*************************************************************************
880 //*************************************************************************
881 bool contains(const_key_reference key) const
882 {
883 return find(key) != end();
884 }
885
886#if ETL_USING_CPP11
887 //*************************************************************************
888 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
889 bool contains(const K& k) const
890 {
891 return find(k) != end();
892 }
893#endif
894
895 //*************************************************************************
897 //*************************************************************************
899 {
900 if (&rhs != this)
901 {
902 assign(rhs.cbegin(), rhs.cend());
903 }
904
905 return *this;
906 }
907
908#if ETL_USING_CPP11
909 //*************************************************************************
911 //*************************************************************************
913 {
914 move_container(etl::move(rhs));
915
916 return *this;
917 }
918#endif
919
920 //*************************************************************************
923 //*************************************************************************
924 size_type size() const
925 {
926 return refmap_t::size();
927 }
928
929 //*************************************************************************
932 //*************************************************************************
933 bool empty() const
934 {
935 return refmap_t::empty();
936 }
937
938 //*************************************************************************
941 //*************************************************************************
942 bool full() const
943 {
944 return refmap_t::full();
945 }
946
947 //*************************************************************************
950 //*************************************************************************
951 size_type capacity() const
952 {
953 return refmap_t::capacity();
954 }
955
956 //*************************************************************************
959 //*************************************************************************
960 size_type max_size() const
961 {
962 return refmap_t::max_size();
963 }
964
965 //*************************************************************************
968 //*************************************************************************
969 size_t available() const
970 {
971 return refmap_t::available();
972 }
973
974 protected:
975
976 //*********************************************************************
978 //*********************************************************************
979 iflat_map(lookup_t& lookup_, storage_t& storage_)
980 : refmap_t(lookup_),
981 storage(storage_)
982 {
983 }
984
985#if ETL_USING_CPP11
986 //*************************************************************************
989 //*************************************************************************
990 void move_container(iflat_map&& rhs)
991 {
992 if (&rhs != this)
993 {
994 this->clear();
995
998
999 // Move all of the elements.
1000 while (first != last)
1001 {
1003 ++temp;
1004
1005 this->insert(etl::move(*first));
1006 first = temp;
1007 }
1008 }
1009 }
1010#endif
1011
1012 private:
1013
1014 // Disable copy construction.
1015 iflat_map(const iflat_map&);
1016
1017 storage_t& storage;
1018
1019 TKeyCompare compare;
1020
1022 ETL_DECLARE_DEBUG_COUNT
1023
1024#if ETL_USING_CPP11
1025 //*************************************************************************
1026 template <typename TValueType>
1027 ETL_OR_STD::pair<iterator, bool> insert_value(iterator i_element, TValueType&& value)
1028 {
1029 ETL_ASSERT(!refmap_t::full(), ETL_ERROR(flat_map_full));
1030
1031 value_type* pvalue = storage.allocate<value_type>();
1032 ::new (pvalue) value_type(etl::forward<TValueType>(value));
1033 ETL_INCREMENT_DEBUG_COUNT
1034 return refmap_t::insert_at(i_element, *pvalue);
1035 }
1036#else
1037 //*************************************************************************
1038 ETL_OR_STD::pair<iterator, bool> insert_value(iterator i_element, const_reference value)
1039 {
1040 ETL_ASSERT(!refmap_t::full(), ETL_ERROR(flat_map_full));
1041
1042 value_type* pvalue = storage.allocate<value_type>();
1043 ::new (pvalue) value_type(value_type(value));
1044 ETL_INCREMENT_DEBUG_COUNT
1045 return refmap_t::insert_at(i_element, *pvalue);
1046 }
1047#endif
1048
1049#if ETL_USING_CPP11
1050 //*************************************************************************
1051 ETL_OR_STD::pair<iterator, bool> insert_default_value(iterator i_element, rvalue_key_reference key)
1052 {
1053 ETL_ASSERT(!refmap_t::full(), ETL_ERROR(flat_map_full));
1054
1055 value_type* pvalue = storage.allocate<value_type>();
1056 ::new ((void*)etl::addressof(pvalue->first)) key_type(etl::move(key));
1057 ::new ((void*)etl::addressof(pvalue->second)) mapped_type();
1058 ETL_INCREMENT_DEBUG_COUNT
1059
1060 return refmap_t::insert_at(i_element, *pvalue);
1061 }
1062#endif
1063
1064 //*************************************************************************
1065 ETL_OR_STD::pair<iterator, bool> insert_default_value(iterator i_element, const_key_reference key)
1066 {
1067 ETL_ASSERT(!refmap_t::full(), ETL_ERROR(flat_map_full));
1068
1069 value_type* pvalue = storage.allocate<value_type>();
1070 ::new ((void*)etl::addressof(pvalue->first)) key_type(key);
1071 ::new ((void*)etl::addressof(pvalue->second)) mapped_type();
1072 ETL_INCREMENT_DEBUG_COUNT
1073
1074 return refmap_t::insert_at(i_element, *pvalue);
1075 }
1076
1077 //*************************************************************************
1079 //*************************************************************************
1080#if defined(ETL_POLYMORPHIC_FLAT_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1081 public:
1082 virtual ~iflat_map()
1083 {
1084 }
1085#else
1086 protected:
1088 {
1089 }
1090#endif
1091 };
1092
1093 //***************************************************************************
1099 //***************************************************************************
1100 template <typename TKey, typename TMapped, typename TKeyCompare>
1102 {
1103 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
1104 }
1105
1106 //***************************************************************************
1112 //***************************************************************************
1113 template <typename TKey, typename TMapped, typename TKeyCompare>
1115 {
1116 return !(lhs == rhs);
1117 }
1118
1119 //***************************************************************************
1126 //***************************************************************************
1127 template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare = etl::less<TKey> >
1128 class flat_map : public etl::iflat_map<TKey, TValue, TCompare>
1129 {
1130 public:
1131
1132 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1133
1134 //*************************************************************************
1136 //*************************************************************************
1138 : etl::iflat_map<TKey, TValue, TCompare>(lookup, storage)
1139 {
1140 }
1141
1142 //*************************************************************************
1144 //*************************************************************************
1145 flat_map(const flat_map& other)
1146 : etl::iflat_map<TKey, TValue, TCompare>(lookup, storage)
1147 {
1148 this->assign(other.cbegin(), other.cend());
1149 }
1150
1151#if ETL_USING_CPP11
1152 //*************************************************************************
1154 //*************************************************************************
1155 flat_map(flat_map&& other)
1156 : etl::iflat_map<TKey, TValue, TCompare>(lookup, storage)
1157 {
1158 if (&other != this)
1159 {
1160 this->move_container(etl::move(other));
1161 }
1162 }
1163#endif
1164
1165 //*************************************************************************
1170 //*************************************************************************
1171 template <typename TIterator>
1172 flat_map(TIterator first, TIterator last)
1173 : etl::iflat_map<TKey, TValue, TCompare>(lookup, storage)
1174 {
1175 this->assign(first, last);
1176 }
1177
1178#if ETL_HAS_INITIALIZER_LIST
1179 //*************************************************************************
1181 //*************************************************************************
1182 flat_map(std::initializer_list<typename etl::iflat_map<TKey, TValue, TCompare>::value_type> init)
1183 : etl::iflat_map<TKey, TValue, TCompare>(lookup, storage)
1184 {
1185 this->assign(init.begin(), init.end());
1186 }
1187#endif
1188
1189 //*************************************************************************
1191 //*************************************************************************
1193 {
1194 this->clear();
1195 }
1196
1197 //*************************************************************************
1199 //*************************************************************************
1201 {
1202 if (&rhs != this)
1203 {
1204 this->assign(rhs.cbegin(), rhs.cend());
1205 }
1206
1207 return *this;
1208 }
1209
1210#if ETL_USING_CPP11
1211 //*************************************************************************
1213 //*************************************************************************
1215 {
1216 if (&rhs != this)
1217 {
1218 this->move_container(etl::move(rhs));
1219 }
1220
1221 return *this;
1222 }
1223#endif
1224
1225 private:
1226
1227 typedef typename etl::iflat_map<TKey, TValue, TCompare>::value_type node_t;
1228
1231
1234 };
1235
1236 template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare>
1237 ETL_CONSTANT size_t flat_map<TKey, TValue, MAX_SIZE_, TCompare>::MAX_SIZE;
1238
1239 //*************************************************************************
1241 //*************************************************************************
1242#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1243 template <typename... TPairs>
1244 flat_map(TPairs...) -> flat_map<typename etl::nth_type_t<0, TPairs...>::first_type,
1245 typename etl::nth_type_t<0, TPairs...>::second_type,
1246 sizeof...(TPairs)>;
1247#endif
1248
1249 //*************************************************************************
1251 //*************************************************************************
1252#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1253 template <typename TKey, typename TMapped, typename TKeyCompare = etl::less<TKey>, typename... TPairs>
1254 constexpr auto make_flat_map(TPairs&&... pairs) -> etl::flat_map<TKey, TMapped, sizeof...(TPairs), TKeyCompare>
1255 {
1256 return { {etl::forward<TPairs>(pairs)...} };
1257 }
1258#endif
1259}
1260
1261#endif
Definition: reference_flat_map.h:218
Definition: reference_flat_map.h:134
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_OR_STD::pair< iterator, bool > emplace(const_key_reference key, const T1 &value1, const T2 &value2)
Emplaces a value to the map.
Definition: flat_map.h:497
const_iterator lower_bound(const_key_reference key) const
Definition: flat_map.h:788
size_t count(const_key_reference key) const
Definition: flat_map.h:750
size_type max_size() const
Definition: flat_map.h:960
reverse_iterator rbegin()
Definition: flat_map.h:182
iterator begin()
Definition: flat_map.h:128
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition: flat_map.h:845
~flat_map()
Destructor.
Definition: flat_map.h:1192
void clear()
Clears the flat_map.
Definition: flat_map.h:685
iflat_map(lookup_t &lookup_, storage_t &storage_)
Constructor.
Definition: flat_map.h:979
size_t available() const
Definition: flat_map.h:969
iterator find(const_key_reference key)
Definition: flat_map.h:712
const_reverse_iterator rbegin() const
Definition: flat_map.h:191
const_iterator upper_bound(const_key_reference key) const
Definition: flat_map.h:826
mapped_reference at(const_key_reference key)
Definition: flat_map.h:276
iterator erase(const_iterator i_element)
Definition: flat_map.h:652
~iflat_map()
Destructor.
Definition: flat_map.h:1087
iterator upper_bound(const_key_reference key)
Definition: flat_map.h:807
ETL_OR_STD::pair< iterator, bool > emplace(const value_type &value)
Emplaces a value to the map.
Definition: flat_map.h:421
const_iterator cend() const
Definition: flat_map.h:173
const_reverse_iterator crbegin() const
Definition: flat_map.h:218
const_mapped_reference at(const_key_reference key) const
Definition: flat_map.h:296
reverse_iterator rend()
Definition: flat_map.h:200
size_type capacity() const
Definition: flat_map.h:951
flat_map()
Constructor.
Definition: flat_map.h:1137
iterator erase(iterator i_element)
Definition: flat_map.h:640
ETL_OR_STD::pair< iterator, bool > insert(const_reference value)
Definition: flat_map.h:339
ETL_OR_STD::pair< iterator, bool > emplace(const_key_reference key, const T1 &value1)
Emplaces a value to the map.
Definition: flat_map.h:465
const_iterator cbegin() const
Definition: flat_map.h:164
size_t erase(const_key_reference key)
Definition: flat_map.h:596
bool contains(const_key_reference key) const
Check if the map contains the key.
Definition: flat_map.h:881
iflat_map & operator=(const iflat_map &rhs)
Assignment operator.
Definition: flat_map.h:898
ETL_OR_STD::pair< iterator, bool > emplace(const_key_reference key, const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Emplaces a value to the map.
Definition: flat_map.h:561
const_iterator begin() const
Definition: flat_map.h:137
const_iterator end() const
Definition: flat_map.h:155
bool full() const
Definition: flat_map.h:942
const_reverse_iterator rend() const
Definition: flat_map.h:209
iterator end()
Definition: flat_map.h:146
bool empty() const
Definition: flat_map.h:933
flat_map(const flat_map &other)
Copy constructor.
Definition: flat_map.h:1145
iterator erase(const_iterator first, const_iterator last)
Definition: flat_map.h:667
const_iterator find(const_key_reference key) const
Definition: flat_map.h:731
void insert(TIterator first, TIterator last)
Definition: flat_map.h:409
void assign(TIterator first, TIterator last)
Definition: flat_map.h:318
iterator insert(const_iterator, const_reference value)
Definition: flat_map.h:383
const_reverse_iterator crend() const
Definition: flat_map.h:227
flat_map(TIterator first, TIterator last)
Definition: flat_map.h:1172
ETL_OR_STD::pair< iterator, bool > emplace(const_key_reference key, const T1 &value1, const T2 &value2, const T3 &value3)
Emplaces a value to the map.
Definition: flat_map.h:529
iterator lower_bound(const_key_reference key)
Definition: flat_map.h:769
size_type size() const
Definition: flat_map.h:924
mapped_reference operator[](const_key_reference key)
Definition: flat_map.h:257
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition: flat_map.h:864
Definition: flat_map.h:1129
Definition: flat_map.h:64
ETL_CONSTEXPR17 T * addressof(T &t)
Definition: addressof.h:51
void release_all()
Release all objects in the pool.
Definition: ipool.h:248
T * allocate()
Definition: ipool.h:113
void release(const void *const p_object)
Definition: ipool.h:239
Definition: ipool.h:102
mapped_type & at(key_parameter_t key)
Definition: reference_flat_map.h:470
iterator begin()
Definition: reference_flat_map.h:360
void clear()
Clears the reference_flat_map.
Definition: reference_flat_map.h:658
ETL_OR_STD::pair< iterator, bool > insert_at(iterator i_element, value_type &value)
Definition: reference_flat_map.h:984
const_reverse_iterator crbegin() const
Definition: reference_flat_map.h:450
reverse_iterator rend()
Definition: reference_flat_map.h:432
size_t count(key_parameter_t key) const
Definition: reference_flat_map.h:762
iterator end()
Definition: reference_flat_map.h:378
const_iterator cbegin() const
Definition: reference_flat_map.h:396
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition: reference_flat_map.h:857
size_t available() const
Definition: reference_flat_map.h:964
const_reverse_iterator crend() const
Definition: reference_flat_map.h:459
size_type max_size() const
Definition: reference_flat_map.h:955
bool empty() const
Definition: reference_flat_map.h:928
iterator lower_bound(key_parameter_t key)
Definition: reference_flat_map.h:781
reverse_iterator rbegin()
Definition: reference_flat_map.h:414
iterator upper_bound(key_parameter_t key)
Definition: reference_flat_map.h:819
size_type size() const
Definition: reference_flat_map.h:919
iterator find(key_parameter_t key)
Definition: reference_flat_map.h:668
const_iterator cend() const
Definition: reference_flat_map.h:405
size_t erase(key_parameter_t key)
Definition: reference_flat_map.h:591
bool full() const
Definition: reference_flat_map.h:937
size_type capacity() const
Definition: reference_flat_map.h:946
Definition: reference_flat_map.h:80
Definition: reference_flat_map.h:110
bitset_ext
Definition: absolute.h:38
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:645
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
Definition: compare.h:52
Definition: type_traits_generator.h:2055
iterator
Definition: iterator.h:399
pair holds two objects of arbitrary type
Definition: utility.h:164