stl_util-inl.h revision c7f5f8508d98d5952d42ed7648c2a8f30a4da156
1// Copyright (c) 2006-2008 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// STL utility functions. Usually, these replace built-in, but slow(!), 6// STL functions with more efficient versions. 7 8#ifndef BASE_STL_UTIL_INL_H_ 9#define BASE_STL_UTIL_INL_H_ 10 11#include <string.h> // for memcpy 12#include <functional> 13#include <set> 14#include <string> 15#include <vector> 16#include <cassert> 17 18// Clear 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> void STLClearObject(T* obj) { 22 T tmp; 23 tmp.swap(*obj); 24 obj->reserve(0); // this is because sometimes "T tmp" allocates objects with 25 // memory (arena implementation?). use reserve() 26 // to clear() even if it doesn't always work 27} 28 29// Reduce memory usage on behalf of object if it is using more than 30// "bytes" bytes of space. By default, we clear objects over 1MB. 31template <class T> inline void STLClearIfBig(T* obj, size_t limit = 1<<20) { 32 if (obj->capacity() >= limit) { 33 STLClearObject(obj); 34 } else { 35 obj->clear(); 36 } 37} 38 39// Reserve space for STL object. 40// STL's reserve() will always copy. 41// This function avoid the copy if we already have capacity 42template<class T> void STLReserveIfNeeded(T* obj, int new_size) { 43 if (obj->capacity() < new_size) // increase capacity 44 obj->reserve(new_size); 45 else if (obj->size() > new_size) // reduce size 46 obj->resize(new_size); 47} 48 49// STLDeleteContainerPointers() 50// For a range within a container of pointers, calls delete 51// (non-array version) on these pointers. 52// NOTE: for these three functions, we could just implement a DeleteObject 53// functor and then call for_each() on the range and functor, but this 54// requires us to pull in all of algorithm.h, which seems expensive. 55// For hash_[multi]set, it is important that this deletes behind the iterator 56// because the hash_set may call the hash function on the iterator when it is 57// advanced, which could result in the hash function trying to deference a 58// stale pointer. 59template <class ForwardIterator> 60void STLDeleteContainerPointers(ForwardIterator begin, 61 ForwardIterator end) { 62 while (begin != end) { 63 ForwardIterator temp = begin; 64 ++begin; 65 delete *temp; 66 } 67} 68 69// STLDeleteContainerPairPointers() 70// For a range within a container of pairs, calls delete 71// (non-array version) on BOTH items in the pairs. 72// NOTE: Like STLDeleteContainerPointers, it is important that this deletes 73// behind the iterator because if both the key and value are deleted, the 74// container may call the hash function on the iterator when it is advanced, 75// which could result in the hash function trying to dereference a stale 76// pointer. 77template <class ForwardIterator> 78void STLDeleteContainerPairPointers(ForwardIterator begin, 79 ForwardIterator end) { 80 while (begin != end) { 81 ForwardIterator temp = begin; 82 ++begin; 83 delete temp->first; 84 delete temp->second; 85 } 86} 87 88// STLDeleteContainerPairFirstPointers() 89// For a range within a container of pairs, calls delete (non-array version) 90// on the FIRST item in the pairs. 91// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 92template <class ForwardIterator> 93void STLDeleteContainerPairFirstPointers(ForwardIterator begin, 94 ForwardIterator end) { 95 while (begin != end) { 96 ForwardIterator temp = begin; 97 ++begin; 98 delete temp->first; 99 } 100} 101 102// STLDeleteContainerPairSecondPointers() 103// For a range within a container of pairs, calls delete 104// (non-array version) on the SECOND item in the pairs. 105template <class ForwardIterator> 106void STLDeleteContainerPairSecondPointers(ForwardIterator begin, 107 ForwardIterator end) { 108 while (begin != end) { 109 delete begin->second; 110 ++begin; 111 } 112} 113 114template<typename T> 115inline void STLAssignToVector(std::vector<T>* vec, 116 const T* ptr, 117 size_t n) { 118 vec->resize(n); 119 memcpy(&vec->front(), ptr, n*sizeof(T)); 120} 121 122/***** Hack to allow faster assignment to a vector *****/ 123 124// This routine speeds up an assignment of 32 bytes to a vector from 125// about 250 cycles per assignment to about 140 cycles. 126// 127// Usage: 128// STLAssignToVectorChar(&vec, ptr, size); 129// STLAssignToString(&str, ptr, size); 130 131inline void STLAssignToVectorChar(std::vector<char>* vec, 132 const char* ptr, 133 size_t n) { 134 STLAssignToVector(vec, ptr, n); 135} 136 137inline void STLAssignToString(std::string* str, const char* ptr, size_t n) { 138 str->resize(n); 139 memcpy(&*str->begin(), ptr, n); 140} 141 142// To treat a possibly-empty vector as an array, use these functions. 143// If you know the array will never be empty, you can use &*v.begin() 144// directly, but that is allowed to dump core if v is empty. This 145// function is the most efficient code that will work, taking into 146// account how our STL is actually implemented. THIS IS NON-PORTABLE 147// CODE, so call us instead of repeating the nonportable code 148// everywhere. If our STL implementation changes, we will need to 149// change this as well. 150 151template<typename T> 152inline T* vector_as_array(std::vector<T>* v) { 153# ifdef NDEBUG 154 return &*v->begin(); 155# else 156 return v->empty() ? NULL : &*v->begin(); 157# endif 158} 159 160template<typename T> 161inline const T* vector_as_array(const std::vector<T>* v) { 162# ifdef NDEBUG 163 return &*v->begin(); 164# else 165 return v->empty() ? NULL : &*v->begin(); 166# endif 167} 168 169// Return a mutable char* pointing to a string's internal buffer, 170// which may not be null-terminated. Writing through this pointer will 171// modify the string. 172// 173// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the 174// next call to a string method that invalidates iterators. 175// 176// As of 2006-04, there is no standard-blessed way of getting a 177// mutable reference to a string's internal buffer. However, issue 530 178// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) 179// proposes this as the method. According to Matt Austern, this should 180// already work on all current implementations. 181inline char* string_as_array(std::string* str) { 182 // DO NOT USE const_cast<char*>(str->data())! See the unittest for why. 183 return str->empty() ? NULL : &*str->begin(); 184} 185 186// These are methods that test two hash maps/sets for equality. These exist 187// because the == operator in the STL can return false when the maps/sets 188// contain identical elements. This is because it compares the internal hash 189// tables which may be different if the order of insertions and deletions 190// differed. 191 192template <class HashSet> 193inline bool 194HashSetEquality(const HashSet& set_a, 195 const HashSet& set_b) { 196 if (set_a.size() != set_b.size()) return false; 197 for (typename HashSet::const_iterator i = set_a.begin(); 198 i != set_a.end(); 199 ++i) { 200 if (set_b.find(*i) == set_b.end()) 201 return false; 202 } 203 return true; 204} 205 206template <class HashMap> 207inline bool 208HashMapEquality(const HashMap& map_a, 209 const HashMap& map_b) { 210 if (map_a.size() != map_b.size()) return false; 211 for (typename HashMap::const_iterator i = map_a.begin(); 212 i != map_a.end(); ++i) { 213 typename HashMap::const_iterator j = map_b.find(i->first); 214 if (j == map_b.end()) return false; 215 if (i->second != j->second) return false; 216 } 217 return true; 218} 219 220// The following functions are useful for cleaning up STL containers 221// whose elements point to allocated memory. 222 223// STLDeleteElements() deletes all the elements in an STL container and clears 224// the container. This function is suitable for use with a vector, set, 225// hash_set, or any other STL container which defines sensible begin(), end(), 226// and clear() methods. 227// 228// If container is NULL, this function is a no-op. 229// 230// As an alternative to calling STLDeleteElements() directly, consider 231// STLElementDeleter (defined below), which ensures that your container's 232// elements are deleted when the STLElementDeleter goes out of scope. 233template <class T> 234void STLDeleteElements(T *container) { 235 if (!container) return; 236 STLDeleteContainerPointers(container->begin(), container->end()); 237 container->clear(); 238} 239 240// Given an STL container consisting of (key, value) pairs, STLDeleteValues 241// deletes all the "value" components and clears the container. Does nothing 242// in the case it's given a NULL pointer. 243 244template <class T> 245void STLDeleteValues(T *v) { 246 if (!v) return; 247 for (typename T::iterator i = v->begin(); i != v->end(); ++i) { 248 delete i->second; 249 } 250 v->clear(); 251} 252 253 254// The following classes provide a convenient way to delete all elements or 255// values from STL containers when they goes out of scope. This greatly 256// simplifies code that creates temporary objects and has multiple return 257// statements. Example: 258// 259// vector<MyProto *> tmp_proto; 260// STLElementDeleter<vector<MyProto *> > d(&tmp_proto); 261// if (...) return false; 262// ... 263// return success; 264 265// Given a pointer to an STL container this class will delete all the element 266// pointers when it goes out of scope. 267 268template<class STLContainer> class STLElementDeleter { 269 public: 270 STLElementDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} 271 ~STLElementDeleter<STLContainer>() { STLDeleteElements(container_ptr_); } 272 private: 273 STLContainer *container_ptr_; 274}; 275 276// Given a pointer to an STL container this class will delete all the value 277// pointers when it goes out of scope. 278 279template<class STLContainer> class STLValueDeleter { 280 public: 281 STLValueDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} 282 ~STLValueDeleter<STLContainer>() { STLDeleteValues(container_ptr_); } 283 private: 284 STLContainer *container_ptr_; 285}; 286 287 288// Forward declare some callback classes in callback.h for STLBinaryFunction 289template <class R, class T1, class T2> 290class ResultCallback2; 291 292// STLBinaryFunction is a wrapper for the ResultCallback2 class in callback.h 293// It provides an operator () method instead of a Run method, so it may be 294// passed to STL functions in <algorithm>. 295// 296// The client should create callback with NewPermanentCallback, and should 297// delete callback after it is done using the STLBinaryFunction. 298 299template <class Result, class Arg1, class Arg2> 300class STLBinaryFunction : public std::binary_function<Arg1, Arg2, Result> { 301 public: 302 typedef ResultCallback2<Result, Arg1, Arg2> Callback; 303 304 STLBinaryFunction(Callback* callback) 305 : callback_(callback) { 306 assert(callback_); 307 } 308 309 Result operator() (Arg1 arg1, Arg2 arg2) { 310 return callback_->Run(arg1, arg2); 311 } 312 313 private: 314 Callback* callback_; 315}; 316 317// STLBinaryPredicate is a specialized version of STLBinaryFunction, where the 318// return type is bool and both arguments have type Arg. It can be used 319// wherever STL requires a StrictWeakOrdering, such as in sort() or 320// lower_bound(). 321// 322// templated typedefs are not supported, so instead we use inheritance. 323 324template <class Arg> 325class STLBinaryPredicate : public STLBinaryFunction<bool, Arg, Arg> { 326 public: 327 typedef typename STLBinaryPredicate<Arg>::Callback Callback; 328 STLBinaryPredicate(Callback* callback) 329 : STLBinaryFunction<bool, Arg, Arg>(callback) { 330 } 331}; 332 333// Functors that compose arbitrary unary and binary functions with a 334// function that "projects" one of the members of a pair. 335// Specifically, if p1 and p2, respectively, are the functions that 336// map a pair to its first and second, respectively, members, the 337// table below summarizes the functions that can be constructed: 338// 339// * UnaryOperate1st<pair>(f) returns the function x -> f(p1(x)) 340// * UnaryOperate2nd<pair>(f) returns the function x -> f(p2(x)) 341// * BinaryOperate1st<pair>(f) returns the function (x,y) -> f(p1(x),p1(y)) 342// * BinaryOperate2nd<pair>(f) returns the function (x,y) -> f(p2(x),p2(y)) 343// 344// A typical usage for these functions would be when iterating over 345// the contents of an STL map. For other sample usage, see the unittest. 346 347template<typename Pair, typename UnaryOp> 348class UnaryOperateOnFirst 349 : public std::unary_function<Pair, typename UnaryOp::result_type> { 350 public: 351 UnaryOperateOnFirst() { 352 } 353 354 UnaryOperateOnFirst(const UnaryOp& f) : f_(f) { 355 } 356 357 typename UnaryOp::result_type operator()(const Pair& p) const { 358 return f_(p.first); 359 } 360 361 private: 362 UnaryOp f_; 363}; 364 365template<typename Pair, typename UnaryOp> 366UnaryOperateOnFirst<Pair, UnaryOp> UnaryOperate1st(const UnaryOp& f) { 367 return UnaryOperateOnFirst<Pair, UnaryOp>(f); 368} 369 370template<typename Pair, typename UnaryOp> 371class UnaryOperateOnSecond 372 : public std::unary_function<Pair, typename UnaryOp::result_type> { 373 public: 374 UnaryOperateOnSecond() { 375 } 376 377 UnaryOperateOnSecond(const UnaryOp& f) : f_(f) { 378 } 379 380 typename UnaryOp::result_type operator()(const Pair& p) const { 381 return f_(p.second); 382 } 383 384 private: 385 UnaryOp f_; 386}; 387 388template<typename Pair, typename UnaryOp> 389UnaryOperateOnSecond<Pair, UnaryOp> UnaryOperate2nd(const UnaryOp& f) { 390 return UnaryOperateOnSecond<Pair, UnaryOp>(f); 391} 392 393template<typename Pair, typename BinaryOp> 394class BinaryOperateOnFirst 395 : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { 396 public: 397 BinaryOperateOnFirst() { 398 } 399 400 BinaryOperateOnFirst(const BinaryOp& f) : f_(f) { 401 } 402 403 typename BinaryOp::result_type operator()(const Pair& p1, 404 const Pair& p2) const { 405 return f_(p1.first, p2.first); 406 } 407 408 private: 409 BinaryOp f_; 410}; 411 412template<typename Pair, typename BinaryOp> 413BinaryOperateOnFirst<Pair, BinaryOp> BinaryOperate1st(const BinaryOp& f) { 414 return BinaryOperateOnFirst<Pair, BinaryOp>(f); 415} 416 417template<typename Pair, typename BinaryOp> 418class BinaryOperateOnSecond 419 : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { 420 public: 421 BinaryOperateOnSecond() { 422 } 423 424 BinaryOperateOnSecond(const BinaryOp& f) : f_(f) { 425 } 426 427 typename BinaryOp::result_type operator()(const Pair& p1, 428 const Pair& p2) const { 429 return f_(p1.second, p2.second); 430 } 431 432 private: 433 BinaryOp f_; 434}; 435 436template<typename Pair, typename BinaryOp> 437BinaryOperateOnSecond<Pair, BinaryOp> BinaryOperate2nd(const BinaryOp& f) { 438 return BinaryOperateOnSecond<Pair, BinaryOp>(f); 439} 440 441// Translates a set into a vector. 442template<typename T> 443std::vector<T> SetToVector(const std::set<T>& values) { 444 std::vector<T> result; 445 result.reserve(values.size()); 446 result.insert(result.begin(), values.begin(), values.end()); 447 return result; 448} 449 450// Test to see if a set, map, hash_set or hash_map contains a particular key. 451// Returns true if the key is in the collection. 452template <typename Collection, typename Key> 453bool ContainsKey(const Collection& collection, const Key& key) { 454 return collection.find(key) != collection.end(); 455} 456 457#endif // BASE_STL_UTIL_INL_H_ 458