OLD | NEW |
---|---|
1 # base/containers library | 1 # base/containers library |
2 | 2 |
3 ## What goes here | 3 ## What goes here |
4 | 4 |
5 This directory contains some STL-like containers. | 5 This directory contains some STL-like containers. |
6 | 6 |
7 Things should be moved here that are generally applicable across the code base. | 7 Things should be moved here that are generally applicable across the code base. |
8 Don't add things here just because you need them in one place and think others | 8 Don't add things here just because you need them in one place and think others |
9 may someday want something similar. You can put specialized containers in | 9 may someday want something similar. You can put specialized containers in |
10 your component's directory and we can promote them here later if we feel there | 10 your component's directory and we can promote them here later if we feel there |
(...skipping 28 matching lines...) Expand all Loading... | |
39 cases, inserts are better or comparable to other containers even for | 39 cases, inserts are better or comparable to other containers even for |
40 several dozen items, and efficiently-moved types are unlikely to have | 40 several dozen items, and efficiently-moved types are unlikely to have |
41 performance problems for most cases until you have hundreds of items. If | 41 performance problems for most cases until you have hundreds of items. If |
42 your container can be constructed in one shot, the constructor from vector | 42 your container can be constructed in one shot, the constructor from vector |
43 gives O(n log n) construction times and it should be strictly better than | 43 gives O(n log n) construction times and it should be strictly better than |
44 a std::map. | 44 a std::map. |
45 | 45 |
46 * **base::small\_map** has better runtime memory usage without the poor | 46 * **base::small\_map** has better runtime memory usage without the poor |
47 mutation performance of large containers that base::flat\_map has. But this | 47 mutation performance of large containers that base::flat\_map has. But this |
48 advantage is partially offset by additional code size. Prefer in cases | 48 advantage is partially offset by additional code size. Prefer in cases |
49 where you make many objects so that the code/heap tradeoff is good. | 49 where you make many objects so that the code/heap tradeoff is good. |
vmpstr
2017/06/26 23:06:34
I wonder if this is causing the patch failure, it
jdoerrie
2017/06/27 12:56:50
Investigating locally this seems to be replacing a
| |
50 | 50 |
51 * Use **std::map** and **std::set** if you can't decide. Even if they're not | 51 * Use **std::map** and **std::set** if you can't decide. Even if they're not |
52 great, they're unlikely to be bad or surprising. | 52 great, they're unlikely to be bad or surprising. |
53 | 53 |
54 ### Map and set details | 54 ### Map and set details |
55 | 55 |
56 Sizes are on 64-bit platforms. Stable iterators aren't invalidated when the | 56 Sizes are on 64-bit platforms. Stable iterators aren't invalidated when the |
57 container is mutated. | 57 container is mutated. |
58 | 58 |
59 | Container | Empty size | Per-item ov erhead | Stable iterators? | | 59 | Container | Empty size | Per-item ov erhead | Stable iterators? | |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
117 set sizes, std::vector's doubling-when-full strategy can waste memory. | 117 set sizes, std::vector's doubling-when-full strategy can waste memory. |
118 | 118 |
119 Supports efficient construction from a vector of items which avoids the O(n^2) | 119 Supports efficient construction from a vector of items which avoids the O(n^2) |
120 insertion time of each element separately. | 120 insertion time of each element separately. |
121 | 121 |
122 The per-item overhead will depend on the underlying std::vector's reallocation | 122 The per-item overhead will depend on the underlying std::vector's reallocation |
123 strategy and the memory access pattern. Assuming items are being linearly added, | 123 strategy and the memory access pattern. Assuming items are being linearly added, |
124 one would expect it to be 3/4 full, so per-item overhead will be 0.25 * | 124 one would expect it to be 3/4 full, so per-item overhead will be 0.25 * |
125 sizeof(T). | 125 sizeof(T). |
126 | 126 |
127 flat\_set/flat\_map support C++14 interface and a notion of transparent | |
128 comparisons. Therefore you can, for example, lookup base::StringPiece in a set | |
129 of std::strings without constructing a temporary std::string. | |
130 You can find more information about transparent comparisons here: | |
131 http://en.cppreference.com/w/cpp/utility/functional/less_void | |
132 | |
133 Example, smart pointer set: | |
134 | |
135 // Define a custom comparator. | |
136 struct UniquePtrComparator { | |
137 // Mark your comparison as transparent. | |
138 using is_transparent = int; | |
139 | |
140 template <typename T> | |
141 bool operator()(const std::unique_ptr<T>& lhs, | |
142 const std::unique_ptr<T>& rhs) const { | |
143 return lhs < rhs; | |
144 } | |
145 | |
146 template <typename T> | |
147 bool operator()(const T* lhs, const std::unique_ptr<T>& rhs) const { | |
148 return lhs < rhs.get(); | |
149 } | |
150 | |
151 template <typename T> | |
152 bool operator()(const std::unique_ptr<T>& lhs, const T* rhs) const { | |
153 return lhs.get() < rhs; | |
154 } | |
155 }; | |
156 | |
157 // Declare a typedef. | |
158 template <typename T> | |
159 using UniquePtrSet = | |
160 base::flat_set<std::unique_ptr<T>, UniquePtrComparator>; | |
161 | |
162 // ... | |
163 | |
164 // Collect data. | |
165 std::vector<std::unique_ptr<int>> ptr_vec; | |
166 ptr_vec.reserve(5); | |
167 std::generate_n(std::back_inserter(ptr_vec), 5, []{ | |
168 return base::MakeUnique<int>(0); | |
169 }); | |
170 | |
171 // Construct a set. | |
172 UniquePtrSet<int> ptr_set(std::move(ptr_vec), base::KEEP_FIRST_OF_DUPES); | |
173 | |
174 // Use raw pointers to lookup keys. | |
175 int* ptr = ptr_set.begin()->get(); | |
176 EXPECT_TRUE(ptr_set.find(ptr) == ptr_set.begin()); | |
177 | |
178 Example flat_map<\std::string, int>: | |
179 | |
180 base::flat_map<std::string, int> str_to_int({{"a", 1}, {"c", 2},{"b", 2}}, | |
181 base::KEEP_FIRST_OF_DUPES); | |
182 | |
183 // NOTE: does construct a temporary string. | |
184 str_to_int["c"] = 3; | |
dyaroshev
2017/06/26 22:40:43
standard doesn't provide a templated overload for
vmpstr
2017/06/26 23:06:34
I agree. I think that if you have a transparent co
dyaroshev
2017/06/27 21:19:29
Done
| |
185 | |
186 // Do not construct temporary strings. | |
vmpstr
2017/06/26 23:06:34
nit: s/Do/Does/
dyaroshev
2017/06/27 21:19:29
Done
| |
187 str_to_int.find("c")->second = 3; | |
188 str_to_int.erase("c"); | |
189 EXPECT_EQ(str_to_int.end(), str_to_int.find("c")->second); | |
190 | |
127 ### base::small\_map | 191 ### base::small\_map |
128 | 192 |
129 A small inline buffer that is brute-force searched that overflows into a full | 193 A small inline buffer that is brute-force searched that overflows into a full |
130 std::map or std::unordered\_map. This gives the memory benefit of | 194 std::map or std::unordered\_map. This gives the memory benefit of |
131 base::flat\_map for small data sizes without the degenerate insertion | 195 base::flat\_map for small data sizes without the degenerate insertion |
132 performance for large container sizes. | 196 performance for large container sizes. |
133 | 197 |
134 Since instantiations require both code for a std::map and a brute-force search | 198 Since instantiations require both code for a std::map and a brute-force search |
135 of the inline container, plus a fancy iterator to cover both cases, code size | 199 of the inline container, plus a fancy iterator to cover both cases, code size |
136 is larger. | 200 is larger. |
(...skipping 24 matching lines...) Expand all Loading... | |
161 printf("Found is %d\n", (int)(found == foo.end())); | 225 printf("Found is %d\n", (int)(found == foo.end())); |
162 found = foo.find("bar"); | 226 found = foo.find("bar"); |
163 printf("Found is %d\n", (int)(found == foo.end())); | 227 printf("Found is %d\n", (int)(found == foo.end())); |
164 found = foo.find("asdfhf"); | 228 found = foo.find("asdfhf"); |
165 printf("Found is %d\n", (int)(found == foo.end())); | 229 printf("Found is %d\n", (int)(found == foo.end())); |
166 found = foo.find("bar1"); | 230 found = foo.find("bar1"); |
167 printf("Found is %d\n", (int)(found == foo.end())); | 231 printf("Found is %d\n", (int)(found == foo.end())); |
168 } | 232 } |
169 ``` | 233 ``` |
170 | 234 |
OLD | NEW |