stl_util-inl.h revision 3345a6884c488ff3a535c2c9acdd33d74b37e311
1// Copyright (c) 2010 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#pragma once 11 12#include <string.h> // for memcpy 13#include <functional> 14#include <set> 15#include <string> 16#include <vector> 17#include <cassert> 18 19// Clear internal memory of an STL object. 20// STL clear()/reserve(0) does not always free internal memory allocated 21// This function uses swap/destructor to ensure the internal memory is freed. 22template<class T> void STLClearObject(T* obj) { 23 T tmp; 24 tmp.swap(*obj); 25 obj->reserve(0); // this is because sometimes "T tmp" allocates objects with 26 // memory (arena implementation?). use reserve() 27 // to clear() even if it doesn't always work 28} 29 30// Reduce memory usage on behalf of object if it is using more than 31// "bytes" bytes of space. By default, we clear objects over 1MB. 32template <class T> inline void STLClearIfBig(T* obj, size_t limit = 1<<20) { 33 if (obj->capacity() >= limit) { 34 STLClearObject(obj); 35 } else { 36 obj->clear(); 37 } 38} 39 40// Reserve space for STL object. 41// STL's reserve() will always copy. 42// This function avoid the copy if we already have capacity 43template<class T> void STLReserveIfNeeded(T* obj, int new_size) { 44 if (obj->capacity() < new_size) // increase capacity 45 obj->reserve(new_size); 46 else if (obj->size() > new_size) // reduce size 47 obj->resize(new_size); 48} 49 50// STLDeleteContainerPointers() 51// For a range within a container of pointers, calls delete 52// (non-array version) on these pointers. 53// NOTE: for these three functions, we could just implement a DeleteObject 54// functor and then call for_each() on the range and functor, but this 55// requires us to pull in all of algorithm.h, which seems expensive. 56// For hash_[multi]set, it is important that this deletes behind the iterator 57// because the hash_set may call the hash function on the iterator when it is 58// advanced, which could result in the hash function trying to deference a 59// stale pointer. 60template <class ForwardIterator> 61void STLDeleteContainerPointers(ForwardIterator begin, 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 HashSetEquality(const HashSet& set_a, const HashSet& set_b) { 194 if (set_a.size() != set_b.size()) return false; 195 for (typename HashSet::const_iterator i = set_a.begin(); 196 i != set_a.end(); ++i) { 197 if (set_b.find(*i) == set_b.end()) 198 return false; 199 } 200 return true; 201} 202 203template <class HashMap> 204inline bool HashMapEquality(const HashMap& map_a, const HashMap& map_b) { 205 if (map_a.size() != map_b.size()) return false; 206 for (typename HashMap::const_iterator i = map_a.begin(); 207 i != map_a.end(); ++i) { 208 typename HashMap::const_iterator j = map_b.find(i->first); 209 if (j == map_b.end()) return false; 210 if (i->second != j->second) return false; 211 } 212 return true; 213} 214 215// The following functions are useful for cleaning up STL containers 216// whose elements point to allocated memory. 217 218// STLDeleteElements() deletes all the elements in an STL container and clears 219// the container. This function is suitable for use with a vector, set, 220// hash_set, or any other STL container which defines sensible begin(), end(), 221// and clear() methods. 222// 223// If container is NULL, this function is a no-op. 224// 225// As an alternative to calling STLDeleteElements() directly, consider 226// STLElementDeleter (defined below), which ensures that your container's 227// elements are deleted when the STLElementDeleter goes out of scope. 228template <class T> 229void STLDeleteElements(T *container) { 230 if (!container) return; 231 STLDeleteContainerPointers(container->begin(), container->end()); 232 container->clear(); 233} 234 235// Given an STL container consisting of (key, value) pairs, STLDeleteValues 236// deletes all the "value" components and clears the container. Does nothing 237// in the case it's given a NULL pointer. 238 239template <class T> 240void STLDeleteValues(T *v) { 241 if (!v) return; 242 for (typename T::iterator i = v->begin(); i != v->end(); ++i) { 243 delete i->second; 244 } 245 v->clear(); 246} 247 248 249// The following classes provide a convenient way to delete all elements or 250// values from STL containers when they goes out of scope. This greatly 251// simplifies code that creates temporary objects and has multiple return 252// statements. Example: 253// 254// vector<MyProto *> tmp_proto; 255// STLElementDeleter<vector<MyProto *> > d(&tmp_proto); 256// if (...) return false; 257// ... 258// return success; 259 260// Given a pointer to an STL container this class will delete all the element 261// pointers when it goes out of scope. 262 263template<class STLContainer> class STLElementDeleter { 264 public: 265 STLElementDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} 266 ~STLElementDeleter<STLContainer>() { STLDeleteElements(container_ptr_); } 267 private: 268 STLContainer *container_ptr_; 269}; 270 271// Given a pointer to an STL container this class will delete all the value 272// pointers when it goes out of scope. 273 274template<class STLContainer> class STLValueDeleter { 275 public: 276 STLValueDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} 277 ~STLValueDeleter<STLContainer>() { STLDeleteValues(container_ptr_); } 278 private: 279 STLContainer *container_ptr_; 280}; 281 282 283// Forward declare some callback classes in callback.h for STLBinaryFunction 284template <class R, class T1, class T2> 285class ResultCallback2; 286 287// STLBinaryFunction is a wrapper for the ResultCallback2 class in callback.h 288// It provides an operator () method instead of a Run method, so it may be 289// passed to STL functions in <algorithm>. 290// 291// The client should create callback with NewPermanentCallback, and should 292// delete callback after it is done using the STLBinaryFunction. 293 294template <class Result, class Arg1, class Arg2> 295class STLBinaryFunction : public std::binary_function<Arg1, Arg2, Result> { 296 public: 297 typedef ResultCallback2<Result, Arg1, Arg2> Callback; 298 299 STLBinaryFunction(Callback* callback) 300 : callback_(callback) { 301 assert(callback_); 302 } 303 304 Result operator() (Arg1 arg1, Arg2 arg2) { 305 return callback_->Run(arg1, arg2); 306 } 307 308 private: 309 Callback* callback_; 310}; 311 312// STLBinaryPredicate is a specialized version of STLBinaryFunction, where the 313// return type is bool and both arguments have type Arg. It can be used 314// wherever STL requires a StrictWeakOrdering, such as in sort() or 315// lower_bound(). 316// 317// templated typedefs are not supported, so instead we use inheritance. 318 319template <class Arg> 320class STLBinaryPredicate : public STLBinaryFunction<bool, Arg, Arg> { 321 public: 322 typedef typename STLBinaryPredicate<Arg>::Callback Callback; 323 STLBinaryPredicate(Callback* callback) 324 : STLBinaryFunction<bool, Arg, Arg>(callback) { 325 } 326}; 327 328// Functors that compose arbitrary unary and binary functions with a 329// function that "projects" one of the members of a pair. 330// Specifically, if p1 and p2, respectively, are the functions that 331// map a pair to its first and second, respectively, members, the 332// table below summarizes the functions that can be constructed: 333// 334// * UnaryOperate1st<pair>(f) returns the function x -> f(p1(x)) 335// * UnaryOperate2nd<pair>(f) returns the function x -> f(p2(x)) 336// * BinaryOperate1st<pair>(f) returns the function (x,y) -> f(p1(x),p1(y)) 337// * BinaryOperate2nd<pair>(f) returns the function (x,y) -> f(p2(x),p2(y)) 338// 339// A typical usage for these functions would be when iterating over 340// the contents of an STL map. For other sample usage, see the unittest. 341 342template<typename Pair, typename UnaryOp> 343class UnaryOperateOnFirst 344 : public std::unary_function<Pair, typename UnaryOp::result_type> { 345 public: 346 UnaryOperateOnFirst() { 347 } 348 349 UnaryOperateOnFirst(const UnaryOp& f) : f_(f) { 350 } 351 352 typename UnaryOp::result_type operator()(const Pair& p) const { 353 return f_(p.first); 354 } 355 356 private: 357 UnaryOp f_; 358}; 359 360template<typename Pair, typename UnaryOp> 361UnaryOperateOnFirst<Pair, UnaryOp> UnaryOperate1st(const UnaryOp& f) { 362 return UnaryOperateOnFirst<Pair, UnaryOp>(f); 363} 364 365template<typename Pair, typename UnaryOp> 366class UnaryOperateOnSecond 367 : public std::unary_function<Pair, typename UnaryOp::result_type> { 368 public: 369 UnaryOperateOnSecond() { 370 } 371 372 UnaryOperateOnSecond(const UnaryOp& f) : f_(f) { 373 } 374 375 typename UnaryOp::result_type operator()(const Pair& p) const { 376 return f_(p.second); 377 } 378 379 private: 380 UnaryOp f_; 381}; 382 383template<typename Pair, typename UnaryOp> 384UnaryOperateOnSecond<Pair, UnaryOp> UnaryOperate2nd(const UnaryOp& f) { 385 return UnaryOperateOnSecond<Pair, UnaryOp>(f); 386} 387 388template<typename Pair, typename BinaryOp> 389class BinaryOperateOnFirst 390 : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { 391 public: 392 BinaryOperateOnFirst() { 393 } 394 395 BinaryOperateOnFirst(const BinaryOp& f) : f_(f) { 396 } 397 398 typename BinaryOp::result_type operator()(const Pair& p1, 399 const Pair& p2) const { 400 return f_(p1.first, p2.first); 401 } 402 403 private: 404 BinaryOp f_; 405}; 406 407template<typename Pair, typename BinaryOp> 408BinaryOperateOnFirst<Pair, BinaryOp> BinaryOperate1st(const BinaryOp& f) { 409 return BinaryOperateOnFirst<Pair, BinaryOp>(f); 410} 411 412template<typename Pair, typename BinaryOp> 413class BinaryOperateOnSecond 414 : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { 415 public: 416 BinaryOperateOnSecond() { 417 } 418 419 BinaryOperateOnSecond(const BinaryOp& f) : f_(f) { 420 } 421 422 typename BinaryOp::result_type operator()(const Pair& p1, 423 const Pair& p2) const { 424 return f_(p1.second, p2.second); 425 } 426 427 private: 428 BinaryOp f_; 429}; 430 431template<typename Pair, typename BinaryOp> 432BinaryOperateOnSecond<Pair, BinaryOp> BinaryOperate2nd(const BinaryOp& f) { 433 return BinaryOperateOnSecond<Pair, BinaryOp>(f); 434} 435 436// Translates a set into a vector. 437template<typename T> 438std::vector<T> SetToVector(const std::set<T>& values) { 439 std::vector<T> result; 440 result.reserve(values.size()); 441 result.insert(result.begin(), values.begin(), values.end()); 442 return result; 443} 444 445// Test to see if a set, map, hash_set or hash_map contains a particular key. 446// Returns true if the key is in the collection. 447template <typename Collection, typename Key> 448bool ContainsKey(const Collection& collection, const Key& key) { 449 return collection.find(key) != collection.end(); 450} 451 452#endif // BASE_STL_UTIL_INL_H_ 453