433 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++1410// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME11 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++2331//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++2336//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++2340 41#include <cassert>42#include <climits> // INT_MAX43#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 53struct A {};54 55int main(int, char**) {56 // Test the explicit deduction guides57 {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(69 std::greater<long>(), v, test_allocator<long>(2)); // priority_queue(Compare, Container, Allocator)70 71 static_assert(72 std::is_same_v<decltype(pri),73 std::priority_queue<long, std::vector<long, test_allocator<long>>, std::greater<long>>>,74 "");75 assert(pri.size() == v.size());76 assert(pri.top() == 10);77 }78 79 {80 std::vector<short> v{10, 11, 12, 13, 14, 15, 28, 17, 18, 19};81 std::priority_queue pri(v.begin(), v.end()); // priority_queue(Iter, Iter)82 83 static_assert(std::is_same_v<decltype(pri), std::priority_queue<short>>, "");84 assert(pri.size() == v.size());85 assert(pri.top() == 28);86 }87 88 {89 std::vector<double> v{10, 11, 12, 13, 6, 15, 28, 17, 18, 19};90 std::priority_queue pri(v.begin(), v.end(), std::greater<double>()); // priority_queue(Iter, Iter, Comp)91 92 static_assert(93 std::is_same_v<decltype(pri), std::priority_queue<double, std::vector<double>, std::greater<double>>>, "");94 assert(pri.size() == v.size());95 assert(pri.top() == 6);96 }97 98 {99 std::vector<double> v{10, 6, 15, 28, 4, 18, 19};100 std::deque<double> deq;101 std::priority_queue pri(102 v.begin(), v.end(), std::greater<double>(), deq); // priority_queue(Iter, Iter, Comp, Container)103 104 static_assert(105 std::is_same_v<decltype(pri), std::priority_queue<double, std::deque<double>, std::greater<double>>>, "");106 assert(pri.size() == v.size());107 assert(pri.top() == 4);108 }109 110 // Test the implicit deduction guides111 {112 // We don't expect this one to work - no way to implicitly get value_type113 // std::priority_queue pri(std::allocator<int>()); // queue (allocator &)114 }115 116 {117 std::priority_queue<float> source;118 std::priority_queue pri(source); // priority_queue(priority_queue &)119 static_assert(std::is_same_v<decltype(pri)::value_type, float>, "");120 static_assert(std::is_same_v<decltype(pri)::container_type, std::vector<float>>, "");121 assert(pri.size() == 0);122 }123 124 {125 typedef short T;126 typedef std::greater<T> Comp;127 typedef test_allocator<T> Alloc;128 typedef std::deque<T, Alloc> Cont;129 typedef test_allocator<int> ConvertibleToAlloc;130 static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&131 !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);132 133 {134 Comp comp;135 Cont cont;136 std::priority_queue pri(comp, cont, Alloc(2));137 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);138 }139 140 {141 Comp comp;142 Cont cont;143 std::priority_queue pri(comp, cont, ConvertibleToAlloc(2));144 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);145 }146 147 {148 Comp comp;149 Cont cont;150 std::priority_queue pri(comp, std::move(cont), Alloc(2));151 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);152 }153 154 {155 Comp comp;156 Cont cont;157 std::priority_queue pri(comp, std::move(cont), ConvertibleToAlloc(2));158 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);159 }160 }161 162 {163 typedef short T;164 typedef signed char ConvertibleToT;165 typedef std::greater<T> Comp;166 typedef test_allocator<T> Alloc;167 typedef std::deque<T, Alloc> Cont;168 typedef test_allocator<int> ConvertibleToAlloc;169 static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&170 !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);171 172 {173 std::priority_queue<T, Cont, Comp> source;174 std::priority_queue pri(source, Alloc(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(source, ConvertibleToAlloc(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), Alloc(2));187 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);188 }189 190 {191 std::priority_queue<T, Cont, Comp> source;192 std::priority_queue pri(std::move(source), ConvertibleToAlloc(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, Alloc(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(), cont, ConvertibleToAlloc(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), Alloc(2));211 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);212 }213 214 {215 Cont cont;216 std::priority_queue pri(Comp(), std::move(cont), ConvertibleToAlloc(2));217 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);218 }219 220 {221 T a[2] = {};222 std::priority_queue pri(a, a + 2, Alloc(2));223 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>>>);224 }225 226 {227 T a[2] = {};228 std::priority_queue pri(a, a + 2, Comp(), Alloc(2));229 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>, Comp>>);230 }231 232 {233 Cont cont;234 ConvertibleToT a[2] = {};235 std::priority_queue pri(a, a + 2, Comp(), cont, Alloc(2));236 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);237 }238 239 {240 Cont cont;241 ConvertibleToT a[2] = {};242 std::priority_queue pri(a, a + 2, Comp(), cont, ConvertibleToAlloc(2));243 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);244 }245 246 {247 Cont cont;248 ConvertibleToT a[2] = {};249 std::priority_queue pri(a, a + 2, Comp(), std::move(cont), Alloc(2));250 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);251 }252 253 {254 Cont cont;255 ConvertibleToT a[2] = {};256 std::priority_queue pri(a, a + 2, Comp(), std::move(cont), ConvertibleToAlloc(2));257 static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);258 }259 260#if TEST_STD_VER >= 23261 { // (from_range, range)262 std::priority_queue c(std::from_range, Cont());263 static_assert(std::is_same_v<decltype(c), std::priority_queue<T>>);264 }265 266 { // (from_range, range, compare)267 std::priority_queue c(std::from_range, Cont(), Comp());268 static_assert(std::is_same_v<decltype(c), std::priority_queue<T, std::vector<T>, Comp>>);269 }270 271 { // (from_range, range, compare, alloc)272 std::priority_queue c(std::from_range, Cont(), Comp(), Alloc(2));273 static_assert(std::is_same_v<decltype(c), std::priority_queue<T, std::vector<T, Alloc>, Comp>>);274 }275 276 { // (from_range, range, alloc)277 std::priority_queue c(std::from_range, Cont(), Alloc(2));278 static_assert(std::is_same_v<decltype(c), std::priority_queue<T, std::vector<T, Alloc>>>);279 }280#endif // TEST_STD_VER >= 23281 }282 283 // Deduction guides should be SFINAE'd away when given:284 // - "bad" input iterators (that is, a type not qualifying as an input285 // iterator);286 // - a bad allocator;287 // - an allocator instead of a comparator;288 // - an allocator instead of a container;289 // - an allocator and a container that uses a different allocator.290 {291 using Comp = std::less<int>;292 using Cont = std::vector<int>;293 using Alloc = std::allocator<int>;294 using Iter = int*;295 296 // The only requirement in the Standard is that integral types cannot be297 // considered input iterators, beyond that it is unspecified.298 using BadIter = int;299#ifdef _LIBCPP_VERSION300 struct OutputIter {301 using iterator_category = std::output_iterator_tag;302 using value_type = void;303 using difference_type = void;304 using pointer = void;305 using reference = void;306 307 const OutputIter& operator*() const { return *this; }308 const OutputIter& operator++() { return *this; }309 OutputIter operator++(int) const { return *this; }310 };311#endif // _LIBCPP_VERSION312 313 struct BadAlloc {};314 using AllocAsComp = Alloc;315 using AllocAsCont = Alloc;316 using DiffAlloc = test_allocator<int>;317 318 // (iter, iter)319 //320 // Cannot deduce from (BAD_iter, BAD_iter)321 static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter>);322 // Note: (OutputIter, OutputIter) is interpreted as (comp, cont) and fails on accessing323 // non-existent typedefs in `OutputIter` (as if it were a container). There is no324 // requirement to SFINAE away bad containers.325 326 // (iter, iter, comp)327 //328 // Cannot deduce from (BAD_iter, BAD_iter, comp)329 static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Comp>);330 LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Comp>);331 // Note: (iter, iter, ALLOC_as_comp) is allowed -- it just calls (iter, iter, alloc).332 333 // (iter, iter, comp, cont)334 //335 // Cannot deduce from (BAD_iter, BAD_iter, comp, cont)336 static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Comp, Cont>);337 LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Comp, Cont>);338 // Cannot deduce from (iter, iter, ALLOC_as_comp, cont)339 static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, AllocAsComp, Cont>);340 // Note: (iter, iter, comp, ALLOC_as_cont) is allowed -- it just calls (iter, iter, comp,341 // alloc).342 343 // (iter, iter, alloc)344 //345 // Cannot deduce from (BAD_iter, BAD_iter, alloc)346 static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Alloc>);347 LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Alloc>);348 // Note: (iter, iter, BAD_alloc) is interpreted as (iter, iter, comp) instead and fails upon349 // instantiation. There is no requirement to SFINAE away bad comparators.350 351 // (iter, iter, comp, alloc)352 //353 // Cannot deduce from (iter, iter, ALLOC_as_comp, alloc)354 static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, AllocAsComp, Alloc>);355 // Note: (iter, iter, comp, BAD_alloc) is interpreted as (iter, iter, comp, cont) instead356 // and fails upon instantiation. There is no requirement to SFINAE away bad containers.357 358 // (iter, iter, comp, cont, alloc)359 //360 // Cannot deduce from (BAD_iter, BAD_iter, comp, cont, alloc)361 static_assert(SFINAEs_away<std::priority_queue, BadIter, BadIter, Comp, Cont, Alloc>);362 LIBCPP_STATIC_ASSERT(SFINAEs_away<std::priority_queue, OutputIter, OutputIter, Comp, Cont, Alloc>);363 // Cannot deduce from (iter, iter, ALLOC_as_comp, cont, alloc)364 static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, AllocAsComp, Cont, Alloc>);365 // Cannot deduce from (iter, iter, comp, ALLOC_as_cont, alloc)366 static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, Comp, AllocAsCont, Alloc>);367 // Cannot deduce from (iter, iter, comp, cont, BAD_alloc)368 static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, Comp, Cont, BadAlloc>);369 // Cannot deduce from (iter, iter, comp, cont, DIFFERENT_alloc)370 static_assert(SFINAEs_away<std::priority_queue, Iter, Iter, Comp, Cont, DiffAlloc>);371 372 // (comp, alloc)373 //374 // Cannot deduce from (ALLOC_as_comp, alloc)375 static_assert(SFINAEs_away<std::priority_queue, AllocAsComp, Alloc>);376 // Cannot deduce from (comp, BAD_alloc)377 static_assert(SFINAEs_away<std::priority_queue, Comp, BadAlloc>);378 379 // (comp, cont, alloc)380 //381 // Cannot deduce from (ALLOC_as_comp, cont, alloc)382 static_assert(SFINAEs_away<std::priority_queue, AllocAsComp, Cont, Alloc>);383 // Cannot deduce from (comp, ALLOC_as_cont, alloc)384 static_assert(SFINAEs_away<std::priority_queue, Comp, AllocAsCont, Alloc>);385 // Cannot deduce from (comp, cont, BAD_alloc)386 static_assert(SFINAEs_away<std::priority_queue, Comp, Cont, BadAlloc>);387 // Cannot deduce from (comp, cont, DIFFERENT_alloc)388 static_assert(SFINAEs_away<std::priority_queue, Comp, Cont, DiffAlloc>);389 390 // (comp, cont)391 //392 // Cannot deduce from (ALLOC_as_comp, cont)393 static_assert(SFINAEs_away<std::priority_queue, AllocAsComp, Cont>);394 // Cannot deduce from (comp, ALLOC_as_cont)395 static_assert(SFINAEs_away<std::priority_queue, Comp, AllocAsCont>);396 397#if TEST_STD_VER >= 23398 using Range = RangeT<int>;399 using BadRange = BadRangeT<int>;400 401 // (from_range, range)402 //403 // Cannot deduce from (from_range, BAD_range)404 static_assert(SFINAEs_away<std::priority_queue, BadRange>);405 406 // (from_range, range, compare)407 //408 // Cannot deduce from (from_range, BAD_range, compare)409 static_assert(SFINAEs_away<std::priority_queue, BadRange, Comp>);410 411 // (from_range, range, compare, alloc)412 //413 // Cannot deduce from (from_range, BAD_range, compare, alloc)414 static_assert(SFINAEs_away<std::priority_queue, BadRange, Comp, Alloc>);415 // Cannot deduce from (from_range, range, compare, BAD_alloc)416 static_assert(SFINAEs_away<std::priority_queue, Range, Comp, BadAlloc>);417 // Cannot deduce from (from_range, range, compare, DIFFERENT_alloc)418 static_assert(SFINAEs_away<std::priority_queue, Range, Comp, DiffAlloc>);419 420 // (from_range, range, alloc)421 //422 // Cannot deduce from (from_range, BAD_range, alloc)423 static_assert(SFINAEs_away<std::priority_queue, BadRange, Alloc>);424 // Cannot deduce from (from_range, range, BAD_alloc)425 static_assert(SFINAEs_away<std::priority_queue, Range, BadAlloc>);426 // Cannot deduce from (from_range, range, DIFFERENT_alloc)427 static_assert(SFINAEs_away<std::priority_queue, Range, DiffAlloc>);428#endif // TEST_STD_VER >= 23429 }430 431 return 0;432}433