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