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   STLDeleteContainerPairSecondPointers(container->begin(), container->end());
 152   container->clear();
 153 }
 154
 155
 156 // The following classes provide a convenient way to delete all elements or
 157 // values from STL containers when they goes out of scope.  This greatly
 158 // simplifies code that creates temporary objects and has multiple return
 159 // statements.  Example:
 160 //
 161 // vector<MyProto *> tmp_proto;
 162 // STLElementDeleter<vector<MyProto *> > d(&tmp_proto);
 163 // if (...) return false;
 164 // ...
 165 // return success;
 166
 167 // Given a pointer to an STL container this class will delete all the element
 168 // pointers when it goes out of scope.
 169 template<class T>
 170 class STLElementDeleter {
 171  public:
 172   STLElementDeleter<T>(T* container) : container_(container) {}
 173   ~STLElementDeleter<T>() { STLDeleteElements(container_); }
 174
 175  private:
 176   T* container_;
 177 };
 178
 179 // Given a pointer to an STL container this class will delete all the value
 180 // pointers when it goes out of scope.
 181 template<class T>
 182 class STLValueDeleter {
 183  public:
 184   STLValueDeleter<T>(T* container) : container_(container) {}
 185   ~STLValueDeleter<T>() { STLDeleteValues(container_); }
 186
 187  private:
 188   T* container_;
 189 };
 190
 191 // Test to see if a set, map, hash_set or hash_map contains a particular key.
 192 // Returns true if the key is in the collection.
 193 template <typename Collection, typename Key>
 194 bool ContainsKey(const Collection& collection, const Key& key) {
 195   return collection.find(key) != collection.end();
 196 }
 197
 198 namespace base {
 199
 200 // Returns true if the container is sorted.
 201 template <typename Container>
 202 bool STLIsSorted(const Container& cont) {
 203   // Note: Use reverse iterator on container to ensure we only require
 204   // value_type to implement operator<.
 205   return std::adjacent_find(cont.rbegin(), cont.rend(),
 206                             std::less<typename Container::value_type>())
 207       == cont.rend();
 208 }
 209
 210 // Returns a new ResultType containing the difference of two sorted containers.
 211 template <typename ResultType, typename Arg1, typename Arg2>
 212 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 213   DCHECK(STLIsSorted(a1));
 214   DCHECK(STLIsSorted(a2));
 215   ResultType difference;
 216   std::set_difference(a1.begin(), a1.end(),
 217                       a2.begin(), a2.end(),
 218                       std::inserter(difference, difference.end()));
 219   return difference;
 220 }
 221
 222 // Returns a new ResultType containing the union of two sorted containers.
 223 template <typename ResultType, typename Arg1, typename Arg2>
 224 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 225   DCHECK(STLIsSorted(a1));
 226   DCHECK(STLIsSorted(a2));
 227   ResultType result;
 228   std::set_union(a1.begin(), a1.end(),
 229                  a2.begin(), a2.end(),
 230                  std::inserter(result, result.end()));
 231   return result;
 232 }
 233
 234 // Returns a new ResultType containing the intersection of two sorted
 235 // containers.
 236 template <typename ResultType, typename Arg1, typename Arg2>
 237 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 238   DCHECK(STLIsSorted(a1));
 239   DCHECK(STLIsSorted(a2));
 240   ResultType result;
 241   std::set_intersection(a1.begin(), a1.end(),
 242                         a2.begin(), a2.end(),
 243                         std::inserter(result, result.end()));
 244   return result;
 245 }
 246
 247 // Returns true if the sorted container |a1| contains all elements of the sorted
 248 // container |a2|.
 249 template <typename Arg1, typename Arg2>
 250 bool STLIncludes(const Arg1& a1, const Arg2& a2) {
 251   DCHECK(STLIsSorted(a1));
 252   DCHECK(STLIsSorted(a2));
 253   return std::includes(a1.begin(), a1.end(),
 254                        a2.begin(), a2.end());
 255 }
 256
 257 }  // namespace base
 258
 259 #endif  // BASE_STL_UTIL_H_