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