| // Copyright 2017 The Abseil Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // ----------------------------------------------------------------------------- |
| // File: container.h |
| // ----------------------------------------------------------------------------- |
| // |
| // This header file provides Container-based versions of algorithmic functions |
| // within the C++ standard library. The following standard library sets of |
| // functions are covered within this file: |
| // |
| // * Algorithmic <iterator> functions |
| // * Algorithmic <numeric> functions |
| // * <algorithm> functions |
| // |
| // The standard library functions operate on iterator ranges; the functions |
| // within this API operate on containers, though many return iterator ranges. |
| // |
| // All functions within this API are named with a `c_` prefix. Calls such as |
| // `absl::c_xx(container, ...) are equivalent to std:: functions such as |
| // `std::xx(std::begin(cont), std::end(cont), ...)`. Functions that act on |
| // iterators but not conceptually on iterator ranges (e.g. `std::iter_swap`) |
| // have no equivalent here. |
| // |
| // For template parameter and variable naming, `C` indicates the container type |
| // to which the function is applied, `Pred` indicates the predicate object type |
| // to be used by the function and `T` indicates the applicable element type. |
| |
| #ifndef ABSL_ALGORITHM_CONTAINER_H_ |
| #define ABSL_ALGORITHM_CONTAINER_H_ |
| |
| #include <algorithm> |
| #include <cassert> |
| #include <iterator> |
| #include <numeric> |
| #include <type_traits> |
| #include <unordered_map> |
| #include <unordered_set> |
| #include <utility> |
| #include <vector> |
| |
| #include "absl/algorithm/algorithm.h" |
| #include "absl/base/macros.h" |
| #include "absl/meta/type_traits.h" |
| |
| namespace absl { |
| namespace container_algorithm_internal { |
| |
| // NOTE: it is important to defer to ADL lookup for building with C++ modules, |
| // especially for headers like <valarray> which are not visible from this file |
| // but specialize std::begin and std::end. |
| using std::begin; |
| using std::end; |
| |
| // The type of the iterator given by begin(c) (possibly std::begin(c)). |
| // ContainerIter<const vector<T>> gives vector<T>::const_iterator, |
| // while ContainerIter<vector<T>> gives vector<T>::iterator. |
| template <typename C> |
| using ContainerIter = decltype(begin(std::declval<C&>())); |
| |
| // An MSVC bug involving template parameter substitution requires us to use |
| // decltype() here instead of just std::pair. |
| template <typename C1, typename C2> |
| using ContainerIterPairType = |
| decltype(std::make_pair(ContainerIter<C1>(), ContainerIter<C2>())); |
| |
| template <typename C> |
| using ContainerDifferenceType = |
| decltype(std::distance(std::declval<ContainerIter<C>>(), |
| std::declval<ContainerIter<C>>())); |
| |
| template <typename C> |
| using ContainerPointerType = |
| typename std::iterator_traits<ContainerIter<C>>::pointer; |
| |
| // container_algorithm_internal::c_begin and |
| // container_algorithm_internal::c_end are abbreviations for proper ADL |
| // lookup of std::begin and std::end, i.e. |
| // using std::begin; |
| // using std::end; |
| // std::foo(begin(c), end(c); |
| // becomes |
| // std::foo(container_algorithm_internal::begin(c), |
| // container_algorithm_internal::end(c)); |
| // These are meant for internal use only. |
| |
| template <typename C> |
| ContainerIter<C> c_begin(C& c) { return begin(c); } |
| |
| template <typename C> |
| ContainerIter<C> c_end(C& c) { return end(c); } |
| |
| template <typename T> |
| struct IsUnorderedContainer : std::false_type {}; |
| |
| template <class Key, class T, class Hash, class KeyEqual, class Allocator> |
| struct IsUnorderedContainer< |
| std::unordered_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {}; |
| |
| template <class Key, class Hash, class KeyEqual, class Allocator> |
| struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>> |
| : std::true_type {}; |
| |
| } // namespace container_algorithm_internal |
| |
| // PUBLIC API |
| |
| //------------------------------------------------------------------------------ |
| // Abseil algorithm.h functions |
| //------------------------------------------------------------------------------ |
| |
| // c_linear_search() |
| // |
| // Container-based version of absl::linear_search() for performing a linear |
| // search within a container. |
| template <typename C, typename EqualityComparable> |
| bool c_linear_search(const C& c, EqualityComparable&& value) { |
| return linear_search(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<EqualityComparable>(value)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <iterator> algorithms |
| //------------------------------------------------------------------------------ |
| |
| // c_distance() |
| // |
| // Container-based version of the <iterator> `std::distance()` function to |
| // return the number of elements within a container. |
| template <typename C> |
| container_algorithm_internal::ContainerDifferenceType<const C> c_distance( |
| const C& c) { |
| return std::distance(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Non-modifying sequence operations |
| //------------------------------------------------------------------------------ |
| |
| // c_all_of() |
| // |
| // Container-based version of the <algorithm> `std::all_of()` function to |
| // test a condition on all elements within a container. |
| template <typename C, typename Pred> |
| bool c_all_of(const C& c, Pred&& pred) { |
| return std::all_of(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_any_of() |
| // |
| // Container-based version of the <algorithm> `std::any_of()` function to |
| // test if any element in a container fulfills a condition. |
| template <typename C, typename Pred> |
| bool c_any_of(const C& c, Pred&& pred) { |
| return std::any_of(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_none_of() |
| // |
| // Container-based version of the <algorithm> `std::none_of()` function to |
| // test if no elements in a container fulfil a condition. |
| template <typename C, typename Pred> |
| bool c_none_of(const C& c, Pred&& pred) { |
| return std::none_of(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_for_each() |
| // |
| // Container-based version of the <algorithm> `std::for_each()` function to |
| // apply a function to a container's elements. |
| template <typename C, typename Function> |
| decay_t<Function> c_for_each(C&& c, Function&& f) { |
| return std::for_each(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Function>(f)); |
| } |
| |
| // c_find() |
| // |
| // Container-based version of the <algorithm> `std::find()` function to find |
| // the first element containing the passed value within a container value. |
| template <typename C, typename T> |
| container_algorithm_internal::ContainerIter<C> c_find(C& c, T&& value) { |
| return std::find(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<T>(value)); |
| } |
| |
| // c_find_if() |
| // |
| // Container-based version of the <algorithm> `std::find_if()` function to find |
| // the first element in a container matching the given condition. |
| template <typename C, typename Pred> |
| container_algorithm_internal::ContainerIter<C> c_find_if(C& c, Pred&& pred) { |
| return std::find_if(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_find_if_not() |
| // |
| // Container-based version of the <algorithm> `std::find_if_not()` function to |
| // find the first element in a container not matching the given condition. |
| template <typename C, typename Pred> |
| container_algorithm_internal::ContainerIter<C> c_find_if_not(C& c, |
| Pred&& pred) { |
| return std::find_if_not(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_find_end() |
| // |
| // Container-based version of the <algorithm> `std::find_end()` function to |
| // find the last subsequence within a container. |
| template <typename Sequence1, typename Sequence2> |
| container_algorithm_internal::ContainerIter<Sequence1> c_find_end( |
| Sequence1& sequence, Sequence2& subsequence) { |
| return std::find_end(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| container_algorithm_internal::c_begin(subsequence), |
| container_algorithm_internal::c_end(subsequence)); |
| } |
| |
| // Overload of c_find_end() for using a predicate evaluation other than `==` as |
| // the function's test condition. |
| template <typename Sequence1, typename Sequence2, typename BinaryPredicate> |
| container_algorithm_internal::ContainerIter<Sequence1> c_find_end( |
| Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { |
| return std::find_end(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| container_algorithm_internal::c_begin(subsequence), |
| container_algorithm_internal::c_end(subsequence), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_find_first_of() |
| // |
| // Container-based version of the <algorithm> `std::find_first_of()` function to |
| // find the first elements in an ordered set within a container. |
| template <typename C1, typename C2> |
| container_algorithm_internal::ContainerIter<C1> c_find_first_of(C1& container, |
| C2& options) { |
| return std::find_first_of(container_algorithm_internal::c_begin(container), |
| container_algorithm_internal::c_end(container), |
| container_algorithm_internal::c_begin(options), |
| container_algorithm_internal::c_end(options)); |
| } |
| |
| // Overload of c_find_first_of() for using a predicate evaluation other than |
| // `==` as the function's test condition. |
| template <typename C1, typename C2, typename BinaryPredicate> |
| container_algorithm_internal::ContainerIter<C1> c_find_first_of( |
| C1& container, C2& options, BinaryPredicate&& pred) { |
| return std::find_first_of(container_algorithm_internal::c_begin(container), |
| container_algorithm_internal::c_end(container), |
| container_algorithm_internal::c_begin(options), |
| container_algorithm_internal::c_end(options), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_adjacent_find() |
| // |
| // Container-based version of the <algorithm> `std::adjacent_find()` function to |
| // find equal adjacent elements within a container. |
| template <typename Sequence> |
| container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find( |
| Sequence& sequence) { |
| return std::adjacent_find(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_adjacent_find() for using a predicate evaluation other than |
| // `==` as the function's test condition. |
| template <typename Sequence, typename BinaryPredicate> |
| container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find( |
| Sequence& sequence, BinaryPredicate&& pred) { |
| return std::adjacent_find(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_count() |
| // |
| // Container-based version of the <algorithm> `std::count()` function to count |
| // values that match within a container. |
| template <typename C, typename T> |
| container_algorithm_internal::ContainerDifferenceType<const C> c_count( |
| const C& c, T&& value) { |
| return std::count(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<T>(value)); |
| } |
| |
| // c_count_if() |
| // |
| // Container-based version of the <algorithm> `std::count_if()` function to |
| // count values matching a condition within a container. |
| template <typename C, typename Pred> |
| container_algorithm_internal::ContainerDifferenceType<const C> c_count_if( |
| const C& c, Pred&& pred) { |
| return std::count_if(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_mismatch() |
| // |
| // Container-based version of the <algorithm> `std::mismatch()` function to |
| // return the first element where two ordered containers differ. |
| template <typename C1, typename C2> |
| container_algorithm_internal::ContainerIterPairType<C1, C2> |
| c_mismatch(C1& c1, C2& c2) { |
| return std::mismatch(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2)); |
| } |
| |
| // Overload of c_mismatch() for using a predicate evaluation other than `==` as |
| // the function's test condition. |
| template <typename C1, typename C2, typename BinaryPredicate> |
| container_algorithm_internal::ContainerIterPairType<C1, C2> |
| c_mismatch(C1& c1, C2& c2, BinaryPredicate&& pred) { |
| return std::mismatch(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_equal() |
| // |
| // Container-based version of the <algorithm> `std::equal()` function to |
| // test whether two containers are equal. |
| // |
| // NOTE: the semantics of c_equal() are slightly different than those of |
| // equal(): while the latter iterates over the second container only up to the |
| // size of the first container, c_equal() also checks whether the container |
| // sizes are equal. This better matches expectations about c_equal() based on |
| // its signature. |
| // |
| // Example: |
| // vector v1 = <1, 2, 3>; |
| // vector v2 = <1, 2, 3, 4>; |
| // equal(std::begin(v1), std::end(v1), std::begin(v2)) returns true |
| // c_equal(v1, v2) returns false |
| |
| template <typename C1, typename C2> |
| bool c_equal(const C1& c1, const C2& c2) { |
| return ((c1.size() == c2.size()) && |
| std::equal(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2))); |
| } |
| |
| // Overload of c_equal() for using a predicate evaluation other than `==` as |
| // the function's test condition. |
| template <typename C1, typename C2, typename BinaryPredicate> |
| bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) { |
| return ((c1.size() == c2.size()) && |
| std::equal(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| std::forward<BinaryPredicate>(pred))); |
| } |
| |
| // c_is_permutation() |
| // |
| // Container-based version of the <algorithm> `std::is_permutation()` function |
| // to test whether a container is a permutation of another. |
| template <typename C1, typename C2> |
| bool c_is_permutation(const C1& c1, const C2& c2) { |
| using std::begin; |
| using std::end; |
| return c1.size() == c2.size() && |
| std::is_permutation(begin(c1), end(c1), begin(c2)); |
| } |
| |
| // Overload of c_is_permutation() for using a predicate evaluation other than |
| // `==` as the function's test condition. |
| template <typename C1, typename C2, typename BinaryPredicate> |
| bool c_is_permutation(const C1& c1, const C2& c2, BinaryPredicate&& pred) { |
| using std::begin; |
| using std::end; |
| return c1.size() == c2.size() && |
| std::is_permutation(begin(c1), end(c1), begin(c2), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_search() |
| // |
| // Container-based version of the <algorithm> `std::search()` function to search |
| // a container for a subsequence. |
| template <typename Sequence1, typename Sequence2> |
| container_algorithm_internal::ContainerIter<Sequence1> c_search( |
| Sequence1& sequence, Sequence2& subsequence) { |
| return std::search(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| container_algorithm_internal::c_begin(subsequence), |
| container_algorithm_internal::c_end(subsequence)); |
| } |
| |
| // Overload of c_search() for using a predicate evaluation other than |
| // `==` as the function's test condition. |
| template <typename Sequence1, typename Sequence2, typename BinaryPredicate> |
| container_algorithm_internal::ContainerIter<Sequence1> c_search( |
| Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { |
| return std::search(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| container_algorithm_internal::c_begin(subsequence), |
| container_algorithm_internal::c_end(subsequence), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_search_n() |
| // |
| // Container-based version of the <algorithm> `std::search_n()` function to |
| // search a container for the first sequence of N elements. |
| template <typename Sequence, typename Size, typename T> |
| container_algorithm_internal::ContainerIter<Sequence> c_search_n( |
| Sequence& sequence, Size count, T&& value) { |
| return std::search_n(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), count, |
| std::forward<T>(value)); |
| } |
| |
| // Overload of c_search_n() for using a predicate evaluation other than |
| // `==` as the function's test condition. |
| template <typename Sequence, typename Size, typename T, |
| typename BinaryPredicate> |
| container_algorithm_internal::ContainerIter<Sequence> c_search_n( |
| Sequence& sequence, Size count, T&& value, BinaryPredicate&& pred) { |
| return std::search_n(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), count, |
| std::forward<T>(value), |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Modifying sequence operations |
| //------------------------------------------------------------------------------ |
| |
| // c_copy() |
| // |
| // Container-based version of the <algorithm> `std::copy()` function to copy a |
| // container's elements into an iterator. |
| template <typename InputSequence, typename OutputIterator> |
| OutputIterator c_copy(const InputSequence& input, OutputIterator output) { |
| return std::copy(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), output); |
| } |
| |
| // c_copy_n() |
| // |
| // Container-based version of the <algorithm> `std::copy_n()` function to copy a |
| // container's first N elements into an iterator. |
| template <typename C, typename Size, typename OutputIterator> |
| OutputIterator c_copy_n(const C& input, Size n, OutputIterator output) { |
| return std::copy_n(container_algorithm_internal::c_begin(input), n, output); |
| } |
| |
| // c_copy_if() |
| // |
| // Container-based version of the <algorithm> `std::copy_if()` function to copy |
| // a container's elements satisfying some condition into an iterator. |
| template <typename InputSequence, typename OutputIterator, typename Pred> |
| OutputIterator c_copy_if(const InputSequence& input, OutputIterator output, |
| Pred&& pred) { |
| return std::copy_if(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), output, |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_copy_backward() |
| // |
| // Container-based version of the <algorithm> `std::copy_backward()` function to |
| // copy a container's elements in reverse order into an iterator. |
| template <typename C, typename BidirectionalIterator> |
| BidirectionalIterator c_copy_backward(const C& src, |
| BidirectionalIterator dest) { |
| return std::copy_backward(container_algorithm_internal::c_begin(src), |
| container_algorithm_internal::c_end(src), dest); |
| } |
| |
| // c_move() |
| // |
| // Container-based version of the <algorithm> `std::move()` function to move |
| // a container's elements into an iterator. |
| template <typename C, typename OutputIterator> |
| OutputIterator c_move(C&& src, OutputIterator dest) { |
| return std::move(container_algorithm_internal::c_begin(src), |
| container_algorithm_internal::c_end(src), dest); |
| } |
| |
| // c_swap_ranges() |
| // |
| // Container-based version of the <algorithm> `std::swap_ranges()` function to |
| // swap a container's elements with another container's elements. |
| template <typename C1, typename C2> |
| container_algorithm_internal::ContainerIter<C2> c_swap_ranges(C1& c1, C2& c2) { |
| return std::swap_ranges(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2)); |
| } |
| |
| // c_transform() |
| // |
| // Container-based version of the <algorithm> `std::transform()` function to |
| // transform a container's elements using the unary operation, storing the |
| // result in an iterator pointing to the last transformed element in the output |
| // range. |
| template <typename InputSequence, typename OutputIterator, typename UnaryOp> |
| OutputIterator c_transform(const InputSequence& input, OutputIterator output, |
| UnaryOp&& unary_op) { |
| return std::transform(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), output, |
| std::forward<UnaryOp>(unary_op)); |
| } |
| |
| // Overload of c_transform() for performing a transformation using a binary |
| // predicate. |
| template <typename InputSequence1, typename InputSequence2, |
| typename OutputIterator, typename BinaryOp> |
| OutputIterator c_transform(const InputSequence1& input1, |
| const InputSequence2& input2, OutputIterator output, |
| BinaryOp&& binary_op) { |
| return std::transform(container_algorithm_internal::c_begin(input1), |
| container_algorithm_internal::c_end(input1), |
| container_algorithm_internal::c_begin(input2), output, |
| std::forward<BinaryOp>(binary_op)); |
| } |
| |
| // c_replace() |
| // |
| // Container-based version of the <algorithm> `std::replace()` function to |
| // replace a container's elements of some value with a new value. The container |
| // is modified in place. |
| template <typename Sequence, typename T> |
| void c_replace(Sequence& sequence, const T& old_value, const T& new_value) { |
| std::replace(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), old_value, |
| new_value); |
| } |
| |
| // c_replace_if() |
| // |
| // Container-based version of the <algorithm> `std::replace_if()` function to |
| // replace a container's elements of some value with a new value based on some |
| // condition. The container is modified in place. |
| template <typename C, typename Pred, typename T> |
| void c_replace_if(C& c, Pred&& pred, T&& new_value) { |
| std::replace_if(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred), std::forward<T>(new_value)); |
| } |
| |
| // c_replace_copy() |
| // |
| // Container-based version of the <algorithm> `std::replace_copy()` function to |
| // replace a container's elements of some value with a new value and return the |
| // results within an iterator. |
| template <typename C, typename OutputIterator, typename T> |
| OutputIterator c_replace_copy(const C& c, OutputIterator result, T&& old_value, |
| T&& new_value) { |
| return std::replace_copy(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), result, |
| std::forward<T>(old_value), |
| std::forward<T>(new_value)); |
| } |
| |
| // c_replace_copy_if() |
| // |
| // Container-based version of the <algorithm> `std::replace_copy_if()` function |
| // to replace a container's elements of some value with a new value based on |
| // some condition, and return the results within an iterator. |
| template <typename C, typename OutputIterator, typename Pred, typename T> |
| OutputIterator c_replace_copy_if(const C& c, OutputIterator result, Pred&& pred, |
| T&& new_value) { |
| return std::replace_copy_if(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), result, |
| std::forward<Pred>(pred), |
| std::forward<T>(new_value)); |
| } |
| |
| // c_fill() |
| // |
| // Container-based version of the <algorithm> `std::fill()` function to fill a |
| // container with some value. |
| template <typename C, typename T> |
| void c_fill(C& c, T&& value) { |
| std::fill(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), std::forward<T>(value)); |
| } |
| |
| // c_fill_n() |
| // |
| // Container-based version of the <algorithm> `std::fill_n()` function to fill |
| // the first N elements in a container with some value. |
| template <typename C, typename Size, typename T> |
| void c_fill_n(C& c, Size n, T&& value) { |
| std::fill_n(container_algorithm_internal::c_begin(c), n, |
| std::forward<T>(value)); |
| } |
| |
| // c_generate() |
| // |
| // Container-based version of the <algorithm> `std::generate()` function to |
| // assign a container's elements to the values provided by the given generator. |
| template <typename C, typename Generator> |
| void c_generate(C& c, Generator&& gen) { |
| std::generate(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Generator>(gen)); |
| } |
| |
| // c_generate_n() |
| // |
| // Container-based version of the <algorithm> `std::generate_n()` function to |
| // assign a container's first N elements to the values provided by the given |
| // generator. |
| template <typename C, typename Size, typename Generator> |
| container_algorithm_internal::ContainerIter<C> c_generate_n(C& c, Size n, |
| Generator&& gen) { |
| return std::generate_n(container_algorithm_internal::c_begin(c), n, |
| std::forward<Generator>(gen)); |
| } |
| |
| // Note: `c_xx()` <algorithm> container versions for `remove()`, `remove_if()`, |
| // and `unique()` are omitted, because it's not clear whether or not such |
| // functions should call erase on their supplied sequences afterwards. Either |
| // behavior would be surprising for a different set of users. |
| |
| // c_remove_copy() |
| // |
| // Container-based version of the <algorithm> `std::remove_copy()` function to |
| // copy a container's elements while removing any elements matching the given |
| // `value`. |
| template <typename C, typename OutputIterator, typename T> |
| OutputIterator c_remove_copy(const C& c, OutputIterator result, T&& value) { |
| return std::remove_copy(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), result, |
| std::forward<T>(value)); |
| } |
| |
| // c_remove_copy_if() |
| // |
| // Container-based version of the <algorithm> `std::remove_copy_if()` function |
| // to copy a container's elements while removing any elements matching the given |
| // condition. |
| template <typename C, typename OutputIterator, typename Pred> |
| OutputIterator c_remove_copy_if(const C& c, OutputIterator result, |
| Pred&& pred) { |
| return std::remove_copy_if(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), result, |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_unique_copy() |
| // |
| // Container-based version of the <algorithm> `std::unique_copy()` function to |
| // copy a container's elements while removing any elements containing duplicate |
| // values. |
| template <typename C, typename OutputIterator> |
| OutputIterator c_unique_copy(const C& c, OutputIterator result) { |
| return std::unique_copy(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), result); |
| } |
| |
| // Overload of c_unique_copy() for using a predicate evaluation other than |
| // `==` for comparing uniqueness of the element values. |
| template <typename C, typename OutputIterator, typename BinaryPredicate> |
| OutputIterator c_unique_copy(const C& c, OutputIterator result, |
| BinaryPredicate&& pred) { |
| return std::unique_copy(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), result, |
| std::forward<BinaryPredicate>(pred)); |
| } |
| |
| // c_reverse() |
| // |
| // Container-based version of the <algorithm> `std::reverse()` function to |
| // reverse a container's elements. |
| template <typename Sequence> |
| void c_reverse(Sequence& sequence) { |
| std::reverse(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // c_reverse_copy() |
| // |
| // Container-based version of the <algorithm> `std::reverse()` function to |
| // reverse a container's elements and write them to an iterator range. |
| template <typename C, typename OutputIterator> |
| OutputIterator c_reverse_copy(const C& sequence, OutputIterator result) { |
| return std::reverse_copy(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| result); |
| } |
| |
| // c_rotate() |
| // |
| // Container-based version of the <algorithm> `std::rotate()` function to |
| // shift a container's elements leftward such that the `middle` element becomes |
| // the first element in the container. |
| template <typename C, |
| typename Iterator = container_algorithm_internal::ContainerIter<C>> |
| Iterator c_rotate(C& sequence, Iterator middle) { |
| return absl::rotate(container_algorithm_internal::c_begin(sequence), middle, |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // c_rotate_copy() |
| // |
| // Container-based version of the <algorithm> `std::rotate_copy()` function to |
| // shift a container's elements leftward such that the `middle` element becomes |
| // the first element in a new iterator range. |
| template <typename C, typename OutputIterator> |
| OutputIterator c_rotate_copy( |
| const C& sequence, |
| container_algorithm_internal::ContainerIter<const C> middle, |
| OutputIterator result) { |
| return std::rotate_copy(container_algorithm_internal::c_begin(sequence), |
| middle, container_algorithm_internal::c_end(sequence), |
| result); |
| } |
| |
| // c_shuffle() |
| // |
| // Container-based version of the <algorithm> `std::shuffle()` function to |
| // randomly shuffle elements within the container using a `gen()` uniform random |
| // number generator. |
| template <typename RandomAccessContainer, typename UniformRandomBitGenerator> |
| void c_shuffle(RandomAccessContainer& c, UniformRandomBitGenerator&& gen) { |
| std::shuffle(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<UniformRandomBitGenerator>(gen)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Partition functions |
| //------------------------------------------------------------------------------ |
| |
| // c_is_partitioned() |
| // |
| // Container-based version of the <algorithm> `std::is_partitioned()` function |
| // to test whether all elements in the container for which `pred` returns `true` |
| // precede those for which `pred` is `false`. |
| template <typename C, typename Pred> |
| bool c_is_partitioned(const C& c, Pred&& pred) { |
| return std::is_partitioned(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_partition() |
| // |
| // Container-based version of the <algorithm> `std::partition()` function |
| // to rearrange all elements in a container in such a way that all elements for |
| // which `pred` returns `true` precede all those for which it returns `false`, |
| // returning an iterator to the first element of the second group. |
| template <typename C, typename Pred> |
| container_algorithm_internal::ContainerIter<C> c_partition(C& c, Pred&& pred) { |
| return std::partition(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_stable_partition() |
| // |
| // Container-based version of the <algorithm> `std::stable_partition()` function |
| // to rearrange all elements in a container in such a way that all elements for |
| // which `pred` returns `true` precede all those for which it returns `false`, |
| // preserving the relative ordering between the two groups. The function returns |
| // an iterator to the first element of the second group. |
| template <typename C, typename Pred> |
| container_algorithm_internal::ContainerIter<C> c_stable_partition(C& c, |
| Pred&& pred) { |
| return std::stable_partition(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| // c_partition_copy() |
| // |
| // Container-based version of the <algorithm> `std::partition_copy()` function |
| // to partition a container's elements and return them into two iterators: one |
| // for which `pred` returns `true`, and one for which `pred` returns `false.` |
| |
| template <typename C, typename OutputIterator1, typename OutputIterator2, |
| typename Pred> |
| std::pair<OutputIterator1, OutputIterator2> c_partition_copy( |
| const C& c, OutputIterator1 out_true, OutputIterator2 out_false, |
| Pred&& pred) { |
| return std::partition_copy(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), out_true, |
| out_false, std::forward<Pred>(pred)); |
| } |
| |
| // c_partition_point() |
| // |
| // Container-based version of the <algorithm> `std::partition_point()` function |
| // to return the first element of an already partitioned container for which |
| // the given `pred` is not `true`. |
| template <typename C, typename Pred> |
| container_algorithm_internal::ContainerIter<C> c_partition_point(C& c, |
| Pred&& pred) { |
| return std::partition_point(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Pred>(pred)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Sorting functions |
| //------------------------------------------------------------------------------ |
| |
| // c_sort() |
| // |
| // Container-based version of the <algorithm> `std::sort()` function |
| // to sort elements in ascending order of their values. |
| template <typename C> |
| void c_sort(C& c) { |
| std::sort(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_sort() for performing a `comp` comparison other than the |
| // default `operator<`. |
| template <typename C, typename Compare> |
| void c_sort(C& c, Compare&& comp) { |
| std::sort(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_stable_sort() |
| // |
| // Container-based version of the <algorithm> `std::stable_sort()` function |
| // to sort elements in ascending order of their values, preserving the order |
| // of equivalents. |
| template <typename C> |
| void c_stable_sort(C& c) { |
| std::stable_sort(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_stable_sort() for performing a `comp` comparison other than the |
| // default `operator<`. |
| template <typename C, typename Compare> |
| void c_stable_sort(C& c, Compare&& comp) { |
| std::stable_sort(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_is_sorted() |
| // |
| // Container-based version of the <algorithm> `std::is_sorted()` function |
| // to evaluate whether the given container is sorted in ascending order. |
| template <typename C> |
| bool c_is_sorted(const C& c) { |
| return std::is_sorted(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // c_is_sorted() overload for performing a `comp` comparison other than the |
| // default `operator<`. |
| template <typename C, typename Compare> |
| bool c_is_sorted(const C& c, Compare&& comp) { |
| return std::is_sorted(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_partial_sort() |
| // |
| // Container-based version of the <algorithm> `std::partial_sort()` function |
| // to rearrange elements within a container such that elements before `middle` |
| // are sorted in ascending order. |
| template <typename RandomAccessContainer> |
| void c_partial_sort( |
| RandomAccessContainer& sequence, |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> middle) { |
| std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_partial_sort() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename RandomAccessContainer, typename Compare> |
| void c_partial_sort( |
| RandomAccessContainer& sequence, |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> middle, |
| Compare&& comp) { |
| std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_partial_sort_copy() |
| // |
| // Container-based version of the <algorithm> `std::partial_sort_copy()` |
| // function to sort elements within a container such that elements before |
| // `middle` are sorted in ascending order, and return the result within an |
| // iterator. |
| template <typename C, typename RandomAccessContainer> |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> |
| c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { |
| return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| container_algorithm_internal::c_begin(result), |
| container_algorithm_internal::c_end(result)); |
| } |
| |
| // Overload of c_partial_sort_copy() for performing a `comp` comparison other |
| // than the default `operator<`. |
| template <typename C, typename RandomAccessContainer, typename Compare> |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> |
| c_partial_sort_copy(const C& sequence, RandomAccessContainer& result, |
| Compare&& comp) { |
| return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| container_algorithm_internal::c_begin(result), |
| container_algorithm_internal::c_end(result), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_is_sorted_until() |
| // |
| // Container-based version of the <algorithm> `std::is_sorted_until()` function |
| // to return the first element within a container that is not sorted in |
| // ascending order as an iterator. |
| template <typename C> |
| container_algorithm_internal::ContainerIter<C> c_is_sorted_until(C& c) { |
| return std::is_sorted_until(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_is_sorted_until() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename C, typename Compare> |
| container_algorithm_internal::ContainerIter<C> c_is_sorted_until( |
| C& c, Compare&& comp) { |
| return std::is_sorted_until(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_nth_element() |
| // |
| // Container-based version of the <algorithm> `std::nth_element()` function |
| // to rearrange the elements within a container such that the `nth` element |
| // would be in that position in an ordered sequence; other elements may be in |
| // any order, except that all preceding `nth` will be less than that element, |
| // and all following `nth` will be greater than that element. |
| template <typename RandomAccessContainer> |
| void c_nth_element( |
| RandomAccessContainer& sequence, |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> nth) { |
| std::nth_element(container_algorithm_internal::c_begin(sequence), nth, |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_nth_element() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename RandomAccessContainer, typename Compare> |
| void c_nth_element( |
| RandomAccessContainer& sequence, |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> nth, |
| Compare&& comp) { |
| std::nth_element(container_algorithm_internal::c_begin(sequence), nth, |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Binary Search |
| //------------------------------------------------------------------------------ |
| |
| // c_lower_bound() |
| // |
| // Container-based version of the <algorithm> `std::lower_bound()` function |
| // to return an iterator pointing to the first element in a sorted container |
| // which does not compare less than `value`. |
| template <typename Sequence, typename T> |
| container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( |
| Sequence& sequence, T&& value) { |
| return std::lower_bound(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value)); |
| } |
| |
| // Overload of c_lower_bound() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename Sequence, typename T, typename Compare> |
| container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( |
| Sequence& sequence, T&& value, Compare&& comp) { |
| return std::lower_bound(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value), std::forward<Compare>(comp)); |
| } |
| |
| // c_upper_bound() |
| // |
| // Container-based version of the <algorithm> `std::upper_bound()` function |
| // to return an iterator pointing to the first element in a sorted container |
| // which is greater than `value`. |
| template <typename Sequence, typename T> |
| container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( |
| Sequence& sequence, T&& value) { |
| return std::upper_bound(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value)); |
| } |
| |
| // Overload of c_upper_bound() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename Sequence, typename T, typename Compare> |
| container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( |
| Sequence& sequence, T&& value, Compare&& comp) { |
| return std::upper_bound(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value), std::forward<Compare>(comp)); |
| } |
| |
| // c_equal_range() |
| // |
| // Container-based version of the <algorithm> `std::equal_range()` function |
| // to return an iterator pair pointing to the first and last elements in a |
| // sorted container which compare equal to `value`. |
| template <typename Sequence, typename T> |
| container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> |
| c_equal_range(Sequence& sequence, T&& value) { |
| return std::equal_range(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value)); |
| } |
| |
| // Overload of c_equal_range() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename Sequence, typename T, typename Compare> |
| container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> |
| c_equal_range(Sequence& sequence, T&& value, Compare&& comp) { |
| return std::equal_range(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value), std::forward<Compare>(comp)); |
| } |
| |
| // c_binary_search() |
| // |
| // Container-based version of the <algorithm> `std::binary_search()` function |
| // to test if any element in the sorted container contains a value equivalent to |
| // 'value'. |
| template <typename Sequence, typename T> |
| bool c_binary_search(Sequence&& sequence, T&& value) { |
| return std::binary_search(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value)); |
| } |
| |
| // Overload of c_binary_search() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename Sequence, typename T, typename Compare> |
| bool c_binary_search(Sequence&& sequence, T&& value, Compare&& comp) { |
| return std::binary_search(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value), |
| std::forward<Compare>(comp)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Merge functions |
| //------------------------------------------------------------------------------ |
| |
| // c_merge() |
| // |
| // Container-based version of the <algorithm> `std::merge()` function |
| // to merge two sorted containers into a single sorted iterator. |
| template <typename C1, typename C2, typename OutputIterator> |
| OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result) { |
| return std::merge(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), result); |
| } |
| |
| // Overload of c_merge() for performing a `comp` comparison other than |
| // the default `operator<`. |
| template <typename C1, typename C2, typename OutputIterator, typename Compare> |
| OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result, |
| Compare&& comp) { |
| return std::merge(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), result, |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_inplace_merge() |
| // |
| // Container-based version of the <algorithm> `std::inplace_merge()` function |
| // to merge a supplied iterator `middle` into a container. |
| template <typename C> |
| void c_inplace_merge(C& c, |
| container_algorithm_internal::ContainerIter<C> middle) { |
| std::inplace_merge(container_algorithm_internal::c_begin(c), middle, |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_inplace_merge() for performing a merge using a `comp` other |
| // than `operator<`. |
| template <typename C, typename Compare> |
| void c_inplace_merge(C& c, |
| container_algorithm_internal::ContainerIter<C> middle, |
| Compare&& comp) { |
| std::inplace_merge(container_algorithm_internal::c_begin(c), middle, |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_includes() |
| // |
| // Container-based version of the <algorithm> `std::includes()` function |
| // to test whether a sorted container `c1` entirely contains another sorted |
| // container `c2`. |
| template <typename C1, typename C2> |
| bool c_includes(const C1& c1, const C2& c2) { |
| return std::includes(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2)); |
| } |
| |
| // Overload of c_includes() for performing a merge using a `comp` other than |
| // `operator<`. |
| template <typename C1, typename C2, typename Compare> |
| bool c_includes(const C1& c1, const C2& c2, Compare&& comp) { |
| return std::includes(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_set_union() |
| // |
| // Container-based version of the <algorithm> `std::set_union()` function |
| // to return an iterator containing the union of two containers; duplicate |
| // values are not copied into the output. |
| template <typename C1, typename C2, typename OutputIterator, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) { |
| return std::set_union(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output); |
| } |
| |
| // Overload of c_set_union() for performing a merge using a `comp` other than |
| // `operator<`. |
| template <typename C1, typename C2, typename OutputIterator, typename Compare, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, |
| Compare&& comp) { |
| return std::set_union(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output, |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_set_intersection() |
| // |
| // Container-based version of the <algorithm> `std::set_intersection()` function |
| // to return an iterator containing the intersection of two containers. |
| template <typename C1, typename C2, typename OutputIterator, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_intersection(const C1& c1, const C2& c2, |
| OutputIterator output) { |
| return std::set_intersection(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output); |
| } |
| |
| // Overload of c_set_intersection() for performing a merge using a `comp` other |
| // than `operator<`. |
| template <typename C1, typename C2, typename OutputIterator, typename Compare, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_intersection(const C1& c1, const C2& c2, |
| OutputIterator output, Compare&& comp) { |
| return std::set_intersection(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output, |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_set_difference() |
| // |
| // Container-based version of the <algorithm> `std::set_difference()` function |
| // to return an iterator containing elements present in the first container but |
| // not in the second. |
| template <typename C1, typename C2, typename OutputIterator, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_difference(const C1& c1, const C2& c2, |
| OutputIterator output) { |
| return std::set_difference(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output); |
| } |
| |
| // Overload of c_set_difference() for performing a merge using a `comp` other |
| // than `operator<`. |
| template <typename C1, typename C2, typename OutputIterator, typename Compare, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_difference(const C1& c1, const C2& c2, |
| OutputIterator output, Compare&& comp) { |
| return std::set_difference(container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output, |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_set_symmetric_difference() |
| // |
| // Container-based version of the <algorithm> `std::set_symmetric_difference()` |
| // function to return an iterator containing elements present in either one |
| // container or the other, but not both. |
| template <typename C1, typename C2, typename OutputIterator, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, |
| OutputIterator output) { |
| return std::set_symmetric_difference( |
| container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output); |
| } |
| |
| // Overload of c_set_symmetric_difference() for performing a merge using a |
| // `comp` other than `operator<`. |
| template <typename C1, typename C2, typename OutputIterator, typename Compare, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C1>::value, |
| void>::type, |
| typename = typename std::enable_if< |
| !container_algorithm_internal::IsUnorderedContainer<C2>::value, |
| void>::type> |
| OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, |
| OutputIterator output, |
| Compare&& comp) { |
| return std::set_symmetric_difference( |
| container_algorithm_internal::c_begin(c1), |
| container_algorithm_internal::c_end(c1), |
| container_algorithm_internal::c_begin(c2), |
| container_algorithm_internal::c_end(c2), output, |
| std::forward<Compare>(comp)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Heap functions |
| //------------------------------------------------------------------------------ |
| |
| // c_push_heap() |
| // |
| // Container-based version of the <algorithm> `std::push_heap()` function |
| // to push a value onto a container heap. |
| template <typename RandomAccessContainer> |
| void c_push_heap(RandomAccessContainer& sequence) { |
| std::push_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_push_heap() for performing a push operation on a heap using a |
| // `comp` other than `operator<`. |
| template <typename RandomAccessContainer, typename Compare> |
| void c_push_heap(RandomAccessContainer& sequence, Compare&& comp) { |
| std::push_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_pop_heap() |
| // |
| // Container-based version of the <algorithm> `std::pop_heap()` function |
| // to pop a value from a heap container. |
| template <typename RandomAccessContainer> |
| void c_pop_heap(RandomAccessContainer& sequence) { |
| std::pop_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_pop_heap() for performing a pop operation on a heap using a |
| // `comp` other than `operator<`. |
| template <typename RandomAccessContainer, typename Compare> |
| void c_pop_heap(RandomAccessContainer& sequence, Compare&& comp) { |
| std::pop_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_make_heap() |
| // |
| // Container-based version of the <algorithm> `std::make_heap()` function |
| // to make a container a heap. |
| template <typename RandomAccessContainer> |
| void c_make_heap(RandomAccessContainer& sequence) { |
| std::make_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_make_heap() for performing heap comparisons using a |
| // `comp` other than `operator<` |
| template <typename RandomAccessContainer, typename Compare> |
| void c_make_heap(RandomAccessContainer& sequence, Compare&& comp) { |
| std::make_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_sort_heap() |
| // |
| // Container-based version of the <algorithm> `std::sort_heap()` function |
| // to sort a heap into ascending order (after which it is no longer a heap). |
| template <typename RandomAccessContainer> |
| void c_sort_heap(RandomAccessContainer& sequence) { |
| std::sort_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_sort_heap() for performing heap comparisons using a |
| // `comp` other than `operator<` |
| template <typename RandomAccessContainer, typename Compare> |
| void c_sort_heap(RandomAccessContainer& sequence, Compare&& comp) { |
| std::sort_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_is_heap() |
| // |
| // Container-based version of the <algorithm> `std::is_heap()` function |
| // to check whether the given container is a heap. |
| template <typename RandomAccessContainer> |
| bool c_is_heap(const RandomAccessContainer& sequence) { |
| return std::is_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_is_heap() for performing heap comparisons using a |
| // `comp` other than `operator<` |
| template <typename RandomAccessContainer, typename Compare> |
| bool c_is_heap(const RandomAccessContainer& sequence, Compare&& comp) { |
| return std::is_heap(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_is_heap_until() |
| // |
| // Container-based version of the <algorithm> `std::is_heap_until()` function |
| // to find the first element in a given container which is not in heap order. |
| template <typename RandomAccessContainer> |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> |
| c_is_heap_until(RandomAccessContainer& sequence) { |
| return std::is_heap_until(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_is_heap_until() for performing heap comparisons using a |
| // `comp` other than `operator<` |
| template <typename RandomAccessContainer, typename Compare> |
| container_algorithm_internal::ContainerIter<RandomAccessContainer> |
| c_is_heap_until(RandomAccessContainer& sequence, Compare&& comp) { |
| return std::is_heap_until(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Min/max |
| //------------------------------------------------------------------------------ |
| |
| // c_min_element() |
| // |
| // Container-based version of the <algorithm> `std::min_element()` function |
| // to return an iterator pointing to the element with the smallest value, using |
| // `operator<` to make the comparisons. |
| template <typename Sequence> |
| container_algorithm_internal::ContainerIter<Sequence> c_min_element( |
| Sequence& sequence) { |
| return std::min_element(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_min_element() for performing a `comp` comparison other than |
| // `operator<`. |
| template <typename Sequence, typename Compare> |
| container_algorithm_internal::ContainerIter<Sequence> c_min_element( |
| Sequence& sequence, Compare&& comp) { |
| return std::min_element(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_max_element() |
| // |
| // Container-based version of the <algorithm> `std::max_element()` function |
| // to return an iterator pointing to the element with the largest value, using |
| // `operator<` to make the comparisons. |
| template <typename Sequence> |
| container_algorithm_internal::ContainerIter<Sequence> c_max_element( |
| Sequence& sequence) { |
| return std::max_element(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence)); |
| } |
| |
| // Overload of c_max_element() for performing a `comp` comparison other than |
| // `operator<`. |
| template <typename Sequence, typename Compare> |
| container_algorithm_internal::ContainerIter<Sequence> c_max_element( |
| Sequence& sequence, Compare&& comp) { |
| return std::max_element(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_minmax_element() |
| // |
| // Container-based version of the <algorithm> `std::minmax_element()` function |
| // to return a pair of iterators pointing to the elements containing the |
| // smallest and largest values, respectively, using `operator<` to make the |
| // comparisons. |
| template <typename C> |
| container_algorithm_internal::ContainerIterPairType<C, C> |
| c_minmax_element(C& c) { |
| return std::minmax_element(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_minmax_element() for performing `comp` comparisons other than |
| // `operator<`. |
| template <typename C, typename Compare> |
| container_algorithm_internal::ContainerIterPairType<C, C> |
| c_minmax_element(C& c, Compare&& comp) { |
| return std::minmax_element(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <algorithm> Lexicographical Comparisons |
| //------------------------------------------------------------------------------ |
| |
| // c_lexicographical_compare() |
| // |
| // Container-based version of the <algorithm> `std::lexicographical_compare()` |
| // function to lexicographically compare (e.g. sort words alphabetically) two |
| // container sequences. The comparison is performed using `operator<`. Note |
| // that capital letters ("A-Z") have ASCII values less than lowercase letters |
| // ("a-z"). |
| template <typename Sequence1, typename Sequence2> |
| bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2) { |
| return std::lexicographical_compare( |
| container_algorithm_internal::c_begin(sequence1), |
| container_algorithm_internal::c_end(sequence1), |
| container_algorithm_internal::c_begin(sequence2), |
| container_algorithm_internal::c_end(sequence2)); |
| } |
| |
| // Overload of c_lexicographical_compare() for performing a lexicographical |
| // comparison using a `comp` operator instead of `operator<`. |
| template <typename Sequence1, typename Sequence2, typename Compare> |
| bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2, |
| Compare&& comp) { |
| return std::lexicographical_compare( |
| container_algorithm_internal::c_begin(sequence1), |
| container_algorithm_internal::c_end(sequence1), |
| container_algorithm_internal::c_begin(sequence2), |
| container_algorithm_internal::c_end(sequence2), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_next_permutation() |
| // |
| // Container-based version of the <algorithm> `std::next_permutation()` function |
| // to rearrange a container's elements into the next lexicographically greater |
| // permutation. |
| template <typename C> |
| bool c_next_permutation(C& c) { |
| return std::next_permutation(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_next_permutation() for performing a lexicographical |
| // comparison using a `comp` operator instead of `operator<`. |
| template <typename C, typename Compare> |
| bool c_next_permutation(C& c, Compare&& comp) { |
| return std::next_permutation(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| // c_prev_permutation() |
| // |
| // Container-based version of the <algorithm> `std::prev_permutation()` function |
| // to rearrange a container's elements into the next lexicographically lesser |
| // permutation. |
| template <typename C> |
| bool c_prev_permutation(C& c) { |
| return std::prev_permutation(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c)); |
| } |
| |
| // Overload of c_prev_permutation() for performing a lexicographical |
| // comparison using a `comp` operator instead of `operator<`. |
| template <typename C, typename Compare> |
| bool c_prev_permutation(C& c, Compare&& comp) { |
| return std::prev_permutation(container_algorithm_internal::c_begin(c), |
| container_algorithm_internal::c_end(c), |
| std::forward<Compare>(comp)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // <numeric> algorithms |
| //------------------------------------------------------------------------------ |
| |
| // c_iota() |
| // |
| // Container-based version of the <algorithm> `std::iota()` function |
| // to compute successive values of `value`, as if incremented with `++value` |
| // after each element is written. and write them to the container. |
| template <typename Sequence, typename T> |
| void c_iota(Sequence& sequence, T&& value) { |
| std::iota(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(value)); |
| } |
| // c_accumulate() |
| // |
| // Container-based version of the <algorithm> `std::accumulate()` function |
| // to accumulate the element values of a container to `init` and return that |
| // accumulation by value. |
| // |
| // Note: Due to a language technicality this function has return type |
| // absl::decay_t<T>. As a user of this function you can casually read |
| // this as "returns T by value" and assume it does the right thing. |
| template <typename Sequence, typename T> |
| decay_t<T> c_accumulate(const Sequence& sequence, T&& init) { |
| return std::accumulate(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(init)); |
| } |
| |
| // Overload of c_accumulate() for using a binary operations other than |
| // addition for computing the accumulation. |
| template <typename Sequence, typename T, typename BinaryOp> |
| decay_t<T> c_accumulate(const Sequence& sequence, T&& init, |
| BinaryOp&& binary_op) { |
| return std::accumulate(container_algorithm_internal::c_begin(sequence), |
| container_algorithm_internal::c_end(sequence), |
| std::forward<T>(init), |
| std::forward<BinaryOp>(binary_op)); |
| } |
| |
| // c_inner_product() |
| // |
| // Container-based version of the <algorithm> `std::inner_product()` function |
| // to compute the cumulative inner product of container element pairs. |
| // |
| // Note: Due to a language technicality this function has return type |
| // absl::decay_t<T>. As a user of this function you can casually read |
| // this as "returns T by value" and assume it does the right thing. |
| template <typename Sequence1, typename Sequence2, typename T> |
| decay_t<T> c_inner_product(const Sequence1& factors1, const Sequence2& factors2, |
| T&& sum) { |
| return std::inner_product(container_algorithm_internal::c_begin(factors1), |
| container_algorithm_internal::c_end(factors1), |
| container_algorithm_internal::c_begin(factors2), |
| std::forward<T>(sum)); |
| } |
| |
| // Overload of c_inner_product() for using binary operations other than |
| // `operator+` (for computing the accumulation) and `operator*` (for computing |
| // the product between the two container's element pair). |
| template <typename Sequence1, typename Sequence2, typename T, |
| typename BinaryOp1, typename BinaryOp2> |
| decay_t<T> c_inner_product(const Sequence1& factors1, const Sequence2& factors2, |
| T&& sum, BinaryOp1&& op1, BinaryOp2&& op2) { |
| return std::inner_product(container_algorithm_internal::c_begin(factors1), |
| container_algorithm_internal::c_end(factors1), |
| container_algorithm_internal::c_begin(factors2), |
| std::forward<T>(sum), std::forward<BinaryOp1>(op1), |
| std::forward<BinaryOp2>(op2)); |
| } |
| |
| // c_adjacent_difference() |
| // |
| // Container-based version of the <algorithm> `std::adjacent_difference()` |
| // function to compute the difference between each element and the one preceding |
| // it and write it to an iterator. |
| template <typename InputSequence, typename OutputIt> |
| OutputIt c_adjacent_difference(const InputSequence& input, |
| OutputIt output_first) { |
| return std::adjacent_difference(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), |
| output_first); |
| } |
| |
| // Overload of c_adjacent_difference() for using a binary operation other than |
| // subtraction to compute the adjacent difference. |
| template <typename InputSequence, typename OutputIt, typename BinaryOp> |
| OutputIt c_adjacent_difference(const InputSequence& input, |
| OutputIt output_first, BinaryOp&& op) { |
| return std::adjacent_difference(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), |
| output_first, std::forward<BinaryOp>(op)); |
| } |
| |
| // c_partial_sum() |
| // |
| // Container-based version of the <algorithm> `std::partial_sum()` function |
| // to compute the partial sum of the elements in a sequence and write them |
| // to an iterator. The partial sum is the sum of all element values so far in |
| // the sequence. |
| template <typename InputSequence, typename OutputIt> |
| OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first) { |
| return std::partial_sum(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), |
| output_first); |
| } |
| |
| // Overload of c_partial_sum() for using a binary operation other than addition |
| // to compute the "partial sum". |
| template <typename InputSequence, typename OutputIt, typename BinaryOp> |
| OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first, |
| BinaryOp&& op) { |
| return std::partial_sum(container_algorithm_internal::c_begin(input), |
| container_algorithm_internal::c_end(input), |
| output_first, std::forward<BinaryOp>(op)); |
| } |
| |
| } // namespace absl |
| |
| #endif // ABSL_ALGORITHM_CONTAINER_H_ |