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