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