1*0b57cec5SDimitry Andric// -*- C++ -*-
2349cc55cSDimitry Andric//===----------------------------------------------------------------------===//
3*0b57cec5SDimitry Andric//
4*0b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5*0b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information.
6*0b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7*0b57cec5SDimitry Andric//
8*0b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
9*0b57cec5SDimitry Andric
10*0b57cec5SDimitry Andric#ifndef _LIBCPP_ALGORITHM
11*0b57cec5SDimitry Andric#define _LIBCPP_ALGORITHM
12*0b57cec5SDimitry Andric
13*0b57cec5SDimitry Andric/*
14*0b57cec5SDimitry Andric    algorithm synopsis
15*0b57cec5SDimitry Andric
16*0b57cec5SDimitry Andric#include <initializer_list>
17*0b57cec5SDimitry Andric
18*0b57cec5SDimitry Andricnamespace std
19*0b57cec5SDimitry Andric{
20*0b57cec5SDimitry Andric
2104eeddc0SDimitry Andricnamespace ranges {
2204eeddc0SDimitry Andric  template <class I1, class I2>
2304eeddc0SDimitry Andric    struct in_in_result; // since C++20
2404eeddc0SDimitry Andric}
2504eeddc0SDimitry Andric
26*0b57cec5SDimitry Andrictemplate <class InputIterator, class Predicate>
27*0b57cec5SDimitry Andric    constexpr bool     // constexpr in C++20
28*0b57cec5SDimitry Andric    all_of(InputIterator first, InputIterator last, Predicate pred);
29*0b57cec5SDimitry Andric
30*0b57cec5SDimitry Andrictemplate <class InputIterator, class Predicate>
31*0b57cec5SDimitry Andric    constexpr bool     // constexpr in C++20
32*0b57cec5SDimitry Andric    any_of(InputIterator first, InputIterator last, Predicate pred);
33*0b57cec5SDimitry Andric
34*0b57cec5SDimitry Andrictemplate <class InputIterator, class Predicate>
35*0b57cec5SDimitry Andric    constexpr bool     // constexpr in C++20
36*0b57cec5SDimitry Andric    none_of(InputIterator first, InputIterator last, Predicate pred);
37*0b57cec5SDimitry Andric
38*0b57cec5SDimitry Andrictemplate <class InputIterator, class Function>
39*0b57cec5SDimitry Andric    constexpr Function          // constexpr in C++20
40*0b57cec5SDimitry Andric    for_each(InputIterator first, InputIterator last, Function f);
41*0b57cec5SDimitry Andric
42*0b57cec5SDimitry Andrictemplate<class InputIterator, class Size, class Function>
43*0b57cec5SDimitry Andric    constexpr InputIterator     // constexpr in C++20
44*0b57cec5SDimitry Andric    for_each_n(InputIterator first, Size n, Function f); // C++17
45*0b57cec5SDimitry Andric
46*0b57cec5SDimitry Andrictemplate <class InputIterator, class T>
47*0b57cec5SDimitry Andric    constexpr InputIterator     // constexpr in C++20
48*0b57cec5SDimitry Andric    find(InputIterator first, InputIterator last, const T& value);
49*0b57cec5SDimitry Andric
50*0b57cec5SDimitry Andrictemplate <class InputIterator, class Predicate>
51*0b57cec5SDimitry Andric    constexpr InputIterator     // constexpr in C++20
52*0b57cec5SDimitry Andric    find_if(InputIterator first, InputIterator last, Predicate pred);
53*0b57cec5SDimitry Andric
54*0b57cec5SDimitry Andrictemplate<class InputIterator, class Predicate>
55e8d8bef9SDimitry Andric    constexpr InputIterator     // constexpr in C++20
56*0b57cec5SDimitry Andric    find_if_not(InputIterator first, InputIterator last, Predicate pred);
57*0b57cec5SDimitry Andric
58*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2>
59e8d8bef9SDimitry Andric    constexpr ForwardIterator1  // constexpr in C++20
60*0b57cec5SDimitry Andric    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
61*0b57cec5SDimitry Andric             ForwardIterator2 first2, ForwardIterator2 last2);
62*0b57cec5SDimitry Andric
63*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
64e8d8bef9SDimitry Andric    constexpr ForwardIterator1  // constexpr in C++20
65*0b57cec5SDimitry Andric    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
66*0b57cec5SDimitry Andric             ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
67*0b57cec5SDimitry Andric
68*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2>
69*0b57cec5SDimitry Andric    constexpr ForwardIterator1  // constexpr in C++20
70*0b57cec5SDimitry Andric    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
71*0b57cec5SDimitry Andric                  ForwardIterator2 first2, ForwardIterator2 last2);
72*0b57cec5SDimitry Andric
73*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
74*0b57cec5SDimitry Andric    constexpr ForwardIterator1  // constexpr in C++20
75*0b57cec5SDimitry Andric    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
76*0b57cec5SDimitry Andric                  ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
77*0b57cec5SDimitry Andric
78*0b57cec5SDimitry Andrictemplate <class ForwardIterator>
79*0b57cec5SDimitry Andric    constexpr ForwardIterator   // constexpr in C++20
80*0b57cec5SDimitry Andric    adjacent_find(ForwardIterator first, ForwardIterator last);
81*0b57cec5SDimitry Andric
82*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class BinaryPredicate>
83*0b57cec5SDimitry Andric    constexpr ForwardIterator   // constexpr in C++20
84*0b57cec5SDimitry Andric    adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
85*0b57cec5SDimitry Andric
86*0b57cec5SDimitry Andrictemplate <class InputIterator, class T>
87*0b57cec5SDimitry Andric    constexpr typename iterator_traits<InputIterator>::difference_type  // constexpr in C++20
88*0b57cec5SDimitry Andric    count(InputIterator first, InputIterator last, const T& value);
89*0b57cec5SDimitry Andric
90*0b57cec5SDimitry Andrictemplate <class InputIterator, class Predicate>
91*0b57cec5SDimitry Andric    constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
92*0b57cec5SDimitry Andric    count_if(InputIterator first, InputIterator last, Predicate pred);
93*0b57cec5SDimitry Andric
94*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2>
95*0b57cec5SDimitry Andric    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
96*0b57cec5SDimitry Andric    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
97*0b57cec5SDimitry Andric
98*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2>
99*0b57cec5SDimitry Andric    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
100*0b57cec5SDimitry Andric    mismatch(InputIterator1 first1, InputIterator1 last1,
101*0b57cec5SDimitry Andric             InputIterator2 first2, InputIterator2 last2); // **C++14**
102*0b57cec5SDimitry Andric
103*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class BinaryPredicate>
104*0b57cec5SDimitry Andric    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
105*0b57cec5SDimitry Andric    mismatch(InputIterator1 first1, InputIterator1 last1,
106*0b57cec5SDimitry Andric             InputIterator2 first2, BinaryPredicate pred);
107*0b57cec5SDimitry Andric
108*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class BinaryPredicate>
109*0b57cec5SDimitry Andric    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
110*0b57cec5SDimitry Andric    mismatch(InputIterator1 first1, InputIterator1 last1,
111*0b57cec5SDimitry Andric             InputIterator2 first2, InputIterator2 last2,
112*0b57cec5SDimitry Andric             BinaryPredicate pred); // **C++14**
113*0b57cec5SDimitry Andric
114*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2>
115*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
116*0b57cec5SDimitry Andric    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
117*0b57cec5SDimitry Andric
118*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2>
119*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
120*0b57cec5SDimitry Andric    equal(InputIterator1 first1, InputIterator1 last1,
121*0b57cec5SDimitry Andric          InputIterator2 first2, InputIterator2 last2); // **C++14**
122*0b57cec5SDimitry Andric
123*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class BinaryPredicate>
124*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
125*0b57cec5SDimitry Andric    equal(InputIterator1 first1, InputIterator1 last1,
126*0b57cec5SDimitry Andric          InputIterator2 first2, BinaryPredicate pred);
127*0b57cec5SDimitry Andric
128*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class BinaryPredicate>
129*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
130*0b57cec5SDimitry Andric    equal(InputIterator1 first1, InputIterator1 last1,
131*0b57cec5SDimitry Andric          InputIterator2 first2, InputIterator2 last2,
132*0b57cec5SDimitry Andric          BinaryPredicate pred); // **C++14**
133*0b57cec5SDimitry Andric
134*0b57cec5SDimitry Andrictemplate<class ForwardIterator1, class ForwardIterator2>
135*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
136*0b57cec5SDimitry Andric    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
137*0b57cec5SDimitry Andric                   ForwardIterator2 first2);
138*0b57cec5SDimitry Andric
139*0b57cec5SDimitry Andrictemplate<class ForwardIterator1, class ForwardIterator2>
140*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
141*0b57cec5SDimitry Andric    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
142*0b57cec5SDimitry Andric                   ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
143*0b57cec5SDimitry Andric
144*0b57cec5SDimitry Andrictemplate<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
145*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
146*0b57cec5SDimitry Andric    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
147*0b57cec5SDimitry Andric                   ForwardIterator2 first2, BinaryPredicate pred);
148*0b57cec5SDimitry Andric
149*0b57cec5SDimitry Andrictemplate<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
150*0b57cec5SDimitry Andric    constexpr bool      // constexpr in C++20
151*0b57cec5SDimitry Andric    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
152*0b57cec5SDimitry Andric                   ForwardIterator2 first2, ForwardIterator2 last2,
153*0b57cec5SDimitry Andric                   BinaryPredicate pred);  // **C++14**
154*0b57cec5SDimitry Andric
155*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2>
156*0b57cec5SDimitry Andric    constexpr ForwardIterator1      // constexpr in C++20
157*0b57cec5SDimitry Andric    search(ForwardIterator1 first1, ForwardIterator1 last1,
158*0b57cec5SDimitry Andric           ForwardIterator2 first2, ForwardIterator2 last2);
159*0b57cec5SDimitry Andric
160*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
161*0b57cec5SDimitry Andric    constexpr ForwardIterator1      // constexpr in C++20
162*0b57cec5SDimitry Andric    search(ForwardIterator1 first1, ForwardIterator1 last1,
163*0b57cec5SDimitry Andric           ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
164*0b57cec5SDimitry Andric
165*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Size, class T>
166*0b57cec5SDimitry Andric    constexpr ForwardIterator       // constexpr in C++20
167*0b57cec5SDimitry Andric    search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
168*0b57cec5SDimitry Andric
169*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Size, class T, class BinaryPredicate>
170*0b57cec5SDimitry Andric    constexpr ForwardIterator       // constexpr in C++20
171*0b57cec5SDimitry Andric    search_n(ForwardIterator first, ForwardIterator last,
172*0b57cec5SDimitry Andric             Size count, const T& value, BinaryPredicate pred);
173*0b57cec5SDimitry Andric
174*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator>
175480093f4SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
176*0b57cec5SDimitry Andric    copy(InputIterator first, InputIterator last, OutputIterator result);
177*0b57cec5SDimitry Andric
178*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class Predicate>
179480093f4SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
180*0b57cec5SDimitry Andric    copy_if(InputIterator first, InputIterator last,
181*0b57cec5SDimitry Andric            OutputIterator result, Predicate pred);
182*0b57cec5SDimitry Andric
183*0b57cec5SDimitry Andrictemplate<class InputIterator, class Size, class OutputIterator>
184480093f4SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
185*0b57cec5SDimitry Andric    copy_n(InputIterator first, Size n, OutputIterator result);
186*0b57cec5SDimitry Andric
187*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator1, class BidirectionalIterator2>
188480093f4SDimitry Andric    constexpr BidirectionalIterator2      // constexpr in C++20
189*0b57cec5SDimitry Andric    copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
190*0b57cec5SDimitry Andric                  BidirectionalIterator2 result);
191*0b57cec5SDimitry Andric
192*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2>
193e8d8bef9SDimitry Andric    constexpr ForwardIterator2    // constexpr in C++20
194*0b57cec5SDimitry Andric    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
195*0b57cec5SDimitry Andric
196*0b57cec5SDimitry Andrictemplate <class ForwardIterator1, class ForwardIterator2>
197e8d8bef9SDimitry Andric    constexpr void                // constexpr in C++20
198*0b57cec5SDimitry Andric    iter_swap(ForwardIterator1 a, ForwardIterator2 b);
199*0b57cec5SDimitry Andric
200*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class UnaryOperation>
201*0b57cec5SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
202*0b57cec5SDimitry Andric    transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
203*0b57cec5SDimitry Andric
204*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
205*0b57cec5SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
206*0b57cec5SDimitry Andric    transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
207*0b57cec5SDimitry Andric              OutputIterator result, BinaryOperation binary_op);
208*0b57cec5SDimitry Andric
209*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
210*0b57cec5SDimitry Andric    constexpr void      // constexpr in C++20
211*0b57cec5SDimitry Andric    replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
212*0b57cec5SDimitry Andric
213*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Predicate, class T>
214*0b57cec5SDimitry Andric    constexpr void      // constexpr in C++20
215*0b57cec5SDimitry Andric    replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
216*0b57cec5SDimitry Andric
217*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class T>
218*0b57cec5SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
219*0b57cec5SDimitry Andric    replace_copy(InputIterator first, InputIterator last, OutputIterator result,
220*0b57cec5SDimitry Andric                 const T& old_value, const T& new_value);
221*0b57cec5SDimitry Andric
222*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class Predicate, class T>
223*0b57cec5SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
224*0b57cec5SDimitry Andric    replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
225*0b57cec5SDimitry Andric
226*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
227*0b57cec5SDimitry Andric    constexpr void      // constexpr in C++20
228*0b57cec5SDimitry Andric    fill(ForwardIterator first, ForwardIterator last, const T& value);
229*0b57cec5SDimitry Andric
230*0b57cec5SDimitry Andrictemplate <class OutputIterator, class Size, class T>
231*0b57cec5SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
232*0b57cec5SDimitry Andric    fill_n(OutputIterator first, Size n, const T& value);
233*0b57cec5SDimitry Andric
234*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Generator>
235*0b57cec5SDimitry Andric    constexpr void      // constexpr in C++20
236*0b57cec5SDimitry Andric    generate(ForwardIterator first, ForwardIterator last, Generator gen);
237*0b57cec5SDimitry Andric
238*0b57cec5SDimitry Andrictemplate <class OutputIterator, class Size, class Generator>
239*0b57cec5SDimitry Andric    constexpr OutputIterator      // constexpr in C++20
240*0b57cec5SDimitry Andric    generate_n(OutputIterator first, Size n, Generator gen);
241*0b57cec5SDimitry Andric
242*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
243*0b57cec5SDimitry Andric    constexpr ForwardIterator     // constexpr in C++20
244*0b57cec5SDimitry Andric    remove(ForwardIterator first, ForwardIterator last, const T& value);
245*0b57cec5SDimitry Andric
246*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Predicate>
247*0b57cec5SDimitry Andric    constexpr ForwardIterator     // constexpr in C++20
248*0b57cec5SDimitry Andric    remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
249*0b57cec5SDimitry Andric
250*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class T>
251*0b57cec5SDimitry Andric    constexpr OutputIterator     // constexpr in C++20
252*0b57cec5SDimitry Andric    remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
253*0b57cec5SDimitry Andric
254*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class Predicate>
255*0b57cec5SDimitry Andric    constexpr OutputIterator     // constexpr in C++20
256*0b57cec5SDimitry Andric    remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
257*0b57cec5SDimitry Andric
258*0b57cec5SDimitry Andrictemplate <class ForwardIterator>
259e8d8bef9SDimitry Andric    constexpr ForwardIterator    // constexpr in C++20
260*0b57cec5SDimitry Andric    unique(ForwardIterator first, ForwardIterator last);
261*0b57cec5SDimitry Andric
262*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class BinaryPredicate>
263e8d8bef9SDimitry Andric    constexpr ForwardIterator    // constexpr in C++20
264*0b57cec5SDimitry Andric    unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
265*0b57cec5SDimitry Andric
266*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator>
267e8d8bef9SDimitry Andric    constexpr OutputIterator     // constexpr in C++20
268*0b57cec5SDimitry Andric    unique_copy(InputIterator first, InputIterator last, OutputIterator result);
269*0b57cec5SDimitry Andric
270*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class BinaryPredicate>
271e8d8bef9SDimitry Andric    constexpr OutputIterator     // constexpr in C++20
272*0b57cec5SDimitry Andric    unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
273*0b57cec5SDimitry Andric
274*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator>
275e8d8bef9SDimitry Andric    constexpr void               // constexpr in C++20
276*0b57cec5SDimitry Andric    reverse(BidirectionalIterator first, BidirectionalIterator last);
277*0b57cec5SDimitry Andric
278*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator, class OutputIterator>
279*0b57cec5SDimitry Andric    constexpr OutputIterator       // constexpr in C++20
280*0b57cec5SDimitry Andric    reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
281*0b57cec5SDimitry Andric
282*0b57cec5SDimitry Andrictemplate <class ForwardIterator>
283e8d8bef9SDimitry Andric    constexpr ForwardIterator      // constexpr in C++20
284*0b57cec5SDimitry Andric    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
285*0b57cec5SDimitry Andric
286*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class OutputIterator>
287e8d8bef9SDimitry Andric    constexpr OutputIterator       // constexpr in C++20
288*0b57cec5SDimitry Andric    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
289*0b57cec5SDimitry Andric
290*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
291*0b57cec5SDimitry Andric    void
292*0b57cec5SDimitry Andric    random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
293*0b57cec5SDimitry Andric
294*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class RandomNumberGenerator>
295*0b57cec5SDimitry Andric    void
296*0b57cec5SDimitry Andric    random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
297*0b57cec5SDimitry Andric                   RandomNumberGenerator& rand);  // deprecated in C++14, removed in C++17
298*0b57cec5SDimitry Andric
299*0b57cec5SDimitry Andrictemplate<class PopulationIterator, class SampleIterator,
300*0b57cec5SDimitry Andric         class Distance, class UniformRandomBitGenerator>
301*0b57cec5SDimitry Andric    SampleIterator sample(PopulationIterator first, PopulationIterator last,
302*0b57cec5SDimitry Andric                          SampleIterator out, Distance n,
303*0b57cec5SDimitry Andric                          UniformRandomBitGenerator&& g); // C++17
304*0b57cec5SDimitry Andric
305*0b57cec5SDimitry Andrictemplate<class RandomAccessIterator, class UniformRandomNumberGenerator>
306*0b57cec5SDimitry Andric    void shuffle(RandomAccessIterator first, RandomAccessIterator last,
307*0b57cec5SDimitry Andric                 UniformRandomNumberGenerator&& g);
308*0b57cec5SDimitry Andric
309e8d8bef9SDimitry Andrictemplate<class ForwardIterator>
310e8d8bef9SDimitry Andric  constexpr ForwardIterator
311e8d8bef9SDimitry Andric    shift_left(ForwardIterator first, ForwardIterator last,
312e8d8bef9SDimitry Andric               typename iterator_traits<ForwardIterator>::difference_type n); // C++20
313e8d8bef9SDimitry Andric
314e8d8bef9SDimitry Andrictemplate<class ForwardIterator>
315e8d8bef9SDimitry Andric  constexpr ForwardIterator
316e8d8bef9SDimitry Andric    shift_right(ForwardIterator first, ForwardIterator last,
317e8d8bef9SDimitry Andric                typename iterator_traits<ForwardIterator>::difference_type n); // C++20
318e8d8bef9SDimitry Andric
319*0b57cec5SDimitry Andrictemplate <class InputIterator, class Predicate>
320*0b57cec5SDimitry Andric    constexpr bool  // constexpr in C++20
321*0b57cec5SDimitry Andric    is_partitioned(InputIterator first, InputIterator last, Predicate pred);
322*0b57cec5SDimitry Andric
323*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Predicate>
324e8d8bef9SDimitry Andric    constexpr ForwardIterator  // constexpr in C++20
325*0b57cec5SDimitry Andric    partition(ForwardIterator first, ForwardIterator last, Predicate pred);
326*0b57cec5SDimitry Andric
327*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator1,
328*0b57cec5SDimitry Andric          class OutputIterator2, class Predicate>
329*0b57cec5SDimitry Andric    constexpr pair<OutputIterator1, OutputIterator2>   // constexpr in C++20
330*0b57cec5SDimitry Andric    partition_copy(InputIterator first, InputIterator last,
331*0b57cec5SDimitry Andric                   OutputIterator1 out_true, OutputIterator2 out_false,
332*0b57cec5SDimitry Andric                   Predicate pred);
333*0b57cec5SDimitry Andric
334*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Predicate>
335*0b57cec5SDimitry Andric    ForwardIterator
336*0b57cec5SDimitry Andric    stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
337*0b57cec5SDimitry Andric
338*0b57cec5SDimitry Andrictemplate<class ForwardIterator, class Predicate>
339*0b57cec5SDimitry Andric    constexpr ForwardIterator  // constexpr in C++20
340*0b57cec5SDimitry Andric    partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
341*0b57cec5SDimitry Andric
342*0b57cec5SDimitry Andrictemplate <class ForwardIterator>
343*0b57cec5SDimitry Andric    constexpr bool  // constexpr in C++20
344*0b57cec5SDimitry Andric    is_sorted(ForwardIterator first, ForwardIterator last);
345*0b57cec5SDimitry Andric
346*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Compare>
347e8d8bef9SDimitry Andric    constexpr bool  // constexpr in C++20
348*0b57cec5SDimitry Andric    is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
349*0b57cec5SDimitry Andric
350*0b57cec5SDimitry Andrictemplate<class ForwardIterator>
351*0b57cec5SDimitry Andric    constexpr ForwardIterator    // constexpr in C++20
352*0b57cec5SDimitry Andric    is_sorted_until(ForwardIterator first, ForwardIterator last);
353*0b57cec5SDimitry Andric
354*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Compare>
355*0b57cec5SDimitry Andric    constexpr ForwardIterator    // constexpr in C++20
356*0b57cec5SDimitry Andric    is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
357*0b57cec5SDimitry Andric
358*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
359fe6060f1SDimitry Andric    constexpr void               // constexpr in C++20
360*0b57cec5SDimitry Andric    sort(RandomAccessIterator first, RandomAccessIterator last);
361*0b57cec5SDimitry Andric
362*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
363fe6060f1SDimitry Andric    constexpr void               // constexpr in C++20
364*0b57cec5SDimitry Andric    sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
365*0b57cec5SDimitry Andric
366*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
367*0b57cec5SDimitry Andric    void
368*0b57cec5SDimitry Andric    stable_sort(RandomAccessIterator first, RandomAccessIterator last);
369*0b57cec5SDimitry Andric
370*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
371*0b57cec5SDimitry Andric    void
372*0b57cec5SDimitry Andric    stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
373*0b57cec5SDimitry Andric
374*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
375fe6060f1SDimitry Andric    constexpr void                    // constexpr in C++20
376*0b57cec5SDimitry Andric    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
377*0b57cec5SDimitry Andric
378*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
379fe6060f1SDimitry Andric    constexpr void                    // constexpr in C++20
380*0b57cec5SDimitry Andric    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
381*0b57cec5SDimitry Andric
382*0b57cec5SDimitry Andrictemplate <class InputIterator, class RandomAccessIterator>
383fe6060f1SDimitry Andric    constexpr RandomAccessIterator    // constexpr in C++20
384*0b57cec5SDimitry Andric    partial_sort_copy(InputIterator first, InputIterator last,
385*0b57cec5SDimitry Andric                      RandomAccessIterator result_first, RandomAccessIterator result_last);
386*0b57cec5SDimitry Andric
387*0b57cec5SDimitry Andrictemplate <class InputIterator, class RandomAccessIterator, class Compare>
388fe6060f1SDimitry Andric    constexpr RandomAccessIterator    // constexpr in C++20
389*0b57cec5SDimitry Andric    partial_sort_copy(InputIterator first, InputIterator last,
390*0b57cec5SDimitry Andric                      RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
391*0b57cec5SDimitry Andric
392*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
393fe6060f1SDimitry Andric    constexpr void                    // constexpr in C++20
394*0b57cec5SDimitry Andric    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
395*0b57cec5SDimitry Andric
396*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
397fe6060f1SDimitry Andric    constexpr void                    // constexpr in C++20
398*0b57cec5SDimitry Andric    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
399*0b57cec5SDimitry Andric
400*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
401*0b57cec5SDimitry Andric    constexpr ForwardIterator                         // constexpr in C++20
402*0b57cec5SDimitry Andric    lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
403*0b57cec5SDimitry Andric
404*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T, class Compare>
405*0b57cec5SDimitry Andric    constexpr ForwardIterator                         // constexpr in C++20
406*0b57cec5SDimitry Andric    lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
407*0b57cec5SDimitry Andric
408*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
409*0b57cec5SDimitry Andric    constexpr ForwardIterator                         // constexpr in C++20
410*0b57cec5SDimitry Andric    upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
411*0b57cec5SDimitry Andric
412*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T, class Compare>
413*0b57cec5SDimitry Andric    constexpr ForwardIterator                         // constexpr in C++20
414*0b57cec5SDimitry Andric    upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
415*0b57cec5SDimitry Andric
416*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
417*0b57cec5SDimitry Andric    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
418*0b57cec5SDimitry Andric    equal_range(ForwardIterator first, ForwardIterator last, const T& value);
419*0b57cec5SDimitry Andric
420*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T, class Compare>
421*0b57cec5SDimitry Andric    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
422*0b57cec5SDimitry Andric    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
423*0b57cec5SDimitry Andric
424*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T>
425*0b57cec5SDimitry Andric    constexpr bool                                    // constexpr in C++20
426*0b57cec5SDimitry Andric    binary_search(ForwardIterator first, ForwardIterator last, const T& value);
427*0b57cec5SDimitry Andric
428*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T, class Compare>
429*0b57cec5SDimitry Andric    constexpr bool                                    // constexpr in C++20
430*0b57cec5SDimitry Andric    binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
431*0b57cec5SDimitry Andric
432*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator>
433e8d8bef9SDimitry Andric    constexpr OutputIterator                          // constexpr in C++20
434*0b57cec5SDimitry Andric    merge(InputIterator1 first1, InputIterator1 last1,
435*0b57cec5SDimitry Andric          InputIterator2 first2, InputIterator2 last2, OutputIterator result);
436*0b57cec5SDimitry Andric
437*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
438e8d8bef9SDimitry Andric    constexpr OutputIterator                          // constexpr in C++20
439*0b57cec5SDimitry Andric    merge(InputIterator1 first1, InputIterator1 last1,
440*0b57cec5SDimitry Andric          InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
441*0b57cec5SDimitry Andric
442*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator>
443*0b57cec5SDimitry Andric    void
444*0b57cec5SDimitry Andric    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
445*0b57cec5SDimitry Andric
446*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator, class Compare>
447*0b57cec5SDimitry Andric    void
448*0b57cec5SDimitry Andric    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
449*0b57cec5SDimitry Andric
450*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2>
451*0b57cec5SDimitry Andric    constexpr bool                                    // constexpr in C++20
452*0b57cec5SDimitry Andric    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
453*0b57cec5SDimitry Andric
454*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class Compare>
455*0b57cec5SDimitry Andric    constexpr bool                                    // constexpr in C++20
456*0b57cec5SDimitry Andric    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
457*0b57cec5SDimitry Andric
458*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator>
459e8d8bef9SDimitry Andric    constexpr OutputIterator                          // constexpr in C++20
460*0b57cec5SDimitry Andric    set_union(InputIterator1 first1, InputIterator1 last1,
461*0b57cec5SDimitry Andric              InputIterator2 first2, InputIterator2 last2, OutputIterator result);
462*0b57cec5SDimitry Andric
463*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
464e8d8bef9SDimitry Andric    constexpr OutputIterator                          // constexpr in C++20
465*0b57cec5SDimitry Andric    set_union(InputIterator1 first1, InputIterator1 last1,
466*0b57cec5SDimitry Andric              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
467*0b57cec5SDimitry Andric
468*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator>
469*0b57cec5SDimitry Andric    constexpr OutputIterator                         // constexpr in C++20
470*0b57cec5SDimitry Andric    set_intersection(InputIterator1 first1, InputIterator1 last1,
471*0b57cec5SDimitry Andric                     InputIterator2 first2, InputIterator2 last2, OutputIterator result);
472*0b57cec5SDimitry Andric
473*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
474*0b57cec5SDimitry Andric    constexpr OutputIterator                         // constexpr in C++20
475*0b57cec5SDimitry Andric    set_intersection(InputIterator1 first1, InputIterator1 last1,
476*0b57cec5SDimitry Andric                     InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
477*0b57cec5SDimitry Andric
478*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator>
479e8d8bef9SDimitry Andric    constexpr OutputIterator                         // constexpr in C++20
480*0b57cec5SDimitry Andric    set_difference(InputIterator1 first1, InputIterator1 last1,
481*0b57cec5SDimitry Andric                   InputIterator2 first2, InputIterator2 last2, OutputIterator result);
482*0b57cec5SDimitry Andric
483*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
484e8d8bef9SDimitry Andric    constexpr OutputIterator                         // constexpr in C++20
485*0b57cec5SDimitry Andric    set_difference(InputIterator1 first1, InputIterator1 last1,
486*0b57cec5SDimitry Andric                   InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
487*0b57cec5SDimitry Andric
488*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator>
489e8d8bef9SDimitry Andric    constexpr OutputIterator                         // constexpr in C++20
490*0b57cec5SDimitry Andric    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
491*0b57cec5SDimitry Andric                             InputIterator2 first2, InputIterator2 last2, OutputIterator result);
492*0b57cec5SDimitry Andric
493*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
494e8d8bef9SDimitry Andric    constexpr OutputIterator                         // constexpr in C++20
495*0b57cec5SDimitry Andric    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
496*0b57cec5SDimitry Andric                             InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
497*0b57cec5SDimitry Andric
498*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
499fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
500*0b57cec5SDimitry Andric    push_heap(RandomAccessIterator first, RandomAccessIterator last);
501*0b57cec5SDimitry Andric
502*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
503fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
504*0b57cec5SDimitry Andric    push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
505*0b57cec5SDimitry Andric
506*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
507fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
508*0b57cec5SDimitry Andric    pop_heap(RandomAccessIterator first, RandomAccessIterator last);
509*0b57cec5SDimitry Andric
510*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
511fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
512*0b57cec5SDimitry Andric    pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
513*0b57cec5SDimitry Andric
514*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
515fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
516*0b57cec5SDimitry Andric    make_heap(RandomAccessIterator first, RandomAccessIterator last);
517*0b57cec5SDimitry Andric
518*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
519fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
520*0b57cec5SDimitry Andric    make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
521*0b57cec5SDimitry Andric
522*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
523fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
524*0b57cec5SDimitry Andric    sort_heap(RandomAccessIterator first, RandomAccessIterator last);
525*0b57cec5SDimitry Andric
526*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
527fe6060f1SDimitry Andric    constexpr void                                   // constexpr in C++20
528*0b57cec5SDimitry Andric    sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
529*0b57cec5SDimitry Andric
530*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
531*0b57cec5SDimitry Andric    constexpr bool   // constexpr in C++20
532*0b57cec5SDimitry Andric    is_heap(RandomAccessIterator first, RandomAccessiterator last);
533*0b57cec5SDimitry Andric
534*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
535*0b57cec5SDimitry Andric    constexpr bool   // constexpr in C++20
536*0b57cec5SDimitry Andric    is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
537*0b57cec5SDimitry Andric
538*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator>
539*0b57cec5SDimitry Andric    constexpr RandomAccessIterator   // constexpr in C++20
540*0b57cec5SDimitry Andric    is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
541*0b57cec5SDimitry Andric
542*0b57cec5SDimitry Andrictemplate <class RandomAccessIterator, class Compare>
543*0b57cec5SDimitry Andric    constexpr RandomAccessIterator   // constexpr in C++20
544*0b57cec5SDimitry Andric    is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
545*0b57cec5SDimitry Andric
546*0b57cec5SDimitry Andrictemplate <class ForwardIterator>
547e8d8bef9SDimitry Andric    constexpr ForwardIterator        // constexpr in C++14
548e8d8bef9SDimitry Andric    min_element(ForwardIterator first, ForwardIterator last);
549*0b57cec5SDimitry Andric
550*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Compare>
551e8d8bef9SDimitry Andric    constexpr ForwardIterator        // constexpr in C++14
552e8d8bef9SDimitry Andric    min_element(ForwardIterator first, ForwardIterator last, Compare comp);
553*0b57cec5SDimitry Andric
554*0b57cec5SDimitry Andrictemplate <class T>
555e8d8bef9SDimitry Andric    constexpr const T&               // constexpr in C++14
556e8d8bef9SDimitry Andric    min(const T& a, const T& b);
557*0b57cec5SDimitry Andric
558*0b57cec5SDimitry Andrictemplate <class T, class Compare>
559e8d8bef9SDimitry Andric    constexpr const T&               // constexpr in C++14
560e8d8bef9SDimitry Andric    min(const T& a, const T& b, Compare comp);
561*0b57cec5SDimitry Andric
562*0b57cec5SDimitry Andrictemplate<class T>
563e8d8bef9SDimitry Andric    constexpr T                      // constexpr in C++14
564e8d8bef9SDimitry Andric    min(initializer_list<T> t);
565*0b57cec5SDimitry Andric
566*0b57cec5SDimitry Andrictemplate<class T, class Compare>
567e8d8bef9SDimitry Andric    constexpr T                      // constexpr in C++14
568e8d8bef9SDimitry Andric    min(initializer_list<T> t, Compare comp);
569*0b57cec5SDimitry Andric
570*0b57cec5SDimitry Andrictemplate<class T>
571*0b57cec5SDimitry Andric    constexpr const T& clamp(const T& v, const T& lo, const T& hi);               // C++17
572*0b57cec5SDimitry Andric
573*0b57cec5SDimitry Andrictemplate<class T, class Compare>
574*0b57cec5SDimitry Andric    constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
575*0b57cec5SDimitry Andric
576*0b57cec5SDimitry Andrictemplate <class ForwardIterator>
577e8d8bef9SDimitry Andric    constexpr ForwardIterator        // constexpr in C++14
578e8d8bef9SDimitry Andric    max_element(ForwardIterator first, ForwardIterator last);
579*0b57cec5SDimitry Andric
580*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class Compare>
581e8d8bef9SDimitry Andric    constexpr ForwardIterator        // constexpr in C++14
582e8d8bef9SDimitry Andric    max_element(ForwardIterator first, ForwardIterator last, Compare comp);
583*0b57cec5SDimitry Andric
584*0b57cec5SDimitry Andrictemplate <class T>
585e8d8bef9SDimitry Andric    constexpr const T&               // constexpr in C++14
586e8d8bef9SDimitry Andric    max(const T& a, const T& b);
587*0b57cec5SDimitry Andric
588*0b57cec5SDimitry Andrictemplate <class T, class Compare>
589e8d8bef9SDimitry Andric    constexpr const T&               // constexpr in C++14
590e8d8bef9SDimitry Andric    max(const T& a, const T& b, Compare comp);
591*0b57cec5SDimitry Andric
592*0b57cec5SDimitry Andrictemplate<class T>
593e8d8bef9SDimitry Andric    constexpr T                      // constexpr in C++14
594e8d8bef9SDimitry Andric    max(initializer_list<T> t);
595*0b57cec5SDimitry Andric
596*0b57cec5SDimitry Andrictemplate<class T, class Compare>
597e8d8bef9SDimitry Andric    constexpr T                      // constexpr in C++14
598e8d8bef9SDimitry Andric    max(initializer_list<T> t, Compare comp);
599*0b57cec5SDimitry Andric
600*0b57cec5SDimitry Andrictemplate<class ForwardIterator>
601e8d8bef9SDimitry Andric    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++14
602e8d8bef9SDimitry Andric    minmax_element(ForwardIterator first, ForwardIterator last);
603*0b57cec5SDimitry Andric
604*0b57cec5SDimitry Andrictemplate<class ForwardIterator, class Compare>
605e8d8bef9SDimitry Andric    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++14
606e8d8bef9SDimitry Andric    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
607*0b57cec5SDimitry Andric
608*0b57cec5SDimitry Andrictemplate<class T>
609e8d8bef9SDimitry Andric    constexpr pair<const T&, const T&>  // constexpr in C++14
610e8d8bef9SDimitry Andric    minmax(const T& a, const T& b);
611*0b57cec5SDimitry Andric
612*0b57cec5SDimitry Andrictemplate<class T, class Compare>
613e8d8bef9SDimitry Andric    constexpr pair<const T&, const T&>  // constexpr in C++14
614e8d8bef9SDimitry Andric    minmax(const T& a, const T& b, Compare comp);
615*0b57cec5SDimitry Andric
616*0b57cec5SDimitry Andrictemplate<class T>
617e8d8bef9SDimitry Andric    constexpr pair<T, T>                // constexpr in C++14
618e8d8bef9SDimitry Andric    minmax(initializer_list<T> t);
619*0b57cec5SDimitry Andric
620*0b57cec5SDimitry Andrictemplate<class T, class Compare>
621e8d8bef9SDimitry Andric    constexpr pair<T, T>                // constexpr in C++14
622e8d8bef9SDimitry Andric    minmax(initializer_list<T> t, Compare comp);
623*0b57cec5SDimitry Andric
624*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2>
625*0b57cec5SDimitry Andric    constexpr bool     // constexpr in C++20
626*0b57cec5SDimitry Andric    lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
627*0b57cec5SDimitry Andric
628*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class Compare>
629*0b57cec5SDimitry Andric    constexpr bool     // constexpr in C++20
630*0b57cec5SDimitry Andric    lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
631*0b57cec5SDimitry Andric                            InputIterator2 first2, InputIterator2 last2, Compare comp);
632*0b57cec5SDimitry Andric
633*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator>
634e8d8bef9SDimitry Andric    constexpr bool     // constexpr in C++20
635*0b57cec5SDimitry Andric    next_permutation(BidirectionalIterator first, BidirectionalIterator last);
636*0b57cec5SDimitry Andric
637*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator, class Compare>
638e8d8bef9SDimitry Andric    constexpr bool     // constexpr in C++20
639*0b57cec5SDimitry Andric    next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
640*0b57cec5SDimitry Andric
641*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator>
642e8d8bef9SDimitry Andric    constexpr bool     // constexpr in C++20
643*0b57cec5SDimitry Andric    prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
644*0b57cec5SDimitry Andric
645*0b57cec5SDimitry Andrictemplate <class BidirectionalIterator, class Compare>
646e8d8bef9SDimitry Andric    constexpr bool     // constexpr in C++20
647*0b57cec5SDimitry Andric    prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
648*0b57cec5SDimitry Andric
64904eeddc0SDimitry Andricnamespace ranges {
65004eeddc0SDimitry Andric// [algorithms.results], algorithm result types
65104eeddc0SDimitry Andrictemplate<class InputIterator, class OutputIterator>
65204eeddc0SDimitry Andric    struct in_out_result;
65304eeddc0SDimitry Andric}
65404eeddc0SDimitry Andric
655*0b57cec5SDimitry Andric}  // std
656*0b57cec5SDimitry Andric
657*0b57cec5SDimitry Andric*/
658*0b57cec5SDimitry Andric
65904eeddc0SDimitry Andric#include <__bits> // __libcpp_clz
660*0b57cec5SDimitry Andric#include <__config>
661fe6060f1SDimitry Andric#include <__debug>
662fe6060f1SDimitry Andric#include <cstddef>
663*0b57cec5SDimitry Andric#include <cstring>
664fe6060f1SDimitry Andric#include <functional>
665fe6060f1SDimitry Andric#include <initializer_list>
666*0b57cec5SDimitry Andric#include <iterator>
667fe6060f1SDimitry Andric#include <memory>
668fe6060f1SDimitry Andric#include <type_traits>
669fe6060f1SDimitry Andric#include <utility> // swap_ranges
670*0b57cec5SDimitry Andric#include <version>
671*0b57cec5SDimitry Andric
672fe6060f1SDimitry Andric#include <__algorithm/adjacent_find.h>
673fe6060f1SDimitry Andric#include <__algorithm/all_of.h>
674fe6060f1SDimitry Andric#include <__algorithm/any_of.h>
675fe6060f1SDimitry Andric#include <__algorithm/binary_search.h>
676fe6060f1SDimitry Andric#include <__algorithm/clamp.h>
677fe6060f1SDimitry Andric#include <__algorithm/comp.h>
678fe6060f1SDimitry Andric#include <__algorithm/comp_ref_type.h>
679fe6060f1SDimitry Andric#include <__algorithm/copy.h>
680fe6060f1SDimitry Andric#include <__algorithm/copy_backward.h>
681fe6060f1SDimitry Andric#include <__algorithm/copy_if.h>
682fe6060f1SDimitry Andric#include <__algorithm/copy_n.h>
683fe6060f1SDimitry Andric#include <__algorithm/count.h>
684fe6060f1SDimitry Andric#include <__algorithm/count_if.h>
685fe6060f1SDimitry Andric#include <__algorithm/equal.h>
686fe6060f1SDimitry Andric#include <__algorithm/equal_range.h>
687fe6060f1SDimitry Andric#include <__algorithm/fill.h>
68804eeddc0SDimitry Andric#include <__algorithm/fill_n.h>
689fe6060f1SDimitry Andric#include <__algorithm/find.h>
690fe6060f1SDimitry Andric#include <__algorithm/find_end.h>
691fe6060f1SDimitry Andric#include <__algorithm/find_first_of.h>
692fe6060f1SDimitry Andric#include <__algorithm/find_if.h>
693fe6060f1SDimitry Andric#include <__algorithm/find_if_not.h>
694fe6060f1SDimitry Andric#include <__algorithm/for_each.h>
695fe6060f1SDimitry Andric#include <__algorithm/for_each_n.h>
696fe6060f1SDimitry Andric#include <__algorithm/generate.h>
69704eeddc0SDimitry Andric#include <__algorithm/generate_n.h>
698fe6060f1SDimitry Andric#include <__algorithm/half_positive.h>
69904eeddc0SDimitry Andric#include <__algorithm/in_in_result.h>
70004eeddc0SDimitry Andric#include <__algorithm/in_out_result.h>
701fe6060f1SDimitry Andric#include <__algorithm/includes.h>
702fe6060f1SDimitry Andric#include <__algorithm/inplace_merge.h>
703fe6060f1SDimitry Andric#include <__algorithm/is_heap.h>
704fe6060f1SDimitry Andric#include <__algorithm/is_heap_until.h>
705fe6060f1SDimitry Andric#include <__algorithm/is_partitioned.h>
706fe6060f1SDimitry Andric#include <__algorithm/is_permutation.h>
707fe6060f1SDimitry Andric#include <__algorithm/is_sorted.h>
708fe6060f1SDimitry Andric#include <__algorithm/is_sorted_until.h>
709fe6060f1SDimitry Andric#include <__algorithm/iter_swap.h>
710fe6060f1SDimitry Andric#include <__algorithm/lexicographical_compare.h>
711fe6060f1SDimitry Andric#include <__algorithm/lower_bound.h>
712fe6060f1SDimitry Andric#include <__algorithm/make_heap.h>
713fe6060f1SDimitry Andric#include <__algorithm/max.h>
714fe6060f1SDimitry Andric#include <__algorithm/max_element.h>
715fe6060f1SDimitry Andric#include <__algorithm/merge.h>
716fe6060f1SDimitry Andric#include <__algorithm/min.h>
717fe6060f1SDimitry Andric#include <__algorithm/min_element.h>
718fe6060f1SDimitry Andric#include <__algorithm/minmax.h>
719fe6060f1SDimitry Andric#include <__algorithm/minmax_element.h>
720fe6060f1SDimitry Andric#include <__algorithm/mismatch.h>
721fe6060f1SDimitry Andric#include <__algorithm/move.h>
722fe6060f1SDimitry Andric#include <__algorithm/move_backward.h>
723fe6060f1SDimitry Andric#include <__algorithm/next_permutation.h>
724fe6060f1SDimitry Andric#include <__algorithm/none_of.h>
725fe6060f1SDimitry Andric#include <__algorithm/nth_element.h>
726fe6060f1SDimitry Andric#include <__algorithm/partial_sort.h>
727fe6060f1SDimitry Andric#include <__algorithm/partial_sort_copy.h>
728fe6060f1SDimitry Andric#include <__algorithm/partition.h>
729fe6060f1SDimitry Andric#include <__algorithm/partition_copy.h>
730fe6060f1SDimitry Andric#include <__algorithm/partition_point.h>
731fe6060f1SDimitry Andric#include <__algorithm/pop_heap.h>
732fe6060f1SDimitry Andric#include <__algorithm/prev_permutation.h>
733fe6060f1SDimitry Andric#include <__algorithm/push_heap.h>
734fe6060f1SDimitry Andric#include <__algorithm/remove.h>
735fe6060f1SDimitry Andric#include <__algorithm/remove_copy.h>
736fe6060f1SDimitry Andric#include <__algorithm/remove_copy_if.h>
737fe6060f1SDimitry Andric#include <__algorithm/remove_if.h>
738fe6060f1SDimitry Andric#include <__algorithm/replace.h>
739fe6060f1SDimitry Andric#include <__algorithm/replace_copy.h>
740fe6060f1SDimitry Andric#include <__algorithm/replace_copy_if.h>
741fe6060f1SDimitry Andric#include <__algorithm/replace_if.h>
742fe6060f1SDimitry Andric#include <__algorithm/reverse.h>
743fe6060f1SDimitry Andric#include <__algorithm/reverse_copy.h>
744fe6060f1SDimitry Andric#include <__algorithm/rotate.h>
745fe6060f1SDimitry Andric#include <__algorithm/rotate_copy.h>
746fe6060f1SDimitry Andric#include <__algorithm/sample.h>
747fe6060f1SDimitry Andric#include <__algorithm/search.h>
748fe6060f1SDimitry Andric#include <__algorithm/search_n.h>
749fe6060f1SDimitry Andric#include <__algorithm/set_difference.h>
750fe6060f1SDimitry Andric#include <__algorithm/set_intersection.h>
751fe6060f1SDimitry Andric#include <__algorithm/set_symmetric_difference.h>
752fe6060f1SDimitry Andric#include <__algorithm/set_union.h>
753fe6060f1SDimitry Andric#include <__algorithm/shift_left.h>
754fe6060f1SDimitry Andric#include <__algorithm/shift_right.h>
755fe6060f1SDimitry Andric#include <__algorithm/shuffle.h>
756fe6060f1SDimitry Andric#include <__algorithm/sift_down.h>
757fe6060f1SDimitry Andric#include <__algorithm/sort.h>
758fe6060f1SDimitry Andric#include <__algorithm/sort_heap.h>
759fe6060f1SDimitry Andric#include <__algorithm/stable_partition.h>
760fe6060f1SDimitry Andric#include <__algorithm/stable_sort.h>
761fe6060f1SDimitry Andric#include <__algorithm/swap_ranges.h>
762fe6060f1SDimitry Andric#include <__algorithm/transform.h>
763fe6060f1SDimitry Andric#include <__algorithm/unique.h>
76404eeddc0SDimitry Andric#include <__algorithm/unique_copy.h>
765fe6060f1SDimitry Andric#include <__algorithm/unwrap_iter.h>
766fe6060f1SDimitry Andric#include <__algorithm/upper_bound.h>
767*0b57cec5SDimitry Andric
768*0b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
769*0b57cec5SDimitry Andric#pragma GCC system_header
770*0b57cec5SDimitry Andric#endif
771*0b57cec5SDimitry Andric
772e40139ffSDimitry Andric#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
773e40139ffSDimitry Andric#   include <__pstl_algorithm>
774e40139ffSDimitry Andric#endif
775e40139ffSDimitry Andric
776*0b57cec5SDimitry Andric#endif // _LIBCPP_ALGORITHM
777