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 106 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 |
| 128 flat\_set/flat\_map support a notion of transparent comparisons. Therefore you |
| 129 can, for example, lookup base::StringPiece in a set of std::strings without |
| 130 constructing a temporary std::string. This functionality is based on C++14 |
| 131 extensions to std::set/std::map interface. |
| 132 |
| 133 You can find more information about transparent comparisons here: |
| 134 http://en.cppreference.com/w/cpp/utility/functional/less_void |
| 135 |
| 136 Example, smart pointer set: |
| 137 |
| 138 ```cpp |
| 139 // Define a custom comparator. |
| 140 struct UniquePtrComparator { |
| 141 // Mark your comparison as transparent. |
| 142 using is_transparent = int; |
| 143 |
| 144 template <typename T> |
| 145 bool operator()(const std::unique_ptr<T>& lhs, |
| 146 const std::unique_ptr<T>& rhs) const { |
| 147 return lhs < rhs; |
| 148 } |
| 149 |
| 150 template <typename T> |
| 151 bool operator()(const T* lhs, const std::unique_ptr<T>& rhs) const { |
| 152 return lhs < rhs.get(); |
| 153 } |
| 154 |
| 155 template <typename T> |
| 156 bool operator()(const std::unique_ptr<T>& lhs, const T* rhs) const { |
| 157 return lhs.get() < rhs; |
| 158 } |
| 159 }; |
| 160 |
| 161 // Declare a typedef. |
| 162 template <typename T> |
| 163 using UniquePtrSet = base::flat_set<std::unique_ptr<T>, UniquePtrComparator>; |
| 164 |
| 165 // ... |
| 166 // Collect data. |
| 167 std::vector<std::unique_ptr<int>> ptr_vec; |
| 168 ptr_vec.reserve(5); |
| 169 std::generate_n(std::back_inserter(ptr_vec), 5, []{ |
| 170 return base::MakeUnique<int>(0); |
| 171 }); |
| 172 |
| 173 // Construct a set. |
| 174 UniquePtrSet<int> ptr_set(std::move(ptr_vec), base::KEEP_FIRST_OF_DUPES); |
| 175 |
| 176 // Use raw pointers to lookup keys. |
| 177 int* ptr = ptr_set.begin()->get(); |
| 178 EXPECT_TRUE(ptr_set.find(ptr) == ptr_set.begin()); |
| 179 ``` |
| 180 |
| 181 Example flat_map<std\::string, int>: |
| 182 |
| 183 ```cpp |
| 184 base::flat_map<std::string, int> str_to_int({{"a", 1}, {"c", 2},{"b", 2}}, |
| 185 base::KEEP_FIRST_OF_DUPES); |
| 186 |
| 187 // Does not construct temporary strings. |
| 188 str_to_int.find("c")->second = 3; |
| 189 str_to_int.erase("c"); |
| 190 EXPECT_EQ(str_to_int.end(), str_to_int.find("c")->second); |
| 191 |
| 192 // NOTE: This does construct a temporary string. This happens since if the |
| 193 // item is not in the container, then it needs to be constructed, which is |
| 194 // something that transparent comparators don't have to guarantee. |
| 195 str_to_int["c"] = 3; |
| 196 ``` |
| 197 |
127 ### base::small\_map | 198 ### base::small\_map |
128 | 199 |
129 A small inline buffer that is brute-force searched that overflows into a full | 200 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 | 201 std::map or std::unordered\_map. This gives the memory benefit of |
131 base::flat\_map for small data sizes without the degenerate insertion | 202 base::flat\_map for small data sizes without the degenerate insertion |
132 performance for large container sizes. | 203 performance for large container sizes. |
133 | 204 |
134 Since instantiations require both code for a std::map and a brute-force search | 205 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 | 206 of the inline container, plus a fancy iterator to cover both cases, code size |
136 is larger. | 207 is larger. |
(...skipping 24 matching lines...) Expand all Loading... |
161 printf("Found is %d\n", (int)(found == foo.end())); | 232 printf("Found is %d\n", (int)(found == foo.end())); |
162 found = foo.find("bar"); | 233 found = foo.find("bar"); |
163 printf("Found is %d\n", (int)(found == foo.end())); | 234 printf("Found is %d\n", (int)(found == foo.end())); |
164 found = foo.find("asdfhf"); | 235 found = foo.find("asdfhf"); |
165 printf("Found is %d\n", (int)(found == foo.end())); | 236 printf("Found is %d\n", (int)(found == foo.end())); |
166 found = foo.find("bar1"); | 237 found = foo.find("bar1"); |
167 printf("Found is %d\n", (int)(found == foo.end())); | 238 printf("Found is %d\n", (int)(found == foo.end())); |
168 } | 239 } |
169 ``` | 240 ``` |
170 | 241 |
OLD | NEW |