xref: /third_party/gn/src/base/stl_util.h (revision 6d528ed9) 
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
26namespace base {
27
28namespace internal {
29
30// Calls erase on iterators of matching elements.
31template <typename Container, typename Predicate>
32void IterateAndEraseIf(Container& container, Predicate pred) {
33  for (auto it = container.begin(); it != container.end();) {
34    if (pred(*it))
35      it = container.erase(it);
36    else
37      ++it;
38  }
39}
40
41}  // namespace internal
42
43// Test to see if a set or map contains a particular key.
44// Returns true if the key is in the collection.
45template <typename Collection, typename Key>
46bool ContainsKey(const Collection& collection, const Key& key) {
47  return collection.find(key) != collection.end();
48}
49
50namespace internal {
51
52template <typename Collection>
53class HasKeyType {
54  template <typename C>
55  static std::true_type test(typename C::key_type*);
56  template <typename C>
57  static std::false_type test(...);
58
59 public:
60  static constexpr bool value = decltype(test<Collection>(nullptr))::value;
61};
62
63}  // namespace internal
64
65// Test to see if a collection like a vector contains a particular value.
66// Returns true if the value is in the collection.
67// Don't use this on collections such as sets or maps. This is enforced by
68// disabling this method if the collection defines a key_type.
69template <typename Collection,
70          typename Value,
71          typename std::enable_if<!internal::HasKeyType<Collection>::value,
72                                  int>::type = 0>
73bool ContainsValue(const Collection& collection, const Value& value) {
74  return std::find(std::begin(collection), std::end(collection), value) !=
75         std::end(collection);
76}
77
78// Returns true if the container is sorted.
79template <typename Container>
80bool STLIsSorted(const Container& cont) {
81  // Note: Use reverse iterator on container to ensure we only require
82  // value_type to implement operator<.
83  return std::adjacent_find(cont.rbegin(), cont.rend(),
84                            std::less<typename Container::value_type>()) ==
85         cont.rend();
86}
87
88// Returns a new ResultType containing the difference of two sorted containers.
89template <typename ResultType, typename Arg1, typename Arg2>
90ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
91  DCHECK(STLIsSorted(a1));
92  DCHECK(STLIsSorted(a2));
93  ResultType difference;
94  std::set_difference(a1.begin(), a1.end(), a2.begin(), a2.end(),
95                      std::inserter(difference, difference.end()));
96  return difference;
97}
98
99// Returns a new ResultType containing the union of two sorted containers.
100template <typename ResultType, typename Arg1, typename Arg2>
101ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
102  DCHECK(STLIsSorted(a1));
103  DCHECK(STLIsSorted(a2));
104  ResultType result;
105  std::set_union(a1.begin(), a1.end(), a2.begin(), a2.end(),
106                 std::inserter(result, result.end()));
107  return result;
108}
109
110// Returns a new ResultType containing the intersection of two sorted
111// containers.
112template <typename ResultType, typename Arg1, typename Arg2>
113ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
114  DCHECK(STLIsSorted(a1));
115  DCHECK(STLIsSorted(a2));
116  ResultType result;
117  std::set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(),
118                        std::inserter(result, result.end()));
119  return result;
120}
121
122// Returns true if the sorted container |a1| contains all elements of the sorted
123// container |a2|.
124template <typename Arg1, typename Arg2>
125bool STLIncludes(const Arg1& a1, const Arg2& a2) {
126  DCHECK(STLIsSorted(a1));
127  DCHECK(STLIsSorted(a2));
128  return std::includes(a1.begin(), a1.end(), a2.begin(), a2.end());
129}
130
131// Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if
132// http://en.cppreference.com/w/cpp/experimental/lib_extensions_2
133// They provide a generic way to erase elements from a container.
134// The functions here implement these for the standard containers until those
135// functions are available in the C++ standard.
136// For Chromium containers overloads should be defined in their own headers
137// (like standard containers).
138// Note: there is no std::erase for standard associative containers so we don't
139// have it either.
140
141template <typename CharT, typename Traits, typename Allocator, typename Value>
142void Erase(std::basic_string<CharT, Traits, Allocator>& container,
143           const Value& value) {
144  container.erase(std::remove(container.begin(), container.end(), value),
145                  container.end());
146}
147
148template <typename CharT, typename Traits, typename Allocator, class Predicate>
149void EraseIf(std::basic_string<CharT, Traits, Allocator>& container,
150             Predicate pred) {
151  container.erase(std::remove_if(container.begin(), container.end(), pred),
152                  container.end());
153}
154
155template <class T, class Allocator, class Value>
156void Erase(std::deque<T, Allocator>& container, const Value& value) {
157  container.erase(std::remove(container.begin(), container.end(), value),
158                  container.end());
159}
160
161template <class T, class Allocator, class Predicate>
162void EraseIf(std::deque<T, Allocator>& container, Predicate pred) {
163  container.erase(std::remove_if(container.begin(), container.end(), pred),
164                  container.end());
165}
166
167template <class T, class Allocator, class Value>
168void Erase(std::vector<T, Allocator>& container, const Value& value) {
169  container.erase(std::remove(container.begin(), container.end(), value),
170                  container.end());
171}
172
173template <class T, class Allocator, class Predicate>
174void EraseIf(std::vector<T, Allocator>& container, Predicate pred) {
175  container.erase(std::remove_if(container.begin(), container.end(), pred),
176                  container.end());
177}
178
179template <class T, class Allocator, class Value>
180void Erase(std::forward_list<T, Allocator>& container, const Value& value) {
181  // Unlike std::forward_list::remove, this function template accepts
182  // heterogeneous types and does not force a conversion to the container's
183  // value type before invoking the == operator.
184  container.remove_if([&](const T& cur) { return cur == value; });
185}
186
187template <class T, class Allocator, class Predicate>
188void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) {
189  container.remove_if(pred);
190}
191
192template <class T, class Allocator, class Value>
193void Erase(std::list<T, Allocator>& container, const Value& value) {
194  // Unlike std::list::remove, this function template accepts heterogeneous
195  // types and does not force a conversion to the container's value type before
196  // invoking the == operator.
197  container.remove_if([&](const T& cur) { return cur == value; });
198}
199
200template <class T, class Allocator, class Predicate>
201void EraseIf(std::list<T, Allocator>& container, Predicate pred) {
202  container.remove_if(pred);
203}
204
205template <class Key, class T, class Compare, class Allocator, class Predicate>
206void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) {
207  internal::IterateAndEraseIf(container, pred);
208}
209
210template <class Key, class T, class Compare, class Allocator, class Predicate>
211void EraseIf(std::multimap<Key, T, Compare, Allocator>& container,
212             Predicate pred) {
213  internal::IterateAndEraseIf(container, pred);
214}
215
216template <class Key, class Compare, class Allocator, class Predicate>
217void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) {
218  internal::IterateAndEraseIf(container, pred);
219}
220
221template <class Key, class Compare, class Allocator, class Predicate>
222void EraseIf(std::multiset<Key, Compare, Allocator>& container,
223             Predicate pred) {
224  internal::IterateAndEraseIf(container, pred);
225}
226
227template <class Key,
228          class T,
229          class Hash,
230          class KeyEqual,
231          class Allocator,
232          class Predicate>
233void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container,
234             Predicate pred) {
235  internal::IterateAndEraseIf(container, pred);
236}
237
238template <class Key,
239          class T,
240          class Hash,
241          class KeyEqual,
242          class Allocator,
243          class Predicate>
244void EraseIf(
245    std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container,
246    Predicate pred) {
247  internal::IterateAndEraseIf(container, pred);
248}
249
250template <class Key,
251          class Hash,
252          class KeyEqual,
253          class Allocator,
254          class Predicate>
255void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container,
256             Predicate pred) {
257  internal::IterateAndEraseIf(container, pred);
258}
259
260template <class Key,
261          class Hash,
262          class KeyEqual,
263          class Allocator,
264          class Predicate>
265void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container,
266             Predicate pred) {
267  internal::IterateAndEraseIf(container, pred);
268}
269
270}  // namespace base
271
272#endif  // BASE_STL_UTIL_H_
273