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