blob: 6d5f6630f7185d51de157e9587f35fe2e3e6ccdb [file] [log] [blame]
mistergc2e75482017-09-19 16:54:40 -04001// Copyright 2017 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// -----------------------------------------------------------------------------
16// File: container.h
17// -----------------------------------------------------------------------------
18//
19// This header file provides Container-based versions of algorithmic functions
20// within the C++ standard library. The following standard library sets of
21// functions are covered within this file:
22//
23// * Algorithmic <iterator> functions
24// * Algorithmic <numeric> functions
25// * <algorithm> functions
26//
27// The standard library functions operate on iterator ranges; the functions
28// within this API operate on containers, though many return iterator ranges.
29//
30// All functions within this API are named with a `c_` prefix. Calls such as
31// `absl::c_xx(container, ...) are equivalent to std:: functions such as
32// `std::xx(std::begin(cont), std::end(cont), ...)`. Functions that act on
33// iterators but not conceptually on iterator ranges (e.g. `std::iter_swap`)
34// have no equivalent here.
35//
36// For template parameter and variable naming, `C` indicates the container type
37// to which the function is applied, `Pred` indicates the predicate object type
38// to be used by the function and `T` indicates the applicable element type.
39//
40
41#ifndef ABSL_ALGORITHM_CONTAINER_H_
42#define ABSL_ALGORITHM_CONTAINER_H_
43
44#include <algorithm>
45#include <cassert>
46#include <iterator>
47#include <numeric>
48#include <type_traits>
Abseil Team7b46e1d2018-11-13 13:22:00 -080049#include <unordered_map>
50#include <unordered_set>
mistergc2e75482017-09-19 16:54:40 -040051#include <utility>
52#include <vector>
53
54#include "absl/algorithm/algorithm.h"
55#include "absl/base/macros.h"
56#include "absl/meta/type_traits.h"
57
58namespace absl {
mistergc2e75482017-09-19 16:54:40 -040059namespace container_algorithm_internal {
60
61// NOTE: it is important to defer to ADL lookup for building with C++ modules,
62// especially for headers like <valarray> which are not visible from this file
63// but specialize std::begin and std::end.
64using std::begin;
65using std::end;
66
67// The type of the iterator given by begin(c) (possibly std::begin(c)).
68// ContainerIter<const vector<T>> gives vector<T>::const_iterator,
69// while ContainerIter<vector<T>> gives vector<T>::iterator.
70template <typename C>
71using ContainerIter = decltype(begin(std::declval<C&>()));
72
Abseil Team95ddf852017-11-13 10:04:29 -080073// An MSVC bug involving template parameter substitution requires us to use
74// decltype() here instead of just std::pair.
75template <typename C1, typename C2>
76using ContainerIterPairType =
77 decltype(std::make_pair(ContainerIter<C1>(), ContainerIter<C2>()));
78
mistergc2e75482017-09-19 16:54:40 -040079template <typename C>
80using ContainerDifferenceType =
81 decltype(std::distance(std::declval<ContainerIter<C>>(),
82 std::declval<ContainerIter<C>>()));
83
84template <typename C>
85using ContainerPointerType =
86 typename std::iterator_traits<ContainerIter<C>>::pointer;
87
88// container_algorithm_internal::c_begin and
89// container_algorithm_internal::c_end are abbreviations for proper ADL
90// lookup of std::begin and std::end, i.e.
91// using std::begin;
92// using std::end;
93// std::foo(begin(c), end(c);
94// becomes
95// std::foo(container_algorithm_internal::begin(c),
96// container_algorithm_internal::end(c));
97// These are meant for internal use only.
98
99template <typename C>
100ContainerIter<C> c_begin(C& c) { return begin(c); }
101
102template <typename C>
103ContainerIter<C> c_end(C& c) { return end(c); }
104
Abseil Team7b46e1d2018-11-13 13:22:00 -0800105template <typename T>
106struct IsUnorderedContainer : std::false_type {};
107
108template <class Key, class T, class Hash, class KeyEqual, class Allocator>
109struct IsUnorderedContainer<
110 std::unordered_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {};
111
112template <class Key, class Hash, class KeyEqual, class Allocator>
113struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>>
114 : std::true_type {};
115
mistergc2e75482017-09-19 16:54:40 -0400116} // namespace container_algorithm_internal
117
118// PUBLIC API
119
120//------------------------------------------------------------------------------
121// Abseil algorithm.h functions
122//------------------------------------------------------------------------------
123
124// c_linear_search()
125//
126// Container-based version of absl::linear_search() for performing a linear
127// search within a container.
128template <typename C, typename EqualityComparable>
129bool c_linear_search(const C& c, EqualityComparable&& value) {
130 return linear_search(container_algorithm_internal::c_begin(c),
131 container_algorithm_internal::c_end(c),
132 std::forward<EqualityComparable>(value));
133}
134
135//------------------------------------------------------------------------------
136// <iterator> algorithms
137//------------------------------------------------------------------------------
138
139// c_distance()
140//
141// Container-based version of the <iterator> `std::distance()` function to
142// return the number of elements within a container.
143template <typename C>
144container_algorithm_internal::ContainerDifferenceType<const C> c_distance(
145 const C& c) {
146 return std::distance(container_algorithm_internal::c_begin(c),
147 container_algorithm_internal::c_end(c));
148}
149
150//------------------------------------------------------------------------------
151// <algorithm> Non-modifying sequence operations
152//------------------------------------------------------------------------------
153
154// c_all_of()
155//
156// Container-based version of the <algorithm> `std::all_of()` function to
157// test a condition on all elements within a container.
158template <typename C, typename Pred>
159bool c_all_of(const C& c, Pred&& pred) {
160 return std::all_of(container_algorithm_internal::c_begin(c),
161 container_algorithm_internal::c_end(c),
162 std::forward<Pred>(pred));
163}
164
165// c_any_of()
166//
167// Container-based version of the <algorithm> `std::any_of()` function to
168// test if any element in a container fulfills a condition.
169template <typename C, typename Pred>
170bool c_any_of(const C& c, Pred&& pred) {
171 return std::any_of(container_algorithm_internal::c_begin(c),
172 container_algorithm_internal::c_end(c),
173 std::forward<Pred>(pred));
174}
175
176// c_none_of()
177//
178// Container-based version of the <algorithm> `std::none_of()` function to
179// test if no elements in a container fulfil a condition.
180template <typename C, typename Pred>
181bool c_none_of(const C& c, Pred&& pred) {
182 return std::none_of(container_algorithm_internal::c_begin(c),
183 container_algorithm_internal::c_end(c),
184 std::forward<Pred>(pred));
185}
186
187// c_for_each()
188//
189// Container-based version of the <algorithm> `std::for_each()` function to
190// apply a function to a container's elements.
191template <typename C, typename Function>
192decay_t<Function> c_for_each(C&& c, Function&& f) {
193 return std::for_each(container_algorithm_internal::c_begin(c),
194 container_algorithm_internal::c_end(c),
195 std::forward<Function>(f));
196}
197
198// c_find()
199//
200// Container-based version of the <algorithm> `std::find()` function to find
201// the first element containing the passed value within a container value.
202template <typename C, typename T>
203container_algorithm_internal::ContainerIter<C> c_find(C& c, T&& value) {
204 return std::find(container_algorithm_internal::c_begin(c),
205 container_algorithm_internal::c_end(c),
206 std::forward<T>(value));
207}
208
209// c_find_if()
210//
211// Container-based version of the <algorithm> `std::find_if()` function to find
212// the first element in a container matching the given condition.
213template <typename C, typename Pred>
214container_algorithm_internal::ContainerIter<C> c_find_if(C& c, Pred&& pred) {
215 return std::find_if(container_algorithm_internal::c_begin(c),
216 container_algorithm_internal::c_end(c),
217 std::forward<Pred>(pred));
218}
219
220// c_find_if_not()
221//
222// Container-based version of the <algorithm> `std::find_if_not()` function to
223// find the first element in a container not matching the given condition.
224template <typename C, typename Pred>
225container_algorithm_internal::ContainerIter<C> c_find_if_not(C& c,
226 Pred&& pred) {
227 return std::find_if_not(container_algorithm_internal::c_begin(c),
228 container_algorithm_internal::c_end(c),
229 std::forward<Pred>(pred));
230}
231
232// c_find_end()
233//
234// Container-based version of the <algorithm> `std::find_end()` function to
235// find the last subsequence within a container.
236template <typename Sequence1, typename Sequence2>
237container_algorithm_internal::ContainerIter<Sequence1> c_find_end(
238 Sequence1& sequence, Sequence2& subsequence) {
239 return std::find_end(container_algorithm_internal::c_begin(sequence),
240 container_algorithm_internal::c_end(sequence),
241 container_algorithm_internal::c_begin(subsequence),
242 container_algorithm_internal::c_end(subsequence));
243}
244
245// Overload of c_find_end() for using a predicate evaluation other than `==` as
246// the function's test condition.
247template <typename Sequence1, typename Sequence2, typename BinaryPredicate>
248container_algorithm_internal::ContainerIter<Sequence1> c_find_end(
249 Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) {
250 return std::find_end(container_algorithm_internal::c_begin(sequence),
251 container_algorithm_internal::c_end(sequence),
252 container_algorithm_internal::c_begin(subsequence),
253 container_algorithm_internal::c_end(subsequence),
254 std::forward<BinaryPredicate>(pred));
255}
256
257// c_find_first_of()
258//
259// Container-based version of the <algorithm> `std::find_first_of()` function to
260// find the first elements in an ordered set within a container.
261template <typename C1, typename C2>
262container_algorithm_internal::ContainerIter<C1> c_find_first_of(C1& container,
263 C2& options) {
264 return std::find_first_of(container_algorithm_internal::c_begin(container),
265 container_algorithm_internal::c_end(container),
266 container_algorithm_internal::c_begin(options),
267 container_algorithm_internal::c_end(options));
268}
269
270// Overload of c_find_first_of() for using a predicate evaluation other than
271// `==` as the function's test condition.
272template <typename C1, typename C2, typename BinaryPredicate>
273container_algorithm_internal::ContainerIter<C1> c_find_first_of(
274 C1& container, C2& options, BinaryPredicate&& pred) {
275 return std::find_first_of(container_algorithm_internal::c_begin(container),
276 container_algorithm_internal::c_end(container),
277 container_algorithm_internal::c_begin(options),
278 container_algorithm_internal::c_end(options),
279 std::forward<BinaryPredicate>(pred));
280}
281
282// c_adjacent_find()
283//
284// Container-based version of the <algorithm> `std::adjacent_find()` function to
285// find equal adjacent elements within a container.
286template <typename Sequence>
287container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find(
288 Sequence& sequence) {
289 return std::adjacent_find(container_algorithm_internal::c_begin(sequence),
290 container_algorithm_internal::c_end(sequence));
291}
292
293// Overload of c_adjacent_find() for using a predicate evaluation other than
294// `==` as the function's test condition.
295template <typename Sequence, typename BinaryPredicate>
296container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find(
297 Sequence& sequence, BinaryPredicate&& pred) {
298 return std::adjacent_find(container_algorithm_internal::c_begin(sequence),
299 container_algorithm_internal::c_end(sequence),
300 std::forward<BinaryPredicate>(pred));
301}
302
303// c_count()
304//
305// Container-based version of the <algorithm> `std::count()` function to count
306// values that match within a container.
307template <typename C, typename T>
308container_algorithm_internal::ContainerDifferenceType<const C> c_count(
309 const C& c, T&& value) {
310 return std::count(container_algorithm_internal::c_begin(c),
311 container_algorithm_internal::c_end(c),
312 std::forward<T>(value));
313}
314
315// c_count_if()
316//
317// Container-based version of the <algorithm> `std::count_if()` function to
318// count values matching a condition within a container.
319template <typename C, typename Pred>
320container_algorithm_internal::ContainerDifferenceType<const C> c_count_if(
321 const C& c, Pred&& pred) {
322 return std::count_if(container_algorithm_internal::c_begin(c),
323 container_algorithm_internal::c_end(c),
324 std::forward<Pred>(pred));
325}
326
327// c_mismatch()
328//
Abseil Team42f22a22018-07-18 10:04:24 -0700329// Container-based version of the <algorithm> `std::mismatch()` function to
mistergc2e75482017-09-19 16:54:40 -0400330// return the first element where two ordered containers differ.
331template <typename C1, typename C2>
Abseil Team95ddf852017-11-13 10:04:29 -0800332container_algorithm_internal::ContainerIterPairType<C1, C2>
mistergc2e75482017-09-19 16:54:40 -0400333c_mismatch(C1& c1, C2& c2) {
334 return std::mismatch(container_algorithm_internal::c_begin(c1),
335 container_algorithm_internal::c_end(c1),
336 container_algorithm_internal::c_begin(c2));
337}
338
339// Overload of c_mismatch() for using a predicate evaluation other than `==` as
340// the function's test condition.
341template <typename C1, typename C2, typename BinaryPredicate>
Abseil Team95ddf852017-11-13 10:04:29 -0800342container_algorithm_internal::ContainerIterPairType<C1, C2>
mistergc2e75482017-09-19 16:54:40 -0400343c_mismatch(C1& c1, C2& c2, BinaryPredicate&& pred) {
344 return std::mismatch(container_algorithm_internal::c_begin(c1),
345 container_algorithm_internal::c_end(c1),
346 container_algorithm_internal::c_begin(c2),
347 std::forward<BinaryPredicate>(pred));
348}
349
350// c_equal()
351//
352// Container-based version of the <algorithm> `std::equal()` function to
353// test whether two containers are equal.
354//
355// NOTE: the semantics of c_equal() are slightly different than those of
356// equal(): while the latter iterates over the second container only up to the
357// size of the first container, c_equal() also checks whether the container
358// sizes are equal. This better matches expectations about c_equal() based on
359// its signature.
360//
361// Example:
362// vector v1 = <1, 2, 3>;
363// vector v2 = <1, 2, 3, 4>;
364// equal(std::begin(v1), std::end(v1), std::begin(v2)) returns true
365// c_equal(v1, v2) returns false
366
367template <typename C1, typename C2>
368bool c_equal(const C1& c1, const C2& c2) {
369 return ((c1.size() == c2.size()) &&
370 std::equal(container_algorithm_internal::c_begin(c1),
371 container_algorithm_internal::c_end(c1),
372 container_algorithm_internal::c_begin(c2)));
373}
374
375// Overload of c_equal() for using a predicate evaluation other than `==` as
376// the function's test condition.
377template <typename C1, typename C2, typename BinaryPredicate>
378bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
379 return ((c1.size() == c2.size()) &&
380 std::equal(container_algorithm_internal::c_begin(c1),
381 container_algorithm_internal::c_end(c1),
382 container_algorithm_internal::c_begin(c2),
383 std::forward<BinaryPredicate>(pred)));
384}
385
386// c_is_permutation()
387//
388// Container-based version of the <algorithm> `std::is_permutation()` function
389// to test whether a container is a permutation of another.
390template <typename C1, typename C2>
391bool c_is_permutation(const C1& c1, const C2& c2) {
392 using std::begin;
393 using std::end;
394 return c1.size() == c2.size() &&
395 std::is_permutation(begin(c1), end(c1), begin(c2));
396}
397
398// Overload of c_is_permutation() for using a predicate evaluation other than
399// `==` as the function's test condition.
400template <typename C1, typename C2, typename BinaryPredicate>
401bool c_is_permutation(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
402 using std::begin;
403 using std::end;
404 return c1.size() == c2.size() &&
405 std::is_permutation(begin(c1), end(c1), begin(c2),
406 std::forward<BinaryPredicate>(pred));
407}
408
409// c_search()
410//
411// Container-based version of the <algorithm> `std::search()` function to search
412// a container for a subsequence.
413template <typename Sequence1, typename Sequence2>
414container_algorithm_internal::ContainerIter<Sequence1> c_search(
415 Sequence1& sequence, Sequence2& subsequence) {
416 return std::search(container_algorithm_internal::c_begin(sequence),
417 container_algorithm_internal::c_end(sequence),
418 container_algorithm_internal::c_begin(subsequence),
419 container_algorithm_internal::c_end(subsequence));
420}
421
422// Overload of c_search() for using a predicate evaluation other than
423// `==` as the function's test condition.
424template <typename Sequence1, typename Sequence2, typename BinaryPredicate>
425container_algorithm_internal::ContainerIter<Sequence1> c_search(
426 Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) {
427 return std::search(container_algorithm_internal::c_begin(sequence),
428 container_algorithm_internal::c_end(sequence),
429 container_algorithm_internal::c_begin(subsequence),
430 container_algorithm_internal::c_end(subsequence),
431 std::forward<BinaryPredicate>(pred));
432}
433
434// c_search_n()
435//
436// Container-based version of the <algorithm> `std::search_n()` function to
437// search a container for the first sequence of N elements.
438template <typename Sequence, typename Size, typename T>
439container_algorithm_internal::ContainerIter<Sequence> c_search_n(
440 Sequence& sequence, Size count, T&& value) {
441 return std::search_n(container_algorithm_internal::c_begin(sequence),
442 container_algorithm_internal::c_end(sequence), count,
443 std::forward<T>(value));
444}
445
446// Overload of c_search_n() for using a predicate evaluation other than
447// `==` as the function's test condition.
448template <typename Sequence, typename Size, typename T,
449 typename BinaryPredicate>
450container_algorithm_internal::ContainerIter<Sequence> c_search_n(
451 Sequence& sequence, Size count, T&& value, BinaryPredicate&& pred) {
452 return std::search_n(container_algorithm_internal::c_begin(sequence),
453 container_algorithm_internal::c_end(sequence), count,
454 std::forward<T>(value),
455 std::forward<BinaryPredicate>(pred));
456}
457
458//------------------------------------------------------------------------------
459// <algorithm> Modifying sequence operations
460//------------------------------------------------------------------------------
461
462// c_copy()
463//
464// Container-based version of the <algorithm> `std::copy()` function to copy a
465// container's elements into an iterator.
466template <typename InputSequence, typename OutputIterator>
467OutputIterator c_copy(const InputSequence& input, OutputIterator output) {
468 return std::copy(container_algorithm_internal::c_begin(input),
469 container_algorithm_internal::c_end(input), output);
470}
471
472// c_copy_n()
473//
474// Container-based version of the <algorithm> `std::copy_n()` function to copy a
475// container's first N elements into an iterator.
476template <typename C, typename Size, typename OutputIterator>
477OutputIterator c_copy_n(const C& input, Size n, OutputIterator output) {
478 return std::copy_n(container_algorithm_internal::c_begin(input), n, output);
479}
480
481// c_copy_if()
482//
483// Container-based version of the <algorithm> `std::copy_if()` function to copy
484// a container's elements satisfying some condition into an iterator.
485template <typename InputSequence, typename OutputIterator, typename Pred>
486OutputIterator c_copy_if(const InputSequence& input, OutputIterator output,
487 Pred&& pred) {
488 return std::copy_if(container_algorithm_internal::c_begin(input),
489 container_algorithm_internal::c_end(input), output,
490 std::forward<Pred>(pred));
491}
492
493// c_copy_backward()
494//
495// Container-based version of the <algorithm> `std::copy_backward()` function to
496// copy a container's elements in reverse order into an iterator.
497template <typename C, typename BidirectionalIterator>
498BidirectionalIterator c_copy_backward(const C& src,
499 BidirectionalIterator dest) {
500 return std::copy_backward(container_algorithm_internal::c_begin(src),
501 container_algorithm_internal::c_end(src), dest);
502}
503
504// c_move()
505//
506// Container-based version of the <algorithm> `std::move()` function to move
507// a container's elements into an iterator.
508template <typename C, typename OutputIterator>
Abseil Team02451912018-09-11 11:22:56 -0700509OutputIterator c_move(C&& src, OutputIterator dest) {
mistergc2e75482017-09-19 16:54:40 -0400510 return std::move(container_algorithm_internal::c_begin(src),
511 container_algorithm_internal::c_end(src), dest);
512}
513
mistergc2e75482017-09-19 16:54:40 -0400514// c_swap_ranges()
515//
516// Container-based version of the <algorithm> `std::swap_ranges()` function to
517// swap a container's elements with another container's elements.
518template <typename C1, typename C2>
519container_algorithm_internal::ContainerIter<C2> c_swap_ranges(C1& c1, C2& c2) {
520 return std::swap_ranges(container_algorithm_internal::c_begin(c1),
521 container_algorithm_internal::c_end(c1),
522 container_algorithm_internal::c_begin(c2));
523}
524
525// c_transform()
526//
527// Container-based version of the <algorithm> `std::transform()` function to
528// transform a container's elements using the unary operation, storing the
529// result in an iterator pointing to the last transformed element in the output
530// range.
531template <typename InputSequence, typename OutputIterator, typename UnaryOp>
532OutputIterator c_transform(const InputSequence& input, OutputIterator output,
533 UnaryOp&& unary_op) {
534 return std::transform(container_algorithm_internal::c_begin(input),
535 container_algorithm_internal::c_end(input), output,
536 std::forward<UnaryOp>(unary_op));
537}
538
539// Overload of c_transform() for performing a transformation using a binary
540// predicate.
541template <typename InputSequence1, typename InputSequence2,
542 typename OutputIterator, typename BinaryOp>
543OutputIterator c_transform(const InputSequence1& input1,
544 const InputSequence2& input2, OutputIterator output,
545 BinaryOp&& binary_op) {
546 return std::transform(container_algorithm_internal::c_begin(input1),
547 container_algorithm_internal::c_end(input1),
548 container_algorithm_internal::c_begin(input2), output,
549 std::forward<BinaryOp>(binary_op));
550}
551
552// c_replace()
553//
554// Container-based version of the <algorithm> `std::replace()` function to
555// replace a container's elements of some value with a new value. The container
556// is modified in place.
557template <typename Sequence, typename T>
558void c_replace(Sequence& sequence, const T& old_value, const T& new_value) {
559 std::replace(container_algorithm_internal::c_begin(sequence),
560 container_algorithm_internal::c_end(sequence), old_value,
561 new_value);
562}
563
564// c_replace_if()
565//
566// Container-based version of the <algorithm> `std::replace_if()` function to
567// replace a container's elements of some value with a new value based on some
568// condition. The container is modified in place.
569template <typename C, typename Pred, typename T>
570void c_replace_if(C& c, Pred&& pred, T&& new_value) {
571 std::replace_if(container_algorithm_internal::c_begin(c),
572 container_algorithm_internal::c_end(c),
573 std::forward<Pred>(pred), std::forward<T>(new_value));
574}
575
576// c_replace_copy()
577//
578// Container-based version of the <algorithm> `std::replace_copy()` function to
579// replace a container's elements of some value with a new value and return the
580// results within an iterator.
581template <typename C, typename OutputIterator, typename T>
582OutputIterator c_replace_copy(const C& c, OutputIterator result, T&& old_value,
583 T&& new_value) {
584 return std::replace_copy(container_algorithm_internal::c_begin(c),
585 container_algorithm_internal::c_end(c), result,
586 std::forward<T>(old_value),
587 std::forward<T>(new_value));
588}
589
590// c_replace_copy_if()
591//
592// Container-based version of the <algorithm> `std::replace_copy_if()` function
593// to replace a container's elements of some value with a new value based on
594// some condition, and return the results within an iterator.
595template <typename C, typename OutputIterator, typename Pred, typename T>
596OutputIterator c_replace_copy_if(const C& c, OutputIterator result, Pred&& pred,
597 T&& new_value) {
598 return std::replace_copy_if(container_algorithm_internal::c_begin(c),
599 container_algorithm_internal::c_end(c), result,
600 std::forward<Pred>(pred),
601 std::forward<T>(new_value));
602}
603
604// c_fill()
605//
606// Container-based version of the <algorithm> `std::fill()` function to fill a
607// container with some value.
608template <typename C, typename T>
609void c_fill(C& c, T&& value) {
610 std::fill(container_algorithm_internal::c_begin(c),
611 container_algorithm_internal::c_end(c), std::forward<T>(value));
612}
613
614// c_fill_n()
615//
616// Container-based version of the <algorithm> `std::fill_n()` function to fill
617// the first N elements in a container with some value.
618template <typename C, typename Size, typename T>
619void c_fill_n(C& c, Size n, T&& value) {
620 std::fill_n(container_algorithm_internal::c_begin(c), n,
621 std::forward<T>(value));
622}
623
624// c_generate()
625//
626// Container-based version of the <algorithm> `std::generate()` function to
627// assign a container's elements to the values provided by the given generator.
628template <typename C, typename Generator>
629void c_generate(C& c, Generator&& gen) {
630 std::generate(container_algorithm_internal::c_begin(c),
631 container_algorithm_internal::c_end(c),
632 std::forward<Generator>(gen));
633}
634
635// c_generate_n()
636//
637// Container-based version of the <algorithm> `std::generate_n()` function to
638// assign a container's first N elements to the values provided by the given
639// generator.
640template <typename C, typename Size, typename Generator>
641container_algorithm_internal::ContainerIter<C> c_generate_n(C& c, Size n,
642 Generator&& gen) {
643 return std::generate_n(container_algorithm_internal::c_begin(c), n,
644 std::forward<Generator>(gen));
645}
646
647// Note: `c_xx()` <algorithm> container versions for `remove()`, `remove_if()`,
648// and `unique()` are omitted, because it's not clear whether or not such
Abseil Team87a4c072018-06-25 09:18:19 -0700649// functions should call erase on their supplied sequences afterwards. Either
mistergc2e75482017-09-19 16:54:40 -0400650// behavior would be surprising for a different set of users.
651//
652
653// c_remove_copy()
654//
655// Container-based version of the <algorithm> `std::remove_copy()` function to
656// copy a container's elements while removing any elements matching the given
657// `value`.
658template <typename C, typename OutputIterator, typename T>
659OutputIterator c_remove_copy(const C& c, OutputIterator result, T&& value) {
660 return std::remove_copy(container_algorithm_internal::c_begin(c),
661 container_algorithm_internal::c_end(c), result,
662 std::forward<T>(value));
663}
664
665// c_remove_copy_if()
666//
667// Container-based version of the <algorithm> `std::remove_copy_if()` function
668// to copy a container's elements while removing any elements matching the given
669// condition.
670template <typename C, typename OutputIterator, typename Pred>
671OutputIterator c_remove_copy_if(const C& c, OutputIterator result,
672 Pred&& pred) {
673 return std::remove_copy_if(container_algorithm_internal::c_begin(c),
674 container_algorithm_internal::c_end(c), result,
675 std::forward<Pred>(pred));
676}
677
678// c_unique_copy()
679//
680// Container-based version of the <algorithm> `std::unique_copy()` function to
681// copy a container's elements while removing any elements containing duplicate
682// values.
683template <typename C, typename OutputIterator>
684OutputIterator c_unique_copy(const C& c, OutputIterator result) {
685 return std::unique_copy(container_algorithm_internal::c_begin(c),
686 container_algorithm_internal::c_end(c), result);
687}
688
689// Overload of c_unique_copy() for using a predicate evaluation other than
690// `==` for comparing uniqueness of the element values.
691template <typename C, typename OutputIterator, typename BinaryPredicate>
692OutputIterator c_unique_copy(const C& c, OutputIterator result,
693 BinaryPredicate&& pred) {
694 return std::unique_copy(container_algorithm_internal::c_begin(c),
695 container_algorithm_internal::c_end(c), result,
696 std::forward<BinaryPredicate>(pred));
697}
698
699// c_reverse()
700//
701// Container-based version of the <algorithm> `std::reverse()` function to
702// reverse a container's elements.
703template <typename Sequence>
704void c_reverse(Sequence& sequence) {
705 std::reverse(container_algorithm_internal::c_begin(sequence),
706 container_algorithm_internal::c_end(sequence));
707}
708
709// c_reverse_copy()
710//
711// Container-based version of the <algorithm> `std::reverse()` function to
712// reverse a container's elements and write them to an iterator range.
713template <typename C, typename OutputIterator>
714OutputIterator c_reverse_copy(const C& sequence, OutputIterator result) {
715 return std::reverse_copy(container_algorithm_internal::c_begin(sequence),
716 container_algorithm_internal::c_end(sequence),
717 result);
718}
719
720// c_rotate()
721//
722// Container-based version of the <algorithm> `std::rotate()` function to
723// shift a container's elements leftward such that the `middle` element becomes
724// the first element in the container.
725template <typename C,
726 typename Iterator = container_algorithm_internal::ContainerIter<C>>
727Iterator c_rotate(C& sequence, Iterator middle) {
728 return absl::rotate(container_algorithm_internal::c_begin(sequence), middle,
729 container_algorithm_internal::c_end(sequence));
730}
731
732// c_rotate_copy()
733//
734// Container-based version of the <algorithm> `std::rotate_copy()` function to
735// shift a container's elements leftward such that the `middle` element becomes
736// the first element in a new iterator range.
737template <typename C, typename OutputIterator>
738OutputIterator c_rotate_copy(
739 const C& sequence,
740 container_algorithm_internal::ContainerIter<const C> middle,
741 OutputIterator result) {
742 return std::rotate_copy(container_algorithm_internal::c_begin(sequence),
743 middle, container_algorithm_internal::c_end(sequence),
744 result);
745}
746
747// c_shuffle()
748//
749// Container-based version of the <algorithm> `std::shuffle()` function to
750// randomly shuffle elements within the container using a `gen()` uniform random
751// number generator.
752template <typename RandomAccessContainer, typename UniformRandomBitGenerator>
753void c_shuffle(RandomAccessContainer& c, UniformRandomBitGenerator&& gen) {
754 std::shuffle(container_algorithm_internal::c_begin(c),
755 container_algorithm_internal::c_end(c),
756 std::forward<UniformRandomBitGenerator>(gen));
757}
758
759//------------------------------------------------------------------------------
760// <algorithm> Partition functions
761//------------------------------------------------------------------------------
762
763// c_is_partitioned()
764//
765// Container-based version of the <algorithm> `std::is_partitioned()` function
766// to test whether all elements in the container for which `pred` returns `true`
767// precede those for which `pred` is `false`.
768template <typename C, typename Pred>
769bool c_is_partitioned(const C& c, Pred&& pred) {
770 return std::is_partitioned(container_algorithm_internal::c_begin(c),
771 container_algorithm_internal::c_end(c),
772 std::forward<Pred>(pred));
773}
774
775// c_partition()
776//
777// Container-based version of the <algorithm> `std::partition()` function
778// to rearrange all elements in a container in such a way that all elements for
779// which `pred` returns `true` precede all those for which it returns `false`,
780// returning an iterator to the first element of the second group.
781template <typename C, typename Pred>
782container_algorithm_internal::ContainerIter<C> c_partition(C& c, Pred&& pred) {
783 return std::partition(container_algorithm_internal::c_begin(c),
784 container_algorithm_internal::c_end(c),
785 std::forward<Pred>(pred));
786}
787
788// c_stable_partition()
789//
790// Container-based version of the <algorithm> `std::stable_partition()` function
791// to rearrange all elements in a container in such a way that all elements for
792// which `pred` returns `true` precede all those for which it returns `false`,
793// preserving the relative ordering between the two groups. The function returns
794// an iterator to the first element of the second group.
795template <typename C, typename Pred>
796container_algorithm_internal::ContainerIter<C> c_stable_partition(C& c,
797 Pred&& pred) {
798 return std::stable_partition(container_algorithm_internal::c_begin(c),
799 container_algorithm_internal::c_end(c),
800 std::forward<Pred>(pred));
801}
802
803// c_partition_copy()
804//
805// Container-based version of the <algorithm> `std::partition_copy()` function
806// to partition a container's elements and return them into two iterators: one
807// for which `pred` returns `true`, and one for which `pred` returns `false.`
808
809template <typename C, typename OutputIterator1, typename OutputIterator2,
810 typename Pred>
811std::pair<OutputIterator1, OutputIterator2> c_partition_copy(
812 const C& c, OutputIterator1 out_true, OutputIterator2 out_false,
813 Pred&& pred) {
814 return std::partition_copy(container_algorithm_internal::c_begin(c),
815 container_algorithm_internal::c_end(c), out_true,
816 out_false, std::forward<Pred>(pred));
817}
818
819// c_partition_point()
820//
821// Container-based version of the <algorithm> `std::partition_point()` function
822// to return the first element of an already partitioned container for which
823// the given `pred` is not `true`.
824template <typename C, typename Pred>
825container_algorithm_internal::ContainerIter<C> c_partition_point(C& c,
826 Pred&& pred) {
827 return std::partition_point(container_algorithm_internal::c_begin(c),
828 container_algorithm_internal::c_end(c),
829 std::forward<Pred>(pred));
830}
831
832//------------------------------------------------------------------------------
833// <algorithm> Sorting functions
834//------------------------------------------------------------------------------
835
836// c_sort()
837//
838// Container-based version of the <algorithm> `std::sort()` function
839// to sort elements in ascending order of their values.
840template <typename C>
841void c_sort(C& c) {
842 std::sort(container_algorithm_internal::c_begin(c),
843 container_algorithm_internal::c_end(c));
844}
845
846// Overload of c_sort() for performing a `comp` comparison other than the
847// default `operator<`.
848template <typename C, typename Compare>
849void c_sort(C& c, Compare&& comp) {
850 std::sort(container_algorithm_internal::c_begin(c),
851 container_algorithm_internal::c_end(c),
852 std::forward<Compare>(comp));
853}
854
855// c_stable_sort()
856//
857// Container-based version of the <algorithm> `std::stable_sort()` function
858// to sort elements in ascending order of their values, preserving the order
859// of equivalents.
860template <typename C>
861void c_stable_sort(C& c) {
862 std::stable_sort(container_algorithm_internal::c_begin(c),
863 container_algorithm_internal::c_end(c));
864}
865
866// Overload of c_stable_sort() for performing a `comp` comparison other than the
867// default `operator<`.
868template <typename C, typename Compare>
869void c_stable_sort(C& c, Compare&& comp) {
870 std::stable_sort(container_algorithm_internal::c_begin(c),
871 container_algorithm_internal::c_end(c),
872 std::forward<Compare>(comp));
873}
874
875// c_is_sorted()
876//
877// Container-based version of the <algorithm> `std::is_sorted()` function
Abseil Team95ddf852017-11-13 10:04:29 -0800878// to evaluate whether the given container is sorted in ascending order.
mistergc2e75482017-09-19 16:54:40 -0400879template <typename C>
880bool c_is_sorted(const C& c) {
881 return std::is_sorted(container_algorithm_internal::c_begin(c),
882 container_algorithm_internal::c_end(c));
883}
884
885// c_is_sorted() overload for performing a `comp` comparison other than the
886// default `operator<`.
887template <typename C, typename Compare>
888bool c_is_sorted(const C& c, Compare&& comp) {
889 return std::is_sorted(container_algorithm_internal::c_begin(c),
890 container_algorithm_internal::c_end(c),
891 std::forward<Compare>(comp));
892}
893
894// c_partial_sort()
895//
896// Container-based version of the <algorithm> `std::partial_sort()` function
897// to rearrange elements within a container such that elements before `middle`
898// are sorted in ascending order.
899template <typename RandomAccessContainer>
900void c_partial_sort(
901 RandomAccessContainer& sequence,
902 container_algorithm_internal::ContainerIter<RandomAccessContainer> middle) {
903 std::partial_sort(container_algorithm_internal::c_begin(sequence), middle,
904 container_algorithm_internal::c_end(sequence));
905}
906
907// Overload of c_partial_sort() for performing a `comp` comparison other than
908// the default `operator<`.
909template <typename RandomAccessContainer, typename Compare>
910void c_partial_sort(
911 RandomAccessContainer& sequence,
912 container_algorithm_internal::ContainerIter<RandomAccessContainer> middle,
913 Compare&& comp) {
914 std::partial_sort(container_algorithm_internal::c_begin(sequence), middle,
915 container_algorithm_internal::c_end(sequence),
916 std::forward<Compare>(comp));
917}
918
919// c_partial_sort_copy()
920//
921// Container-based version of the <algorithm> `std::partial_sort_copy()`
922// function to sort elements within a container such that elements before
923// `middle` are sorted in ascending order, and return the result within an
924// iterator.
925template <typename C, typename RandomAccessContainer>
926container_algorithm_internal::ContainerIter<RandomAccessContainer>
927c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) {
928 return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence),
929 container_algorithm_internal::c_end(sequence),
930 container_algorithm_internal::c_begin(result),
931 container_algorithm_internal::c_end(result));
932}
933
934// Overload of c_partial_sort_copy() for performing a `comp` comparison other
935// than the default `operator<`.
936template <typename C, typename RandomAccessContainer, typename Compare>
937container_algorithm_internal::ContainerIter<RandomAccessContainer>
938c_partial_sort_copy(const C& sequence, RandomAccessContainer& result,
939 Compare&& comp) {
940 return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence),
941 container_algorithm_internal::c_end(sequence),
942 container_algorithm_internal::c_begin(result),
943 container_algorithm_internal::c_end(result),
944 std::forward<Compare>(comp));
945}
946
947// c_is_sorted_until()
948//
949// Container-based version of the <algorithm> `std::is_sorted_until()` function
950// to return the first element within a container that is not sorted in
951// ascending order as an iterator.
952template <typename C>
953container_algorithm_internal::ContainerIter<C> c_is_sorted_until(C& c) {
954 return std::is_sorted_until(container_algorithm_internal::c_begin(c),
955 container_algorithm_internal::c_end(c));
956}
957
958// Overload of c_is_sorted_until() for performing a `comp` comparison other than
959// the default `operator<`.
960template <typename C, typename Compare>
961container_algorithm_internal::ContainerIter<C> c_is_sorted_until(
962 C& c, Compare&& comp) {
963 return std::is_sorted_until(container_algorithm_internal::c_begin(c),
964 container_algorithm_internal::c_end(c),
965 std::forward<Compare>(comp));
966}
967
968// c_nth_element()
969//
970// Container-based version of the <algorithm> `std::nth_element()` function
971// to rearrange the elements within a container such that the `nth` element
972// would be in that position in an ordered sequence; other elements may be in
973// any order, except that all preceding `nth` will be less than that element,
974// and all following `nth` will be greater than that element.
975template <typename RandomAccessContainer>
976void c_nth_element(
977 RandomAccessContainer& sequence,
978 container_algorithm_internal::ContainerIter<RandomAccessContainer> nth) {
979 std::nth_element(container_algorithm_internal::c_begin(sequence), nth,
980 container_algorithm_internal::c_end(sequence));
981}
982
983// Overload of c_nth_element() for performing a `comp` comparison other than
984// the default `operator<`.
985template <typename RandomAccessContainer, typename Compare>
986void c_nth_element(
987 RandomAccessContainer& sequence,
988 container_algorithm_internal::ContainerIter<RandomAccessContainer> nth,
989 Compare&& comp) {
990 std::nth_element(container_algorithm_internal::c_begin(sequence), nth,
991 container_algorithm_internal::c_end(sequence),
992 std::forward<Compare>(comp));
993}
994
995//------------------------------------------------------------------------------
996// <algorithm> Binary Search
997//------------------------------------------------------------------------------
998
999// c_lower_bound()
1000//
1001// Container-based version of the <algorithm> `std::lower_bound()` function
1002// to return an iterator pointing to the first element in a sorted container
1003// which does not compare less than `value`.
1004template <typename Sequence, typename T>
1005container_algorithm_internal::ContainerIter<Sequence> c_lower_bound(
1006 Sequence& sequence, T&& value) {
1007 return std::lower_bound(container_algorithm_internal::c_begin(sequence),
1008 container_algorithm_internal::c_end(sequence),
1009 std::forward<T>(value));
1010}
1011
1012// Overload of c_lower_bound() for performing a `comp` comparison other than
1013// the default `operator<`.
1014template <typename Sequence, typename T, typename Compare>
1015container_algorithm_internal::ContainerIter<Sequence> c_lower_bound(
1016 Sequence& sequence, T&& value, Compare&& comp) {
1017 return std::lower_bound(container_algorithm_internal::c_begin(sequence),
1018 container_algorithm_internal::c_end(sequence),
1019 std::forward<T>(value), std::forward<Compare>(comp));
1020}
1021
1022// c_upper_bound()
1023//
1024// Container-based version of the <algorithm> `std::upper_bound()` function
1025// to return an iterator pointing to the first element in a sorted container
1026// which is greater than `value`.
1027template <typename Sequence, typename T>
1028container_algorithm_internal::ContainerIter<Sequence> c_upper_bound(
1029 Sequence& sequence, T&& value) {
1030 return std::upper_bound(container_algorithm_internal::c_begin(sequence),
1031 container_algorithm_internal::c_end(sequence),
1032 std::forward<T>(value));
1033}
1034
1035// Overload of c_upper_bound() for performing a `comp` comparison other than
1036// the default `operator<`.
1037template <typename Sequence, typename T, typename Compare>
1038container_algorithm_internal::ContainerIter<Sequence> c_upper_bound(
1039 Sequence& sequence, T&& value, Compare&& comp) {
1040 return std::upper_bound(container_algorithm_internal::c_begin(sequence),
1041 container_algorithm_internal::c_end(sequence),
1042 std::forward<T>(value), std::forward<Compare>(comp));
1043}
1044
1045// c_equal_range()
1046//
1047// Container-based version of the <algorithm> `std::equal_range()` function
1048// to return an iterator pair pointing to the first and last elements in a
1049// sorted container which compare equal to `value`.
1050template <typename Sequence, typename T>
Abseil Team95ddf852017-11-13 10:04:29 -08001051container_algorithm_internal::ContainerIterPairType<Sequence, Sequence>
mistergc2e75482017-09-19 16:54:40 -04001052c_equal_range(Sequence& sequence, T&& value) {
1053 return std::equal_range(container_algorithm_internal::c_begin(sequence),
1054 container_algorithm_internal::c_end(sequence),
1055 std::forward<T>(value));
1056}
1057
1058// Overload of c_equal_range() for performing a `comp` comparison other than
1059// the default `operator<`.
1060template <typename Sequence, typename T, typename Compare>
Abseil Team95ddf852017-11-13 10:04:29 -08001061container_algorithm_internal::ContainerIterPairType<Sequence, Sequence>
mistergc2e75482017-09-19 16:54:40 -04001062c_equal_range(Sequence& sequence, T&& value, Compare&& comp) {
1063 return std::equal_range(container_algorithm_internal::c_begin(sequence),
1064 container_algorithm_internal::c_end(sequence),
1065 std::forward<T>(value), std::forward<Compare>(comp));
1066}
1067
1068// c_binary_search()
1069//
1070// Container-based version of the <algorithm> `std::binary_search()` function
1071// to test if any element in the sorted container contains a value equivalent to
1072// 'value'.
1073template <typename Sequence, typename T>
1074bool c_binary_search(Sequence&& sequence, T&& value) {
1075 return std::binary_search(container_algorithm_internal::c_begin(sequence),
1076 container_algorithm_internal::c_end(sequence),
1077 std::forward<T>(value));
1078}
1079
1080// Overload of c_binary_search() for performing a `comp` comparison other than
1081// the default `operator<`.
1082template <typename Sequence, typename T, typename Compare>
1083bool c_binary_search(Sequence&& sequence, T&& value, Compare&& comp) {
1084 return std::binary_search(container_algorithm_internal::c_begin(sequence),
1085 container_algorithm_internal::c_end(sequence),
1086 std::forward<T>(value),
1087 std::forward<Compare>(comp));
1088}
1089
1090//------------------------------------------------------------------------------
1091// <algorithm> Merge functions
1092//------------------------------------------------------------------------------
1093
1094// c_merge()
1095//
1096// Container-based version of the <algorithm> `std::merge()` function
1097// to merge two sorted containers into a single sorted iterator.
1098template <typename C1, typename C2, typename OutputIterator>
1099OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result) {
1100 return std::merge(container_algorithm_internal::c_begin(c1),
1101 container_algorithm_internal::c_end(c1),
1102 container_algorithm_internal::c_begin(c2),
1103 container_algorithm_internal::c_end(c2), result);
1104}
1105
1106// Overload of c_merge() for performing a `comp` comparison other than
1107// the default `operator<`.
1108template <typename C1, typename C2, typename OutputIterator, typename Compare>
1109OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result,
1110 Compare&& comp) {
1111 return std::merge(container_algorithm_internal::c_begin(c1),
1112 container_algorithm_internal::c_end(c1),
1113 container_algorithm_internal::c_begin(c2),
1114 container_algorithm_internal::c_end(c2), result,
1115 std::forward<Compare>(comp));
1116}
1117
1118// c_inplace_merge()
1119//
1120// Container-based version of the <algorithm> `std::inplace_merge()` function
1121// to merge a supplied iterator `middle` into a container.
1122template <typename C>
1123void c_inplace_merge(C& c,
1124 container_algorithm_internal::ContainerIter<C> middle) {
1125 std::inplace_merge(container_algorithm_internal::c_begin(c), middle,
1126 container_algorithm_internal::c_end(c));
1127}
1128
1129// Overload of c_inplace_merge() for performing a merge using a `comp` other
1130// than `operator<`.
1131template <typename C, typename Compare>
1132void c_inplace_merge(C& c,
1133 container_algorithm_internal::ContainerIter<C> middle,
1134 Compare&& comp) {
1135 std::inplace_merge(container_algorithm_internal::c_begin(c), middle,
1136 container_algorithm_internal::c_end(c),
1137 std::forward<Compare>(comp));
1138}
1139
1140// c_includes()
1141//
1142// Container-based version of the <algorithm> `std::includes()` function
1143// to test whether a sorted container `c1` entirely contains another sorted
1144// container `c2`.
1145template <typename C1, typename C2>
1146bool c_includes(const C1& c1, const C2& c2) {
1147 return std::includes(container_algorithm_internal::c_begin(c1),
1148 container_algorithm_internal::c_end(c1),
1149 container_algorithm_internal::c_begin(c2),
1150 container_algorithm_internal::c_end(c2));
1151}
1152
1153// Overload of c_includes() for performing a merge using a `comp` other than
1154// `operator<`.
1155template <typename C1, typename C2, typename Compare>
1156bool c_includes(const C1& c1, const C2& c2, Compare&& comp) {
1157 return std::includes(container_algorithm_internal::c_begin(c1),
1158 container_algorithm_internal::c_end(c1),
1159 container_algorithm_internal::c_begin(c2),
1160 container_algorithm_internal::c_end(c2),
1161 std::forward<Compare>(comp));
1162}
1163
1164// c_set_union()
1165//
1166// Container-based version of the <algorithm> `std::set_union()` function
1167// to return an iterator containing the union of two containers; duplicate
1168// values are not copied into the output.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001169template <typename C1, typename C2, typename OutputIterator,
1170 typename = typename std::enable_if<
1171 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1172 void>::type,
1173 typename = typename std::enable_if<
1174 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1175 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001176OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) {
1177 return std::set_union(container_algorithm_internal::c_begin(c1),
1178 container_algorithm_internal::c_end(c1),
1179 container_algorithm_internal::c_begin(c2),
1180 container_algorithm_internal::c_end(c2), output);
1181}
1182
1183// Overload of c_set_union() for performing a merge using a `comp` other than
1184// `operator<`.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001185template <typename C1, typename C2, typename OutputIterator, typename Compare,
1186 typename = typename std::enable_if<
1187 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1188 void>::type,
1189 typename = typename std::enable_if<
1190 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1191 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001192OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output,
1193 Compare&& comp) {
1194 return std::set_union(container_algorithm_internal::c_begin(c1),
1195 container_algorithm_internal::c_end(c1),
1196 container_algorithm_internal::c_begin(c2),
1197 container_algorithm_internal::c_end(c2), output,
1198 std::forward<Compare>(comp));
1199}
1200
1201// c_set_intersection()
1202//
1203// Container-based version of the <algorithm> `std::set_intersection()` function
1204// to return an iterator containing the intersection of two containers.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001205template <typename C1, typename C2, typename OutputIterator,
1206 typename = typename std::enable_if<
1207 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1208 void>::type,
1209 typename = typename std::enable_if<
1210 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1211 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001212OutputIterator c_set_intersection(const C1& c1, const C2& c2,
1213 OutputIterator output) {
1214 return std::set_intersection(container_algorithm_internal::c_begin(c1),
1215 container_algorithm_internal::c_end(c1),
1216 container_algorithm_internal::c_begin(c2),
1217 container_algorithm_internal::c_end(c2), output);
1218}
1219
1220// Overload of c_set_intersection() for performing a merge using a `comp` other
1221// than `operator<`.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001222template <typename C1, typename C2, typename OutputIterator, typename Compare,
1223 typename = typename std::enable_if<
1224 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1225 void>::type,
1226 typename = typename std::enable_if<
1227 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1228 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001229OutputIterator c_set_intersection(const C1& c1, const C2& c2,
1230 OutputIterator output, Compare&& comp) {
1231 return std::set_intersection(container_algorithm_internal::c_begin(c1),
1232 container_algorithm_internal::c_end(c1),
1233 container_algorithm_internal::c_begin(c2),
1234 container_algorithm_internal::c_end(c2), output,
1235 std::forward<Compare>(comp));
1236}
1237
1238// c_set_difference()
1239//
1240// Container-based version of the <algorithm> `std::set_difference()` function
1241// to return an iterator containing elements present in the first container but
1242// not in the second.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001243template <typename C1, typename C2, typename OutputIterator,
1244 typename = typename std::enable_if<
1245 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1246 void>::type,
1247 typename = typename std::enable_if<
1248 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1249 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001250OutputIterator c_set_difference(const C1& c1, const C2& c2,
1251 OutputIterator output) {
1252 return std::set_difference(container_algorithm_internal::c_begin(c1),
1253 container_algorithm_internal::c_end(c1),
1254 container_algorithm_internal::c_begin(c2),
1255 container_algorithm_internal::c_end(c2), output);
1256}
1257
1258// Overload of c_set_difference() for performing a merge using a `comp` other
1259// than `operator<`.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001260template <typename C1, typename C2, typename OutputIterator, typename Compare,
1261 typename = typename std::enable_if<
1262 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1263 void>::type,
1264 typename = typename std::enable_if<
1265 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1266 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001267OutputIterator c_set_difference(const C1& c1, const C2& c2,
1268 OutputIterator output, Compare&& comp) {
1269 return std::set_difference(container_algorithm_internal::c_begin(c1),
1270 container_algorithm_internal::c_end(c1),
1271 container_algorithm_internal::c_begin(c2),
1272 container_algorithm_internal::c_end(c2), output,
1273 std::forward<Compare>(comp));
1274}
1275
1276// c_set_symmetric_difference()
1277//
1278// Container-based version of the <algorithm> `std::set_symmetric_difference()`
1279// function to return an iterator containing elements present in either one
1280// container or the other, but not both.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001281template <typename C1, typename C2, typename OutputIterator,
1282 typename = typename std::enable_if<
1283 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1284 void>::type,
1285 typename = typename std::enable_if<
1286 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1287 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001288OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2,
1289 OutputIterator output) {
1290 return std::set_symmetric_difference(
1291 container_algorithm_internal::c_begin(c1),
1292 container_algorithm_internal::c_end(c1),
1293 container_algorithm_internal::c_begin(c2),
1294 container_algorithm_internal::c_end(c2), output);
1295}
1296
1297// Overload of c_set_symmetric_difference() for performing a merge using a
1298// `comp` other than `operator<`.
Abseil Team7b46e1d2018-11-13 13:22:00 -08001299template <typename C1, typename C2, typename OutputIterator, typename Compare,
1300 typename = typename std::enable_if<
1301 !container_algorithm_internal::IsUnorderedContainer<C1>::value,
1302 void>::type,
1303 typename = typename std::enable_if<
1304 !container_algorithm_internal::IsUnorderedContainer<C2>::value,
1305 void>::type>
mistergc2e75482017-09-19 16:54:40 -04001306OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2,
1307 OutputIterator output,
1308 Compare&& comp) {
1309 return std::set_symmetric_difference(
1310 container_algorithm_internal::c_begin(c1),
1311 container_algorithm_internal::c_end(c1),
1312 container_algorithm_internal::c_begin(c2),
1313 container_algorithm_internal::c_end(c2), output,
1314 std::forward<Compare>(comp));
1315}
1316
1317//------------------------------------------------------------------------------
1318// <algorithm> Heap functions
1319//------------------------------------------------------------------------------
1320
1321// c_push_heap()
1322//
1323// Container-based version of the <algorithm> `std::push_heap()` function
1324// to push a value onto a container heap.
1325template <typename RandomAccessContainer>
1326void c_push_heap(RandomAccessContainer& sequence) {
1327 std::push_heap(container_algorithm_internal::c_begin(sequence),
1328 container_algorithm_internal::c_end(sequence));
1329}
1330
1331// Overload of c_push_heap() for performing a push operation on a heap using a
1332// `comp` other than `operator<`.
1333template <typename RandomAccessContainer, typename Compare>
1334void c_push_heap(RandomAccessContainer& sequence, Compare&& comp) {
1335 std::push_heap(container_algorithm_internal::c_begin(sequence),
1336 container_algorithm_internal::c_end(sequence),
1337 std::forward<Compare>(comp));
1338}
1339
1340// c_pop_heap()
1341//
1342// Container-based version of the <algorithm> `std::pop_heap()` function
1343// to pop a value from a heap container.
1344template <typename RandomAccessContainer>
1345void c_pop_heap(RandomAccessContainer& sequence) {
1346 std::pop_heap(container_algorithm_internal::c_begin(sequence),
1347 container_algorithm_internal::c_end(sequence));
1348}
1349
1350// Overload of c_pop_heap() for performing a pop operation on a heap using a
1351// `comp` other than `operator<`.
1352template <typename RandomAccessContainer, typename Compare>
1353void c_pop_heap(RandomAccessContainer& sequence, Compare&& comp) {
1354 std::pop_heap(container_algorithm_internal::c_begin(sequence),
1355 container_algorithm_internal::c_end(sequence),
1356 std::forward<Compare>(comp));
1357}
1358
1359// c_make_heap()
1360//
1361// Container-based version of the <algorithm> `std::make_heap()` function
1362// to make a container a heap.
1363template <typename RandomAccessContainer>
1364void c_make_heap(RandomAccessContainer& sequence) {
1365 std::make_heap(container_algorithm_internal::c_begin(sequence),
1366 container_algorithm_internal::c_end(sequence));
1367}
1368
1369// Overload of c_make_heap() for performing heap comparisons using a
1370// `comp` other than `operator<`
1371template <typename RandomAccessContainer, typename Compare>
1372void c_make_heap(RandomAccessContainer& sequence, Compare&& comp) {
1373 std::make_heap(container_algorithm_internal::c_begin(sequence),
1374 container_algorithm_internal::c_end(sequence),
1375 std::forward<Compare>(comp));
1376}
1377
1378// c_sort_heap()
1379//
1380// Container-based version of the <algorithm> `std::sort_heap()` function
1381// to sort a heap into ascending order (after which it is no longer a heap).
1382template <typename RandomAccessContainer>
1383void c_sort_heap(RandomAccessContainer& sequence) {
1384 std::sort_heap(container_algorithm_internal::c_begin(sequence),
1385 container_algorithm_internal::c_end(sequence));
1386}
1387
1388// Overload of c_sort_heap() for performing heap comparisons using a
1389// `comp` other than `operator<`
1390template <typename RandomAccessContainer, typename Compare>
1391void c_sort_heap(RandomAccessContainer& sequence, Compare&& comp) {
1392 std::sort_heap(container_algorithm_internal::c_begin(sequence),
1393 container_algorithm_internal::c_end(sequence),
1394 std::forward<Compare>(comp));
1395}
1396
1397// c_is_heap()
1398//
1399// Container-based version of the <algorithm> `std::is_heap()` function
1400// to check whether the given container is a heap.
1401template <typename RandomAccessContainer>
1402bool c_is_heap(const RandomAccessContainer& sequence) {
1403 return std::is_heap(container_algorithm_internal::c_begin(sequence),
1404 container_algorithm_internal::c_end(sequence));
1405}
1406
1407// Overload of c_is_heap() for performing heap comparisons using a
1408// `comp` other than `operator<`
1409template <typename RandomAccessContainer, typename Compare>
1410bool c_is_heap(const RandomAccessContainer& sequence, Compare&& comp) {
1411 return std::is_heap(container_algorithm_internal::c_begin(sequence),
1412 container_algorithm_internal::c_end(sequence),
1413 std::forward<Compare>(comp));
1414}
1415
1416// c_is_heap_until()
1417//
1418// Container-based version of the <algorithm> `std::is_heap_until()` function
1419// to find the first element in a given container which is not in heap order.
1420template <typename RandomAccessContainer>
1421container_algorithm_internal::ContainerIter<RandomAccessContainer>
1422c_is_heap_until(RandomAccessContainer& sequence) {
1423 return std::is_heap_until(container_algorithm_internal::c_begin(sequence),
1424 container_algorithm_internal::c_end(sequence));
1425}
1426
1427// Overload of c_is_heap_until() for performing heap comparisons using a
1428// `comp` other than `operator<`
1429template <typename RandomAccessContainer, typename Compare>
1430container_algorithm_internal::ContainerIter<RandomAccessContainer>
1431c_is_heap_until(RandomAccessContainer& sequence, Compare&& comp) {
1432 return std::is_heap_until(container_algorithm_internal::c_begin(sequence),
1433 container_algorithm_internal::c_end(sequence),
1434 std::forward<Compare>(comp));
1435}
1436
1437//------------------------------------------------------------------------------
1438// <algorithm> Min/max
1439//------------------------------------------------------------------------------
1440
1441// c_min_element()
1442//
1443// Container-based version of the <algorithm> `std::min_element()` function
1444// to return an iterator pointing to the element with the smallest value, using
1445// `operator<` to make the comparisons.
1446template <typename Sequence>
1447container_algorithm_internal::ContainerIter<Sequence> c_min_element(
1448 Sequence& sequence) {
1449 return std::min_element(container_algorithm_internal::c_begin(sequence),
1450 container_algorithm_internal::c_end(sequence));
1451}
1452
1453// Overload of c_min_element() for performing a `comp` comparison other than
1454// `operator<`.
1455template <typename Sequence, typename Compare>
1456container_algorithm_internal::ContainerIter<Sequence> c_min_element(
1457 Sequence& sequence, Compare&& comp) {
1458 return std::min_element(container_algorithm_internal::c_begin(sequence),
1459 container_algorithm_internal::c_end(sequence),
1460 std::forward<Compare>(comp));
1461}
1462
1463// c_max_element()
1464//
1465// Container-based version of the <algorithm> `std::max_element()` function
1466// to return an iterator pointing to the element with the largest value, using
1467// `operator<` to make the comparisons.
1468template <typename Sequence>
1469container_algorithm_internal::ContainerIter<Sequence> c_max_element(
1470 Sequence& sequence) {
1471 return std::max_element(container_algorithm_internal::c_begin(sequence),
1472 container_algorithm_internal::c_end(sequence));
1473}
1474
1475// Overload of c_max_element() for performing a `comp` comparison other than
1476// `operator<`.
1477template <typename Sequence, typename Compare>
1478container_algorithm_internal::ContainerIter<Sequence> c_max_element(
1479 Sequence& sequence, Compare&& comp) {
1480 return std::max_element(container_algorithm_internal::c_begin(sequence),
1481 container_algorithm_internal::c_end(sequence),
1482 std::forward<Compare>(comp));
1483}
1484
1485// c_minmax_element()
1486//
1487// Container-based version of the <algorithm> `std::minmax_element()` function
1488// to return a pair of iterators pointing to the elements containing the
1489// smallest and largest values, respectively, using `operator<` to make the
1490// comparisons.
1491template <typename C>
Abseil Team95ddf852017-11-13 10:04:29 -08001492container_algorithm_internal::ContainerIterPairType<C, C>
mistergc2e75482017-09-19 16:54:40 -04001493c_minmax_element(C& c) {
1494 return std::minmax_element(container_algorithm_internal::c_begin(c),
1495 container_algorithm_internal::c_end(c));
1496}
1497
1498// Overload of c_minmax_element() for performing `comp` comparisons other than
1499// `operator<`.
1500template <typename C, typename Compare>
Abseil Team95ddf852017-11-13 10:04:29 -08001501container_algorithm_internal::ContainerIterPairType<C, C>
mistergc2e75482017-09-19 16:54:40 -04001502c_minmax_element(C& c, Compare&& comp) {
1503 return std::minmax_element(container_algorithm_internal::c_begin(c),
1504 container_algorithm_internal::c_end(c),
1505 std::forward<Compare>(comp));
1506}
1507
1508//------------------------------------------------------------------------------
1509// <algorithm> Lexicographical Comparisons
1510//------------------------------------------------------------------------------
1511
1512// c_lexicographical_compare()
1513//
1514// Container-based version of the <algorithm> `std::lexicographical_compare()`
1515// function to lexicographically compare (e.g. sort words alphabetically) two
1516// container sequences. The comparison is performed using `operator<`. Note
1517// that capital letters ("A-Z") have ASCII values less than lowercase letters
1518// ("a-z").
1519template <typename Sequence1, typename Sequence2>
1520bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2) {
1521 return std::lexicographical_compare(
1522 container_algorithm_internal::c_begin(sequence1),
1523 container_algorithm_internal::c_end(sequence1),
1524 container_algorithm_internal::c_begin(sequence2),
1525 container_algorithm_internal::c_end(sequence2));
1526}
1527
1528// Overload of c_lexicographical_compare() for performing a lexicographical
1529// comparison using a `comp` operator instead of `operator<`.
1530template <typename Sequence1, typename Sequence2, typename Compare>
1531bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2,
1532 Compare&& comp) {
1533 return std::lexicographical_compare(
1534 container_algorithm_internal::c_begin(sequence1),
1535 container_algorithm_internal::c_end(sequence1),
1536 container_algorithm_internal::c_begin(sequence2),
1537 container_algorithm_internal::c_end(sequence2),
1538 std::forward<Compare>(comp));
1539}
1540
1541// c_next_permutation()
1542//
1543// Container-based version of the <algorithm> `std::next_permutation()` function
1544// to rearrange a container's elements into the next lexicographically greater
1545// permutation.
1546template <typename C>
1547bool c_next_permutation(C& c) {
1548 return std::next_permutation(container_algorithm_internal::c_begin(c),
1549 container_algorithm_internal::c_end(c));
1550}
1551
1552// Overload of c_next_permutation() for performing a lexicographical
1553// comparison using a `comp` operator instead of `operator<`.
1554template <typename C, typename Compare>
1555bool c_next_permutation(C& c, Compare&& comp) {
1556 return std::next_permutation(container_algorithm_internal::c_begin(c),
1557 container_algorithm_internal::c_end(c),
1558 std::forward<Compare>(comp));
1559}
1560
1561// c_prev_permutation()
1562//
1563// Container-based version of the <algorithm> `std::prev_permutation()` function
1564// to rearrange a container's elements into the next lexicographically lesser
1565// permutation.
1566template <typename C>
1567bool c_prev_permutation(C& c) {
1568 return std::prev_permutation(container_algorithm_internal::c_begin(c),
1569 container_algorithm_internal::c_end(c));
1570}
1571
1572// Overload of c_prev_permutation() for performing a lexicographical
1573// comparison using a `comp` operator instead of `operator<`.
1574template <typename C, typename Compare>
1575bool c_prev_permutation(C& c, Compare&& comp) {
1576 return std::prev_permutation(container_algorithm_internal::c_begin(c),
1577 container_algorithm_internal::c_end(c),
1578 std::forward<Compare>(comp));
1579}
1580
1581//------------------------------------------------------------------------------
1582// <numeric> algorithms
1583//------------------------------------------------------------------------------
1584
1585// c_iota()
1586//
1587// Container-based version of the <algorithm> `std::iota()` function
1588// to compute successive values of `value`, as if incremented with `++value`
1589// after each element is written. and write them to the container.
1590template <typename Sequence, typename T>
1591void c_iota(Sequence& sequence, T&& value) {
1592 std::iota(container_algorithm_internal::c_begin(sequence),
1593 container_algorithm_internal::c_end(sequence),
1594 std::forward<T>(value));
1595}
1596// c_accumulate()
1597//
1598// Container-based version of the <algorithm> `std::accumulate()` function
1599// to accumulate the element values of a container to `init` and return that
1600// accumulation by value.
1601//
1602// Note: Due to a language technicality this function has return type
1603// absl::decay_t<T>. As a user of this function you can casually read
1604// this as "returns T by value" and assume it does the right thing.
1605template <typename Sequence, typename T>
1606decay_t<T> c_accumulate(const Sequence& sequence, T&& init) {
1607 return std::accumulate(container_algorithm_internal::c_begin(sequence),
1608 container_algorithm_internal::c_end(sequence),
1609 std::forward<T>(init));
1610}
1611
1612// Overload of c_accumulate() for using a binary operations other than
1613// addition for computing the accumulation.
1614template <typename Sequence, typename T, typename BinaryOp>
1615decay_t<T> c_accumulate(const Sequence& sequence, T&& init,
1616 BinaryOp&& binary_op) {
1617 return std::accumulate(container_algorithm_internal::c_begin(sequence),
1618 container_algorithm_internal::c_end(sequence),
1619 std::forward<T>(init),
1620 std::forward<BinaryOp>(binary_op));
1621}
1622
1623// c_inner_product()
1624//
1625// Container-based version of the <algorithm> `std::inner_product()` function
1626// to compute the cumulative inner product of container element pairs.
1627//
1628// Note: Due to a language technicality this function has return type
1629// absl::decay_t<T>. As a user of this function you can casually read
1630// this as "returns T by value" and assume it does the right thing.
1631template <typename Sequence1, typename Sequence2, typename T>
1632decay_t<T> c_inner_product(const Sequence1& factors1, const Sequence2& factors2,
1633 T&& sum) {
1634 return std::inner_product(container_algorithm_internal::c_begin(factors1),
1635 container_algorithm_internal::c_end(factors1),
1636 container_algorithm_internal::c_begin(factors2),
1637 std::forward<T>(sum));
1638}
1639
1640// Overload of c_inner_product() for using binary operations other than
Bruce Mitchener08760ad2018-04-20 01:11:44 +07001641// `operator+` (for computing the accumulation) and `operator*` (for computing
mistergc2e75482017-09-19 16:54:40 -04001642// the product between the two container's element pair).
1643template <typename Sequence1, typename Sequence2, typename T,
1644 typename BinaryOp1, typename BinaryOp2>
1645decay_t<T> c_inner_product(const Sequence1& factors1, const Sequence2& factors2,
1646 T&& sum, BinaryOp1&& op1, BinaryOp2&& op2) {
1647 return std::inner_product(container_algorithm_internal::c_begin(factors1),
1648 container_algorithm_internal::c_end(factors1),
1649 container_algorithm_internal::c_begin(factors2),
1650 std::forward<T>(sum), std::forward<BinaryOp1>(op1),
1651 std::forward<BinaryOp2>(op2));
1652}
1653
1654// c_adjacent_difference()
1655//
1656// Container-based version of the <algorithm> `std::adjacent_difference()`
1657// function to compute the difference between each element and the one preceding
1658// it and write it to an iterator.
1659template <typename InputSequence, typename OutputIt>
1660OutputIt c_adjacent_difference(const InputSequence& input,
1661 OutputIt output_first) {
1662 return std::adjacent_difference(container_algorithm_internal::c_begin(input),
1663 container_algorithm_internal::c_end(input),
1664 output_first);
1665}
1666
1667// Overload of c_adjacent_difference() for using a binary operation other than
1668// subtraction to compute the adjacent difference.
1669template <typename InputSequence, typename OutputIt, typename BinaryOp>
1670OutputIt c_adjacent_difference(const InputSequence& input,
1671 OutputIt output_first, BinaryOp&& op) {
1672 return std::adjacent_difference(container_algorithm_internal::c_begin(input),
1673 container_algorithm_internal::c_end(input),
1674 output_first, std::forward<BinaryOp>(op));
1675}
1676
1677// c_partial_sum()
1678//
1679// Container-based version of the <algorithm> `std::partial_sum()` function
1680// to compute the partial sum of the elements in a sequence and write them
1681// to an iterator. The partial sum is the sum of all element values so far in
1682// the sequence.
1683template <typename InputSequence, typename OutputIt>
1684OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first) {
1685 return std::partial_sum(container_algorithm_internal::c_begin(input),
1686 container_algorithm_internal::c_end(input),
1687 output_first);
1688}
1689
1690// Overload of c_partial_sum() for using a binary operation other than addition
1691// to compute the "partial sum".
1692template <typename InputSequence, typename OutputIt, typename BinaryOp>
1693OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first,
1694 BinaryOp&& op) {
1695 return std::partial_sum(container_algorithm_internal::c_begin(input),
1696 container_algorithm_internal::c_end(input),
1697 output_first, std::forward<BinaryOp>(op));
1698}
1699
1700} // namespace absl
1701
1702#endif // ABSL_ALGORITHM_CONTAINER_H_