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


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:18