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 <string> 13 #include <vector> 14 15 #include "base/logging.h" 16 17 // Clears internal memory of an STL object. 18 // STL clear()/reserve(0) does not always free internal memory allocated 19 // This function uses swap/destructor to ensure the internal memory is freed. 20 template<class T> 21 void STLClearObject(T* obj) { 22 T tmp; 23 tmp.swap(*obj); 24 // Sometimes "T tmp" allocates objects with memory (arena implementation?). 25 // Hence using additional reserve(0) even if it doesn't always work. 26 obj->reserve(0); 27 } 28 29 // For a range within a container of pointers, calls delete (non-array version) 30 // on these pointers. 31 // NOTE: for these three functions, we could just implement a DeleteObject 32 // functor and then call for_each() on the range and functor, but this 33 // requires us to pull in all of algorithm.h, which seems expensive. 34 // For hash_[multi]set, it is important that this deletes behind the iterator 35 // because the hash_set may call the hash function on the iterator when it is 36 // advanced, which could result in the hash function trying to deference a 37 // stale pointer. 38 template <class ForwardIterator> 39 void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) { 40 while (begin != end) { 41 ForwardIterator temp = begin; 42 ++begin; 43 delete *temp; 44 } 45 } 46 47 // For a range within a container of pairs, calls delete (non-array version) on 48 // BOTH items in the pairs. 49 // NOTE: Like STLDeleteContainerPointers, it is important that this deletes 50 // behind the iterator because if both the key and value are deleted, the 51 // container may call the hash function on the iterator when it is advanced, 52 // which could result in the hash function trying to dereference a stale 53 // pointer. 54 template <class ForwardIterator> 55 void STLDeleteContainerPairPointers(ForwardIterator begin, 56 ForwardIterator end) { 57 while (begin != end) { 58 ForwardIterator temp = begin; 59 ++begin; 60 delete temp->first; 61 delete temp->second; 62 } 63 } 64 65 // For a range within a container of pairs, calls delete (non-array version) on 66 // the FIRST item in the pairs. 67 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 68 template <class ForwardIterator> 69 void STLDeleteContainerPairFirstPointers(ForwardIterator begin, 70 ForwardIterator end) { 71 while (begin != end) { 72 ForwardIterator temp = begin; 73 ++begin; 74 delete temp->first; 75 } 76 } 77 78 // For a range within a container of pairs, calls delete. 79 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 80 // Deleting the value does not always invalidate the iterator, but it may 81 // do so if the key is a pointer into the value object. 82 template <class ForwardIterator> 83 void STLDeleteContainerPairSecondPointers(ForwardIterator begin, 84 ForwardIterator end) { 85 while (begin != end) { 86 ForwardIterator temp = begin; 87 ++begin; 88 delete temp->second; 89 } 90 } 91 92 // To treat a possibly-empty vector as an array, use these functions. 93 // If you know the array will never be empty, you can use &*v.begin() 94 // directly, but that is undefined behaviour if |v| is empty. 95 template<typename T> 96 inline T* vector_as_array(std::vector<T>* v) { 97 return v->empty() ? NULL : &*v->begin(); 98 } 99 100 template<typename T> 101 inline const T* vector_as_array(const std::vector<T>* v) { 102 return v->empty() ? NULL : &*v->begin(); 103 } 104 105 // Return a mutable char* pointing to a string's internal buffer, 106 // which may not be null-terminated. Writing through this pointer will 107 // modify the string. 108 // 109 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the 110 // next call to a string method that invalidates iterators. 111 // 112 // As of 2006-04, there is no standard-blessed way of getting a 113 // mutable reference to a string's internal buffer. However, issue 530 114 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) 115 // proposes this as the method. According to Matt Austern, this should 116 // already work on all current implementations. 117 inline char* string_as_array(std::string* str) { 118 // DO NOT USE const_cast<char*>(str->data()) 119 return str->empty() ? NULL : &*str->begin(); 120 } 121 122 // The following functions are useful for cleaning up STL containers whose 123 // elements point to allocated memory. 124 125 // STLDeleteElements() deletes all the elements in an STL container and clears 126 // the container. This function is suitable for use with a vector, set, 127 // hash_set, or any other STL container which defines sensible begin(), end(), 128 // and clear() methods. 129 // 130 // If container is NULL, this function is a no-op. 131 // 132 // As an alternative to calling STLDeleteElements() directly, consider 133 // STLElementDeleter (defined below), which ensures that your container's 134 // elements are deleted when the STLElementDeleter goes out of scope. 135 template <class T> 136 void STLDeleteElements(T* container) { 137 if (!container) 138 return; 139 STLDeleteContainerPointers(container->begin(), container->end()); 140 container->clear(); 141 } 142 143 // Given an STL container consisting of (key, value) pairs, STLDeleteValues 144 // deletes all the "value" components and clears the container. Does nothing 145 // in the case it's given a NULL pointer. 146 template <class T> 147 void STLDeleteValues(T* container) { 148 if (!container) 149 return; 150 for (typename T::iterator i(container->begin()); i != container->end(); ++i) 151 delete i->second; 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 return std::adjacent_find(cont.begin(), cont.end(), 204 std::greater<typename Container::value_type>()) 205 == cont.end(); 206 } 207 208 // Returns a new ResultType containing the difference of two sorted containers. 209 template <typename ResultType, typename Arg1, typename Arg2> 210 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { 211 DCHECK(STLIsSorted(a1)); 212 DCHECK(STLIsSorted(a2)); 213 ResultType difference; 214 std::set_difference(a1.begin(), a1.end(), 215 a2.begin(), a2.end(), 216 std::inserter(difference, difference.end())); 217 return difference; 218 } 219 220 } // namespace base 221 222 #endif // BASE_STL_UTIL_H_ 223