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. 21template<class T> 22void 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. 39template <class ForwardIterator> 40void 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. 55template <class ForwardIterator> 56void 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. 69template <class ForwardIterator> 70void 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. 83template <class ForwardIterator> 84void 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. 96template<typename T> 97inline T* vector_as_array(std::vector<T>* v) { 98 return v->empty() ? NULL : &*v->begin(); 99} 100 101template<typename T> 102inline 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. 118inline 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. 136template <class T> 137void 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. 147template <class T> 148void 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. 170template<class T> 171class 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. 182template<class T> 183class 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. 194template <typename Collection, typename Key> 195bool ContainsKey(const Collection& collection, const Key& key) { 196 return collection.find(key) != collection.end(); 197} 198 199namespace base { 200 201// Returns true if the container is sorted. 202template <typename Container> 203bool 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. 212template <typename ResultType, typename Arg1, typename Arg2> 213ResultType 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. 224template <typename ResultType, typename Arg1, typename Arg2> 225ResultType 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. 237template <typename ResultType, typename Arg1, typename Arg2> 238ResultType 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|. 250template <typename Arg1, typename Arg2> 251bool 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_ 261