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_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>
  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>
  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>
  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>
  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>
  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:
  97   explicit IsNotIn(const Collection& collection)
  98       : i_(collection.begin()), end_(collection.end()) {}
  99
 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_