1 // Copyright (c) 2011 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 // Derived from google3/util/gtl/stl_util.h
6
7 #ifndef BASE_STL_UTIL_H_
8 #define BASE_STL_UTIL_H_
9
10 #include <algorithm>
11 #include <deque>
12 #include <forward_list>
13 #include <functional>
14 #include <iterator>
15 #include <list>
16 #include <map>
17 #include <set>
18 #include <string>
19 #include <unordered_map>
20 #include <unordered_set>
21 #include <vector>
22
23 #include "base/logging.h"
24
25 namespace base {
26
27 namespace internal {
28
29 // Calls erase on iterators of matching elements.
30 template <typename Container, typename Predicate>
IterateAndEraseIf(Container & container,Predicate pred)31 void IterateAndEraseIf(Container& container, Predicate pred) {
32 for (auto it = container.begin(); it != container.end();) {
33 if (pred(*it))
34 it = container.erase(it);
35 else
36 ++it;
37 }
38 }
39
40 } // namespace internal
41
42 // Clears internal memory of an STL object.
43 // STL clear()/reserve(0) does not always free internal memory allocated
44 // This function uses swap/destructor to ensure the internal memory is freed.
45 template<class T>
STLClearObject(T * obj)46 void STLClearObject(T* obj) {
47 T tmp;
48 tmp.swap(*obj);
49 // Sometimes "T tmp" allocates objects with memory (arena implementation?).
50 // Hence using additional reserve(0) even if it doesn't always work.
51 obj->reserve(0);
52 }
53
54 // Counts the number of instances of val in a container.
55 template <typename Container, typename T>
56 typename std::iterator_traits<
57 typename Container::const_iterator>::difference_type
STLCount(const Container & container,const T & val)58 STLCount(const Container& container, const T& val) {
59 return std::count(container.begin(), container.end(), val);
60 }
61
62 // Return a mutable char* pointing to a string's internal buffer,
63 // which may not be null-terminated. Writing through this pointer will
64 // modify the string.
65 //
66 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
67 // next call to a string method that invalidates iterators.
68 //
69 // As of 2006-04, there is no standard-blessed way of getting a
70 // mutable reference to a string's internal buffer. However, issue 530
71 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530)
72 // proposes this as the method. According to Matt Austern, this should
73 // already work on all current implementations.
string_as_array(std::string * str)74 inline char* string_as_array(std::string* str) {
75 // DO NOT USE const_cast<char*>(str->data())
76 return str->empty() ? NULL : &*str->begin();
77 }
78
79 // Test to see if a set or map contains a particular key.
80 // Returns true if the key is in the collection.
81 template <typename Collection, typename Key>
ContainsKey(const Collection & collection,const Key & key)82 bool ContainsKey(const Collection& collection, const Key& key) {
83 return collection.find(key) != collection.end();
84 }
85
86 namespace internal {
87
88 template <typename Collection>
89 class HasKeyType {
90 template <typename C>
91 static std::true_type test(typename C::key_type*);
92 template <typename C>
93 static std::false_type test(...);
94
95 public:
96 static constexpr bool value = decltype(test<Collection>(nullptr))::value;
97 };
98
99 } // namespace internal
100
101 // Test to see if a collection like a vector contains a particular value.
102 // Returns true if the value is in the collection.
103 // Don't use this on collections such as sets or maps. This is enforced by
104 // disabling this method if the collection defines a key_type.
105 template <typename Collection,
106 typename Value,
107 typename std::enable_if<!internal::HasKeyType<Collection>::value,
108 int>::type = 0>
ContainsValue(const Collection & collection,const Value & value)109 bool ContainsValue(const Collection& collection, const Value& value) {
110 return std::find(std::begin(collection), std::end(collection), value) !=
111 std::end(collection);
112 }
113
114 // Returns true if the container is sorted.
115 template <typename Container>
STLIsSorted(const Container & cont)116 bool STLIsSorted(const Container& cont) {
117 // Note: Use reverse iterator on container to ensure we only require
118 // value_type to implement operator<.
119 return std::adjacent_find(cont.rbegin(), cont.rend(),
120 std::less<typename Container::value_type>())
121 == cont.rend();
122 }
123
124 // Returns a new ResultType containing the difference of two sorted containers.
125 template <typename ResultType, typename Arg1, typename Arg2>
STLSetDifference(const Arg1 & a1,const Arg2 & a2)126 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
127 DCHECK(STLIsSorted(a1));
128 DCHECK(STLIsSorted(a2));
129 ResultType difference;
130 std::set_difference(a1.begin(), a1.end(),
131 a2.begin(), a2.end(),
132 std::inserter(difference, difference.end()));
133 return difference;
134 }
135
136 // Returns a new ResultType containing the union of two sorted containers.
137 template <typename ResultType, typename Arg1, typename Arg2>
STLSetUnion(const Arg1 & a1,const Arg2 & a2)138 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
139 DCHECK(STLIsSorted(a1));
140 DCHECK(STLIsSorted(a2));
141 ResultType result;
142 std::set_union(a1.begin(), a1.end(),
143 a2.begin(), a2.end(),
144 std::inserter(result, result.end()));
145 return result;
146 }
147
148 // Returns a new ResultType containing the intersection of two sorted
149 // containers.
150 template <typename ResultType, typename Arg1, typename Arg2>
STLSetIntersection(const Arg1 & a1,const Arg2 & a2)151 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
152 DCHECK(STLIsSorted(a1));
153 DCHECK(STLIsSorted(a2));
154 ResultType result;
155 std::set_intersection(a1.begin(), a1.end(),
156 a2.begin(), a2.end(),
157 std::inserter(result, result.end()));
158 return result;
159 }
160
161 // Returns true if the sorted container |a1| contains all elements of the sorted
162 // container |a2|.
163 template <typename Arg1, typename Arg2>
STLIncludes(const Arg1 & a1,const Arg2 & a2)164 bool STLIncludes(const Arg1& a1, const Arg2& a2) {
165 DCHECK(STLIsSorted(a1));
166 DCHECK(STLIsSorted(a2));
167 return std::includes(a1.begin(), a1.end(),
168 a2.begin(), a2.end());
169 }
170
171 // Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if
172 // http://en.cppreference.com/w/cpp/experimental/lib_extensions_2
173 // They provide a generic way to erase elements from a container.
174 // The functions here implement these for the standard containers until those
175 // functions are available in the C++ standard.
176 // For Chromium containers overloads should be defined in their own headers
177 // (like standard containers).
178 // Note: there is no std::erase for standard associative containers so we don't
179 // have it either.
180
181 template <typename CharT, typename Traits, typename Allocator, typename Value>
Erase(std::basic_string<CharT,Traits,Allocator> & container,const Value & value)182 void Erase(std::basic_string<CharT, Traits, Allocator>& container,
183 const Value& value) {
184 container.erase(std::remove(container.begin(), container.end(), value),
185 container.end());
186 }
187
188 template <typename CharT, typename Traits, typename Allocator, class Predicate>
EraseIf(std::basic_string<CharT,Traits,Allocator> & container,Predicate pred)189 void EraseIf(std::basic_string<CharT, Traits, Allocator>& container,
190 Predicate pred) {
191 container.erase(std::remove_if(container.begin(), container.end(), pred),
192 container.end());
193 }
194
195 template <class T, class Allocator, class Value>
Erase(std::deque<T,Allocator> & container,const Value & value)196 void Erase(std::deque<T, Allocator>& container, const Value& value) {
197 container.erase(std::remove(container.begin(), container.end(), value),
198 container.end());
199 }
200
201 template <class T, class Allocator, class Predicate>
EraseIf(std::deque<T,Allocator> & container,Predicate pred)202 void EraseIf(std::deque<T, Allocator>& container, Predicate pred) {
203 container.erase(std::remove_if(container.begin(), container.end(), pred),
204 container.end());
205 }
206
207 template <class T, class Allocator, class Value>
Erase(std::vector<T,Allocator> & container,const Value & value)208 void Erase(std::vector<T, Allocator>& container, const Value& value) {
209 container.erase(std::remove(container.begin(), container.end(), value),
210 container.end());
211 }
212
213 template <class T, class Allocator, class Predicate>
EraseIf(std::vector<T,Allocator> & container,Predicate pred)214 void EraseIf(std::vector<T, Allocator>& container, Predicate pred) {
215 container.erase(std::remove_if(container.begin(), container.end(), pred),
216 container.end());
217 }
218
219 template <class T, class Allocator, class Value>
Erase(std::forward_list<T,Allocator> & container,const Value & value)220 void Erase(std::forward_list<T, Allocator>& container, const Value& value) {
221 // Unlike std::forward_list::remove, this function template accepts
222 // heterogeneous types and does not force a conversion to the container's
223 // value type before invoking the == operator.
224 container.remove_if([&](const T& cur) { return cur == value; });
225 }
226
227 template <class T, class Allocator, class Predicate>
EraseIf(std::forward_list<T,Allocator> & container,Predicate pred)228 void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) {
229 container.remove_if(pred);
230 }
231
232 template <class T, class Allocator, class Value>
Erase(std::list<T,Allocator> & container,const Value & value)233 void Erase(std::list<T, Allocator>& container, const Value& value) {
234 // Unlike std::list::remove, this function template accepts heterogeneous
235 // types and does not force a conversion to the container's value type before
236 // invoking the == operator.
237 container.remove_if([&](const T& cur) { return cur == value; });
238 }
239
240 template <class T, class Allocator, class Predicate>
EraseIf(std::list<T,Allocator> & container,Predicate pred)241 void EraseIf(std::list<T, Allocator>& container, Predicate pred) {
242 container.remove_if(pred);
243 }
244
245 template <class Key, class T, class Compare, class Allocator, class Predicate>
EraseIf(std::map<Key,T,Compare,Allocator> & container,Predicate pred)246 void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) {
247 internal::IterateAndEraseIf(container, pred);
248 }
249
250 template <class Key, class T, class Compare, class Allocator, class Predicate>
EraseIf(std::multimap<Key,T,Compare,Allocator> & container,Predicate pred)251 void EraseIf(std::multimap<Key, T, Compare, Allocator>& container,
252 Predicate pred) {
253 internal::IterateAndEraseIf(container, pred);
254 }
255
256 template <class Key, class Compare, class Allocator, class Predicate>
EraseIf(std::set<Key,Compare,Allocator> & container,Predicate pred)257 void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) {
258 internal::IterateAndEraseIf(container, pred);
259 }
260
261 template <class Key, class Compare, class Allocator, class Predicate>
EraseIf(std::multiset<Key,Compare,Allocator> & container,Predicate pred)262 void EraseIf(std::multiset<Key, Compare, Allocator>& container,
263 Predicate pred) {
264 internal::IterateAndEraseIf(container, pred);
265 }
266
267 template <class Key,
268 class T,
269 class Hash,
270 class KeyEqual,
271 class Allocator,
272 class Predicate>
EraseIf(std::unordered_map<Key,T,Hash,KeyEqual,Allocator> & container,Predicate pred)273 void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container,
274 Predicate pred) {
275 internal::IterateAndEraseIf(container, pred);
276 }
277
278 template <class Key,
279 class T,
280 class Hash,
281 class KeyEqual,
282 class Allocator,
283 class Predicate>
EraseIf(std::unordered_multimap<Key,T,Hash,KeyEqual,Allocator> & container,Predicate pred)284 void EraseIf(
285 std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container,
286 Predicate pred) {
287 internal::IterateAndEraseIf(container, pred);
288 }
289
290 template <class Key,
291 class Hash,
292 class KeyEqual,
293 class Allocator,
294 class Predicate>
EraseIf(std::unordered_set<Key,Hash,KeyEqual,Allocator> & container,Predicate pred)295 void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container,
296 Predicate pred) {
297 internal::IterateAndEraseIf(container, pred);
298 }
299
300 template <class Key,
301 class Hash,
302 class KeyEqual,
303 class Allocator,
304 class Predicate>
EraseIf(std::unordered_multiset<Key,Hash,KeyEqual,Allocator> & container,Predicate pred)305 void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container,
306 Predicate pred) {
307 internal::IterateAndEraseIf(container, pred);
308 }
309
310 } // namespace base
311
312 #endif // BASE_STL_UTIL_H_
313