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 <functional>
  12 #include <iterator>
  13 #include <string>
  14 #include <vector>
  15
  16 #include "base/logging.h"
  17
  18 // Clears internal memory of an STL object.
  19 // STL clear()/reserve(0) does not always free internal memory allocated
  20 // This function uses swap/destructor to ensure the internal memory is freed.
  21 template<class T>
  22 void STLClearObject(T* obj) {
  23   T tmp;
  24   tmp.swap(*obj);
  25   // Sometimes "T tmp" allocates objects with memory (arena implementation?).
  26   // Hence using additional reserve(0) even if it doesn't always work.
  27   obj->reserve(0);
  28 }
  29
  30 // For a range within a container of pointers, calls delete (non-array version)
  31 // on these pointers.
  32 // NOTE: for these three functions, we could just implement a DeleteObject
  33 // functor and then call for_each() on the range and functor, but this
  34 // requires us to pull in all of algorithm.h, which seems expensive.
  35 // For hash_[multi]set, it is important that this deletes behind the iterator
  36 // because the hash_set may call the hash function on the iterator when it is
  37 // advanced, which could result in the hash function trying to deference a
  38 // stale pointer.
  39 template <class ForwardIterator>
  40 void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) {
  41   while (begin != end) {
  42     ForwardIterator temp = begin;
  43     ++begin;
  44     delete *temp;
  45   }
  46 }
  47
  48 // For a range within a container of pairs, calls delete (non-array version) on
  49 // BOTH items in the pairs.
  50 // NOTE: Like STLDeleteContainerPointers, it is important that this deletes
  51 // behind the iterator because if both the key and value are deleted, the
  52 // container may call the hash function on the iterator when it is advanced,
  53 // which could result in the hash function trying to dereference a stale
  54 // pointer.
  55 template <class ForwardIterator>
  56 void STLDeleteContainerPairPointers(ForwardIterator begin,
  57                                     ForwardIterator end) {
  58   while (begin != end) {
  59     ForwardIterator temp = begin;
  60     ++begin;
  61     delete temp->first;
  62     delete temp->second;
  63   }
  64 }
  65
  66 // For a range within a container of pairs, calls delete (non-array version) on
  67 // the FIRST item in the pairs.
  68 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
  69 template <class ForwardIterator>
  70 void STLDeleteContainerPairFirstPointers(ForwardIterator begin,
  71                                          ForwardIterator end) {
  72   while (begin != end) {
  73     ForwardIterator temp = begin;
  74     ++begin;
  75     delete temp->first;
  76   }
  77 }
  78
  79 // For a range within a container of pairs, calls delete.
  80 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
  81 // Deleting the value does not always invalidate the iterator, but it may
  82 // do so if the key is a pointer into the value object.
  83 template <class ForwardIterator>
  84 void STLDeleteContainerPairSecondPointers(ForwardIterator begin,
  85                                           ForwardIterator end) {
  86   while (begin != end) {
  87     ForwardIterator temp = begin;
  88     ++begin;
  89     delete temp->second;
  90   }
  91 }
  92
  93 // To treat a possibly-empty vector as an array, use these functions.
  94 // If you know the array will never be empty, you can use &*v.begin()
  95 // directly, but that is undefined behaviour if |v| is empty.
  96 template<typename T>
  97 inline T* vector_as_array(std::vector<T>* v) {
  98   return v->empty() ? NULL : &*v->begin();
  99 }
 100
 101 template<typename T>
 102 inline const T* vector_as_array(const std::vector<T>* v) {
 103   return v->empty() ? NULL : &*v->begin();
 104 }
 105
 106 // Return a mutable char* pointing to a string's internal buffer,
 107 // which may not be null-terminated. Writing through this pointer will
 108 // modify the string.
 109 //
 110 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
 111 // next call to a string method that invalidates iterators.
 112 //
 113 // As of 2006-04, there is no standard-blessed way of getting a
 114 // mutable reference to a string's internal buffer. However, issue 530
 115 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530)
 116 // proposes this as the method. According to Matt Austern, this should
 117 // already work on all current implementations.
 118 inline char* string_as_array(std::string* str) {
 119   // DO NOT USE const_cast<char*>(str->data())
 120   return str->empty() ? NULL : &*str->begin();
 121 }
 122
 123 // The following functions are useful for cleaning up STL containers whose
 124 // elements point to allocated memory.
 125
 126 // STLDeleteElements() deletes all the elements in an STL container and clears
 127 // the container.  This function is suitable for use with a vector, set,
 128 // hash_set, or any other STL container which defines sensible begin(), end(),
 129 // and clear() methods.
 130 //
 131 // If container is NULL, this function is a no-op.
 132 //
 133 // As an alternative to calling STLDeleteElements() directly, consider
 134 // STLElementDeleter (defined below), which ensures that your container's
 135 // elements are deleted when the STLElementDeleter goes out of scope.
 136 template <class T>
 137 void STLDeleteElements(T* container) {
 138   if (!container)
 139     return;
 140   STLDeleteContainerPointers(container->begin(), container->end());
 141   container->clear();
 142 }
 143
 144 // Given an STL container consisting of (key, value) pairs, STLDeleteValues
 145 // deletes all the "value" components and clears the container.  Does nothing
 146 // in the case it's given a NULL pointer.
 147 template <class T>
 148 void STLDeleteValues(T* container) {
 149   if (!container)
 150     return;
 151   for (typename T::iterator i(container->begin()); i != container->end(); ++i)
 152     delete i->second;
 153   container->clear();
 154 }
 155
 156
 157 // The following classes provide a convenient way to delete all elements or
 158 // values from STL containers when they goes out of scope.  This greatly
 159 // simplifies code that creates temporary objects and has multiple return
 160 // statements.  Example:
 161 //
 162 // vector<MyProto *> tmp_proto;
 163 // STLElementDeleter<vector<MyProto *> > d(&tmp_proto);
 164 // if (...) return false;
 165 // ...
 166 // return success;
 167
 168 // Given a pointer to an STL container this class will delete all the element
 169 // pointers when it goes out of scope.
 170 template<class T>
 171 class STLElementDeleter {
 172  public:
 173   STLElementDeleter<T>(T* container) : container_(container) {}
 174   ~STLElementDeleter<T>() { STLDeleteElements(container_); }
 175
 176  private:
 177   T* container_;
 178 };
 179
 180 // Given a pointer to an STL container this class will delete all the value
 181 // pointers when it goes out of scope.
 182 template<class T>
 183 class STLValueDeleter {
 184  public:
 185   STLValueDeleter<T>(T* container) : container_(container) {}
 186   ~STLValueDeleter<T>() { STLDeleteValues(container_); }
 187
 188  private:
 189   T* container_;
 190 };
 191
 192 // Test to see if a set, map, hash_set or hash_map contains a particular key.
 193 // Returns true if the key is in the collection.
 194 template <typename Collection, typename Key>
 195 bool ContainsKey(const Collection& collection, const Key& key) {
 196   return collection.find(key) != collection.end();
 197 }
 198
 199 namespace base {
 200
 201 // Returns true if the container is sorted.
 202 template <typename Container>
 203 bool STLIsSorted(const Container& cont) {
 204   // Note: Use reverse iterator on container to ensure we only require
 205   // value_type to implement operator<.
 206   return std::adjacent_find(cont.rbegin(), cont.rend(),
 207                             std::less<typename Container::value_type>())
 208       == cont.rend();
 209 }
 210
 211 // Returns a new ResultType containing the difference of two sorted containers.
 212 template <typename ResultType, typename Arg1, typename Arg2>
 213 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 214   DCHECK(STLIsSorted(a1));
 215   DCHECK(STLIsSorted(a2));
 216   ResultType difference;
 217   std::set_difference(a1.begin(), a1.end(),
 218                       a2.begin(), a2.end(),
 219                       std::inserter(difference, difference.end()));
 220   return difference;
 221 }
 222
 223 // Returns a new ResultType containing the union of two sorted containers.
 224 template <typename ResultType, typename Arg1, typename Arg2>
 225 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 226   DCHECK(STLIsSorted(a1));
 227   DCHECK(STLIsSorted(a2));
 228   ResultType result;
 229   std::set_union(a1.begin(), a1.end(),
 230                  a2.begin(), a2.end(),
 231                  std::inserter(result, result.end()));
 232   return result;
 233 }
 234
 235 // Returns a new ResultType containing the intersection of two sorted
 236 // containers.
 237 template <typename ResultType, typename Arg1, typename Arg2>
 238 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 239   DCHECK(STLIsSorted(a1));
 240   DCHECK(STLIsSorted(a2));
 241   ResultType result;
 242   std::set_intersection(a1.begin(), a1.end(),
 243                         a2.begin(), a2.end(),
 244                         std::inserter(result, result.end()));
 245   return result;
 246 }
 247
 248 // Returns true if the sorted container |a1| contains all elements of the sorted
 249 // container |a2|.
 250 template <typename Arg1, typename Arg2>
 251 bool STLIncludes(const Arg1& a1, const Arg2& a2) {
 252   DCHECK(STLIsSorted(a1));
 253   DCHECK(STLIsSorted(a2));
 254   return std::includes(a1.begin(), a1.end(),
 255                        a2.begin(), a2.end());
 256 }
 257
 258 }  // namespace base
 259
 260 #endif  // BASE_STL_UTIL_H_