| // Copyright 2011 The Chromium Authors | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| // Derived from google3/util/gtl/stl_util.h | |
| #ifndef BASE_STL_UTIL_H_ | |
| #define BASE_STL_UTIL_H_ | |
| #include <algorithm> | |
| #include <iterator> | |
| #include "polyfills/base/check.h" | |
| namespace gurl_base { | |
| // Returns a const reference to the underlying container of a container adapter. | |
| // Works for std::priority_queue, std::queue, and std::stack. | |
| template <class A> | |
| const typename A::container_type& GetUnderlyingContainer(const A& adapter) { | |
| struct ExposedAdapter : A { | |
| using A::c; | |
| }; | |
| return adapter.*&ExposedAdapter::c; | |
| } | |
| // Clears internal memory of an STL object. | |
| // STL clear()/reserve(0) does not always free internal memory allocated | |
| // This function uses swap/destructor to ensure the internal memory is freed. | |
| template <class T> | |
| void STLClearObject(T* obj) { | |
| T tmp; | |
| tmp.swap(*obj); | |
| // Sometimes "T tmp" allocates objects with memory (arena implementation?). | |
| // Hence using additional reserve(0) even if it doesn't always work. | |
| obj->reserve(0); | |
| } | |
| // Returns a new ResultType containing the difference of two sorted containers. | |
| template <typename ResultType, typename Arg1, typename Arg2> | |
| ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { | |
| GURL_DCHECK(std::ranges::is_sorted(a1)); | |
| GURL_DCHECK(std::ranges::is_sorted(a2)); | |
| ResultType difference; | |
| std::set_difference(a1.begin(), a1.end(), a2.begin(), a2.end(), | |
| std::inserter(difference, difference.end())); | |
| return difference; | |
| } | |
| // Returns a new ResultType containing the union of two sorted containers. | |
| template <typename ResultType, typename Arg1, typename Arg2> | |
| ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) { | |
| GURL_DCHECK(std::ranges::is_sorted(a1)); | |
| GURL_DCHECK(std::ranges::is_sorted(a2)); | |
| ResultType result; | |
| std::set_union(a1.begin(), a1.end(), a2.begin(), a2.end(), | |
| std::inserter(result, result.end())); | |
| return result; | |
| } | |
| // Returns a new ResultType containing the intersection of two sorted | |
| // containers. | |
| template <typename ResultType, typename Arg1, typename Arg2> | |
| ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) { | |
| GURL_DCHECK(std::ranges::is_sorted(a1)); | |
| GURL_DCHECK(std::ranges::is_sorted(a2)); | |
| ResultType result; | |
| std::set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(), | |
| std::inserter(result, result.end())); | |
| return result; | |
| } | |
| // A helper class to be used as the predicate with |EraseIf| to implement | |
| // in-place set intersection. Helps implement the algorithm of going through | |
| // each container an element at a time, erasing elements from the first | |
| // container if they aren't in the second container. Requires each container be | |
| // sorted. Note that the logic below appears inverted since it is returning | |
| // whether an element should be erased. | |
| template <class Collection> | |
| class IsNotIn { | |
| public: | |
| explicit IsNotIn(const Collection& collection) | |
| : it_(collection.begin()), end_(collection.end()) {} | |
| bool operator()(const typename Collection::value_type& x) { | |
| while (it_ != end_ && *it_ < x) { | |
| ++it_; | |
| } | |
| if (it_ == end_ || *it_ != x) { | |
| return true; | |
| } | |
| ++it_; | |
| return false; | |
| } | |
| private: | |
| typename Collection::const_iterator it_; | |
| const typename Collection::const_iterator end_; | |
| }; | |
| } // namespace base | |
| #endif // BASE_STL_UTIL_H_ |