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