libcxx/test/std/containers/unord/from_range_unordered_containers.h

   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 #ifndef SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H
  10 #define SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H
  11
  12 #include <algorithm>
  13 #include <cassert>
  14 #include <cmath>
  15 #include <cstddef>
  16 #include <limits>
  17 #include <ranges>
  18 #include <vector>
  19 #include <utility>
  20
  21 #include "../exception_safety_helpers.h"
  22 #include "../from_range_helpers.h"
  23 #include "../test_compare.h"
  24 #include "../test_hash.h"
  25 #include "MoveOnly.h"
  26 #include "almost_satisfies_types.h"
  27 #include "count_new.h"
  28 #include "test_macros.h"
  29
  30 // template<container-compatible-range<value_type> R>
  31 //   unordered-container(from_range_t, R&& rg, size_type n = see below,
  32 //     const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  33 //     const allocator_type& a = allocator_type()); // C++23
  34 //
  35 // template<container-compatible-range<value_type> R>
  36 //   unordered-container(from_range_t, R&& rg, size_type n, const allocator_type& a)
  37 //     : unordered-container(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
  38 //
  39 // template<container-compatible-range<value_type> R>
  40 //   unordered-container(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
  41 //     : unordered-container(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
  42
  43 template <class Container, class Range>
  44 concept HasFromRangeCtr = requires (Range&& range) {
  45   // (from_range, range)
  46   Container(std::from_range, std::forward<Range>(range));
  47   // (from_range, range, n)
  48   Container(std::from_range, std::forward<Range>(range), 0);
  49   // (from_range, range, n, hash)
  50   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>());
  51   // (from_range, range, n, hash, equal)
  52   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(),
  53             std::equal_to<typename Container::key_type>());
  54   // (from_range, range, n, hash, equal, alloc)
  55   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(),
  56             std::equal_to<typename Container::key_type>(), std::allocator<typename Container::value_type>());
  57   // (from_range, range, n, alloc)
  58   Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>());
  59   // (from_range, range, n, hash, alloc)
  60   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(),
  61             std::allocator<typename Container::value_type>());
  62 };
  63
  64 template <template <class...> class Container, class K, class V, class K2, class V2>
  65 constexpr bool test_map_constraints() {
  66   using ValueType = std::pair<const K, V>;
  67
  68   // Input range with the same value type.
  69   static_assert(HasFromRangeCtr<Container<K, V>, InputRange<ValueType>>);
  70   // Input range with a convertible value type.
  71   static_assert(HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K2, V2>>>);
  72   // Input range with a non-convertible value type.
  73   static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const Empty, V>>>);
  74   static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K, Empty>>>);
  75   // Not an input range.
  76   static_assert(!HasFromRangeCtr<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>);
  77
  78   return true;
  79 }
  80
  81 template <template <class ...> class Container,
  82           class K,
  83           class V,
  84           class Iter,
  85           class Sent,
  86           class Hash,
  87           class Equal,
  88           class Alloc,
  89           class ValueType = std::pair<const K, V>>
  90 void test_unordered_map_with_input(std::vector<ValueType>&& input) {
  91   using DefaultHash = std::hash<int>;
  92   using DefaultEqual = std::equal_to<int>;
  93
  94   auto validate = [](auto&& c) {
  95     if (!c.empty()) {
  96       auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count());
  97       assert(std::fabs(diff) < std::numeric_limits<float>::epsilon());
  98     }
  99     assert(c.max_load_factor() == 1);
 100   };
 101
 102   auto in = wrap_input<Iter, Sent>(input);
 103
 104   { // (range)
 105     Container<K, V> c(std::from_range, in);
 106
 107     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 108     assert(std::ranges::is_permutation(input, c));
 109     validate(c);
 110   }
 111
 112   { // (range, n)
 113     Container<K, V> c(std::from_range, in, 123);
 114
 115     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 116     assert(std::ranges::is_permutation(input, c));
 117     validate(c);
 118   }
 119
 120   { // (range, n, hasher)
 121     Container<K, V, Hash> c(std::from_range, in, 123, Hash());
 122
 123     assert(c.hash_function() == Hash());
 124     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 125     assert(std::ranges::is_permutation(input, c));
 126     validate(c);
 127   }
 128
 129   { // (range, n, hasher, key_equal)
 130     Container<K, V, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal());
 131
 132     assert(c.hash_function() == Hash());
 133     assert(c.key_eq() == Equal());
 134     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 135     assert(std::ranges::is_permutation(input, c));
 136     validate(c);
 137   }
 138
 139   { // (range, n, hasher, key_equal, allocator)
 140     Alloc alloc;
 141     Container<K, V, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc);
 142
 143     assert(c.hash_function() == Hash());
 144     assert(c.key_eq() == Equal());
 145     assert(c.get_allocator() == alloc);
 146     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 147     assert(std::ranges::is_permutation(input, c));
 148     validate(c);
 149   }
 150
 151   { // (range, n, allocator)
 152     Alloc alloc;
 153     Container<K, V, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc);
 154
 155     assert(c.get_allocator() == alloc);
 156     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 157     assert(std::ranges::is_permutation(input, c));
 158     validate(c);
 159   }
 160
 161   { // (range, n, hasher, allocator)
 162     Alloc alloc;
 163     Container<K, V, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc);
 164
 165     assert(c.hash_function() == Hash());
 166     assert(c.get_allocator() == alloc);
 167     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 168     assert(std::ranges::is_permutation(input, c));
 169     validate(c);
 170   }
 171 }
 172
 173 template <template <class ...> class Container,
 174           class K,
 175           class V,
 176           class Iter,
 177           class Sent,
 178           class Hash,
 179           class Equal,
 180           class Alloc>
 181 void test_unordered_map() {
 182   auto test_with_input = &test_unordered_map_with_input<Container, K, V, Iter, Sent, Hash, Equal, Alloc>;
 183
 184   // Normal input.
 185   test_with_input({{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}});
 186   // Empty input.
 187   test_with_input({});
 188   // Single-element input.
 189   test_with_input({{1, 2}});
 190 }
 191
 192 template <template <class ...> class Container>
 193 void test_unordered_map_move_only() {
 194   std::pair<const int, MoveOnly> input[5];
 195   std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
 196
 197   [[maybe_unused]] Container<int, MoveOnly> c(std::from_range, in);
 198 }
 199
 200 template <template <class ...> class Container>
 201 void test_map_exception_safety_throwing_copy() {
 202 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 203   using K = int;
 204   using V = ThrowingCopy<3>;
 205
 206   V::throwing_enabled = false;
 207   std::pair<const K, V> in[5] = {
 208     {1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}}
 209   };
 210   V::throwing_enabled = true;
 211   V::reset();
 212
 213   try {
 214     Container<K, V> c(std::from_range, in);
 215     assert(false); // The constructor call above should throw.
 216
 217   } catch (int) {
 218     assert(V::created_by_copying == 3);
 219     assert(V::destroyed == 2); // No destructor call for the partially-constructed element.
 220   }
 221 #endif
 222 }
 223
 224 template <template <class ...> class Container, class K, class V>
 225 void test_map_exception_safety_throwing_allocator() {
 226 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 227   using ValueType = std::pair<const K, V>;
 228   ValueType in[] = {
 229     ValueType{K{1}, V{1}}
 230   };
 231
 232   try {
 233     ThrowingAllocator<ValueType> alloc;
 234
 235     globalMemCounter.reset();
 236     Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>>
 237         c(std::from_range, in, /*n=*/0, alloc);
 238     assert(false); // The constructor call should throw.
 239
 240   } catch (int) {
 241     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 242   }
 243 #endif
 244 }
 245
 246 template <class Container, class Range>
 247 concept SetHasFromRangeCtr = requires (Range&& range) {
 248   // (from_range, range)
 249   Container(std::from_range, std::forward<Range>(range));
 250   // (from_range, range, n)
 251   Container(std::from_range, std::forward<Range>(range), 0);
 252   // (from_range, range, n, hash)
 253   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>());
 254   // (from_range, range, n, hash, equal)
 255   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(),
 256             std::equal_to<typename Container::value_type>());
 257   // (from_range, range, n, hash, equal, alloc)
 258   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(),
 259             std::equal_to<typename Container::value_type>(), std::allocator<typename Container::value_type>());
 260   // (from_range, range, n, alloc)
 261   Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>());
 262   // (from_range, range, n, hash, alloc)
 263   Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(),
 264             std::allocator<typename Container::value_type>());
 265 };
 266
 267 template <template <class...> class Container, class T, class U>
 268 constexpr bool test_set_constraints() {
 269   // Input range with the same value type.
 270   static_assert(HasFromRangeCtr<Container<T>, InputRange<T>>);
 271   // Input range with a convertible value type.
 272   static_assert(HasFromRangeCtr<Container<T>, InputRange<U>>);
 273   // Input range with a non-convertible value type.
 274   static_assert(!HasFromRangeCtr<Container<T>, InputRange<Empty>>);
 275   // Not an input range.
 276   static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotDerivedFromGeneric<T>>);
 277
 278   return true;
 279 }
 280
 281 template <template <class ...> class Container,
 282           class T,
 283           class Iter,
 284           class Sent,
 285           class Hash,
 286           class Equal,
 287           class Alloc>
 288 void test_unordered_set_with_input(std::vector<T>&& input) {
 289   using DefaultHash = std::hash<int>;
 290   using DefaultEqual = std::equal_to<int>;
 291
 292   auto validate = [](auto&& c) {
 293     if (!c.empty()) {
 294       auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count());
 295       assert(std::fabs(diff) < std::numeric_limits<float>::epsilon());
 296     }
 297     assert(c.max_load_factor() == 1);
 298   };
 299
 300   auto b = Iter(input.data());
 301   auto e = Iter(input.data() + input.size());
 302   std::ranges::subrange in(std::move(b), Sent(std::move(e)));
 303
 304   { // (range)
 305     Container<T> c(std::from_range, in);
 306
 307     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 308     assert(std::ranges::is_permutation(input, c));
 309     validate(c);
 310   }
 311
 312   { // (range, n)
 313     Container<T> c(std::from_range, in, 123);
 314
 315     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 316     assert(std::ranges::is_permutation(input, c));
 317     validate(c);
 318   }
 319
 320   { // (range, n, hasher)
 321     Container<T, Hash> c(std::from_range, in, 123, Hash());
 322
 323     assert(c.hash_function() == Hash());
 324     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 325     assert(std::ranges::is_permutation(input, c));
 326     validate(c);
 327   }
 328
 329   { // (range, n, hasher, key_equal)
 330     Container<T, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal());
 331
 332     assert(c.hash_function() == Hash());
 333     assert(c.key_eq() == Equal());
 334     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 335     assert(std::ranges::is_permutation(input, c));
 336     validate(c);
 337   }
 338
 339   { // (range, n, hasher, key_equal, allocator)
 340     Alloc alloc;
 341     Container<T, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc);
 342
 343     assert(c.hash_function() == Hash());
 344     assert(c.key_eq() == Equal());
 345     assert(c.get_allocator() == alloc);
 346     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 347     assert(std::ranges::is_permutation(input, c));
 348     validate(c);
 349   }
 350
 351   { // (range, n, allocator)
 352     Alloc alloc;
 353     Container<T, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc);
 354
 355     assert(c.get_allocator() == alloc);
 356     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 357     assert(std::ranges::is_permutation(input, c));
 358     validate(c);
 359   }
 360
 361   { // (range, n, hasher, allocator)
 362     Alloc alloc;
 363     Container<T, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc);
 364
 365     assert(c.hash_function() == Hash());
 366     assert(c.get_allocator() == alloc);
 367     assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
 368     assert(std::ranges::is_permutation(input, c));
 369     validate(c);
 370   }
 371 }
 372
 373 template <template <class ...> class Container,
 374           class T,
 375           class Iter,
 376           class Sent,
 377           class Hash,
 378           class Equal,
 379           class Alloc>
 380 void test_unordered_set() {
 381   auto test_with_input = &test_unordered_set_with_input<Container, T, Iter, Sent, Hash, Equal, Alloc>;
 382
 383   // Normal input.
 384   test_with_input({0, 5, 12, 7, -1, 8, 26});
 385   // Empty input.
 386   test_with_input({});
 387   // Single-element input.
 388   test_with_input({5});
 389 }
 390
 391 template <template <class ...> class Container>
 392 void test_unordered_set_move_only() {
 393   MoveOnly input[5];
 394   std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
 395
 396   [[maybe_unused]] Container<MoveOnly> c(std::from_range, in);
 397 }
 398
 399 template <template <class ...> class Container>
 400 void test_set_exception_safety_throwing_copy() {
 401 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 402   using T = ThrowingCopy<3>;
 403   T::reset();
 404   T in[5] = {{1}, {2}, {3}, {4}, {5}};
 405
 406   try {
 407     Container<T, test_hash<T>> c(std::from_range, in);
 408     assert(false); // The constructor call above should throw.
 409
 410   } catch (int) {
 411     assert(T::created_by_copying == 3);
 412     assert(T::destroyed == 2); // No destructor call for the partially-constructed element.
 413   }
 414 #endif
 415 }
 416
 417 template <template <class ...> class Container, class T>
 418 void test_set_exception_safety_throwing_allocator() {
 419 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 420   T in[] = {1, 2, 3};
 421
 422   try {
 423     ThrowingAllocator<T> alloc;
 424
 425     globalMemCounter.reset();
 426     Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(std::from_range, in, /*n=*/0, alloc);
 427     assert(false); // The constructor call should throw.
 428
 429   } catch (int) {
 430     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 431   }
 432 #endif
 433 }
 434
 435 #endif // SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H