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.
21 template<class T>
STLClearObject(T * obj)22 void 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.
39 template <class ForwardIterator>
STLDeleteContainerPointers(ForwardIterator begin,ForwardIterator end)40 void 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.
55 template <class ForwardIterator>
STLDeleteContainerPairPointers(ForwardIterator begin,ForwardIterator end)56 void 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.
69 template <class ForwardIterator>
STLDeleteContainerPairFirstPointers(ForwardIterator begin,ForwardIterator end)70 void 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.
83 template <class ForwardIterator>
STLDeleteContainerPairSecondPointers(ForwardIterator begin,ForwardIterator end)84 void 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.
96 template<typename T>
vector_as_array(std::vector<T> * v)97 inline T* vector_as_array(std::vector<T>* v) {
98 return v->empty() ? NULL : &*v->begin();
99 }
100
101 template<typename T>
vector_as_array(const std::vector<T> * v)102 inline 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.
string_as_array(std::string * str)118 inline 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.
136 template <class T>
STLDeleteElements(T * container)137 void 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.
147 template <class T>
STLDeleteValues(T * container)148 void 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.
170 template<class T>
171 class STLElementDeleter {
172 public:
container_(container)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.
182 template<class T>
183 class STLValueDeleter {
184 public:
container_(container)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.
194 template <typename Collection, typename Key>
ContainsKey(const Collection & collection,const Key & key)195 bool ContainsKey(const Collection& collection, const Key& key) {
196 return collection.find(key) != collection.end();
197 }
198
199 namespace base {
200
201 // Returns true if the container is sorted.
202 template <typename Container>
STLIsSorted(const Container & cont)203 bool 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.
212 template <typename ResultType, typename Arg1, typename Arg2>
STLSetDifference(const Arg1 & a1,const Arg2 & a2)213 ResultType 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.
224 template <typename ResultType, typename Arg1, typename Arg2>
STLSetUnion(const Arg1 & a1,const Arg2 & a2)225 ResultType 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.
237 template <typename ResultType, typename Arg1, typename Arg2>
STLSetIntersection(const Arg1 & a1,const Arg2 & a2)238 ResultType 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|.
250 template <typename Arg1, typename Arg2>
STLIncludes(const Arg1 & a1,const Arg2 & a2)251 bool 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