| // 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_ |