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// Return a mutable char* pointing to a string's internal buffer, 102b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// which may not be null-terminated. Writing through this pointer will 103b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// modify the string. 104b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 105b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the 106b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// next call to a string method that invalidates iterators. 107b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 108b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// As of 2006-04, there is no standard-blessed way of getting a 109b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// mutable reference to a string's internal buffer. However, issue 530 110b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) 111b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// proposes this as the method. According to Matt Austern, this should 112b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// already work on all current implementations. 113b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratinline char* string_as_array(std::string* str) { 114b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // DO NOT USE const_cast<char*>(str->data()) 115b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return str->empty() ? NULL : &*str->begin(); 116b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 117b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 118b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// The following functions are useful for cleaning up STL containers whose 119b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// elements point to allocated memory. 120b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 121b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STLDeleteElements() deletes all the elements in an STL container and clears 122b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// the container. This function is suitable for use with a vector, set, 123b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// hash_set, or any other STL container which defines sensible begin(), end(), 124b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// and clear() methods. 125b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 126b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// If container is NULL, this function is a no-op. 127b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 128b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// As an alternative to calling STLDeleteElements() directly, consider 129b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STLElementDeleter (defined below), which ensures that your container's 130b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// elements are deleted when the STLElementDeleter goes out of scope. 131b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class T> 132b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteElements(T* container) { 133b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!container) 134b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return; 135b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLDeleteContainerPointers(container->begin(), container->end()); 136b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat container->clear(); 137b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 138b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 139b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Given an STL container consisting of (key, value) pairs, STLDeleteValues 140b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// deletes all the "value" components and clears the container. Does nothing 141b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// in the case it's given a NULL pointer. 142b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <class T> 143b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid STLDeleteValues(T* container) { 144b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!container) 145b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return; 146b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLDeleteContainerPairSecondPointers(container->begin(), container->end()); 147b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat container->clear(); 148b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 149b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 150b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 151b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// The following classes provide a convenient way to delete all elements or 152b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// values from STL containers when they goes out of scope. This greatly 153b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// simplifies code that creates temporary objects and has multiple return 154b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// statements. Example: 155b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 156b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// vector<MyProto *> tmp_proto; 157b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// STLElementDeleter<vector<MyProto *> > d(&tmp_proto); 158b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// if (...) return false; 159b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// ... 160b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// return success; 161b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 162b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Given a pointer to an STL container this class will delete all the element 163b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// pointers when it goes out of scope. 164b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<class T> 165b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratclass STLElementDeleter { 166b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat public: 167b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLElementDeleter<T>(T* container) : container_(container) {} 168b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ~STLElementDeleter<T>() { STLDeleteElements(container_); } 169b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 170b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat private: 171b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat T* container_; 172b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat}; 173b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 174b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Given a pointer to an STL container this class will delete all the value 175b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// pointers when it goes out of scope. 176b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<class T> 177b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratclass STLValueDeleter { 178b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat public: 179b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat STLValueDeleter<T>(T* container) : container_(container) {} 180b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ~STLValueDeleter<T>() { STLDeleteValues(container_); } 181b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 182b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat private: 183b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat T* container_; 184b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat}; 185b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 186b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Test to see if a set, map, hash_set or hash_map contains a particular key. 187b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the key is in the collection. 188b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Collection, typename Key> 189b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool ContainsKey(const Collection& collection, const Key& key) { 190b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return collection.find(key) != collection.end(); 191b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 192b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 193b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Test to see if a collection like a vector contains a particular value. 194b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the value is in the collection. 195b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Collection, typename Value> 196b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool ContainsValue(const Collection& collection, const Value& value) { 197b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::find(collection.begin(), collection.end(), value) != 198b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat collection.end(); 199b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 200b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 201b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratnamespace base { 202b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 203b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns true if the container is sorted. 204b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Container> 205b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool STLIsSorted(const Container& cont) { 206b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Note: Use reverse iterator on container to ensure we only require 207b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // value_type to implement operator<. 208b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::adjacent_find(cont.rbegin(), cont.rend(), 209b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::less<typename Container::value_type>()) 210b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat == cont.rend(); 211b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 212b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 213b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns a new ResultType containing the difference of two sorted containers. 214b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename ResultType, typename Arg1, typename Arg2> 215b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { 216b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 217b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 218b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ResultType difference; 219b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::set_difference(a1.begin(), a1.end(), 220b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end(), 221b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::inserter(difference, difference.end())); 222b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return difference; 223b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 224b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 225b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns a new ResultType containing the union of two sorted containers. 226b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename ResultType, typename Arg1, typename Arg2> 227b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratResultType STLSetUnion(const Arg1& a1, const Arg2& a2) { 228b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 229b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 230b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ResultType result; 231b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::set_union(a1.begin(), a1.end(), 232b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end(), 233b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::inserter(result, result.end())); 234b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return result; 235b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 236b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 237b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Returns a new ResultType containing the intersection of two sorted 238b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// containers. 239b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename ResultType, typename Arg1, typename Arg2> 240b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) { 241b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 242b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 243b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat ResultType result; 244b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::set_intersection(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 true if the sorted container |a1| contains all elements of the sorted 251b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// container |a2|. 252b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate <typename Arg1, typename Arg2> 253b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool STLIncludes(const Arg1& a1, const Arg2& a2) { 254b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a1)); 255b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat DCHECK(STLIsSorted(a2)); 256b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::includes(a1.begin(), a1.end(), 257b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat a2.begin(), a2.end()); 258b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 259b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 260b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} // namespace base 261b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 262b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#endif // BASE_STL_UTIL_H_ 263