OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #ifndef BASE_CONTAINERS_FLAT_MAP_H_ | |
6 #define BASE_CONTAINERS_FLAT_MAP_H_ | |
7 | |
8 #include <utility> | |
9 | |
10 #include "base/containers/flat_tree.h" | |
11 #include "base/logging.h" | |
12 | |
13 namespace base { | |
14 | |
15 namespace internal { | |
16 | |
17 // An implementation of the flat_set GetKeyFromValue template parameter that | |
18 // extracts the key as the first() element of a pair. | |
19 template <class Key, class Mapped> | |
20 struct GetKeyFromValuePairFirst { | |
21 const Key& operator()(const std::pair<Key, Mapped>& p) const { | |
22 return p.first; | |
23 } | |
24 }; | |
25 | |
26 } // namespace internal | |
27 | |
28 // Overview: | |
29 // This file implements flat_map container. It is an alternative to standard | |
30 // sorted containers that stores its elements in contiguous memory (a vector> | |
31 // | |
32 // Additional documentation and usage advice is in flat_set.h. | |
33 // | |
34 // Most of the core functionality is inherited from flat_tree. | |
35 template <class Key, class Mapped, class Compare = std::less<Key>> | |
36 // Meets the requirements of Container, AssociativeContainer, | |
37 // ReversibleContainer. | |
38 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. | |
39 class flat_map : public ::base::internal::flat_tree< | |
40 Key, | |
41 std::pair<Key, Mapped>, | |
42 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, | |
43 Compare> { | |
44 private: | |
45 using tree = typename ::base::internal::flat_tree< | |
46 Key, | |
47 std::pair<Key, Mapped>, | |
48 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, | |
49 Compare>; | |
50 | |
51 public: | |
52 using mapped_type = Mapped; | |
53 using value_type = typename tree::value_type; | |
54 | |
55 // -------------------------------------------------------------------------- | |
56 // Lifetime. | |
57 // | |
58 // Constructors that take range guarantee O(N * log(N)) + O(N) complexity | |
59 // (N is a range length). Thr range constructors are NOT stable. If there are | |
60 // duplicates an arbitrary one will be chosen. | |
61 // | |
62 // Assume that move constructors invalidate iterators and references. | |
63 | |
64 flat_map(); | |
65 explicit flat_map(const Compare& comp); | |
66 | |
67 template <class InputIterator> | |
68 flat_map(InputIterator first, | |
69 InputIterator last, | |
70 const Compare& comp = Compare()); | |
71 | |
72 flat_map(const flat_map&); | |
73 flat_map(flat_map&&) noexcept; | |
74 | |
75 flat_map(std::initializer_list<value_type> ilist, | |
76 const Compare& comp = Compare()); | |
dyaroshev
2017/02/28 18:40:53
It would be nice to inherit all of these construct
dyaroshev
2017/03/06 17:41:55
I've checked - it doesn't work - compiler doesn't
brettw
2017/03/20 22:42:19
Thanks for checking!
| |
77 | |
78 ~flat_map(); | |
79 | |
80 // -------------------------------------------------------------------------- | |
81 // Assignments. | |
82 // | |
83 // Assume that move assignment invalidates iterators and references. | |
84 | |
85 flat_map& operator=(const flat_map&); | |
86 flat_map& operator=(flat_map&&); | |
87 // Not stable in the presence of duplicates in the initializer list. | |
88 flat_map& operator=(std::initializer_list<value_type> ilist); | |
89 | |
90 // -------------------------------------------------------------------------- | |
91 // Map-specific insert operations. | |
92 // | |
93 // Normal insert() functions are inherited from flat_tree. | |
94 // | |
95 // Assume that every operation invalidates iterators and references. | |
96 // Insertion of one element can take O(size). | |
97 | |
98 Mapped& operator[](const Key& key); | |
99 Mapped& operator[](Key&& key); | |
100 | |
101 // CHECK()s if the element does not exist. | |
102 value_type& at(const Key& key); | |
103 const value_type& at(const Key& key) const; | |
104 | |
105 // -------------------------------------------------------------------------- | |
106 // General operations. | |
107 // | |
108 // Assume that swap invalidates iterators and references. | |
109 | |
110 void swap(flat_map& other) noexcept; | |
111 | |
112 friend void swap(flat_map& lhs, flat_map& rhs) noexcept { lhs.swap(rhs); } | |
113 }; | |
114 | |
115 // ---------------------------------------------------------------------------- | |
116 // Lifetime. | |
117 | |
118 template <class Key, class Mapped, class Compare> | |
119 flat_map<Key, Mapped, Compare>::flat_map() = default; | |
120 | |
121 template <class Key, class Mapped, class Compare> | |
122 flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree(comp) {} | |
123 | |
124 template <class Key, class Mapped, class Compare> | |
125 template <class InputIterator> | |
126 flat_map<Key, Mapped, Compare>::flat_map(InputIterator first, | |
127 InputIterator last, | |
128 const Compare& comp) | |
129 : tree(first, last, comp) {} | |
130 | |
131 template <class Key, class Mapped, class Compare> | |
132 flat_map<Key, Mapped, Compare>::flat_map(const flat_map&) = default; | |
133 | |
134 template <class Key, class Mapped, class Compare> | |
135 flat_map<Key, Mapped, Compare>::flat_map(flat_map&&) = default; | |
136 | |
137 template <class Key, class Mapped, class Compare> | |
138 flat_map<Key, Mapped, Compare>::flat_map( | |
139 std::initializer_list<value_type> ilist, | |
140 const Compare& comp) | |
141 : flat_map(std::begin(ilist), std::end(ilist), comp) {} | |
142 | |
143 template <class Key, class Mapped, class Compare> | |
144 flat_map<Key, Mapped, Compare>::~flat_map() = default; | |
145 | |
146 // ---------------------------------------------------------------------------- | |
147 // Assignments. | |
148 | |
149 template <class Key, class Mapped, class Compare> | |
150 auto flat_map<Key, Mapped, Compare>::operator=(const flat_map&) | |
151 -> flat_map& = default; | |
152 | |
153 template <class Key, class Mapped, class Compare> | |
154 auto flat_map<Key, Mapped, Compare>::operator=(flat_map &&) | |
155 -> flat_map& = default; | |
156 | |
157 template <class Key, class Mapped, class Compare> | |
158 auto flat_map<Key, Mapped, Compare>::operator=( | |
159 std::initializer_list<value_type> ilist) -> flat_map& { | |
160 tree::operator=(ilist); | |
161 return *this; | |
162 } | |
163 | |
164 // ---------------------------------------------------------------------------- | |
165 // Insert operations. | |
166 | |
167 template <class Key, class Mapped, class Compare> | |
168 auto flat_map<Key, Mapped, Compare>::operator[](const Key& key) -> Mapped& { | |
169 typename tree::iterator found = tree::lower_bound(key); | |
170 if (found == tree::end() || tree::key_comp()(key, found->first)) | |
171 found = unsafe_insert_new_at(found, value_type(key, Mapped())); | |
172 return found->second; | |
173 } | |
174 | |
175 template <class Key, class Mapped, class Compare> | |
176 auto flat_map<Key, Mapped, Compare>::operator[](Key&& key) | |
177 -> Mapped& { | |
178 const Key& key_ref = key; | |
179 typename tree::iterator found = tree::lower_bound(key_ref); | |
180 if (found == tree::end() || tree::key_comp()(key, found->first)) { | |
181 found = tree::unsafe_insert_new_at(found, | |
182 value_type(std::move(key), Mapped())); | |
183 } | |
184 return found->second; | |
185 } | |
186 | |
187 template <class Key, class Mapped, class Compare> | |
188 auto flat_map<Key, Mapped, Compare>::at(const Key& key) -> value_type& { | |
189 typename tree::const_iterator found = tree::lower_bound(key); | |
190 CHECK(found == tree::end() || tree::key_comp()(key, found->first)); | |
dyaroshev
2017/02/28 18:40:53
This should probably just be tree::find.
| |
191 return found->second; | |
192 } | |
193 | |
194 template <class Key, class Mapped, class Compare> | |
195 auto flat_map<Key, Mapped, Compare>::at(const Key& key) const | |
196 -> const value_type& { | |
197 typename tree::iterator found = tree::lower_bound(key); | |
198 CHECK(found == tree::end() || tree::key_comp()(key, found->first)); | |
199 return found->second; | |
200 } | |
201 | |
202 // ---------------------------------------------------------------------------- | |
203 // General operations. | |
204 | |
205 template <class Key, class Mapped, class Compare> | |
206 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { | |
207 tree::swap(other); | |
208 } | |
209 | |
210 } // namespace base | |
211 | |
212 #endif // BASE_CONTAINERS_FLAT_MAP_H_ | |
OLD | NEW |