stl_util.h 6.6 KB

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