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 <deque> 12 #include <forward_list> 13 #include <functional> 14 #include <iterator> 15 #include <list> 16 #include <map> 17 #include <set> 18 #include <string> 19 #include <unordered_map> 20 #include <unordered_set> 21 #include <vector> 22 23 #include "base/logging.h" 24 25 namespace base { 26 27 namespace internal { 28 29 // Calls erase on iterators of matching elements. 30 template <typename Container, typename Predicate> 31 void IterateAndEraseIf(Container& container, Predicate pred) { 32 for (auto it = container.begin(); it != container.end();) { 33 if (pred(*it)) 34 it = container.erase(it); 35 else 36 ++it; 37 } 38 } 39 40 } // namespace internal 41 42 // Clears internal memory of an STL object. 43 // STL clear()/reserve(0) does not always free internal memory allocated 44 // This function uses swap/destructor to ensure the internal memory is freed. 45 template<class T> 46 void STLClearObject(T* obj) { 47 T tmp; 48 tmp.swap(*obj); 49 // Sometimes "T tmp" allocates objects with memory (arena implementation?). 50 // Hence using additional reserve(0) even if it doesn't always work. 51 obj->reserve(0); 52 } 53 54 // Counts the number of instances of val in a container. 55 template <typename Container, typename T> 56 typename std::iterator_traits< 57 typename Container::const_iterator>::difference_type 58 STLCount(const Container& container, const T& val) { 59 return std::count(container.begin(), container.end(), val); 60 } 61 62 // Return a mutable char* pointing to a string's internal buffer, 63 // which may not be null-terminated. Writing through this pointer will 64 // modify the string. 65 // 66 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the 67 // next call to a string method that invalidates iterators. 68 // 69 // As of 2006-04, there is no standard-blessed way of getting a 70 // mutable reference to a string's internal buffer. However, issue 530 71 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) 72 // proposes this as the method. According to Matt Austern, this should 73 // already work on all current implementations. 74 inline char* string_as_array(std::string* str) { 75 // DO NOT USE const_cast<char*>(str->data()) 76 return str->empty() ? NULL : &*str->begin(); 77 } 78 79 // Test to see if a set, map, hash_set or hash_map contains a particular key. 80 // Returns true if the key is in the collection. 81 template <typename Collection, typename Key> 82 bool ContainsKey(const Collection& collection, const Key& key) { 83 return collection.find(key) != collection.end(); 84 } 85 86 // Test to see if a collection like a vector contains a particular value. 87 // Returns true if the value is in the collection. 88 template <typename Collection, typename Value> 89 bool ContainsValue(const Collection& collection, const Value& value) { 90 return std::find(collection.begin(), collection.end(), value) != 91 collection.end(); 92 } 93 94 // Returns true if the container is sorted. 95 template <typename Container> 96 bool STLIsSorted(const Container& cont) { 97 // Note: Use reverse iterator on container to ensure we only require 98 // value_type to implement operator<. 99 return std::adjacent_find(cont.rbegin(), cont.rend(), 100 std::less<typename Container::value_type>()) 101 == cont.rend(); 102 } 103 104 // Returns a new ResultType containing the difference of two sorted containers. 105 template <typename ResultType, typename Arg1, typename Arg2> 106 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { 107 DCHECK(STLIsSorted(a1)); 108 DCHECK(STLIsSorted(a2)); 109 ResultType difference; 110 std::set_difference(a1.begin(), a1.end(), 111 a2.begin(), a2.end(), 112 std::inserter(difference, difference.end())); 113 return difference; 114 } 115 116 // Returns a new ResultType containing the union of two sorted containers. 117 template <typename ResultType, typename Arg1, typename Arg2> 118 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) { 119 DCHECK(STLIsSorted(a1)); 120 DCHECK(STLIsSorted(a2)); 121 ResultType result; 122 std::set_union(a1.begin(), a1.end(), 123 a2.begin(), a2.end(), 124 std::inserter(result, result.end())); 125 return result; 126 } 127 128 // Returns a new ResultType containing the intersection of two sorted 129 // containers. 130 template <typename ResultType, typename Arg1, typename Arg2> 131 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) { 132 DCHECK(STLIsSorted(a1)); 133 DCHECK(STLIsSorted(a2)); 134 ResultType result; 135 std::set_intersection(a1.begin(), a1.end(), 136 a2.begin(), a2.end(), 137 std::inserter(result, result.end())); 138 return result; 139 } 140 141 // Returns true if the sorted container |a1| contains all elements of the sorted 142 // container |a2|. 143 template <typename Arg1, typename Arg2> 144 bool STLIncludes(const Arg1& a1, const Arg2& a2) { 145 DCHECK(STLIsSorted(a1)); 146 DCHECK(STLIsSorted(a2)); 147 return std::includes(a1.begin(), a1.end(), 148 a2.begin(), a2.end()); 149 } 150 151 // Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if 152 // http://en.cppreference.com/w/cpp/experimental/lib_extensions_2 153 // They provide a generic way to erase elements from a container. 154 // The functions here implement these for the standard containers until those 155 // functions are available in the C++ standard. 156 // For Chromium containers overloads should be defined in their own headers 157 // (like standard containers). 158 // Note: there is no std::erase for standard associative containers so we don't 159 // have it either. 160 161 template <typename CharT, typename Traits, typename Allocator, typename Value> 162 void Erase(std::basic_string<CharT, Traits, Allocator>& container, 163 const Value& value) { 164 container.erase(std::remove(container.begin(), container.end(), value), 165 container.end()); 166 } 167 168 template <typename CharT, typename Traits, typename Allocator, class Predicate> 169 void EraseIf(std::basic_string<CharT, Traits, Allocator>& container, 170 Predicate pred) { 171 container.erase(std::remove_if(container.begin(), container.end(), pred), 172 container.end()); 173 } 174 175 template <class T, class Allocator, class Value> 176 void Erase(std::deque<T, Allocator>& container, const Value& value) { 177 container.erase(std::remove(container.begin(), container.end(), value), 178 container.end()); 179 } 180 181 template <class T, class Allocator, class Predicate> 182 void EraseIf(std::deque<T, Allocator>& container, Predicate pred) { 183 container.erase(std::remove_if(container.begin(), container.end(), pred), 184 container.end()); 185 } 186 187 template <class T, class Allocator, class Value> 188 void Erase(std::vector<T, Allocator>& container, const Value& value) { 189 container.erase(std::remove(container.begin(), container.end(), value), 190 container.end()); 191 } 192 193 template <class T, class Allocator, class Predicate> 194 void EraseIf(std::vector<T, Allocator>& container, Predicate pred) { 195 container.erase(std::remove_if(container.begin(), container.end(), pred), 196 container.end()); 197 } 198 199 template <class T, class Allocator, class Value> 200 void Erase(std::forward_list<T, Allocator>& container, const Value& value) { 201 // Unlike std::forward_list::remove, this function template accepts 202 // heterogeneous types and does not force a conversion to the container's 203 // value type before invoking the == operator. 204 container.remove_if([&](const T& cur) { return cur == value; }); 205 } 206 207 template <class T, class Allocator, class Predicate> 208 void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) { 209 container.remove_if(pred); 210 } 211 212 template <class T, class Allocator, class Value> 213 void Erase(std::list<T, Allocator>& container, const Value& value) { 214 // Unlike std::list::remove, this function template accepts heterogeneous 215 // types and does not force a conversion to the container's value type before 216 // invoking the == operator. 217 container.remove_if([&](const T& cur) { return cur == value; }); 218 } 219 220 template <class T, class Allocator, class Predicate> 221 void EraseIf(std::list<T, Allocator>& container, Predicate pred) { 222 container.remove_if(pred); 223 } 224 225 template <class Key, class T, class Compare, class Allocator, class Predicate> 226 void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) { 227 internal::IterateAndEraseIf(container, pred); 228 } 229 230 template <class Key, class T, class Compare, class Allocator, class Predicate> 231 void EraseIf(std::multimap<Key, T, Compare, Allocator>& container, 232 Predicate pred) { 233 internal::IterateAndEraseIf(container, pred); 234 } 235 236 template <class Key, class Compare, class Allocator, class Predicate> 237 void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) { 238 internal::IterateAndEraseIf(container, pred); 239 } 240 241 template <class Key, class Compare, class Allocator, class Predicate> 242 void EraseIf(std::multiset<Key, Compare, Allocator>& container, 243 Predicate pred) { 244 internal::IterateAndEraseIf(container, pred); 245 } 246 247 template <class Key, 248 class T, 249 class Hash, 250 class KeyEqual, 251 class Allocator, 252 class Predicate> 253 void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container, 254 Predicate pred) { 255 internal::IterateAndEraseIf(container, pred); 256 } 257 258 template <class Key, 259 class T, 260 class Hash, 261 class KeyEqual, 262 class Allocator, 263 class Predicate> 264 void EraseIf( 265 std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container, 266 Predicate pred) { 267 internal::IterateAndEraseIf(container, pred); 268 } 269 270 template <class Key, 271 class Hash, 272 class KeyEqual, 273 class Allocator, 274 class Predicate> 275 void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container, 276 Predicate pred) { 277 internal::IterateAndEraseIf(container, pred); 278 } 279 280 template <class Key, 281 class Hash, 282 class KeyEqual, 283 class Allocator, 284 class Predicate> 285 void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container, 286 Predicate pred) { 287 internal::IterateAndEraseIf(container, pred); 288 } 289 290 } // namespace base 291 292 #endif // BASE_STL_UTIL_H_ 293
