base/stl_util.h

   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
   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 <tuple>
  14 #include <type_traits>
  15 #include <utility>
  16
  17 #include "base/check.h"
  18 #include "base/ranges/algorithm.h"
  19 #include "third_party/abseil-cpp/absl/types/optional.h"
  20
  21 namespace base {
  22
  23 namespace internal {
  24
  25 template <typename Iter>
  26 constexpr bool IsRandomAccessIter =
  27     std::is_same<typename std::iterator_traits<Iter>::iterator_category,
  28                  std::random_access_iterator_tag>::value;
  29
  30 }  // namespace internal
  31
  32 // Implementation of C++23's std::to_underlying.
  33 //
  34 // Note: This has an additional `std::is_enum<EnumT>` requirement to be SFINAE
  35 // friendly prior to C++20.
  36 //
  37 // Reference: https://en.cppreference.com/w/cpp/utility/to_underlying
  38 template <typename EnumT, typename = std::enable_if_t<std::is_enum<EnumT>{}>>
  39 constexpr std::underlying_type_t<EnumT> to_underlying(EnumT e) noexcept {
  40   return static_cast<std::underlying_type_t<EnumT>>(e);
  41 }
  42
  43 // Returns a const reference to the underlying container of a container adapter.
  44 // Works for std::priority_queue, std::queue, and std::stack.
  45 template <class A>
  46 const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
  47   struct ExposedAdapter : A {
  48     using A::c;
  49   };
  50   return adapter.*&ExposedAdapter::c;
  51 }
  52
  53 // Clears internal memory of an STL object.
  54 // STL clear()/reserve(0) does not always free internal memory allocated
  55 // This function uses swap/destructor to ensure the internal memory is freed.
  56 template<class T>
  57 void STLClearObject(T* obj) {
  58   T tmp;
  59   tmp.swap(*obj);
  60   // Sometimes "T tmp" allocates objects with memory (arena implementation?).
  61   // Hence using additional reserve(0) even if it doesn't always work.
  62   obj->reserve(0);
  63 }
  64
  65 // Counts the number of instances of val in a container.
  66 template <typename Container, typename T>
  67 typename std::iterator_traits<
  68     typename Container::const_iterator>::difference_type
  69 STLCount(const Container& container, const T& val) {
  70   return std::count(container.begin(), container.end(), val);
  71 }
  72
  73 // O(1) implementation of const casting an iterator for any sequence,
  74 // associative or unordered associative container in the STL.
  75 //
  76 // Reference: https://stackoverflow.com/a/10669041
  77 template <typename Container,
  78           typename ConstIter,
  79           std::enable_if_t<!internal::IsRandomAccessIter<ConstIter>>* = nullptr>
  80 constexpr auto ConstCastIterator(Container& c, ConstIter it) {
  81   return c.erase(it, it);
  82 }
  83
  84 // Explicit overload for std::forward_list where erase() is named erase_after().
  85 template <typename T, typename Allocator>
  86 constexpr auto ConstCastIterator(
  87     std::forward_list<T, Allocator>& c,
  88     typename std::forward_list<T, Allocator>::const_iterator it) {
  89 // The erase_after(it, it) trick used below does not work for libstdc++ [1],
  90 // thus we need a different way.
  91 // TODO(crbug.com/972541): Remove this workaround once libstdc++ is fixed on all
  92 // platforms.
  93 //
  94 // [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90857
  95 #if defined(__GLIBCXX__)
  96   return c.insert_after(it, {});
  97 #else
  98   return c.erase_after(it, it);
  99 #endif
 100 }
 101
 102 // Specialized O(1) const casting for random access iterators. This is
 103 // necessary, because erase() is either not available (e.g. array-like
 104 // containers), or has O(n) complexity (e.g. std::deque or std::vector).
 105 template <typename Container,
 106           typename ConstIter,
 107           std::enable_if_t<internal::IsRandomAccessIter<ConstIter>>* = nullptr>
 108 constexpr auto ConstCastIterator(Container& c, ConstIter it) {
 109   using std::begin;
 110   using std::cbegin;
 111   return begin(c) + (it - cbegin(c));
 112 }
 113
 114 namespace internal {
 115
 116 template <typename Map, typename Key, typename Value>
 117 std::pair<typename Map::iterator, bool> InsertOrAssignImpl(Map& map,
 118                                                            Key&& key,
 119                                                            Value&& value) {
 120   auto lower = map.lower_bound(key);
 121   if (lower != map.end() && !map.key_comp()(key, lower->first)) {
 122     // key already exists, perform assignment.
 123     lower->second = std::forward<Value>(value);
 124     return {lower, false};
 125   }
 126
 127   // key did not yet exist, insert it.
 128   return {map.emplace_hint(lower, std::forward<Key>(key),
 129                            std::forward<Value>(value)),
 130           true};
 131 }
 132
 133 template <typename Map, typename Key, typename Value>
 134 typename Map::iterator InsertOrAssignImpl(Map& map,
 135                                           typename Map::const_iterator hint,
 136                                           Key&& key,
 137                                           Value&& value) {
 138   auto&& key_comp = map.key_comp();
 139   if ((hint == map.begin() || key_comp(std::prev(hint)->first, key))) {
 140     if (hint == map.end() || key_comp(key, hint->first)) {
 141       // *(hint - 1) < key < *hint => key did not exist and hint is correct.
 142       return map.emplace_hint(hint, std::forward<Key>(key),
 143                               std::forward<Value>(value));
 144     }
 145
 146     if (!key_comp(hint->first, key)) {
 147       // key == *hint => key already exists and hint is correct.
 148       auto mutable_hint = ConstCastIterator(map, hint);
 149       mutable_hint->second = std::forward<Value>(value);
 150       return mutable_hint;
 151     }
 152   }
 153
 154   // hint was not helpful, dispatch to hintless version.
 155   return InsertOrAssignImpl(map, std::forward<Key>(key),
 156                             std::forward<Value>(value))
 157       .first;
 158 }
 159
 160 template <typename Map, typename Key, typename... Args>
 161 std::pair<typename Map::iterator, bool> TryEmplaceImpl(Map& map,
 162                                                        Key&& key,
 163                                                        Args&&... args) {
 164   auto lower = map.lower_bound(key);
 165   if (lower != map.end() && !map.key_comp()(key, lower->first)) {
 166     // key already exists, do nothing.
 167     return {lower, false};
 168   }
 169
 170   // key did not yet exist, insert it.
 171   return {map.emplace_hint(lower, std::piecewise_construct,
 172                            std::forward_as_tuple(std::forward<Key>(key)),
 173                            std::forward_as_tuple(std::forward<Args>(args)...)),
 174           true};
 175 }
 176
 177 template <typename Map, typename Key, typename... Args>
 178 typename Map::iterator TryEmplaceImpl(Map& map,
 179                                       typename Map::const_iterator hint,
 180                                       Key&& key,
 181                                       Args&&... args) {
 182   auto&& key_comp = map.key_comp();
 183   if ((hint == map.begin() || key_comp(std::prev(hint)->first, key))) {
 184     if (hint == map.end() || key_comp(key, hint->first)) {
 185       // *(hint - 1) < key < *hint => key did not exist and hint is correct.
 186       return map.emplace_hint(
 187           hint, std::piecewise_construct,
 188           std::forward_as_tuple(std::forward<Key>(key)),
 189           std::forward_as_tuple(std::forward<Args>(args)...));
 190     }
 191
 192     if (!key_comp(hint->first, key)) {
 193       // key == *hint => no-op, return correct hint.
 194       return ConstCastIterator(map, hint);
 195     }
 196   }
 197
 198   // hint was not helpful, dispatch to hintless version.
 199   return TryEmplaceImpl(map, std::forward<Key>(key),
 200                         std::forward<Args>(args)...)
 201       .first;
 202 }
 203
 204 }  // namespace internal
 205
 206 // Implementation of C++17's std::map::insert_or_assign as a free function.
 207 template <typename Map, typename Value>
 208 std::pair<typename Map::iterator, bool>
 209 InsertOrAssign(Map& map, const typename Map::key_type& key, Value&& value) {
 210   return internal::InsertOrAssignImpl(map, key, std::forward<Value>(value));
 211 }
 212
 213 template <typename Map, typename Value>
 214 std::pair<typename Map::iterator, bool>
 215 InsertOrAssign(Map& map, typename Map::key_type&& key, Value&& value) {
 216   return internal::InsertOrAssignImpl(map, std::move(key),
 217                                       std::forward<Value>(value));
 218 }
 219
 220 // Implementation of C++17's std::map::insert_or_assign with hint as a free
 221 // function.
 222 template <typename Map, typename Value>
 223 typename Map::iterator InsertOrAssign(Map& map,
 224                                       typename Map::const_iterator hint,
 225                                       const typename Map::key_type& key,
 226                                       Value&& value) {
 227   return internal::InsertOrAssignImpl(map, hint, key,
 228                                       std::forward<Value>(value));
 229 }
 230
 231 template <typename Map, typename Value>
 232 typename Map::iterator InsertOrAssign(Map& map,
 233                                       typename Map::const_iterator hint,
 234                                       typename Map::key_type&& key,
 235                                       Value&& value) {
 236   return internal::InsertOrAssignImpl(map, hint, std::move(key),
 237                                       std::forward<Value>(value));
 238 }
 239
 240 // Implementation of C++17's std::map::try_emplace as a free function.
 241 template <typename Map, typename... Args>
 242 std::pair<typename Map::iterator, bool>
 243 TryEmplace(Map& map, const typename Map::key_type& key, Args&&... args) {
 244   return internal::TryEmplaceImpl(map, key, std::forward<Args>(args)...);
 245 }
 246
 247 template <typename Map, typename... Args>
 248 std::pair<typename Map::iterator, bool> TryEmplace(Map& map,
 249                                                    typename Map::key_type&& key,
 250                                                    Args&&... args) {
 251   return internal::TryEmplaceImpl(map, std::move(key),
 252                                   std::forward<Args>(args)...);
 253 }
 254
 255 // Implementation of C++17's std::map::try_emplace with hint as a free
 256 // function.
 257 template <typename Map, typename... Args>
 258 typename Map::iterator TryEmplace(Map& map,
 259                                   typename Map::const_iterator hint,
 260                                   const typename Map::key_type& key,
 261                                   Args&&... args) {
 262   return internal::TryEmplaceImpl(map, hint, key, std::forward<Args>(args)...);
 263 }
 264
 265 template <typename Map, typename... Args>
 266 typename Map::iterator TryEmplace(Map& map,
 267                                   typename Map::const_iterator hint,
 268                                   typename Map::key_type&& key,
 269                                   Args&&... args) {
 270   return internal::TryEmplaceImpl(map, hint, std::move(key),
 271                                   std::forward<Args>(args)...);
 272 }
 273
 274 // Returns a new ResultType containing the difference of two sorted containers.
 275 template <typename ResultType, typename Arg1, typename Arg2>
 276 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 277   DCHECK(ranges::is_sorted(a1));
 278   DCHECK(ranges::is_sorted(a2));
 279   ResultType difference;
 280   std::set_difference(a1.begin(), a1.end(),
 281                       a2.begin(), a2.end(),
 282                       std::inserter(difference, difference.end()));
 283   return difference;
 284 }
 285
 286 // Returns a new ResultType containing the union of two sorted containers.
 287 template <typename ResultType, typename Arg1, typename Arg2>
 288 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 289   DCHECK(ranges::is_sorted(a1));
 290   DCHECK(ranges::is_sorted(a2));
 291   ResultType result;
 292   std::set_union(a1.begin(), a1.end(),
 293                  a2.begin(), a2.end(),
 294                  std::inserter(result, result.end()));
 295   return result;
 296 }
 297
 298 // Returns a new ResultType containing the intersection of two sorted
 299 // containers.
 300 template <typename ResultType, typename Arg1, typename Arg2>
 301 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 302   DCHECK(ranges::is_sorted(a1));
 303   DCHECK(ranges::is_sorted(a2));
 304   ResultType result;
 305   std::set_intersection(a1.begin(), a1.end(),
 306                         a2.begin(), a2.end(),
 307                         std::inserter(result, result.end()));
 308   return result;
 309 }
 310
 311 // A helper class to be used as the predicate with |EraseIf| to implement
 312 // in-place set intersection. Helps implement the algorithm of going through
 313 // each container an element at a time, erasing elements from the first
 314 // container if they aren't in the second container. Requires each container be
 315 // sorted. Note that the logic below appears inverted since it is returning
 316 // whether an element should be erased.
 317 template <class Collection>
 318 class IsNotIn {
 319  public:
 320   explicit IsNotIn(const Collection& collection)
 321       : i_(collection.begin()), end_(collection.end()) {}
 322
 323   bool operator()(const typename Collection::value_type& x) {
 324     while (i_ != end_ && *i_ < x)
 325       ++i_;
 326     if (i_ == end_)
 327       return true;
 328     if (*i_ == x) {
 329       ++i_;
 330       return false;
 331     }
 332     return true;
 333   }
 334
 335  private:
 336   typename Collection::const_iterator i_;
 337   const typename Collection::const_iterator end_;
 338 };
 339
 340 // Helper for returning the optional value's address, or nullptr.
 341 template <class T>
 342 T* OptionalOrNullptr(absl::optional<T>& optional) {
 343   return optional.has_value() ? &optional.value() : nullptr;
 344 }
 345
 346 template <class T>
 347 const T* OptionalOrNullptr(const absl::optional<T>& optional) {
 348   return optional.has_value() ? &optional.value() : nullptr;
 349 }
 350
 351 // Helper for creating an optional<T> from a potentially nullptr T*.
 352 template <class T>
 353 absl::optional<T> OptionalFromPtr(const T* value) {
 354   if (value)
 355     return absl::optional<T>(*value);
 356   return absl::nullopt;
 357 }
 358
 359 }  // namespace base
 360
 361 #endif  // BASE_STL_UTIL_H_