| // 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 <forward_list> |
| #include <iterator> |
| #include <type_traits> |
| |
| #include "polyfills/base/check.h" |
| #include "base/ranges/algorithm.h" |
| |
| namespace gurl_base { |
| |
| namespace internal { |
| |
| template <typename Iter> |
| constexpr bool IsRandomAccessIter = |
| std::is_same<typename std::iterator_traits<Iter>::iterator_category, |
| std::random_access_iterator_tag>::value; |
| |
| } // namespace internal |
| |
| // 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); |
| } |
| |
| // O(1) implementation of const casting an iterator for any sequence, |
| // associative or unordered associative container in the STL. |
| // |
| // Reference: https://stackoverflow.com/a/10669041 |
| template <typename Container, |
| typename ConstIter, |
| std::enable_if_t<!internal::IsRandomAccessIter<ConstIter>>* = nullptr> |
| constexpr auto ConstCastIterator(Container& c, ConstIter it) { |
| return c.erase(it, it); |
| } |
| |
| // Explicit overload for std::forward_list where erase() is named erase_after(). |
| template <typename T, typename Allocator> |
| constexpr auto ConstCastIterator( |
| std::forward_list<T, Allocator>& c, |
| typename std::forward_list<T, Allocator>::const_iterator it) { |
| // The erase_after(it, it) trick used below does not work for libstdc++ [1], |
| // thus we need a different way. |
| // TODO(crbug.com/972541): Remove this workaround once libstdc++ is fixed on all |
| // platforms. |
| // |
| // [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90857 |
| #if defined(__GLIBCXX__) |
| return c.insert_after(it, {}); |
| #else |
| return c.erase_after(it, it); |
| #endif |
| } |
| |
| // Specialized O(1) const casting for random access iterators. This is |
| // necessary, because erase() is either not available (e.g. array-like |
| // containers), or has O(n) complexity (e.g. std::deque or std::vector). |
| template <typename Container, |
| typename ConstIter, |
| std::enable_if_t<internal::IsRandomAccessIter<ConstIter>>* = nullptr> |
| constexpr auto ConstCastIterator(Container& c, ConstIter it) { |
| using std::begin; |
| using std::cbegin; |
| return begin(c) + (it - cbegin(c)); |
| } |
| |
| // 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(ranges::is_sorted(a1)); |
| GURL_DCHECK(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(ranges::is_sorted(a1)); |
| GURL_DCHECK(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(ranges::is_sorted(a1)); |
| GURL_DCHECK(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) |
| : i_(collection.begin()), end_(collection.end()) {} |
| |
| bool operator()(const typename Collection::value_type& x) { |
| while (i_ != end_ && *i_ < x) |
| ++i_; |
| if (i_ == end_) |
| return true; |
| if (*i_ == x) { |
| ++i_; |
| return false; |
| } |
| return true; |
| } |
| |
| private: |
| typename Collection::const_iterator i_; |
| const typename Collection::const_iterator end_; |
| }; |
| |
| } // namespace base |
| |
| #endif // BASE_STL_UTIL_H_ |