base/stl_util.h

   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<typename std::iterator_traits<Iter>::iterator_category,
  25                  std::random_access_iterator_tag>::value;
  26
  27 }  // namespace internal
  28
  29 // Implementation of C++23's std::to_underlying.
  30 //
  31 // Note: This has an additional `std::is_enum<EnumT>` requirement to be SFINAE
  32 // friendly prior to C++20.
  33 //
  34 // Reference: https://en.cppreference.com/w/cpp/utility/to_underlying
  35 template <typename EnumT, typename = std::enable_if_t<std::is_enum<EnumT>{}>>
  36 constexpr std::underlying_type_t<EnumT> to_underlying(EnumT e) noexcept {
  37   return static_cast<std::underlying_type_t<EnumT>>(e);
  38 }
  39
  40 // Returns a const reference to the underlying container of a container adapter.
  41 // Works for std::priority_queue, std::queue, and std::stack.
  42 template <class A>
  43 const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
  44   struct ExposedAdapter : A {
  45     using A::c;
  46   };
  47   return adapter.*&ExposedAdapter::c;
  48 }
  49
  50 // Clears internal memory of an STL object.
  51 // STL clear()/reserve(0) does not always free internal memory allocated
  52 // This function uses swap/destructor to ensure the internal memory is freed.
  53 template<class T>
  54 void STLClearObject(T* obj) {
  55   T tmp;
  56   tmp.swap(*obj);
  57   // Sometimes "T tmp" allocates objects with memory (arena implementation?).
  58   // Hence using additional reserve(0) even if it doesn't always work.
  59   obj->reserve(0);
  60 }
  61
  62 // Counts the number of instances of val in a container.
  63 template <typename Container, typename T>
  64 typename std::iterator_traits<
  65     typename Container::const_iterator>::difference_type
  66 STLCount(const Container& container, const T& val) {
  67   return std::count(container.begin(), container.end(), val);
  68 }
  69
  70 // O(1) implementation of const casting an iterator for any sequence,
  71 // associative or unordered associative container in the STL.
  72 //
  73 // Reference: https://stackoverflow.com/a/10669041
  74 template <typename Container,
  75           typename ConstIter,
  76           std::enable_if_t<!internal::IsRandomAccessIter<ConstIter>>* = nullptr>
  77 constexpr auto ConstCastIterator(Container& c, ConstIter it) {
  78   return c.erase(it, it);
  79 }
  80
  81 // Explicit overload for std::forward_list where erase() is named erase_after().
  82 template <typename T, typename Allocator>
  83 constexpr auto ConstCastIterator(
  84     std::forward_list<T, Allocator>& c,
  85     typename std::forward_list<T, Allocator>::const_iterator it) {
  86 // The erase_after(it, it) trick used below does not work for libstdc++ [1],
  87 // thus we need a different way.
  88 // TODO(crbug.com/972541): Remove this workaround once libstdc++ is fixed on all
  89 // platforms.
  90 //
  91 // [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90857
  92 #if defined(__GLIBCXX__)
  93   return c.insert_after(it, {});
  94 #else
  95   return c.erase_after(it, it);
  96 #endif
  97 }
  98
  99 // Specialized O(1) const casting for random access iterators. This is
 100 // necessary, because erase() is either not available (e.g. array-like
 101 // containers), or has O(n) complexity (e.g. std::deque or std::vector).
 102 template <typename Container,
 103           typename ConstIter,
 104           std::enable_if_t<internal::IsRandomAccessIter<ConstIter>>* = nullptr>
 105 constexpr auto ConstCastIterator(Container& c, ConstIter it) {
 106   using std::begin;
 107   using std::cbegin;
 108   return begin(c) + (it - cbegin(c));
 109 }
 110
 111 // Returns a new ResultType containing the difference of two sorted containers.
 112 template <typename ResultType, typename Arg1, typename Arg2>
 113 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 114   DCHECK(ranges::is_sorted(a1));
 115   DCHECK(ranges::is_sorted(a2));
 116   ResultType difference;
 117   std::set_difference(a1.begin(), a1.end(),
 118                       a2.begin(), a2.end(),
 119                       std::inserter(difference, difference.end()));
 120   return difference;
 121 }
 122
 123 // Returns a new ResultType containing the union of two sorted containers.
 124 template <typename ResultType, typename Arg1, typename Arg2>
 125 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 126   DCHECK(ranges::is_sorted(a1));
 127   DCHECK(ranges::is_sorted(a2));
 128   ResultType result;
 129   std::set_union(a1.begin(), a1.end(),
 130                  a2.begin(), a2.end(),
 131                  std::inserter(result, result.end()));
 132   return result;
 133 }
 134
 135 // Returns a new ResultType containing the intersection of two sorted
 136 // containers.
 137 template <typename ResultType, typename Arg1, typename Arg2>
 138 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 139   DCHECK(ranges::is_sorted(a1));
 140   DCHECK(ranges::is_sorted(a2));
 141   ResultType result;
 142   std::set_intersection(a1.begin(), a1.end(),
 143                         a2.begin(), a2.end(),
 144                         std::inserter(result, result.end()));
 145   return result;
 146 }
 147
 148 // A helper class to be used as the predicate with |EraseIf| to implement
 149 // in-place set intersection. Helps implement the algorithm of going through
 150 // each container an element at a time, erasing elements from the first
 151 // container if they aren't in the second container. Requires each container be
 152 // sorted. Note that the logic below appears inverted since it is returning
 153 // whether an element should be erased.
 154 template <class Collection>
 155 class IsNotIn {
 156  public:
 157   explicit IsNotIn(const Collection& collection)
 158       : i_(collection.begin()), end_(collection.end()) {}
 159
 160   bool operator()(const typename Collection::value_type& x) {
 161     while (i_ != end_ && *i_ < x)
 162       ++i_;
 163     if (i_ == end_)
 164       return true;
 165     if (*i_ == x) {
 166       ++i_;
 167       return false;
 168     }
 169     return true;
 170   }
 171
 172  private:
 173   typename Collection::const_iterator i_;
 174   const typename Collection::const_iterator end_;
 175 };
 176
 177 }  // namespace base
 178
 179 #endif  // BASE_STL_UTIL_H_