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