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 // Counts the number of instances of val in a container.
  94 template <typename Container, typename T>
  95 typename std::iterator_traits<
  96     typename Container::const_iterator>::difference_type
  97 STLCount(const Container& container, const T& val) {
  98   return std::count(container.begin(), container.end(), val);
  99 }
 100
 101 // To treat a possibly-empty vector as an array, use these functions.
 102 // If you know the array will never be empty, you can use &*v.begin()
 103 // directly, but that is undefined behaviour if |v| is empty.
 104 template<typename T>
 105 inline T* vector_as_array(std::vector<T>* v) {
 106   return v->empty() ? NULL : &*v->begin();
 107 }
 108
 109 template<typename T>
 110 inline const T* vector_as_array(const std::vector<T>* v) {
 111   return v->empty() ? NULL : &*v->begin();
 112 }
 113
 114 // Return a mutable char* pointing to a string's internal buffer,
 115 // which may not be null-terminated. Writing through this pointer will
 116 // modify the string.
 117 //
 118 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
 119 // next call to a string method that invalidates iterators.
 120 //
 121 // As of 2006-04, there is no standard-blessed way of getting a
 122 // mutable reference to a string's internal buffer. However, issue 530
 123 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530)
 124 // proposes this as the method. According to Matt Austern, this should
 125 // already work on all current implementations.
 126 inline char* string_as_array(std::string* str) {
 127   // DO NOT USE const_cast<char*>(str->data())
 128   return str->empty() ? NULL : &*str->begin();
 129 }
 130
 131 // The following functions are useful for cleaning up STL containers whose
 132 // elements point to allocated memory.
 133
 134 // STLDeleteElements() deletes all the elements in an STL container and clears
 135 // the container.  This function is suitable for use with a vector, set,
 136 // hash_set, or any other STL container which defines sensible begin(), end(),
 137 // and clear() methods.
 138 //
 139 // If container is NULL, this function is a no-op.
 140 //
 141 // As an alternative to calling STLDeleteElements() directly, consider
 142 // STLElementDeleter (defined below), which ensures that your container's
 143 // elements are deleted when the STLElementDeleter goes out of scope.
 144 template <class T>
 145 void STLDeleteElements(T* container) {
 146   if (!container)
 147     return;
 148   STLDeleteContainerPointers(container->begin(), container->end());
 149   container->clear();
 150 }
 151
 152 // Given an STL container consisting of (key, value) pairs, STLDeleteValues
 153 // deletes all the "value" components and clears the container.  Does nothing
 154 // in the case it's given a NULL pointer.
 155 template <class T>
 156 void STLDeleteValues(T* container) {
 157   if (!container)
 158     return;
 159   STLDeleteContainerPairSecondPointers(container->begin(), container->end());
 160   container->clear();
 161 }
 162
 163
 164 // The following classes provide a convenient way to delete all elements or
 165 // values from STL containers when they goes out of scope.  This greatly
 166 // simplifies code that creates temporary objects and has multiple return
 167 // statements.  Example:
 168 //
 169 // vector<MyProto *> tmp_proto;
 170 // STLElementDeleter<vector<MyProto *> > d(&tmp_proto);
 171 // if (...) return false;
 172 // ...
 173 // return success;
 174
 175 // Given a pointer to an STL container this class will delete all the element
 176 // pointers when it goes out of scope.
 177 template<class T>
 178 class STLElementDeleter {
 179  public:
 180   STLElementDeleter<T>(T* container) : container_(container) {}
 181   ~STLElementDeleter<T>() { STLDeleteElements(container_); }
 182
 183  private:
 184   T* container_;
 185 };
 186
 187 // Given a pointer to an STL container this class will delete all the value
 188 // pointers when it goes out of scope.
 189 template<class T>
 190 class STLValueDeleter {
 191  public:
 192   STLValueDeleter<T>(T* container) : container_(container) {}
 193   ~STLValueDeleter<T>() { STLDeleteValues(container_); }
 194
 195  private:
 196   T* container_;
 197 };
 198
 199 // Test to see if a set, map, hash_set or hash_map contains a particular key.
 200 // Returns true if the key is in the collection.
 201 template <typename Collection, typename Key>
 202 bool ContainsKey(const Collection& collection, const Key& key) {
 203   return collection.find(key) != collection.end();
 204 }
 205
 206 // Test to see if a collection like a vector contains a particular value.
 207 // Returns true if the value is in the collection.
 208 template <typename Collection, typename Value>
 209 bool ContainsValue(const Collection& collection, const Value& value) {
 210   return std::find(collection.begin(), collection.end(), value) !=
 211       collection.end();
 212 }
 213
 214 namespace base {
 215
 216 // Returns true if the container is sorted.
 217 template <typename Container>
 218 bool STLIsSorted(const Container& cont) {
 219   // Note: Use reverse iterator on container to ensure we only require
 220   // value_type to implement operator<.
 221   return std::adjacent_find(cont.rbegin(), cont.rend(),
 222                             std::less<typename Container::value_type>())
 223       == cont.rend();
 224 }
 225
 226 // Returns a new ResultType containing the difference of two sorted containers.
 227 template <typename ResultType, typename Arg1, typename Arg2>
 228 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
 229   DCHECK(STLIsSorted(a1));
 230   DCHECK(STLIsSorted(a2));
 231   ResultType difference;
 232   std::set_difference(a1.begin(), a1.end(),
 233                       a2.begin(), a2.end(),
 234                       std::inserter(difference, difference.end()));
 235   return difference;
 236 }
 237
 238 // Returns a new ResultType containing the union of two sorted containers.
 239 template <typename ResultType, typename Arg1, typename Arg2>
 240 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) {
 241   DCHECK(STLIsSorted(a1));
 242   DCHECK(STLIsSorted(a2));
 243   ResultType result;
 244   std::set_union(a1.begin(), a1.end(),
 245                  a2.begin(), a2.end(),
 246                  std::inserter(result, result.end()));
 247   return result;
 248 }
 249
 250 // Returns a new ResultType containing the intersection of two sorted
 251 // containers.
 252 template <typename ResultType, typename Arg1, typename Arg2>
 253 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) {
 254   DCHECK(STLIsSorted(a1));
 255   DCHECK(STLIsSorted(a2));
 256   ResultType result;
 257   std::set_intersection(a1.begin(), a1.end(),
 258                         a2.begin(), a2.end(),
 259                         std::inserter(result, result.end()));
 260   return result;
 261 }
 262
 263 // Returns true if the sorted container |a1| contains all elements of the sorted
 264 // container |a2|.
 265 template <typename Arg1, typename Arg2>
 266 bool STLIncludes(const Arg1& a1, const Arg2& a2) {
 267   DCHECK(STLIsSorted(a1));
 268   DCHECK(STLIsSorted(a2));
 269   return std::includes(a1.begin(), a1.end(),
 270                        a2.begin(), a2.end());
 271 }
 272
 273 }  // namespace base
 274
 275 #endif  // BASE_STL_UTIL_H_