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 <initializer_list>
15#include <iterator>
16#include <list>
17#include <map>
18#include <set>
19#include <string>
20#include <unordered_map>
21#include <unordered_set>
22#include <vector>
23
24#include "base/logging.h"
25#include "base/optional.h"
26
27namespace base {
28
29namespace internal {
30
31// Calls erase on iterators of matching elements.
32template <typename Container, typename Predicate>
33void IterateAndEraseIf(Container& container, Predicate pred) {
34 for (auto it = container.begin(); it != container.end();) {
35 if (pred(*it))
36 it = container.erase(it);
37 else
38 ++it;
39 }
40}
41
42} // namespace internal
43
44// C++14 implementation of C++17's std::size():
45// http://en.cppreference.com/w/cpp/iterator/size
46template <typename Container>
47constexpr auto size(const Container& c) -> decltype(c.size()) {
48 return c.size();
49}
50
51template <typename T, size_t N>
52constexpr size_t size(const T (&array)[N]) noexcept {
53 return N;
54}
55
56// C++14 implementation of C++17's std::empty():
57// http://en.cppreference.com/w/cpp/iterator/empty
58template <typename Container>
59constexpr auto empty(const Container& c) -> decltype(c.empty()) {
60 return c.empty();
61}
62
63template <typename T, size_t N>
64constexpr bool empty(const T (&array)[N]) noexcept {
65 return false;
66}
67
68template <typename T>
69constexpr bool empty(std::initializer_list<T> il) noexcept {
70 return il.size() == 0;
71}
72
73// C++14 implementation of C++17's std::data():
74// http://en.cppreference.com/w/cpp/iterator/data
75template <typename Container>
76constexpr auto data(Container& c) -> decltype(c.data()) {
77 return c.data();
78}
79
80// std::basic_string::data() had no mutable overload prior to C++17 [1].
81// Hence this overload is provided.
82// Note: str[0] is safe even for empty strings, as they are guaranteed to be
83// null-terminated [2].
84//
85// [1] http://en.cppreference.com/w/cpp/string/basic_string/data
86// [2] http://en.cppreference.com/w/cpp/string/basic_string/operator_at
87template <typename CharT, typename Traits, typename Allocator>
88CharT* data(std::basic_string<CharT, Traits, Allocator>& str) {
89 return std::addressof(str[0]);
90}
91
92template <typename Container>
93constexpr auto data(const Container& c) -> decltype(c.data()) {
94 return c.data();
95}
96
97template <typename T, size_t N>
98constexpr T* data(T (&array)[N]) noexcept {
99 return array;
100}
101
102template <typename T>
103constexpr const T* data(std::initializer_list<T> il) noexcept {
104 return il.begin();
105}
106
107// Returns a const reference to the underlying container of a container adapter.
108// Works for std::priority_queue, std::queue, and std::stack.
109template <class A>
110const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
111 struct ExposedAdapter : A {
112 using A::c;
113 };
114 return adapter.*&ExposedAdapter::c;
115}
116
117// Clears internal memory of an STL object.
118// STL clear()/reserve(0) does not always free internal memory allocated
119// This function uses swap/destructor to ensure the internal memory is freed.
120template<class T>
121void STLClearObject(T* obj) {
122 T tmp;
123 tmp.swap(*obj);
124 // Sometimes "T tmp" allocates objects with memory (arena implementation?).
125 // Hence using additional reserve(0) even if it doesn't always work.
126 obj->reserve(0);
127}
128
129// Counts the number of instances of val in a container.
130template <typename Container, typename T>
131typename std::iterator_traits<
132 typename Container::const_iterator>::difference_type
133STLCount(const Container& container, const T& val) {
134 return std::count(container.begin(), container.end(), val);
135}
136
137// Test to see if a set or map contains a particular key.
138// Returns true if the key is in the collection.
139template <typename Collection, typename Key>
140bool ContainsKey(const Collection& collection, const Key& key) {
141 return collection.find(key) != collection.end();
142}
143
144namespace internal {
145
146template <typename Collection>
147class HasKeyType {
148 template <typename C>
149 static std::true_type test(typename C::key_type*);
150 template <typename C>
151 static std::false_type test(...);
152
153 public:
154 static constexpr bool value = decltype(test<Collection>(nullptr))::value;
155};
156
157} // namespace internal
158
159// Test to see if a collection like a vector contains a particular value.
160// Returns true if the value is in the collection.
161// Don't use this on collections such as sets or maps. This is enforced by
162// disabling this method if the collection defines a key_type.
163template <typename Collection,
164 typename Value,
165 typename std::enable_if<!internal::HasKeyType<Collection>::value,
166 int>::type = 0>
167bool ContainsValue(const Collection& collection, const Value& value) {
168 return std::find(std::begin(collection), std::end(collection), value) !=
169 std::end(collection);
170}
171
172// Returns true if the container is sorted.
173template <typename Container>
174bool STLIsSorted(const Container& cont) {
175 return std::is_sorted(std::begin(cont), std::end(cont));
176}
177
178// Returns a new ResultType containing the difference of two sorted containers.
179template <typename ResultType, typename Arg1, typename Arg2>
180ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
181 DCHECK(STLIsSorted(a1));
182 DCHECK(STLIsSorted(a2));
183 ResultType difference;
184 std::set_difference(a1.begin(), a1.end(),
185 a2.begin(), a2.end(),
186 std::inserter(difference, difference.end()));
187 return difference;
188}
189
190// Returns a new ResultType containing the union of two sorted containers.
191template <typename ResultType, typename Arg1, typename Arg2>
192ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
193 DCHECK(STLIsSorted(a1));
194 DCHECK(STLIsSorted(a2));
195 ResultType result;
196 std::set_union(a1.begin(), a1.end(),
197 a2.begin(), a2.end(),
198 std::inserter(result, result.end()));
199 return result;
200}
201
202// Returns a new ResultType containing the intersection of two sorted
203// containers.
204template <typename ResultType, typename Arg1, typename Arg2>
205ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
206 DCHECK(STLIsSorted(a1));
207 DCHECK(STLIsSorted(a2));
208 ResultType result;
209 std::set_intersection(a1.begin(), a1.end(),
210 a2.begin(), a2.end(),
211 std::inserter(result, result.end()));
212 return result;
213}
214
215// Returns true if the sorted container |a1| contains all elements of the sorted
216// container |a2|.
217template <typename Arg1, typename Arg2>
218bool STLIncludes(const Arg1& a1, const Arg2& a2) {
219 DCHECK(STLIsSorted(a1));
220 DCHECK(STLIsSorted(a2));
221 return std::includes(a1.begin(), a1.end(),
222 a2.begin(), a2.end());
223}
224
225// Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if
226// http://en.cppreference.com/w/cpp/experimental/lib_extensions_2
227// They provide a generic way to erase elements from a container.
228// The functions here implement these for the standard containers until those
229// functions are available in the C++ standard.
230// For Chromium containers overloads should be defined in their own headers
231// (like standard containers).
232// Note: there is no std::erase for standard associative containers so we don't
233// have it either.
234
235template <typename CharT, typename Traits, typename Allocator, typename Value>
236void Erase(std::basic_string<CharT, Traits, Allocator>& container,
237 const Value& value) {
238 container.erase(std::remove(container.begin(), container.end(), value),
239 container.end());
240}
241
242template <typename CharT, typename Traits, typename Allocator, class Predicate>
243void EraseIf(std::basic_string<CharT, Traits, Allocator>& container,
244 Predicate pred) {
245 container.erase(std::remove_if(container.begin(), container.end(), pred),
246 container.end());
247}
248
249template <class T, class Allocator, class Value>
250void Erase(std::deque<T, Allocator>& container, const Value& value) {
251 container.erase(std::remove(container.begin(), container.end(), value),
252 container.end());
253}
254
255template <class T, class Allocator, class Predicate>
256void EraseIf(std::deque<T, Allocator>& container, Predicate pred) {
257 container.erase(std::remove_if(container.begin(), container.end(), pred),
258 container.end());
259}
260
261template <class T, class Allocator, class Value>
262void Erase(std::vector<T, Allocator>& container, const Value& value) {
263 container.erase(std::remove(container.begin(), container.end(), value),
264 container.end());
265}
266
267template <class T, class Allocator, class Predicate>
268void EraseIf(std::vector<T, Allocator>& container, Predicate pred) {
269 container.erase(std::remove_if(container.begin(), container.end(), pred),
270 container.end());
271}
272
273template <class T, class Allocator, class Value>
274void Erase(std::forward_list<T, Allocator>& container, const Value& value) {
275 // Unlike std::forward_list::remove, this function template accepts
276 // heterogeneous types and does not force a conversion to the container's
277 // value type before invoking the == operator.
278 container.remove_if([&](const T& cur) { return cur == value; });
279}
280
281template <class T, class Allocator, class Predicate>
282void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) {
283 container.remove_if(pred);
284}
285
286template <class T, class Allocator, class Value>
287void Erase(std::list<T, Allocator>& container, const Value& value) {
288 // Unlike std::list::remove, this function template accepts heterogeneous
289 // types and does not force a conversion to the container's value type before
290 // invoking the == operator.
291 container.remove_if([&](const T& cur) { return cur == value; });
292}
293
294template <class T, class Allocator, class Predicate>
295void EraseIf(std::list<T, Allocator>& container, Predicate pred) {
296 container.remove_if(pred);
297}
298
299template <class Key, class T, class Compare, class Allocator, class Predicate>
300void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) {
301 internal::IterateAndEraseIf(container, pred);
302}
303
304template <class Key, class T, class Compare, class Allocator, class Predicate>
305void EraseIf(std::multimap<Key, T, Compare, Allocator>& container,
306 Predicate pred) {
307 internal::IterateAndEraseIf(container, pred);
308}
309
310template <class Key, class Compare, class Allocator, class Predicate>
311void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) {
312 internal::IterateAndEraseIf(container, pred);
313}
314
315template <class Key, class Compare, class Allocator, class Predicate>
316void EraseIf(std::multiset<Key, Compare, Allocator>& container,
317 Predicate pred) {
318 internal::IterateAndEraseIf(container, pred);
319}
320
321template <class Key,
322 class T,
323 class Hash,
324 class KeyEqual,
325 class Allocator,
326 class Predicate>
327void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container,
328 Predicate pred) {
329 internal::IterateAndEraseIf(container, pred);
330}
331
332template <class Key,
333 class T,
334 class Hash,
335 class KeyEqual,
336 class Allocator,
337 class Predicate>
338void EraseIf(
339 std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container,
340 Predicate pred) {
341 internal::IterateAndEraseIf(container, pred);
342}
343
344template <class Key,
345 class Hash,
346 class KeyEqual,
347 class Allocator,
348 class Predicate>
349void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container,
350 Predicate pred) {
351 internal::IterateAndEraseIf(container, pred);
352}
353
354template <class Key,
355 class Hash,
356 class KeyEqual,
357 class Allocator,
358 class Predicate>
359void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container,
360 Predicate pred) {
361 internal::IterateAndEraseIf(container, pred);
362}
363
364// A helper class to be used as the predicate with |EraseIf| to implement
365// in-place set intersection. Helps implement the algorithm of going through
366// each container an element at a time, erasing elements from the first
367// container if they aren't in the second container. Requires each container be
368// sorted. Note that the logic below appears inverted since it is returning
369// whether an element should be erased.
370template <class Collection>
371class IsNotIn {
372 public:
373 explicit IsNotIn(const Collection& collection)
374 : i_(collection.begin()), end_(collection.end()) {}
375
376 bool operator()(const typename Collection::value_type& x) {
377 while (i_ != end_ && *i_ < x)
378 ++i_;
379 if (i_ == end_)
380 return true;
381 if (*i_ == x) {
382 ++i_;
383 return false;
384 }
385 return true;
386 }
387
388 private:
389 typename Collection::const_iterator i_;
390 const typename Collection::const_iterator end_;
391};
392
393// Helper for returning the optional value's address, or nullptr.
394template <class T>
395T* OptionalOrNullptr(base::Optional<T>& optional) {
396 return optional.has_value() ? &optional.value() : nullptr;
397}
398
399template <class T>
400const T* OptionalOrNullptr(const base::Optional<T>& optional) {
401 return optional.has_value() ? &optional.value() : nullptr;
402}
403
404} // namespace base
405
406#endif // BASE_STL_UTIL_H_
407