// Copyright (c) 2011 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. // Derived from google3/util/gtl/stl_util.h #ifndef BASE_STL_UTIL_H_ #define BASE_STL_UTIL_H_ #include <algorithm> #include <deque> #include <forward_list> #include <functional> #include <initializer_list> #include <iterator> #include <list> #include <map> #include <set> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #include "base/logging.h" namespace base { namespace internal { // Calls erase on iterators of matching elements. template <typename Container, typename Predicate> void IterateAndEraseIf(Container& container, Predicate pred) { for (auto it = container.begin(); it != container.end();) { if (pred(*it)) it = container.erase(it); else ++it; } } } // namespace internal // Test to see if a set or map contains a particular key. // Returns true if the key is in the collection. template <typename Collection, typename Key> bool ContainsKey(const Collection& collection, const Key& key) { return collection.find(key) != collection.end(); } namespace internal { template <typename Collection> class HasKeyType { template <typename C> static std::true_type test(typename C::key_type*); template <typename C> static std::false_type test(...); public: static constexpr bool value = decltype(test<Collection>(nullptr))::value; }; } // namespace internal // Test to see if a collection like a vector contains a particular value. // Returns true if the value is in the collection. // Don't use this on collections such as sets or maps. This is enforced by // disabling this method if the collection defines a key_type. template <typename Collection, typename Value, typename std::enable_if<!internal::HasKeyType<Collection>::value, int>::type = 0> bool ContainsValue(const Collection& collection, const Value& value) { return std::find(std::begin(collection), std::end(collection), value) != std::end(collection); } // Returns true if the container is sorted. template <typename Container> bool STLIsSorted(const Container& cont) { // Note: Use reverse iterator on container to ensure we only require // value_type to implement operator<. return std::adjacent_find(cont.rbegin(), cont.rend(), std::less<typename Container::value_type>()) == cont.rend(); } // Returns a new ResultType containing the difference of two sorted containers. template <typename ResultType, typename Arg1, typename Arg2> ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { DCHECK(STLIsSorted(a1)); DCHECK(STLIsSorted(a2)); ResultType difference; std::set_difference(a1.begin(), a1.end(), a2.begin(), a2.end(), std::inserter(difference, difference.end())); return difference; } // Returns a new ResultType containing the union of two sorted containers. template <typename ResultType, typename Arg1, typename Arg2> ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) { DCHECK(STLIsSorted(a1)); DCHECK(STLIsSorted(a2)); ResultType result; std::set_union(a1.begin(), a1.end(), a2.begin(), a2.end(), std::inserter(result, result.end())); return result; } // Returns a new ResultType containing the intersection of two sorted // containers. template <typename ResultType, typename Arg1, typename Arg2> ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) { DCHECK(STLIsSorted(a1)); DCHECK(STLIsSorted(a2)); ResultType result; std::set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(), std::inserter(result, result.end())); return result; } // Returns true if the sorted container |a1| contains all elements of the sorted // container |a2|. template <typename Arg1, typename Arg2> bool STLIncludes(const Arg1& a1, const Arg2& a2) { DCHECK(STLIsSorted(a1)); DCHECK(STLIsSorted(a2)); return std::includes(a1.begin(), a1.end(), a2.begin(), a2.end()); } // Erase/EraseIf are based on library fundamentals ts v2 erase/erase_if // http://en.cppreference.com/w/cpp/experimental/lib_extensions_2 // They provide a generic way to erase elements from a container. // The functions here implement these for the standard containers until those // functions are available in the C++ standard. // For Chromium containers overloads should be defined in their own headers // (like standard containers). // Note: there is no std::erase for standard associative containers so we don't // have it either. template <typename CharT, typename Traits, typename Allocator, typename Value> void Erase(std::basic_string<CharT, Traits, Allocator>& container, const Value& value) { container.erase(std::remove(container.begin(), container.end(), value), container.end()); } template <typename CharT, typename Traits, typename Allocator, class Predicate> void EraseIf(std::basic_string<CharT, Traits, Allocator>& container, Predicate pred) { container.erase(std::remove_if(container.begin(), container.end(), pred), container.end()); } template <class T, class Allocator, class Value> void Erase(std::deque<T, Allocator>& container, const Value& value) { container.erase(std::remove(container.begin(), container.end(), value), container.end()); } template <class T, class Allocator, class Predicate> void EraseIf(std::deque<T, Allocator>& container, Predicate pred) { container.erase(std::remove_if(container.begin(), container.end(), pred), container.end()); } template <class T, class Allocator, class Value> void Erase(std::vector<T, Allocator>& container, const Value& value) { container.erase(std::remove(container.begin(), container.end(), value), container.end()); } template <class T, class Allocator, class Predicate> void EraseIf(std::vector<T, Allocator>& container, Predicate pred) { container.erase(std::remove_if(container.begin(), container.end(), pred), container.end()); } template <class T, class Allocator, class Value> void Erase(std::forward_list<T, Allocator>& container, const Value& value) { // Unlike std::forward_list::remove, this function template accepts // heterogeneous types and does not force a conversion to the container's // value type before invoking the == operator. container.remove_if([&](const T& cur) { return cur == value; }); } template <class T, class Allocator, class Predicate> void EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) { container.remove_if(pred); } template <class T, class Allocator, class Value> void Erase(std::list<T, Allocator>& container, const Value& value) { // Unlike std::list::remove, this function template accepts heterogeneous // types and does not force a conversion to the container's value type before // invoking the == operator. container.remove_if([&](const T& cur) { return cur == value; }); } template <class T, class Allocator, class Predicate> void EraseIf(std::list<T, Allocator>& container, Predicate pred) { container.remove_if(pred); } template <class Key, class T, class Compare, class Allocator, class Predicate> void EraseIf(std::map<Key, T, Compare, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class T, class Compare, class Allocator, class Predicate> void EraseIf(std::multimap<Key, T, Compare, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class Compare, class Allocator, class Predicate> void EraseIf(std::set<Key, Compare, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class Compare, class Allocator, class Predicate> void EraseIf(std::multiset<Key, Compare, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class T, class Hash, class KeyEqual, class Allocator, class Predicate> void EraseIf(std::unordered_map<Key, T, Hash, KeyEqual, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class T, class Hash, class KeyEqual, class Allocator, class Predicate> void EraseIf( std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class Hash, class KeyEqual, class Allocator, class Predicate> void EraseIf(std::unordered_set<Key, Hash, KeyEqual, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } template <class Key, class Hash, class KeyEqual, class Allocator, class Predicate> void EraseIf(std::unordered_multiset<Key, Hash, KeyEqual, Allocator>& container, Predicate pred) { internal::IterateAndEraseIf(container, pred); } } // namespace base #endif // BASE_STL_UTIL_H_