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 // Not stable in the presence of duplicates in the initializer list. | |
68 template <class InputIterator> | |
69 flat_map(InputIterator first, | |
70 InputIterator last, | |
71 const Compare& comp = Compare()); | |
72 | |
73 flat_map(const flat_map&); | |
74 flat_map(flat_map&&); | |
75 | |
76 // Not stable in the presence of duplicates in the initializer list. | |
77 flat_map(std::initializer_list<value_type> ilist, | |
78 const Compare& comp = Compare()); | |
79 | |
80 ~flat_map(); | |
81 | |
82 // -------------------------------------------------------------------------- | |
83 // Assignments. | |
84 // | |
85 // Assume that move assignment invalidates iterators and references. | |
86 | |
87 flat_map& operator=(const flat_map&); | |
88 flat_map& operator=(flat_map&&); | |
89 // Not stable in the presence of duplicates in the initializer list. | |
90 flat_map& operator=(std::initializer_list<value_type> ilist); | |
91 | |
92 // -------------------------------------------------------------------------- | |
93 // Map-specific insert operations. | |
94 // | |
95 // Normal insert() functions are inherited from flat_tree. | |
96 // | |
97 // Assume that every operation invalidates iterators and references. | |
98 // Insertion of one element can take O(size). | |
99 | |
100 Mapped& operator[](const Key& key); | |
101 Mapped& operator[](Key&& key); | |
102 | |
103 // CHECK()s if the element does not exist. | |
104 Mapped& at(const Key& key); | |
105 const Mapped& at(const Key& key) const; | |
dyaroshev
2017/03/21 18:40:37
mapped_type?
| |
106 | |
107 // -------------------------------------------------------------------------- | |
108 // General operations. | |
109 // | |
110 // Assume that swap invalidates iterators and references. | |
111 | |
112 void swap(flat_map& other); | |
113 | |
114 friend void swap(flat_map& lhs, flat_map& rhs) { lhs.swap(rhs); } | |
115 }; | |
116 | |
117 // ---------------------------------------------------------------------------- | |
118 // Lifetime. | |
119 | |
120 template <class Key, class Mapped, class Compare> | |
121 flat_map<Key, Mapped, Compare>::flat_map() = default; | |
122 | |
123 template <class Key, class Mapped, class Compare> | |
124 flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree(comp) {} | |
125 | |
126 template <class Key, class Mapped, class Compare> | |
127 template <class InputIterator> | |
128 flat_map<Key, Mapped, Compare>::flat_map(InputIterator first, | |
129 InputIterator last, | |
130 const Compare& comp) | |
131 : tree(first, last, comp) {} | |
132 | |
133 template <class Key, class Mapped, class Compare> | |
134 flat_map<Key, Mapped, Compare>::flat_map(const flat_map&) = default; | |
135 | |
136 template <class Key, class Mapped, class Compare> | |
137 flat_map<Key, Mapped, Compare>::flat_map(flat_map&&) = default; | |
138 | |
139 template <class Key, class Mapped, class Compare> | |
140 flat_map<Key, Mapped, Compare>::flat_map( | |
141 std::initializer_list<value_type> ilist, | |
142 const Compare& comp) | |
143 : flat_map(std::begin(ilist), std::end(ilist), comp) {} | |
144 | |
145 template <class Key, class Mapped, class Compare> | |
146 flat_map<Key, Mapped, Compare>::~flat_map() = default; | |
147 | |
148 // ---------------------------------------------------------------------------- | |
149 // Assignments. | |
150 | |
151 template <class Key, class Mapped, class Compare> | |
152 auto flat_map<Key, Mapped, Compare>::operator=(const flat_map&) | |
153 -> flat_map& = default; | |
154 | |
155 template <class Key, class Mapped, class Compare> | |
156 auto flat_map<Key, Mapped, Compare>::operator=(flat_map &&) | |
157 -> flat_map& = default; | |
158 | |
159 template <class Key, class Mapped, class Compare> | |
160 auto flat_map<Key, Mapped, Compare>::operator=( | |
161 std::initializer_list<value_type> ilist) -> flat_map& { | |
162 tree::operator=(ilist); | |
163 return *this; | |
164 } | |
165 | |
166 // ---------------------------------------------------------------------------- | |
167 // Insert operations. | |
168 | |
169 template <class Key, class Mapped, class Compare> | |
170 auto flat_map<Key, Mapped, Compare>::operator[](const Key& key) -> Mapped& { | |
171 typename tree::iterator found = tree::lower_bound(key); | |
172 if (found == tree::end() || tree::key_comp()(key, found->first)) | |
173 found = unsafe_emplace(found, key, Mapped()); | |
174 return found->second; | |
175 } | |
176 | |
177 template <class Key, class Mapped, class Compare> | |
178 auto flat_map<Key, Mapped, Compare>::operator[](Key&& key) -> Mapped& { | |
179 const Key& key_ref = key; | |
180 typename tree::iterator found = tree::lower_bound(key_ref); | |
181 if (found == tree::end() || tree::key_comp()(key, found->first)) | |
182 found = tree::unsafe_emplace(found, std::move(key), Mapped()); | |
183 return found->second; | |
184 } | |
185 | |
186 template <class Key, class Mapped, class Compare> | |
187 auto flat_map<Key, Mapped, Compare>::at(const Key& key) -> mapped_type& { | |
188 typename tree::iterator found = tree::find(key); | |
189 CHECK(found != tree::end()); | |
190 return found->second; | |
191 } | |
192 | |
193 template <class Key, class Mapped, class Compare> | |
194 auto flat_map<Key, Mapped, Compare>::at(const Key& key) const | |
195 -> const mapped_type& { | |
196 typename tree::const_iterator found = tree::find(key); | |
197 CHECK(found != tree::end()); | |
198 return found->second; | |
199 } | |
200 | |
201 // ---------------------------------------------------------------------------- | |
202 // General operations. | |
203 | |
204 template <class Key, class Mapped, class Compare> | |
205 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { | |
206 tree::swap(other); | |
207 } | |
208 | |
209 } // namespace base | |
210 | |
211 #endif // BASE_CONTAINERS_FLAT_MAP_H_ | |
OLD | NEW |