1 // Copyright 2011 The Chromium Authors
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 <forward_list>
12 #include <iterator>
13 #include <type_traits>
14
15 #include "base/check.h"
16 #include "base/ranges/algorithm.h"
17
18 namespace base {
19
20 namespace internal {
21
22 template <typename Iter>
23 constexpr bool IsRandomAccessIter =
24 std::is_same_v<typename std::iterator_traits<Iter>::iterator_category,
25 std::random_access_iterator_tag>;
26
27 } // namespace internal
28
29 // Returns a const reference to the underlying container of a container adapter.
30 // Works for std::priority_queue, std::queue, and std::stack.
31 template <class A>
GetUnderlyingContainer(const A & adapter)32 const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
33 struct ExposedAdapter : A {
34 using A::c;
35 };
36 return adapter.*&ExposedAdapter::c;
37 }
38
39 // Clears internal memory of an STL object.
40 // STL clear()/reserve(0) does not always free internal memory allocated
41 // This function uses swap/destructor to ensure the internal memory is freed.
42 template<class T>
STLClearObject(T * obj)43 void STLClearObject(T* obj) {
44 T tmp;
45 tmp.swap(*obj);
46 // Sometimes "T tmp" allocates objects with memory (arena implementation?).
47 // Hence using additional reserve(0) even if it doesn't always work.
48 obj->reserve(0);
49 }
50
51 // Returns a new ResultType containing the difference of two sorted containers.
52 template <typename ResultType, typename Arg1, typename Arg2>
STLSetDifference(const Arg1 & a1,const Arg2 & a2)53 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
54 DCHECK(ranges::is_sorted(a1));
55 DCHECK(ranges::is_sorted(a2));
56 ResultType difference;
57 std::set_difference(a1.begin(), a1.end(),
58 a2.begin(), a2.end(),
59 std::inserter(difference, difference.end()));
60 return difference;
61 }
62
63 // Returns a new ResultType containing the union of two sorted containers.
64 template <typename ResultType, typename Arg1, typename Arg2>
STLSetUnion(const Arg1 & a1,const Arg2 & a2)65 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
66 DCHECK(ranges::is_sorted(a1));
67 DCHECK(ranges::is_sorted(a2));
68 ResultType result;
69 std::set_union(a1.begin(), a1.end(),
70 a2.begin(), a2.end(),
71 std::inserter(result, result.end()));
72 return result;
73 }
74
75 // Returns a new ResultType containing the intersection of two sorted
76 // containers.
77 template <typename ResultType, typename Arg1, typename Arg2>
STLSetIntersection(const Arg1 & a1,const Arg2 & a2)78 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
79 DCHECK(ranges::is_sorted(a1));
80 DCHECK(ranges::is_sorted(a2));
81 ResultType result;
82 std::set_intersection(a1.begin(), a1.end(),
83 a2.begin(), a2.end(),
84 std::inserter(result, result.end()));
85 return result;
86 }
87
88 // A helper class to be used as the predicate with |EraseIf| to implement
89 // in-place set intersection. Helps implement the algorithm of going through
90 // each container an element at a time, erasing elements from the first
91 // container if they aren't in the second container. Requires each container be
92 // sorted. Note that the logic below appears inverted since it is returning
93 // whether an element should be erased.
94 template <class Collection>
95 class IsNotIn {
96 public:
IsNotIn(const Collection & collection)97 explicit IsNotIn(const Collection& collection)
98 : i_(collection.begin()), end_(collection.end()) {}
99
operator()100 bool operator()(const typename Collection::value_type& x) {
101 while (i_ != end_ && *i_ < x)
102 ++i_;
103 if (i_ == end_)
104 return true;
105 if (*i_ == x) {
106 ++i_;
107 return false;
108 }
109 return true;
110 }
111
112 private:
113 typename Collection::const_iterator i_;
114 const typename Collection::const_iterator end_;
115 };
116
117 } // namespace base
118
119 #endif // BASE_STL_UTIL_H_
120