1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // <queue>
10 // UNSUPPORTED: c++03, c++11, c++14
11 
12 // template<class Compare, class Container>
13 // priority_queue(Compare, Container)
14 //     -> priority_queue<typename Container::value_type, Container, Compare>;
15 //
16 // template<class InputIterator,
17 //          class Compare = less<typename iterator_traits<InputIterator>::value_type>,
18 //          class Container = vector<typename iterator_traits<InputIterator>::value_type>>
19 // priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
20 //     -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>;
21 //
22 // template<class Compare, class Container, class Allocator>
23 // priority_queue(Compare, Container, Allocator)
24 //     -> priority_queue<typename Container::value_type, Container, Compare>;
25 //
26 // template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>>
27 //   priority_queue(from_range_t, R&&, Compare = Compare())
28 //     -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>>, Compare>; // C++23
29 //
30 // template<ranges::input_range R, class Compare, class Allocator>
31 //   priority_queue(from_range_t, R&&, Compare, Allocator)
32 //     -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>,
33 //                         Compare>; // C++23
34 //
35 // template<ranges::input_range R, class Allocator>
36 //   priority_queue(from_range_t, R&&, Allocator)
37 //     -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>>; // C++23
38 
39 #include <cassert>
40 #include <climits> // INT_MAX
41 #include <cstddef>
42 #include <iterator>
43 #include <queue>
44 #include <vector>
45 
46 #include "deduction_guides_sfinae_checks.h"
47 #include "test_macros.h"
48 #include "test_iterators.h"
49 #include "test_allocator.h"
50 
51 struct A {};
52 
53 int main(int, char**)
54 {
55 
56 //  Test the explicit deduction guides
57     {
58     std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
59     std::priority_queue pri(std::greater<int>(), v); // priority_queue(Compare, Container)
60 
61     static_assert(std::is_same_v<decltype(pri), std::priority_queue<int, std::vector<int>, std::greater<int>>>, "");
62     assert(pri.size() == v.size());
63     assert(pri.top() == 0);
64     }
65 
66     {
67     std::vector<long, test_allocator<long>> v{10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
68     std::priority_queue pri(std::greater<long>(), v, test_allocator<long>(2)); // priority_queue(Compare, Container, Allocator)
69 
70     static_assert(std::is_same_v<decltype(pri),
71                                  std::priority_queue<long, std::vector<long, test_allocator<long>>, std::greater<long>>>, "");
72     assert(pri.size() == v.size());
73     assert(pri.top() == 10);
74     }
75 
76     {
77     std::vector<short> v{10, 11, 12, 13, 14, 15, 28, 17, 18, 19 };
78     std::priority_queue pri(v.begin(), v.end()); // priority_queue(Iter, Iter)
79 
80     static_assert(std::is_same_v<decltype(pri), std::priority_queue<short>>, "");
81     assert(pri.size() == v.size());
82     assert(pri.top() == 28);
83     }
84 
85     {
86     std::vector<double> v{10, 11, 12, 13, 6, 15, 28, 17, 18, 19 };
87     std::priority_queue pri(v.begin(), v.end(), std::greater<double>()); // priority_queue(Iter, Iter, Comp)
88 
89     static_assert(std::is_same_v<decltype(pri), std::priority_queue<double, std::vector<double>, std::greater<double>>>, "");
90     assert(pri.size() == v.size());
91     assert(pri.top() == 6);
92     }
93 
94     {
95     std::vector<double> v{10, 6, 15, 28, 4, 18, 19 };
96     std::deque<double> deq;
97     std::priority_queue pri(v.begin(), v.end(), std::greater<double>(), deq); // priority_queue(Iter, Iter, Comp, Container)
98 
99     static_assert(std::is_same_v<decltype(pri), std::priority_queue<double, std::deque<double>, std::greater<double>>>, "");
100     assert(pri.size() == v.size());
101     assert(pri.top() == 4);
102     }
103 
104 //  Test the implicit deduction guides
105     {
106 //  We don't expect this one to work - no way to implicitly get value_type
107 //  std::priority_queue pri(std::allocator<int>()); // queue (allocator &)
108     }
109 
110     {
111     std::priority_queue<float> source;
112     std::priority_queue pri(source); // priority_queue(priority_queue &)
113     static_assert(std::is_same_v<decltype(pri)::value_type, float>, "");
114     static_assert(std::is_same_v<decltype(pri)::container_type, std::vector<float>>, "");
115     assert(pri.size() == 0);
116     }
117 
118     {
119         typedef short T;
120         typedef std::greater<T> Comp;
121         typedef test_allocator<T> Alloc;
122         typedef std::deque<T, Alloc> Cont;
123         typedef test_allocator<int> ConvertibleToAlloc;
124         static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
125                       !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
126 
127         {
128         Comp comp;
129         Cont cont;
130         std::priority_queue pri(comp, cont, Alloc(2));
131         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
132         }
133 
134         {
135         Comp comp;
136         Cont cont;
137         std::priority_queue pri(comp, cont, ConvertibleToAlloc(2));
138         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
139         }
140 
141         {
142         Comp comp;
143         Cont cont;
144         std::priority_queue pri(comp, std::move(cont), Alloc(2));
145         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
146         }
147 
148         {
149         Comp comp;
150         Cont cont;
151         std::priority_queue pri(comp, std::move(cont), ConvertibleToAlloc(2));
152         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
153         }
154     }
155 
156     {
157         typedef short T;
158         typedef signed char ConvertibleToT;
159         typedef std::greater<T> Comp;
160         typedef test_allocator<T> Alloc;
161         typedef std::deque<T, Alloc> Cont;
162         typedef test_allocator<int> ConvertibleToAlloc;
163         static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
164                       !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
165 
166         {
167         std::priority_queue<T, Cont, Comp> source;
168         std::priority_queue pri(source, Alloc(2));
169         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
170         }
171 
172         {
173         std::priority_queue<T, Cont, Comp> source;
174         std::priority_queue pri(source, ConvertibleToAlloc(2));
175         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
176         }
177 
178         {
179         std::priority_queue<T, Cont, Comp> source;
180         std::priority_queue pri(std::move(source), Alloc(2));
181         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
182         }
183 
184         {
185         std::priority_queue<T, Cont, Comp> source;
186         std::priority_queue pri(std::move(source), ConvertibleToAlloc(2));
187         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
188         }
189 
190         {
191         Cont cont;
192         std::priority_queue pri(Comp(), cont, Alloc(2));
193         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
194         }
195 
196         {
197         Cont cont;
198         std::priority_queue pri(Comp(), cont, ConvertibleToAlloc(2));
199         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
200         }
201 
202         {
203         Cont cont;
204         std::priority_queue pri(Comp(), std::move(cont), Alloc(2));
205         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
206         }
207 
208         {
209         Cont cont;
210         std::priority_queue pri(Comp(), std::move(cont), ConvertibleToAlloc(2));
211         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
212         }
213 
214         {
215         T a[2] = {};
216         std::priority_queue pri(a, a+2, Alloc(2));
217         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>>>);
218         }
219 
220         {
221         T a[2] = {};
222         std::priority_queue pri(a, a+2, Comp(), Alloc(2));
223         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>, Comp>>);
224         }
225 
226         {
227         Cont cont;
228         ConvertibleToT a[2] = {};
229         std::priority_queue pri(a, a+2, Comp(), cont, Alloc(2));
230         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
231         }
232 
233         {
234         Cont cont;
235         ConvertibleToT a[2] = {};
236         std::priority_queue pri(a, a+2, Comp(), cont, ConvertibleToAlloc(2));
237         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
238         }
239 
240         {
241         Cont cont;
242         ConvertibleToT a[2] = {};
243         std::priority_queue pri(a, a+2, Comp(), std::move(cont), Alloc(2));
244         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
245         }
246 
247         {
248         Cont cont;
249         ConvertibleToT a[2] = {};
250         std::priority_queue pri(a, a+2, Comp(), std::move(cont), ConvertibleToAlloc(2));
251         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
252         }
253 
254 #if TEST_STD_VER >= 23
255         { // (from_range, range)
256           std::priority_queue c(std::from_range, Cont());
257           static_assert(std::is_same_v<decltype(c), std::priority_queue<T>>);
258         }
259 
260         { // (from_range, range, compare)
261           std::priority_queue c(std::from_range, Cont(), Comp());
262           static_assert(std::is_same_v<decltype(c), std::priority_queue<T, std::vector<T>, Comp>>);
263         }
264 
265         { // (from_range, range, compare, alloc)
266           std::priority_queue c(std::from_range, Cont(), Comp(), Alloc(2));
267           static_assert(std::is_same_v<decltype(c), std::priority_queue<T, std::vector<T, Alloc>, Comp>>);
268         }
269 
270         { // (from_range, range, alloc)
271           std::priority_queue c(std::from_range, Cont(), Alloc(2));
272           static_assert(std::is_same_v<decltype(c), std::priority_queue<T, std::vector<T, Alloc>>>);
273         }
274 #endif // TEST_STD_VER >= 23
275     }
276 
277     // Deduction guides should be SFINAE'd away when given:
278     // - "bad" input iterators (that is, a type not qualifying as an input
279     //   iterator);
280     // - a bad allocator;
281     // - an allocator instead of a comparator;
282     // - an allocator instead of a container;
283     // - an allocator and a container that uses a different allocator.
284     {
285         using Comp = std::less<int>;
286         using Cont = std::vector<int>;
287         using Alloc = std::allocator<int>;
288         using Iter = int*;
289 
290         // The only requirement in the Standard is that integral types cannot be
291         // considered input iterators, beyond that it is unspecified.
292         using BadIter = int;
293 #ifdef _LIBCPP_VERSION
294         struct OutputIter {
295           using iterator_category = std::output_iterator_tag;
296           using value_type = void;
297           using difference_type = void;
298           using pointer = void;
299           using reference = void;
300 
301           const OutputIter& operator*() const { return *this; }
302           const OutputIter& operator++() { return *this; }
303           OutputIter operator++(int) const { return *this; }
304         };
305 #endif // _LIBCPP_VERSION
306 
307         struct BadAlloc {};
308         using AllocAsComp = Alloc;
309         using AllocAsCont = Alloc;
310         using DiffAlloc = test_allocator<int>;
311 
312         // (iter, iter)
313         //
314         // Cannot deduce from (BAD_iter, BAD_iter)
315         static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter>);
316         // Note: (OutputIter, OutputIter) is interpreted as (comp, cont) and fails on accessing
317         // non-existent typedefs in `OutputIter` (as if it were a container). There is no
318         // requirement to SFINAE away bad containers.
319 
320         // (iter, iter, comp)
321         //
322         // Cannot deduce from (BAD_iter, BAD_iter, comp)
323         static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Comp>);
324         LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Comp>);
325         // Note: (iter, iter, ALLOC_as_comp) is allowed -- it just calls (iter, iter, alloc).
326 
327         // (iter, iter, comp, cont)
328         //
329         // Cannot deduce from (BAD_iter, BAD_iter, comp, cont)
330         static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Comp, Cont>);
331         LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Comp, Cont>);
332         // Cannot deduce from (iter, iter, ALLOC_as_comp, cont)
333         static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, AllocAsComp, Cont>);
334         // Note: (iter, iter, comp, ALLOC_as_cont) is allowed -- it just calls (iter, iter, comp,
335         // alloc).
336 
337         // (iter, iter, alloc)
338         //
339         // Cannot deduce from (BAD_iter, BAD_iter, alloc)
340         static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Alloc>);
341         LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Alloc>);
342         // Note: (iter, iter, BAD_alloc) is interpreted as (iter, iter, comp) instead and fails upon
343         // instantiation. There is no requirement to SFINAE away bad comparators.
344 
345         // (iter, iter, comp, alloc)
346         //
347         // Cannot deduce from (iter, iter, ALLOC_as_comp, alloc)
348         static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, AllocAsComp, Alloc>);
349         // Note: (iter, iter, comp, BAD_alloc) is interpreted as (iter, iter, comp, cont) instead
350         // and fails upon instantiation. There is no requirement to SFINAE away bad containers.
351 
352         // (iter, iter, comp, cont, alloc)
353         //
354         // Cannot deduce from (BAD_iter, BAD_iter, comp, cont, alloc)
355         static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Comp, Cont, Alloc>);
356         LIBCPP_STATIC_ASSERT(
357             SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Comp, Cont, Alloc>);
358         // Cannot deduce from (iter, iter, ALLOC_as_comp, cont, alloc)
359         static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, AllocAsComp, Cont, Alloc>);
360         // Cannot deduce from (iter, iter, comp, ALLOC_as_cont, alloc)
361         static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, Comp, AllocAsCont, Alloc>);
362         // Cannot deduce from (iter, iter, comp, cont, BAD_alloc)
363         static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, Comp, Cont, BadAlloc>);
364         // Cannot deduce from (iter, iter, comp, cont, DIFFERENT_alloc)
365         static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, Comp, Cont, DiffAlloc>);
366 
367         // (comp, alloc)
368         //
369         // Cannot deduce from (ALLOC_as_comp, alloc)
370         static_assert(SFINAEs_away<std::priority_queue, AllocAsComp, Alloc>);
371         // Cannot deduce from (comp, BAD_alloc)
372         static_assert(SFINAEs_away<std::priority_queue, Comp, BadAlloc>);
373 
374         // (comp, cont, alloc)
375         //
376         // Cannot deduce from (ALLOC_as_comp, cont, alloc)
377         static_assert(SFINAEs_away<std::priority_queue, AllocAsComp, Cont, Alloc>);
378         // Cannot deduce from (comp, ALLOC_as_cont, alloc)
379         static_assert(SFINAEs_away<std::priority_queue, Comp, AllocAsCont, Alloc>);
380         // Cannot deduce from (comp, cont, BAD_alloc)
381         static_assert(SFINAEs_away<std::priority_queue, Comp, Cont, BadAlloc>);
382         // Cannot deduce from (comp, cont, DIFFERENT_alloc)
383         static_assert(SFINAEs_away<std::priority_queue, Comp, Cont, DiffAlloc>);
384 
385         // (comp, cont)
386         //
387         // Cannot deduce from (ALLOC_as_comp, cont)
388         static_assert(SFINAEs_away<std::priority_queue, AllocAsComp, Cont>);
389         // Cannot deduce from (comp, ALLOC_as_cont)
390         static_assert(SFINAEs_away<std::priority_queue, Comp, AllocAsCont>);
391 
392 #if TEST_STD_VER >= 23
393         using Range = RangeT<int>;
394         using BadRange = BadRangeT<int>;
395 
396         // (from_range, range)
397         //
398         // Cannot deduce from (from_range, BAD_range)
399         static_assert(SFINAEs_away<std::priority_queue, BadRange>);
400 
401         // (from_range, range, compare)
402         //
403         // Cannot deduce from (from_range, BAD_range, compare)
404         static_assert(SFINAEs_away<std::priority_queue, BadRange, Comp>);
405 
406         // (from_range, range, compare, alloc)
407         //
408         // Cannot deduce from (from_range, BAD_range, compare, alloc)
409         static_assert(SFINAEs_away<std::priority_queue, BadRange, Comp, Alloc>);
410         // Cannot deduce from (from_range, range, compare, BAD_alloc)
411         static_assert(SFINAEs_away<std::priority_queue, Range, Comp, BadAlloc>);
412         // Cannot deduce from (from_range, range, compare, DIFFERENT_alloc)
413         static_assert(SFINAEs_away<std::priority_queue, Range, Comp, DiffAlloc>);
414 
415         // (from_range, range, alloc)
416         //
417         // Cannot deduce from (from_range, BAD_range, alloc)
418         static_assert(SFINAEs_away<std::priority_queue, BadRange, Alloc>);
419         // Cannot deduce from (from_range, range, BAD_alloc)
420         static_assert(SFINAEs_away<std::priority_queue, Range, BadAlloc>);
421         // Cannot deduce from (from_range, range, DIFFERENT_alloc)
422         static_assert(SFINAEs_away<std::priority_queue, Range, DiffAlloc>);
423 #endif // TEST_STD_VER >= 23
424     }
425 
426     return 0;
427 }
428