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   // Note: Use reverse iterator on container to ensure we only require
 176   // value_type to implement operator<.
 177   return std::adjacent_find(cont.rbegin(), cont.rend(),
 178                             std::less<typename Container::value_type>())
 179       == cont.rend();
 180 }
 181
 182 // Returns a new ResultType containing the difference of two sorted containers.
 183 template <typename ResultType, typename Arg1, typename Arg2>
 184 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 185   DCHECK(STLIsSorted(a1));
 186   DCHECK(STLIsSorted(a2));
 187   ResultType difference;
 188   std::set_difference(a1.begin(), a1.end(),
 189                       a2.begin(), a2.end(),
 190                       std::inserter(difference, difference.end()));
 191   return difference;
 192 }
 193
 194 // Returns a new ResultType containing the union of two sorted containers.
 195 template <typename ResultType, typename Arg1, typename Arg2>
 196 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 197   DCHECK(STLIsSorted(a1));
 198   DCHECK(STLIsSorted(a2));
 199   ResultType result;
 200   std::set_union(a1.begin(), a1.end(),
 201                  a2.begin(), a2.end(),
 202                  std::inserter(result, result.end()));
 203   return result;
 204 }
 205
 206 // Returns a new ResultType containing the intersection of two sorted
 207 // containers.
 208 template <typename ResultType, typename Arg1, typename Arg2>
 209 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 210   DCHECK(STLIsSorted(a1));
 211   DCHECK(STLIsSorted(a2));
 212   ResultType result;
 213   std::set_intersection(a1.begin(), a1.end(),
 214                         a2.begin(), a2.end(),
 215                         std::inserter(result, result.end()));
 216   return result;
 217 }
 218
 219 // Returns true if the sorted container |a1| contains all elements of the sorted
 220 // container |a2|.
 221 template <typename Arg1, typename Arg2>
 222 bool STLIncludes(const Arg1& a1, const Arg2& a2) {
 223   DCHECK(STLIsSorted(a1));
 224   DCHECK(STLIsSorted(a2));
 225   return std::includes(a1.begin(), a1.end(),
 226                        a2.begin(), a2.end());
 227 }
 228
 229 // Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if
 230 // http://en.cppreference.com/w/cpp/experimental/lib_extensions_2
 231 // They provide a generic way to erase elements from a container.
 232 // The functions here implement these for the standard containers until those
 233 // functions are available in the C++ standard.
 234 // For Chromium containers overloads should be defined in their own headers
 235 // (like standard containers).
 236 // Note: there is no std::erase for standard associative containers so we don't
 237 // have it either.
 238
 239 template <typename CharT, typename Traits, typename Allocator, typename Value>
 240 void Erase(std::basic_string<CharT, Traits, Allocator>& container,
 241            const Value& value) {
 242   container.erase(std::remove(container.begin(), container.end(), value),
 243                   container.end());
 244 }
 245
 246 template <typename CharT, typename Traits, typename Allocator, class Predicate>
 247 void EraseIf(std::basic_string<CharT, Traits, Allocator>& container,
 248              Predicate pred) {
 249   container.erase(std::remove_if(container.begin(), container.end(), pred),
 250                   container.end());
 251 }
 252
 253 template <class T, class Allocator, class Value>
 254 void Erase(std::deque<T, Allocator>& container, const Value& value) {
 255   container.erase(std::remove(container.begin(), container.end(), value),
 256                   container.end());
 257 }
 258
 259 template <class T, class Allocator, class Predicate>
 260 void EraseIf(std::deque<T, Allocator>& container, Predicate pred) {
 261   container.erase(std::remove_if(container.begin(), container.end(), pred),
 262                   container.end());
 263 }
 264
 265 template <class T, class Allocator, class Value>
 266 void Erase(std::vector<T, Allocator>& container, const Value& value) {
 267   container.erase(std::remove(container.begin(), container.end(), value),
 268                   container.end());
 269 }
 270
 271 template <class T, class Allocator, class Predicate>
 272 void EraseIf(std::vector<T, Allocator>& container, Predicate pred) {
 273   container.erase(std::remove_if(container.begin(), container.end(), pred),
 274                   container.end());
 275 }
 276
 277 template <class T, class Allocator, class Value>
 278 void Erase(std::forward_list<T, Allocator>& container, const Value& value) {
 279   // Unlike std::forward_list::remove, this function template accepts
 280   // heterogeneous types and does not force a conversion to the container's
 281   // value type before invoking the == operator.
 282   container.remove_if([&](const T& cur) { return cur == value; });
 283 }
 284
 285 template <class T, class Allocator, class Predicate>
 286 void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) {
 287   container.remove_if(pred);
 288 }
 289
 290 template <class T, class Allocator, class Value>
 291 void Erase(std::list<T, Allocator>& container, const Value& value) {
 292   // Unlike std::list::remove, this function template accepts heterogeneous
 293   // types and does not force a conversion to the container's value type before
 294   // invoking the == operator.
 295   container.remove_if([&](const T& cur) { return cur == value; });
 296 }
 297
 298 template <class T, class Allocator, class Predicate>
 299 void EraseIf(std::list<T, Allocator>& container, Predicate pred) {
 300   container.remove_if(pred);
 301 }
 302
 303 template <class Key, class T, class Compare, class Allocator, class Predicate>
 304 void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) {
 305   internal::IterateAndEraseIf(container, pred);
 306 }
 307
 308 template <class Key, class T, class Compare, class Allocator, class Predicate>
 309 void EraseIf(std::multimap<Key, T, Compare, Allocator>& container,
 310              Predicate pred) {
 311   internal::IterateAndEraseIf(container, pred);
 312 }
 313
 314 template <class Key, class Compare, class Allocator, class Predicate>
 315 void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) {
 316   internal::IterateAndEraseIf(container, pred);
 317 }
 318
 319 template <class Key, class Compare, class Allocator, class Predicate>
 320 void EraseIf(std::multiset<Key, Compare, Allocator>& container,
 321              Predicate pred) {
 322   internal::IterateAndEraseIf(container, pred);
 323 }
 324
 325 template <class Key,
 326           class T,
 327           class Hash,
 328           class KeyEqual,
 329           class Allocator,
 330           class Predicate>
 331 void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container,
 332              Predicate pred) {
 333   internal::IterateAndEraseIf(container, pred);
 334 }
 335
 336 template <class Key,
 337           class T,
 338           class Hash,
 339           class KeyEqual,
 340           class Allocator,
 341           class Predicate>
 342 void EraseIf(
 343     std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container,
 344     Predicate pred) {
 345   internal::IterateAndEraseIf(container, pred);
 346 }
 347
 348 template <class Key,
 349           class Hash,
 350           class KeyEqual,
 351           class Allocator,
 352           class Predicate>
 353 void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container,
 354              Predicate pred) {
 355   internal::IterateAndEraseIf(container, pred);
 356 }
 357
 358 template <class Key,
 359           class Hash,
 360           class KeyEqual,
 361           class Allocator,
 362           class Predicate>
 363 void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container,
 364              Predicate pred) {
 365   internal::IterateAndEraseIf(container, pred);
 366 }
 367
 368 // A helper class to be used as the predicate with |EraseIf| to implement
 369 // in-place set intersection. Helps implement the algorithm of going through
 370 // each container an element at a time, erasing elements from the first
 371 // container if they aren't in the second container. Requires each container be
 372 // sorted. Note that the logic below appears inverted since it is returning
 373 // whether an element should be erased.
 374 template <class Collection>
 375 class IsNotIn {
 376  public:
 377   explicit IsNotIn(const Collection& collection)
 378       : i_(collection.begin()), end_(collection.end()) {}
 379
 380   bool operator()(const typename Collection::value_type& x) {
 381     while (i_ != end_ && *i_ < x)
 382       ++i_;
 383     if (i_ == end_)
 384       return true;
 385     if (*i_ == x) {
 386       ++i_;
 387       return false;
 388     }
 389     return true;
 390   }
 391
 392  private:
 393   typename Collection::const_iterator i_;
 394   const typename Collection::const_iterator end_;
 395 };
 396
 397 // Helper for returning the optional value's address, or nullptr.
 398 template <class T>
 399 T* OptionalOrNullptr(base::Optional<T>& optional) {
 400   return optional.has_value() ? &optional.value() : nullptr;
 401 }
 402
 403 template <class T>
 404 const T* OptionalOrNullptr(const base::Optional<T>& optional) {
 405   return optional.has_value() ? &optional.value() : nullptr;
 406 }
 407
 408 }  // namespace base
 409
 410 #endif  // BASE_STL_UTIL_H_