stl_util.h revision b8cf94937c52feb53b55c39e3f82094d27de464c
1b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Copyright (c) 2011 The Chromium Authors. All rights reserved. 2b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Use of this source code is governed by a BSD-style license that can be 3b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// found in the LICENSE file. 4b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 5b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Derived from google3/util/gtl/stl_util.h 6b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 7b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#ifndef BASE_STL_UTIL_H_ 8b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#define BASE_STL_UTIL_H_ 9b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 10b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <algorithm> 11b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <functional> 12b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <iterator> 13b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <string> 14b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <vector> 15b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 16b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include "base/logging.h" 17b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 18b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Clears internal memory of an STL object. 19b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STL clear()/reserve(0) does not always free internal memory allocated 20b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// This function uses swap/destructor to ensure the internal memory is freed. 21b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<class T> 22b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLClearObject(T* obj) { 23b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat T tmp; 24b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat tmp.swap(*obj); 25b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Sometimes "T tmp" allocates objects with memory (arena implementation?). 26b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Hence using additional reserve(0) even if it doesn't always work. 27b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat obj->reserve(0); 28b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 29b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 30b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// For a range within a container of pointers, calls delete (non-array version) 31b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// on these pointers. 32b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// NOTE: for these three functions, we could just implement a DeleteObject 33b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// functor and then call for_each() on the range and functor, but this 34b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// requires us to pull in all of algorithm.h, which seems expensive. 35b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// For hash_[multi]set, it is important that this deletes behind the iterator 36b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// because the hash_set may call the hash function on the iterator when it is 37b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// advanced, which could result in the hash function trying to deference a 38b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// stale pointer. 39b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class ForwardIterator> 40b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) { 41b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat while (begin != end) { 42b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator temp = begin; 43b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ++begin; 44b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat delete *temp; 45b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 46b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 47b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 48b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// For a range within a container of pairs, calls delete (non-array version) on 49b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// BOTH items in the pairs. 50b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// NOTE: Like STLDeleteContainerPointers, it is important that this deletes 51b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// behind the iterator because if both the key and value are deleted, the 52b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// container may call the hash function on the iterator when it is advanced, 53b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// which could result in the hash function trying to dereference a stale 54b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// pointer. 55b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class ForwardIterator> 56b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteContainerPairPointers(ForwardIterator begin, 57b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator end) { 58b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat while (begin != end) { 59b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator temp = begin; 60b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ++begin; 61b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat delete temp->first; 62b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat delete temp->second; 63b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 64b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 65b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 66b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// For a range within a container of pairs, calls delete (non-array version) on 67b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// the FIRST item in the pairs. 68b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 69b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class ForwardIterator> 70b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteContainerPairFirstPointers(ForwardIterator begin, 71b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator end) { 72b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat while (begin != end) { 73b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator temp = begin; 74b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ++begin; 75b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat delete temp->first; 76b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 77b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 78b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 79b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// For a range within a container of pairs, calls delete. 80b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 81b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Deleting the value does not always invalidate the iterator, but it may 82b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// do so if the key is a pointer into the value object. 83b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class ForwardIterator> 84b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteContainerPairSecondPointers(ForwardIterator begin, 85b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator end) { 86b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat while (begin != end) { 87b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ForwardIterator temp = begin; 88b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ++begin; 89b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat delete temp->second; 90b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 91b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 92b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 93b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Counts the number of instances of val in a container. 94b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Container, typename T> 95b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattypename std::iterator_traits< 96b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename Container::const_iterator>::difference_type 97b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratSTLCount(const Container& container, const T& val) { 98b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::count(container.begin(), container.end(), val); 99b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 100b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 101b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// To treat a possibly-empty vector as an array, use these functions. 102b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// If you know the array will never be empty, you can use &*v.begin() 103b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// directly, but that is undefined behaviour if |v| is empty. 104b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename T> 105b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratinline T* vector_as_array(std::vector<T>* v) { 106b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return v->empty() ? NULL : &*v->begin(); 107b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 108b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 109b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename T> 110b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratinline const T* vector_as_array(const std::vector<T>* v) { 111b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return v->empty() ? NULL : &*v->begin(); 112b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 113b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 114b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Return a mutable char* pointing to a string's internal buffer, 115b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// which may not be null-terminated. Writing through this pointer will 116b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// modify the string. 117b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 118b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the 119b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// next call to a string method that invalidates iterators. 120b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 121b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// As of 2006-04, there is no standard-blessed way of getting a 122b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// mutable reference to a string's internal buffer. However, issue 530 123b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) 124b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// proposes this as the method. According to Matt Austern, this should 125b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// already work on all current implementations. 126b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratinline char* string_as_array(std::string* str) { 127b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // DO NOT USE const_cast<char*>(str->data()) 128b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return str->empty() ? NULL : &*str->begin(); 129b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 130b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 131b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// The following functions are useful for cleaning up STL containers whose 132b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// elements point to allocated memory. 133b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 134b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STLDeleteElements() deletes all the elements in an STL container and clears 135b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// the container. This function is suitable for use with a vector, set, 136b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// hash_set, or any other STL container which defines sensible begin(), end(), 137b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// and clear() methods. 138b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 139b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// If container is NULL, this function is a no-op. 140b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 141b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// As an alternative to calling STLDeleteElements() directly, consider 142b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STLElementDeleter (defined below), which ensures that your container's 143b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// elements are deleted when the STLElementDeleter goes out of scope. 144b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class T> 145b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteElements(T* container) { 146b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!container) 147b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return; 148b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLDeleteContainerPointers(container->begin(), container->end()); 149b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat container->clear(); 150b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 151b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 152b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Given an STL container consisting of (key, value) pairs, STLDeleteValues 153b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// deletes all the "value" components and clears the container. Does nothing 154b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// in the case it's given a NULL pointer. 155b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class T> 156b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteValues(T* container) { 157b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!container) 158b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return; 159b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLDeleteContainerPairSecondPointers(container->begin(), container->end()); 160b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat container->clear(); 161b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 162b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 163b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 164b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// The following classes provide a convenient way to delete all elements or 165b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// values from STL containers when they goes out of scope. This greatly 166b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// simplifies code that creates temporary objects and has multiple return 167b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// statements. Example: 168b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 169b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// vector<MyProto *> tmp_proto; 170b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STLElementDeleter<vector<MyProto *> > d(&tmp_proto); 171b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// if (...) return false; 172b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// ... 173b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// return success; 174b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 175b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Given a pointer to an STL container this class will delete all the element 176b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// pointers when it goes out of scope. 177b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<class T> 178b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratclass STLElementDeleter { 179b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat public: 180b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLElementDeleter<T>(T* container) : container_(container) {} 181b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ~STLElementDeleter<T>() { STLDeleteElements(container_); } 182b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 183b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat private: 184b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat T* container_; 185b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat}; 186b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 187b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Given a pointer to an STL container this class will delete all the value 188b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// pointers when it goes out of scope. 189b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<class T> 190b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratclass STLValueDeleter { 191b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat public: 192b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLValueDeleter<T>(T* container) : container_(container) {} 193b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ~STLValueDeleter<T>() { STLDeleteValues(container_); } 194b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 195b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat private: 196b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat T* container_; 197b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat}; 198b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 199b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Test to see if a set, map, hash_set or hash_map contains a particular key. 200b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the key is in the collection. 201b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Collection, typename Key> 202b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool ContainsKey(const Collection& collection, const Key& key) { 203b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return collection.find(key) != collection.end(); 204b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 205b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 206b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Test to see if a collection like a vector contains a particular value. 207b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the value is in the collection. 208b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Collection, typename Value> 209b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool ContainsValue(const Collection& collection, const Value& value) { 210b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::find(collection.begin(), collection.end(), value) != 211b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat collection.end(); 212b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 213b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 214b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratnamespace base { 215b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 216b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the container is sorted. 217b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Container> 218b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool STLIsSorted(const Container& cont) { 219b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Note: Use reverse iterator on container to ensure we only require 220b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // value_type to implement operator<. 221b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::adjacent_find(cont.rbegin(), cont.rend(), 222b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::less<typename Container::value_type>()) 223b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat == cont.rend(); 224b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 225b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 226b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns a new ResultType containing the difference of two sorted containers. 227b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename ResultType, typename Arg1, typename Arg2> 228b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { 229b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 230b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 231b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ResultType difference; 232b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::set_difference(a1.begin(), a1.end(), 233b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end(), 234b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::inserter(difference, difference.end())); 235b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return difference; 236b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 237b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 238b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns a new ResultType containing the union of two sorted containers. 239b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename ResultType, typename Arg1, typename Arg2> 240b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratResultType STLSetUnion(const Arg1& a1, const Arg2& a2) { 241b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 242b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 243b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ResultType result; 244b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::set_union(a1.begin(), a1.end(), 245b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end(), 246b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::inserter(result, result.end())); 247b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return result; 248b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 249b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 250b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns a new ResultType containing the intersection of two sorted 251b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// containers. 252b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename ResultType, typename Arg1, typename Arg2> 253b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) { 254b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 255b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 256b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ResultType result; 257b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::set_intersection(a1.begin(), a1.end(), 258b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end(), 259b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::inserter(result, result.end())); 260b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return result; 261b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 262b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 263b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the sorted container |a1| contains all elements of the sorted 264b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// container |a2|. 265b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Arg1, typename Arg2> 266b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool STLIncludes(const Arg1& a1, const Arg2& a2) { 267b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 268b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 269b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::includes(a1.begin(), a1.end(), 270b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end()); 271b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 272b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 273b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} // namespace base 274b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 275b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#endif // BASE_STL_UTIL_H_ 276