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.
5 // STL utility functions. Usually, these replace built-in, but slow(!),
6 // STL functions with more efficient versions.
8 #ifndef BASE_STL_UTIL_INL_H_
9 #define BASE_STL_UTIL_INL_H_
11 #include <string.h> // for memcpy
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.
21 template<class T
> void STLClearObject(T
* 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
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.
31 template <class T
> inline void STLClearIfBig(T
* obj
, size_t limit
= 1<<20) {
32 if (obj
->capacity() >= limit
) {
39 // Reserve space for STL object.
40 // STL's reserve() will always copy.
41 // This function avoid the copy if we already have capacity
42 template<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
);
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
59 template <class ForwardIterator
>
60 void STLDeleteContainerPointers(ForwardIterator begin
,
61 ForwardIterator end
) {
62 while (begin
!= end
) {
63 ForwardIterator temp
= begin
;
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
77 template <class ForwardIterator
>
78 void STLDeleteContainerPairPointers(ForwardIterator begin
,
79 ForwardIterator end
) {
80 while (begin
!= end
) {
81 ForwardIterator temp
= begin
;
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.
92 template <class ForwardIterator
>
93 void STLDeleteContainerPairFirstPointers(ForwardIterator begin
,
94 ForwardIterator end
) {
95 while (begin
!= end
) {
96 ForwardIterator temp
= begin
;
102 // STLDeleteContainerPairSecondPointers()
103 // For a range within a container of pairs, calls delete
104 // (non-array version) on the SECOND item in the pairs.
105 template <class ForwardIterator
>
106 void STLDeleteContainerPairSecondPointers(ForwardIterator begin
,
107 ForwardIterator end
) {
108 while (begin
!= end
) {
109 delete begin
->second
;
115 inline void STLAssignToVector(std::vector
<T
>* vec
,
119 memcpy(&vec
->front(), ptr
, n
*sizeof(T
));
122 /***** Hack to allow faster assignment to a vector *****/
124 // This routine speeds up an assignment of 32 bytes to a vector from
125 // about 250 cycles per assignment to about 140 cycles.
128 // STLAssignToVectorChar(&vec, ptr, size);
129 // STLAssignToString(&str, ptr, size);
131 inline void STLAssignToVectorChar(std::vector
<char>* vec
,
134 STLAssignToVector(vec
, ptr
, n
);
137 inline void STLAssignToString(std::string
* str
, const char* ptr
, size_t n
) {
139 memcpy(&*str
->begin(), ptr
, n
);
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.
152 inline T
* vector_as_array(std::vector
<T
>* v
) {
156 return v
->empty() ? NULL
: &*v
->begin();
161 inline const T
* vector_as_array(const std::vector
<T
>* v
) {
165 return v
->empty() ? NULL
: &*v
->begin();
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.
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.
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.
181 inline 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();
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
192 template <class HashSet
>
194 HashSetEquality(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();
200 if (set_b
.find(*i
) == set_b
.end())
206 template <class HashMap
>
208 HashMapEquality(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;
220 // The following functions are useful for cleaning up STL containers
221 // whose elements point to allocated memory.
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.
228 // If container is NULL, this function is a no-op.
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.
234 void STLDeleteElements(T
*container
) {
235 if (!container
) return;
236 STLDeleteContainerPointers(container
->begin(), container
->end());
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.
245 void STLDeleteValues(T
*v
) {
247 for (typename
T::iterator i
= v
->begin(); i
!= v
->end(); ++i
) {
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:
259 // vector<MyProto *> tmp_proto;
260 // STLElementDeleter<vector<MyProto *> > d(&tmp_proto);
261 // if (...) return false;
265 // Given a pointer to an STL container this class will delete all the element
266 // pointers when it goes out of scope.
268 template<class STLContainer
> class STLElementDeleter
{
270 STLElementDeleter
<STLContainer
>(STLContainer
*ptr
) : container_ptr_(ptr
) {}
271 ~STLElementDeleter
<STLContainer
>() { STLDeleteElements(container_ptr_
); }
273 STLContainer
*container_ptr_
;
276 // Given a pointer to an STL container this class will delete all the value
277 // pointers when it goes out of scope.
279 template<class STLContainer
> class STLValueDeleter
{
281 STLValueDeleter
<STLContainer
>(STLContainer
*ptr
) : container_ptr_(ptr
) {}
282 ~STLValueDeleter
<STLContainer
>() { STLDeleteValues(container_ptr_
); }
284 STLContainer
*container_ptr_
;
288 // Forward declare some callback classes in callback.h for STLBinaryFunction
289 template <class R
, class T1
, class T2
>
290 class ResultCallback2
;
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>.
296 // The client should create callback with NewPermanentCallback, and should
297 // delete callback after it is done using the STLBinaryFunction.
299 template <class Result
, class Arg1
, class Arg2
>
300 class STLBinaryFunction
: public std::binary_function
<Arg1
, Arg2
, Result
> {
302 typedef ResultCallback2
<Result
, Arg1
, Arg2
> Callback
;
304 STLBinaryFunction(Callback
* callback
)
305 : callback_(callback
) {
309 Result
operator() (Arg1 arg1
, Arg2 arg2
) {
310 return callback_
->Run(arg1
, arg2
);
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
322 // templated typedefs are not supported, so instead we use inheritance.
325 class STLBinaryPredicate
: public STLBinaryFunction
<bool, Arg
, Arg
> {
327 typedef typename STLBinaryPredicate
<Arg
>::Callback Callback
;
328 STLBinaryPredicate(Callback
* callback
)
329 : STLBinaryFunction
<bool, Arg
, Arg
>(callback
) {
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:
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))
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.
347 template<typename Pair
, typename UnaryOp
>
348 class UnaryOperateOnFirst
349 : public std::unary_function
<Pair
, typename
UnaryOp::result_type
> {
351 UnaryOperateOnFirst() {
354 UnaryOperateOnFirst(const UnaryOp
& f
) : f_(f
) {
357 typename
UnaryOp::result_type
operator()(const Pair
& p
) const {
365 template<typename Pair
, typename UnaryOp
>
366 UnaryOperateOnFirst
<Pair
, UnaryOp
> UnaryOperate1st(const UnaryOp
& f
) {
367 return UnaryOperateOnFirst
<Pair
, UnaryOp
>(f
);
370 template<typename Pair
, typename UnaryOp
>
371 class UnaryOperateOnSecond
372 : public std::unary_function
<Pair
, typename
UnaryOp::result_type
> {
374 UnaryOperateOnSecond() {
377 UnaryOperateOnSecond(const UnaryOp
& f
) : f_(f
) {
380 typename
UnaryOp::result_type
operator()(const Pair
& p
) const {
388 template<typename Pair
, typename UnaryOp
>
389 UnaryOperateOnSecond
<Pair
, UnaryOp
> UnaryOperate2nd(const UnaryOp
& f
) {
390 return UnaryOperateOnSecond
<Pair
, UnaryOp
>(f
);
393 template<typename Pair
, typename BinaryOp
>
394 class BinaryOperateOnFirst
395 : public std::binary_function
<Pair
, Pair
, typename
BinaryOp::result_type
> {
397 BinaryOperateOnFirst() {
400 BinaryOperateOnFirst(const BinaryOp
& f
) : f_(f
) {
403 typename
BinaryOp::result_type
operator()(const Pair
& p1
,
404 const Pair
& p2
) const {
405 return f_(p1
.first
, p2
.first
);
412 template<typename Pair
, typename BinaryOp
>
413 BinaryOperateOnFirst
<Pair
, BinaryOp
> BinaryOperate1st(const BinaryOp
& f
) {
414 return BinaryOperateOnFirst
<Pair
, BinaryOp
>(f
);
417 template<typename Pair
, typename BinaryOp
>
418 class BinaryOperateOnSecond
419 : public std::binary_function
<Pair
, Pair
, typename
BinaryOp::result_type
> {
421 BinaryOperateOnSecond() {
424 BinaryOperateOnSecond(const BinaryOp
& f
) : f_(f
) {
427 typename
BinaryOp::result_type
operator()(const Pair
& p1
,
428 const Pair
& p2
) const {
429 return f_(p1
.second
, p2
.second
);
436 template<typename Pair
, typename BinaryOp
>
437 BinaryOperateOnSecond
<Pair
, BinaryOp
> BinaryOperate2nd(const BinaryOp
& f
) {
438 return BinaryOperateOnSecond
<Pair
, BinaryOp
>(f
);
441 // Translates a set into a vector.
443 std::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());
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.
452 template <typename Collection
, typename Key
>
453 bool ContainsKey(const Collection
& collection
, const Key
& key
) {
454 return collection
.find(key
) != collection
.end();
457 #endif // BASE_STL_UTIL_INL_H_