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 <deque>
  12 #include <forward_list>
  13 #include <functional>
  14 #include <initializer_list>
  15 #include <iterator>
  16 #include <list>
  17 #include <map>
  18 #include <set>
  19 #include <string>
  20 #include <unordered_map>
  21 #include <unordered_set>
  22 #include <vector>
  23
  24 #include "base/logging.h"
  25 #include "base/optional.h"
  26
  27 namespace base {
  28
  29 namespace internal {
  30
  31 // Calls erase on iterators of matching elements.
  32 template <typename Container, typename Predicate>
  33 void IterateAndEraseIf(Container& container, Predicate pred) {
  34   for (auto it = container.begin(); it != container.end();) {
  35     if (pred(*it))
  36       it = container.erase(it);
  37     else
  38       ++it;
  39   }
  40 }
  41
  42 }  // namespace internal
  43
  44 // C++14 implementation of C++17's std::size():
  45 // http://en.cppreference.com/w/cpp/iterator/size
  46 template <typename Container>
  47 constexpr auto size(const Container& c) -> decltype(c.size()) {
  48   return c.size();
  49 }
  50
  51 template <typename T, size_t N>
  52 constexpr size_t size(const T (&array)[N]) noexcept {
  53   return N;
  54 }
  55
  56 // C++14 implementation of C++17's std::empty():
  57 // http://en.cppreference.com/w/cpp/iterator/empty
  58 template <typename Container>
  59 constexpr auto empty(const Container& c) -> decltype(c.empty()) {
  60   return c.empty();
  61 }
  62
  63 template <typename T, size_t N>
  64 constexpr bool empty(const T (&array)[N]) noexcept {
  65   return false;
  66 }
  67
  68 template <typename T>
  69 constexpr bool empty(std::initializer_list<T> il) noexcept {
  70   return il.size() == 0;
  71 }
  72
  73 // C++14 implementation of C++17's std::data():
  74 // http://en.cppreference.com/w/cpp/iterator/data
  75 template <typename Container>
  76 constexpr auto data(Container& c) -> decltype(c.data()) {
  77   return c.data();
  78 }
  79
  80 // std::basic_string::data() had no mutable overload prior to C++17 [1].
  81 // Hence this overload is provided.
  82 // Note: str[0] is safe even for empty strings, as they are guaranteed to be
  83 // null-terminated [2].
  84 //
  85 // [1] http://en.cppreference.com/w/cpp/string/basic_string/data
  86 // [2] http://en.cppreference.com/w/cpp/string/basic_string/operator_at
  87 template <typename CharT, typename Traits, typename Allocator>
  88 CharT* data(std::basic_string<CharT, Traits, Allocator>& str) {
  89   return std::addressof(str[0]);
  90 }
  91
  92 template <typename Container>
  93 constexpr auto data(const Container& c) -> decltype(c.data()) {
  94   return c.data();
  95 }
  96
  97 template <typename T, size_t N>
  98 constexpr T* data(T (&array)[N]) noexcept {
  99   return array;
 100 }
 101
 102 template <typename T>
 103 constexpr const T* data(std::initializer_list<T> il) noexcept {
 104   return il.begin();
 105 }
 106
 107 // Returns a const reference to the underlying container of a container adapter.
 108 // Works for std::priority_queue, std::queue, and std::stack.
 109 template <class A>
 110 const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
 111   struct ExposedAdapter : A {
 112     using A::c;
 113   };
 114   return adapter.*&ExposedAdapter::c;
 115 }
 116
 117 // Clears internal memory of an STL object.
 118 // STL clear()/reserve(0) does not always free internal memory allocated
 119 // This function uses swap/destructor to ensure the internal memory is freed.
 120 template<class T>
 121 void STLClearObject(T* obj) {
 122   T tmp;
 123   tmp.swap(*obj);
 124   // Sometimes "T tmp" allocates objects with memory (arena implementation?).
 125   // Hence using additional reserve(0) even if it doesn't always work.
 126   obj->reserve(0);
 127 }
 128
 129 // Counts the number of instances of val in a container.
 130 template <typename Container, typename T>
 131 typename std::iterator_traits<
 132     typename Container::const_iterator>::difference_type
 133 STLCount(const Container& container, const T& val) {
 134   return std::count(container.begin(), container.end(), val);
 135 }
 136
 137 // Test to see if a set or map contains a particular key.
 138 // Returns true if the key is in the collection.
 139 template <typename Collection, typename Key>
 140 bool ContainsKey(const Collection& collection, const Key& key) {
 141   return collection.find(key) != collection.end();
 142 }
 143
 144 namespace internal {
 145
 146 template <typename Collection>
 147 class HasKeyType {
 148   template <typename C>
 149   static std::true_type test(typename C::key_type*);
 150   template <typename C>
 151   static std::false_type test(...);
 152
 153  public:
 154   static constexpr bool value = decltype(test<Collection>(nullptr))::value;
 155 };
 156
 157 }  // namespace internal
 158
 159 // Test to see if a collection like a vector contains a particular value.
 160 // Returns true if the value is in the collection.
 161 // Don't use this on collections such as sets or maps. This is enforced by
 162 // disabling this method if the collection defines a key_type.
 163 template <typename Collection,
 164           typename Value,
 165           typename std::enable_if<!internal::HasKeyType<Collection>::value,
 166                                   int>::type = 0>
 167 bool ContainsValue(const Collection& collection, const Value& value) {
 168   return std::find(std::begin(collection), std::end(collection), value) !=
 169          std::end(collection);
 170 }
 171
 172 // Returns true if the container is sorted.
 173 template <typename Container>
 174 bool STLIsSorted(const Container& cont) {
 175   return std::is_sorted(std::begin(cont), std::end(cont));
 176 }
 177
 178 // Returns a new ResultType containing the difference of two sorted containers.
 179 template <typename ResultType, typename Arg1, typename Arg2>
 180 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 181   DCHECK(STLIsSorted(a1));
 182   DCHECK(STLIsSorted(a2));
 183   ResultType difference;
 184   std::set_difference(a1.begin(), a1.end(),
 185                       a2.begin(), a2.end(),
 186                       std::inserter(difference, difference.end()));
 187   return difference;
 188 }
 189
 190 // Returns a new ResultType containing the union of two sorted containers.
 191 template <typename ResultType, typename Arg1, typename Arg2>
 192 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 193   DCHECK(STLIsSorted(a1));
 194   DCHECK(STLIsSorted(a2));
 195   ResultType result;
 196   std::set_union(a1.begin(), a1.end(),
 197                  a2.begin(), a2.end(),
 198                  std::inserter(result, result.end()));
 199   return result;
 200 }
 201
 202 // Returns a new ResultType containing the intersection of two sorted
 203 // containers.
 204 template <typename ResultType, typename Arg1, typename Arg2>
 205 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 206   DCHECK(STLIsSorted(a1));
 207   DCHECK(STLIsSorted(a2));
 208   ResultType result;
 209   std::set_intersection(a1.begin(), a1.end(),
 210                         a2.begin(), a2.end(),
 211                         std::inserter(result, result.end()));
 212   return result;
 213 }
 214
 215 // Returns true if the sorted container |a1| contains all elements of the sorted
 216 // container |a2|.
 217 template <typename Arg1, typename Arg2>
 218 bool STLIncludes(const Arg1& a1, const Arg2& a2) {
 219   DCHECK(STLIsSorted(a1));
 220   DCHECK(STLIsSorted(a2));
 221   return std::includes(a1.begin(), a1.end(),
 222                        a2.begin(), a2.end());
 223 }
 224
 225 // Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if
 226 // http://en.cppreference.com/w/cpp/experimental/lib_extensions_2
 227 // They provide a generic way to erase elements from a container.
 228 // The functions here implement these for the standard containers until those
 229 // functions are available in the C++ standard.
 230 // For Chromium containers overloads should be defined in their own headers
 231 // (like standard containers).
 232 // Note: there is no std::erase for standard associative containers so we don't
 233 // have it either.
 234
 235 template <typename CharT, typename Traits, typename Allocator, typename Value>
 236 void Erase(std::basic_string<CharT, Traits, Allocator>& container,
 237            const Value& value) {
 238   container.erase(std::remove(container.begin(), container.end(), value),
 239                   container.end());
 240 }
 241
 242 template <typename CharT, typename Traits, typename Allocator, class Predicate>
 243 void EraseIf(std::basic_string<CharT, Traits, Allocator>& container,
 244              Predicate pred) {
 245   container.erase(std::remove_if(container.begin(), container.end(), pred),
 246                   container.end());
 247 }
 248
 249 template <class T, class Allocator, class Value>
 250 void Erase(std::deque<T, Allocator>& container, const Value& value) {
 251   container.erase(std::remove(container.begin(), container.end(), value),
 252                   container.end());
 253 }
 254
 255 template <class T, class Allocator, class Predicate>
 256 void EraseIf(std::deque<T, Allocator>& container, Predicate pred) {
 257   container.erase(std::remove_if(container.begin(), container.end(), pred),
 258                   container.end());
 259 }
 260
 261 template <class T, class Allocator, class Value>
 262 void Erase(std::vector<T, Allocator>& container, const Value& value) {
 263   container.erase(std::remove(container.begin(), container.end(), value),
 264                   container.end());
 265 }
 266
 267 template <class T, class Allocator, class Predicate>
 268 void EraseIf(std::vector<T, Allocator>& container, Predicate pred) {
 269   container.erase(std::remove_if(container.begin(), container.end(), pred),
 270                   container.end());
 271 }
 272
 273 template <class T, class Allocator, class Value>
 274 void Erase(std::forward_list<T, Allocator>& container, const Value& value) {
 275   // Unlike std::forward_list::remove, this function template accepts
 276   // heterogeneous types and does not force a conversion to the container's
 277   // value type before invoking the == operator.
 278   container.remove_if([&](const T& cur) { return cur == value; });
 279 }
 280
 281 template <class T, class Allocator, class Predicate>
 282 void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) {
 283   container.remove_if(pred);
 284 }
 285
 286 template <class T, class Allocator, class Value>
 287 void Erase(std::list<T, Allocator>& container, const Value& value) {
 288   // Unlike std::list::remove, this function template accepts heterogeneous
 289   // types and does not force a conversion to the container's value type before
 290   // invoking the == operator.
 291   container.remove_if([&](const T& cur) { return cur == value; });
 292 }
 293
 294 template <class T, class Allocator, class Predicate>
 295 void EraseIf(std::list<T, Allocator>& container, Predicate pred) {
 296   container.remove_if(pred);
 297 }
 298
 299 template <class Key, class T, class Compare, class Allocator, class Predicate>
 300 void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) {
 301   internal::IterateAndEraseIf(container, pred);
 302 }
 303
 304 template <class Key, class T, class Compare, class Allocator, class Predicate>
 305 void EraseIf(std::multimap<Key, T, Compare, Allocator>& container,
 306              Predicate pred) {
 307   internal::IterateAndEraseIf(container, pred);
 308 }
 309
 310 template <class Key, class Compare, class Allocator, class Predicate>
 311 void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) {
 312   internal::IterateAndEraseIf(container, pred);
 313 }
 314
 315 template <class Key, class Compare, class Allocator, class Predicate>
 316 void EraseIf(std::multiset<Key, Compare, Allocator>& container,
 317              Predicate pred) {
 318   internal::IterateAndEraseIf(container, pred);
 319 }
 320
 321 template <class Key,
 322           class T,
 323           class Hash,
 324           class KeyEqual,
 325           class Allocator,
 326           class Predicate>
 327 void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container,
 328              Predicate pred) {
 329   internal::IterateAndEraseIf(container, pred);
 330 }
 331
 332 template <class Key,
 333           class T,
 334           class Hash,
 335           class KeyEqual,
 336           class Allocator,
 337           class Predicate>
 338 void EraseIf(
 339     std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container,
 340     Predicate pred) {
 341   internal::IterateAndEraseIf(container, pred);
 342 }
 343
 344 template <class Key,
 345           class Hash,
 346           class KeyEqual,
 347           class Allocator,
 348           class Predicate>
 349 void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container,
 350              Predicate pred) {
 351   internal::IterateAndEraseIf(container, pred);
 352 }
 353
 354 template <class Key,
 355           class Hash,
 356           class KeyEqual,
 357           class Allocator,
 358           class Predicate>
 359 void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container,
 360              Predicate pred) {
 361   internal::IterateAndEraseIf(container, pred);
 362 }
 363
 364 // A helper class to be used as the predicate with |EraseIf| to implement
 365 // in-place set intersection. Helps implement the algorithm of going through
 366 // each container an element at a time, erasing elements from the first
 367 // container if they aren't in the second container. Requires each container be
 368 // sorted. Note that the logic below appears inverted since it is returning
 369 // whether an element should be erased.
 370 template <class Collection>
 371 class IsNotIn {
 372  public:
 373   explicit IsNotIn(const Collection& collection)
 374       : i_(collection.begin()), end_(collection.end()) {}
 375
 376   bool operator()(const typename Collection::value_type& x) {
 377     while (i_ != end_ && *i_ < x)
 378       ++i_;
 379     if (i_ == end_)
 380       return true;
 381     if (*i_ == x) {
 382       ++i_;
 383       return false;
 384     }
 385     return true;
 386   }
 387
 388  private:
 389   typename Collection::const_iterator i_;
 390   const typename Collection::const_iterator end_;
 391 };
 392
 393 // Helper for returning the optional value's address, or nullptr.
 394 template <class T>
 395 T* OptionalOrNullptr(base::Optional<T>& optional) {
 396   return optional.has_value() ? &optional.value() : nullptr;
 397 }
 398
 399 template <class T>
 400 const T* OptionalOrNullptr(const base::Optional<T>& optional) {
 401   return optional.has_value() ? &optional.value() : nullptr;
 402 }
 403
 404 }  // namespace base
 405
 406 #endif  // BASE_STL_UTIL_H_