blob: 25114122d799be2a04c0621a6a0cece11d2ba7a6 [file] [log] [blame]
// Copyright 2011 The Chromium Authors
// 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 <forward_list>
#include <iterator>
#include <type_traits>
#include "polyfills/base/check.h"
#include "base/ranges/algorithm.h"
namespace gurl_base {
namespace internal {
template <typename Iter>
constexpr bool IsRandomAccessIter =
std::is_same<typename std::iterator_traits<Iter>::iterator_category,
std::random_access_iterator_tag>::value;
} // namespace internal
// Returns a const reference to the underlying container of a container adapter.
// Works for std::priority_queue, std::queue, and std::stack.
template <class A>
const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
struct ExposedAdapter : A {
using A::c;
};
return adapter.*&ExposedAdapter::c;
}
// Clears internal memory of an STL object.
// STL clear()/reserve(0) does not always free internal memory allocated
// This function uses swap/destructor to ensure the internal memory is freed.
template<class T>
void STLClearObject(T* obj) {
T tmp;
tmp.swap(*obj);
// Sometimes "T tmp" allocates objects with memory (arena implementation?).
// Hence using additional reserve(0) even if it doesn't always work.
obj->reserve(0);
}
// O(1) implementation of const casting an iterator for any sequence,
// associative or unordered associative container in the STL.
//
// Reference: https://stackoverflow.com/a/10669041
template <typename Container,
typename ConstIter,
std::enable_if_t<!internal::IsRandomAccessIter<ConstIter>>* = nullptr>
constexpr auto ConstCastIterator(Container& c, ConstIter it) {
return c.erase(it, it);
}
// Explicit overload for std::forward_list where erase() is named erase_after().
template <typename T, typename Allocator>
constexpr auto ConstCastIterator(
std::forward_list<T, Allocator>& c,
typename std::forward_list<T, Allocator>::const_iterator it) {
// The erase_after(it, it) trick used below does not work for libstdc++ [1],
// thus we need a different way.
// TODO(crbug.com/972541): Remove this workaround once libstdc++ is fixed on all
// platforms.
//
// [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90857
#if defined(__GLIBCXX__)
return c.insert_after(it, {});
#else
return c.erase_after(it, it);
#endif
}
// Specialized O(1) const casting for random access iterators. This is
// necessary, because erase() is either not available (e.g. array-like
// containers), or has O(n) complexity (e.g. std::deque or std::vector).
template <typename Container,
typename ConstIter,
std::enable_if_t<internal::IsRandomAccessIter<ConstIter>>* = nullptr>
constexpr auto ConstCastIterator(Container& c, ConstIter it) {
using std::begin;
using std::cbegin;
return begin(c) + (it - cbegin(c));
}
// 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) {
GURL_DCHECK(ranges::is_sorted(a1));
GURL_DCHECK(ranges::is_sorted(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) {
GURL_DCHECK(ranges::is_sorted(a1));
GURL_DCHECK(ranges::is_sorted(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) {
GURL_DCHECK(ranges::is_sorted(a1));
GURL_DCHECK(ranges::is_sorted(a2));
ResultType result;
std::set_intersection(a1.begin(), a1.end(),
a2.begin(), a2.end(),
std::inserter(result, result.end()));
return result;
}
// A helper class to be used as the predicate with |EraseIf| to implement
// in-place set intersection. Helps implement the algorithm of going through
// each container an element at a time, erasing elements from the first
// container if they aren't in the second container. Requires each container be
// sorted. Note that the logic below appears inverted since it is returning
// whether an element should be erased.
template <class Collection>
class IsNotIn {
public:
explicit IsNotIn(const Collection& collection)
: i_(collection.begin()), end_(collection.end()) {}
bool operator()(const typename Collection::value_type& x) {
while (i_ != end_ && *i_ < x)
++i_;
if (i_ == end_)
return true;
if (*i_ == x) {
++i_;
return false;
}
return true;
}
private:
typename Collection::const_iterator i_;
const typename Collection::const_iterator end_;
};
} // namespace base
#endif // BASE_STL_UTIL_H_