ceph/src/boost/libs/unordered/test/unordered/insert_tests.cpp

   1
   2 // Copyright 2006-2010 Daniel James.
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #if !defined(PIECEWISE_TEST_NAME)
   7
   8 // clang-format off
   9 #include "../helpers/prefix.hpp"
  10 #include <boost/unordered_set.hpp>
  11 #include <boost/unordered_map.hpp>
  12 #include "../helpers/postfix.hpp"
  13 // clang-format on
  14
  15 #include "../helpers/test.hpp"
  16 #include "../objects/test.hpp"
  17 #include "../helpers/random_values.hpp"
  18 #include "../helpers/tracker.hpp"
  19 #include "../helpers/equivalent.hpp"
  20 #include "../helpers/invariants.hpp"
  21 #include "../helpers/input_iterator.hpp"
  22 #include "../helpers/helpers.hpp"
  23
  24 namespace insert_tests {
  25
  26   test::seed_t initialize_seed(243432);
  27
  28   template <class X>
  29   void unique_insert_tests1(X*, test::random_generator generator)
  30   {
  31     test::check_instances check_;
  32
  33     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
  34     typedef test::ordered<X> ordered;
  35
  36     UNORDERED_SUB_TEST("insert(value) tests for containers with unique keys")
  37     {
  38       X x;
  39       test::ordered<X> tracker = test::create_ordered(x);
  40
  41       test::random_values<X> v(1000, generator);
  42
  43       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
  44              v.begin();
  45            it != v.end(); ++it) {
  46
  47         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
  48         float b = x.max_load_factor();
  49
  50         std::pair<iterator, bool> r1 = x.insert(*it);
  51         std::pair<BOOST_DEDUCED_TYPENAME ordered::iterator, bool> r2 =
  52           tracker.insert(*it);
  53
  54         BOOST_TEST(r1.second == r2.second);
  55         BOOST_TEST(*r1.first == *r2.first);
  56
  57         tracker.compare_key(x, *it);
  58
  59         if (static_cast<double>(x.size()) <=
  60             b * static_cast<double>(old_bucket_count))
  61           BOOST_TEST(x.bucket_count() == old_bucket_count);
  62       }
  63
  64       test::check_equivalent_keys(x);
  65     }
  66
  67     UNORDERED_SUB_TEST("insert(rvalue) tests for containers with unique keys")
  68     {
  69       X x;
  70       test::ordered<X> tracker = test::create_ordered(x);
  71
  72       test::random_values<X> v(1000, generator);
  73
  74       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
  75              v.begin();
  76            it != v.end(); ++it) {
  77
  78         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
  79         float b = x.max_load_factor();
  80
  81         typename X::value_type value = *it;
  82         std::pair<iterator, bool> r1 = x.insert(boost::move(value));
  83         std::pair<BOOST_DEDUCED_TYPENAME ordered::iterator, bool> r2 =
  84           tracker.insert(*it);
  85
  86         BOOST_TEST(r1.second == r2.second);
  87         BOOST_TEST(*r1.first == *r2.first);
  88
  89         tracker.compare_key(x, *it);
  90
  91         if (static_cast<double>(x.size()) <=
  92             b * static_cast<double>(old_bucket_count))
  93           BOOST_TEST(x.bucket_count() == old_bucket_count);
  94       }
  95
  96       test::check_equivalent_keys(x);
  97     }
  98   }
  99
 100   template <class X>
 101   void equivalent_insert_tests1(X*, test::random_generator generator)
 102   {
 103     test::check_instances check_;
 104
 105     UNORDERED_SUB_TEST(
 106       "insert(value) tests for containers with equivalent keys")
 107     {
 108       X x;
 109       test::ordered<X> tracker = test::create_ordered(x);
 110
 111       test::random_values<X> v(1000, generator);
 112       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 113              v.begin();
 114            it != v.end(); ++it) {
 115         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 116         float b = x.max_load_factor();
 117
 118         BOOST_DEDUCED_TYPENAME X::iterator r1 = x.insert(*it);
 119         BOOST_DEDUCED_TYPENAME test::ordered<X>::iterator r2 =
 120           tracker.insert(*it);
 121
 122         BOOST_TEST(*r1 == *r2);
 123
 124         tracker.compare_key(x, *it);
 125
 126         if (static_cast<double>(x.size()) <=
 127             b * static_cast<double>(old_bucket_count))
 128           BOOST_TEST(x.bucket_count() == old_bucket_count);
 129       }
 130
 131       test::check_equivalent_keys(x);
 132     }
 133
 134     UNORDERED_SUB_TEST(
 135       "insert(rvalue) tests for containers with equivalent keys")
 136     {
 137       X x;
 138       test::ordered<X> tracker = test::create_ordered(x);
 139
 140       test::random_values<X> v(1000, generator);
 141       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 142              v.begin();
 143            it != v.end(); ++it) {
 144         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 145         float b = x.max_load_factor();
 146
 147         typename X::value_type value = *it;
 148         BOOST_DEDUCED_TYPENAME X::iterator r1 = x.insert(boost::move(value));
 149         BOOST_DEDUCED_TYPENAME test::ordered<X>::iterator r2 =
 150           tracker.insert(*it);
 151
 152         BOOST_TEST(*r1 == *r2);
 153
 154         tracker.compare_key(x, *it);
 155
 156         if (static_cast<double>(x.size()) <=
 157             b * static_cast<double>(old_bucket_count))
 158           BOOST_TEST(x.bucket_count() == old_bucket_count);
 159       }
 160
 161       test::check_equivalent_keys(x);
 162     }
 163   }
 164
 165   template <class X> void insert_tests2(X*, test::random_generator generator)
 166   {
 167     typedef BOOST_DEDUCED_TYPENAME test::ordered<X> tracker_type;
 168     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 169     typedef BOOST_DEDUCED_TYPENAME X::const_iterator const_iterator;
 170     typedef BOOST_DEDUCED_TYPENAME tracker_type::iterator tracker_iterator;
 171
 172     UNORDERED_SUB_TEST("insert(begin(), value) tests")
 173     {
 174       test::check_instances check_;
 175
 176       X x;
 177       tracker_type tracker = test::create_ordered(x);
 178
 179       test::random_values<X> v(1000, generator);
 180       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 181              v.begin();
 182            it != v.end(); ++it) {
 183         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 184         float b = x.max_load_factor();
 185
 186         iterator r1 = x.insert(x.begin(), *it);
 187         tracker_iterator r2 = tracker.insert(tracker.begin(), *it);
 188         BOOST_TEST(*r1 == *r2);
 189         tracker.compare_key(x, *it);
 190
 191         if (static_cast<double>(x.size()) <=
 192             b * static_cast<double>(old_bucket_count))
 193           BOOST_TEST(x.bucket_count() == old_bucket_count);
 194       }
 195
 196       tracker.compare(x);
 197       test::check_equivalent_keys(x);
 198     }
 199
 200     UNORDERED_SUB_TEST("insert(end(), value) tests")
 201     {
 202       test::check_instances check_;
 203
 204       X x;
 205       X const& x_const = x;
 206       tracker_type tracker = test::create_ordered(x);
 207
 208       test::random_values<X> v(100, generator);
 209       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 210              v.begin();
 211            it != v.end(); ++it) {
 212         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 213         float b = x.max_load_factor();
 214
 215         const_iterator r1 = x.insert(x_const.end(), *it);
 216         tracker_iterator r2 = tracker.insert(tracker.end(), *it);
 217         BOOST_TEST(*r1 == *r2);
 218         tracker.compare_key(x, *it);
 219
 220         if (static_cast<double>(x.size()) <=
 221             b * static_cast<double>(old_bucket_count))
 222           BOOST_TEST(x.bucket_count() == old_bucket_count);
 223       }
 224
 225       tracker.compare(x);
 226       test::check_equivalent_keys(x);
 227     }
 228
 229     UNORDERED_SUB_TEST("insert(pos, value) tests")
 230     {
 231       test::check_instances check_;
 232
 233       X x;
 234       const_iterator pos = x.begin();
 235       tracker_type tracker = test::create_ordered(x);
 236
 237       test::random_values<X> v(1000, generator);
 238       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 239              v.begin();
 240            it != v.end(); ++it) {
 241         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 242         float b = x.max_load_factor();
 243
 244         pos = x.insert(pos, *it);
 245         tracker_iterator r2 = tracker.insert(tracker.begin(), *it);
 246         BOOST_TEST(*pos == *r2);
 247         tracker.compare_key(x, *it);
 248
 249         if (static_cast<double>(x.size()) <=
 250             b * static_cast<double>(old_bucket_count))
 251           BOOST_TEST(x.bucket_count() == old_bucket_count);
 252       }
 253
 254       tracker.compare(x);
 255       test::check_equivalent_keys(x);
 256     }
 257
 258     UNORDERED_SUB_TEST("insert(pos, rvalue) tests")
 259     {
 260       test::check_instances check_;
 261
 262       X x;
 263       const_iterator pos = x.begin();
 264       tracker_type tracker = test::create_ordered(x);
 265
 266       test::random_values<X> v(1000, generator);
 267       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 268              v.begin();
 269            it != v.end(); ++it) {
 270         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 271         float b = x.max_load_factor();
 272
 273         typename X::value_type value = *it;
 274         pos = x.insert(pos, boost::move(value));
 275         tracker_iterator r2 = tracker.insert(tracker.begin(), *it);
 276         BOOST_TEST(*pos == *r2);
 277         tracker.compare_key(x, *it);
 278
 279         if (static_cast<double>(x.size()) <=
 280             b * static_cast<double>(old_bucket_count))
 281           BOOST_TEST(x.bucket_count() == old_bucket_count);
 282       }
 283
 284       tracker.compare(x);
 285       test::check_equivalent_keys(x);
 286     }
 287
 288     UNORDERED_SUB_TEST("insert single item range tests")
 289     {
 290       test::check_instances check_;
 291
 292       X x;
 293       tracker_type tracker = test::create_ordered(x);
 294
 295       test::random_values<X> v(1000, generator);
 296       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 297              v.begin();
 298            it != v.end(); ++it) {
 299         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 300         float b = x.max_load_factor();
 301
 302         x.insert(it, test::next(it));
 303         tracker.insert(*it);
 304         tracker.compare_key(x, *it);
 305
 306         if (static_cast<double>(x.size()) <=
 307             b * static_cast<double>(old_bucket_count))
 308           BOOST_TEST(x.bucket_count() == old_bucket_count);
 309       }
 310
 311       tracker.compare(x);
 312       test::check_equivalent_keys(x);
 313     }
 314
 315     UNORDERED_SUB_TEST("insert range tests")
 316     {
 317       test::check_instances check_;
 318
 319       X x;
 320
 321       test::random_values<X> v(1000, generator);
 322       x.insert(v.begin(), v.end());
 323
 324       test::check_container(x, v);
 325       test::check_equivalent_keys(x);
 326     }
 327
 328     UNORDERED_SUB_TEST("insert range with rehash tests")
 329     {
 330       test::check_instances check_;
 331
 332       X x;
 333
 334       test::random_values<X> v(1000, generator);
 335
 336       x.insert(*v.begin());
 337       x.clear();
 338
 339       x.insert(v.begin(), v.end());
 340
 341       test::check_container(x, v);
 342       test::check_equivalent_keys(x);
 343     }
 344
 345     UNORDERED_SUB_TEST("insert input iterator range tests")
 346     {
 347       test::check_instances check_;
 348
 349       X x;
 350
 351       test::random_values<X> v(1000, generator);
 352       BOOST_DEDUCED_TYPENAME test::random_values<X>::const_iterator begin =
 353                                                                       v.begin(),
 354                                                                     end =
 355                                                                       v.end();
 356       x.insert(test::input_iterator(begin), test::input_iterator(end));
 357       test::check_container(x, v);
 358
 359       test::check_equivalent_keys(x);
 360     }
 361
 362     UNORDERED_SUB_TEST("insert copy iterator range tests")
 363     {
 364       test::check_instances check_;
 365
 366       X x;
 367
 368       test::random_values<X> v(1000, generator);
 369       x.insert(test::copy_iterator(v.begin()), test::copy_iterator(v.end()));
 370       test::check_container(x, v);
 371
 372       test::check_equivalent_keys(x);
 373     }
 374
 375     UNORDERED_SUB_TEST("insert copy iterator range test 2")
 376     {
 377       test::check_instances check_;
 378
 379       X x;
 380
 381       test::random_values<X> v1(500, generator);
 382       test::random_values<X> v2(500, generator);
 383       x.insert(test::copy_iterator(v1.begin()), test::copy_iterator(v1.end()));
 384       x.insert(test::copy_iterator(v2.begin()), test::copy_iterator(v2.end()));
 385
 386       test::check_equivalent_keys(x);
 387     }
 388
 389     UNORDERED_SUB_TEST("insert various ranges")
 390     {
 391       for (int i = 0; i < 100; ++i) {
 392         X x;
 393         test::ordered<X> tracker = test::create_ordered(x);
 394
 395         test::random_values<X> v(1000, generator);
 396
 397         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 398                v.begin();
 399              it != v.end();) {
 400           BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 401             x.bucket_count();
 402           float b = x.max_load_factor();
 403
 404           BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator next = it;
 405           for (std::size_t j = test::random_value(20); j > 0; ++j) {
 406             ++next;
 407             if (next == v.end()) {
 408               break;
 409             }
 410           }
 411
 412           x.insert(it, next);
 413           tracker.insert(it, next);
 414           it = next;
 415
 416           tracker.compare(x); // Slow, but I can't see any other way.
 417
 418           if (static_cast<double>(x.size()) <=
 419               b * static_cast<double>(old_bucket_count))
 420             BOOST_TEST(x.bucket_count() == old_bucket_count);
 421         }
 422
 423         test::check_equivalent_keys(x);
 424       }
 425     }
 426   }
 427
 428   template <class X>
 429   void unique_emplace_tests1(X*, test::random_generator generator)
 430   {
 431     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 432     typedef test::ordered<X> ordered;
 433
 434     X x;
 435     test::ordered<X> tracker = test::create_ordered(x);
 436
 437     test::random_values<X> v(1000, generator);
 438
 439     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 440          it != v.end(); ++it) {
 441
 442       BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 443       float b = x.max_load_factor();
 444
 445       std::pair<iterator, bool> r1 = x.emplace(*it);
 446       std::pair<BOOST_DEDUCED_TYPENAME ordered::iterator, bool> r2 =
 447         tracker.insert(*it);
 448
 449       BOOST_TEST(r1.second == r2.second);
 450       BOOST_TEST(*r1.first == *r2.first);
 451
 452       tracker.compare_key(x, *it);
 453
 454       if (static_cast<double>(x.size()) <=
 455           b * static_cast<double>(old_bucket_count))
 456         BOOST_TEST(x.bucket_count() == old_bucket_count);
 457     }
 458
 459     tracker.compare(x);
 460     test::check_equivalent_keys(x);
 461   }
 462
 463   template <class X>
 464   void equivalent_emplace_tests1(X*, test::random_generator generator)
 465   {
 466     X x;
 467     test::ordered<X> tracker = test::create_ordered(x);
 468
 469     test::random_values<X> v(1000, generator);
 470     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 471          it != v.end(); ++it) {
 472       BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 473       float b = x.max_load_factor();
 474
 475       BOOST_DEDUCED_TYPENAME X::iterator r1 = x.emplace(*it);
 476       BOOST_DEDUCED_TYPENAME test::ordered<X>::iterator r2 =
 477         tracker.insert(*it);
 478
 479       BOOST_TEST(*r1 == *r2);
 480
 481       tracker.compare_key(x, *it);
 482
 483       if (static_cast<double>(x.size()) <=
 484           b * static_cast<double>(old_bucket_count))
 485         BOOST_TEST(x.bucket_count() == old_bucket_count);
 486     }
 487
 488     tracker.compare(x);
 489     test::check_equivalent_keys(x);
 490   }
 491
 492   template <class X>
 493   void move_emplace_tests(X*, test::random_generator generator)
 494   {
 495     X x;
 496     test::ordered<X> tracker = test::create_ordered(x);
 497
 498     test::random_values<X> v(1000, generator);
 499
 500     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 501          it != v.end(); ++it) {
 502
 503       BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 504       float b = x.max_load_factor();
 505
 506       typename X::value_type value = *it;
 507       x.emplace(boost::move(value));
 508       tracker.insert(*it);
 509       tracker.compare_key(x, *it);
 510
 511       if (static_cast<double>(x.size()) <=
 512           b * static_cast<double>(old_bucket_count))
 513         BOOST_TEST(x.bucket_count() == old_bucket_count);
 514     }
 515
 516     tracker.compare(x);
 517     test::check_equivalent_keys(x);
 518   }
 519
 520   template <class X> void default_emplace_tests(X*, test::random_generator)
 521   {
 522 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
 523     bool is_unique = test::has_unique_keys<X>::value;
 524
 525     X x;
 526
 527     x.emplace();
 528     BOOST_TEST(x.size() == 1);
 529     x.emplace();
 530     BOOST_TEST(x.size() == (is_unique ? 1u : 2u));
 531     x.emplace();
 532     BOOST_TEST(x.size() == (is_unique ? 1u : 3u));
 533
 534     typename X::value_type y;
 535     BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 3u));
 536     BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
 537
 538     x.emplace(y);
 539     BOOST_TEST(x.size() == (is_unique ? 1u : 4u));
 540     BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 4u));
 541     BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
 542
 543     x.clear();
 544     BOOST_TEST(x.empty());
 545     x.emplace(y);
 546     BOOST_TEST(x.size() == 1);
 547     x.emplace(y);
 548     BOOST_TEST(x.size() == (is_unique ? 1u : 2u));
 549
 550     BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 2u));
 551     BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
 552 #endif
 553   }
 554
 555   template <class X> void map_tests(X*, test::random_generator generator)
 556   {
 557     X x;
 558     test::ordered<X> tracker = test::create_ordered(x);
 559
 560     test::random_values<X> v(1000, generator);
 561     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 562          it != v.end(); ++it) {
 563       BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 564       float b = x.max_load_factor();
 565
 566       x[it->first] = it->second;
 567       tracker[it->first] = it->second;
 568
 569       tracker.compare_key(x, *it);
 570
 571       if (static_cast<double>(x.size()) <=
 572           b * static_cast<double>(old_bucket_count))
 573         BOOST_TEST(x.bucket_count() == old_bucket_count);
 574     }
 575
 576     tracker.compare(x);
 577     test::check_equivalent_keys(x);
 578   }
 579
 580   template <class X> void map_tests2(X*, test::random_generator generator)
 581   {
 582     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 583
 584     UNORDERED_SUB_TEST("insert_or_assign")
 585     {
 586       test::check_instances check_;
 587
 588       X x;
 589       test::ordered<X> tracker = test::create_ordered(x);
 590
 591       test::random_values<X> v(1000, generator);
 592       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 593              v.begin();
 594            it != v.end(); ++it) {
 595         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 596         float b = x.max_load_factor();
 597
 598         std::pair<iterator, bool> r = x.insert_or_assign(it->first, it->second);
 599         BOOST_TEST(*r.first == *it);
 600
 601         tracker[it->first] = it->second;
 602         tracker.compare_key(x, *it);
 603
 604         if (static_cast<double>(x.size()) <
 605             b * static_cast<double>(old_bucket_count))
 606           BOOST_TEST(x.bucket_count() == old_bucket_count);
 607       }
 608
 609       tracker.compare(x);
 610       test::check_equivalent_keys(x);
 611     }
 612
 613     UNORDERED_SUB_TEST("insert_or_assign(begin)")
 614     {
 615       test::check_instances check_;
 616
 617       X x;
 618       test::ordered<X> tracker = test::create_ordered(x);
 619
 620       test::random_values<X> v(1000, generator);
 621       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 622              v.begin();
 623            it != v.end(); ++it) {
 624         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 625         float b = x.max_load_factor();
 626
 627         iterator r = x.insert_or_assign(x.begin(), it->first, it->second);
 628         BOOST_TEST(*r == *it);
 629
 630         tracker[it->first] = it->second;
 631         tracker.compare_key(x, *it);
 632
 633         if (static_cast<double>(x.size()) <
 634             b * static_cast<double>(old_bucket_count))
 635           BOOST_TEST(x.bucket_count() == old_bucket_count);
 636       }
 637
 638       tracker.compare(x);
 639       test::check_equivalent_keys(x);
 640     }
 641
 642     UNORDERED_SUB_TEST("insert_or_assign(end)")
 643     {
 644       test::check_instances check_;
 645
 646       X x;
 647       test::ordered<X> tracker = test::create_ordered(x);
 648
 649       test::random_values<X> v(1000, generator);
 650       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 651              v.begin();
 652            it != v.end(); ++it) {
 653         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 654         float b = x.max_load_factor();
 655
 656         iterator r = x.insert_or_assign(x.end(), it->first, it->second);
 657         BOOST_TEST(*r == *it);
 658
 659         tracker[it->first] = it->second;
 660         tracker.compare_key(x, *it);
 661
 662         if (static_cast<double>(x.size()) <
 663             b * static_cast<double>(old_bucket_count))
 664           BOOST_TEST(x.bucket_count() == old_bucket_count);
 665       }
 666
 667       tracker.compare(x);
 668       test::check_equivalent_keys(x);
 669     }
 670
 671     UNORDERED_SUB_TEST("insert_or_assign(last)")
 672     {
 673       test::check_instances check_;
 674
 675       X x;
 676       test::ordered<X> tracker = test::create_ordered(x);
 677       iterator last = x.begin();
 678
 679       test::random_values<X> v(1000, generator);
 680       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 681              v.begin();
 682            it != v.end(); ++it) {
 683         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 684         float b = x.max_load_factor();
 685
 686         iterator r = x.insert_or_assign(last, it->first, it->second);
 687         BOOST_TEST(*r == *it);
 688
 689         tracker[it->first] = it->second;
 690         tracker.compare_key(x, *it);
 691
 692         if (static_cast<double>(x.size()) <
 693             b * static_cast<double>(old_bucket_count))
 694           BOOST_TEST(x.bucket_count() == old_bucket_count);
 695
 696         last = r;
 697       }
 698
 699       tracker.compare(x);
 700       test::check_equivalent_keys(x);
 701     }
 702   }
 703
 704   template <class X>
 705   void try_emplace_tests(X*, test::random_generator generator)
 706   {
 707     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 708
 709     UNORDERED_SUB_TEST("try_emplace(key, value)")
 710     {
 711       test::check_instances check_;
 712
 713       X x;
 714       test::ordered<X> tracker = test::create_ordered(x);
 715
 716       test::random_values<X> v(1000, generator);
 717       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 718              v.begin();
 719            it != v.end(); ++it) {
 720         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 721         float b = x.max_load_factor();
 722
 723         iterator pos = x.find(it->first);
 724         bool found = pos != x.end();
 725
 726         std::pair<typename X::iterator, bool> r =
 727           x.try_emplace(it->first, it->second);
 728         if (found) {
 729           BOOST_TEST(pos == r.first);
 730           BOOST_TEST(!r.second);
 731         } else {
 732           BOOST_TEST(r.second);
 733         }
 734         BOOST_TEST_EQ(r.first->first, it->first);
 735         BOOST_TEST_EQ(r.first->second, it->second);
 736
 737         tracker.insert(*it);
 738         tracker.compare_key(x, *it);
 739
 740         if (static_cast<double>(x.size()) <
 741             b * static_cast<double>(old_bucket_count))
 742           BOOST_TEST(x.bucket_count() == old_bucket_count);
 743       }
 744
 745       test::check_equivalent_keys(x);
 746     }
 747
 748     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 749
 750     UNORDERED_SUB_TEST("try_emplace(begin(), key, value)")
 751     {
 752       test::check_instances check_;
 753
 754       X x;
 755       test::ordered<X> tracker = test::create_ordered(x);
 756
 757       test::random_values<X> v(1000, generator);
 758       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 759              v.begin();
 760            it != v.end(); ++it) {
 761         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 762         float b = x.max_load_factor();
 763
 764         iterator pos = x.find(it->first);
 765         bool found = pos != x.end();
 766
 767         typename X::iterator r =
 768           x.try_emplace(r.begin(), it->first, it->second);
 769         if (found) {
 770           BOOST_TEST(pos == r);
 771         }
 772         BOOST_TEST_EQ(r->first, it->first);
 773         BOOST_TEST_EQ(r->second, it->second);
 774
 775         tracker.insert(*it);
 776         tracker.compare_key(x, *it);
 777
 778         if (static_cast<double>(x.size()) <
 779             b * static_cast<double>(old_bucket_count))
 780           BOOST_TEST(x.bucket_count() == old_bucket_count);
 781       }
 782
 783       test::check_equivalent_keys(x);
 784     }
 785
 786     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 787
 788     UNORDERED_SUB_TEST("try_emplace(end(), key, value)")
 789     {
 790       test::check_instances check_;
 791
 792       X x;
 793       test::ordered<X> tracker = test::create_ordered(x);
 794
 795       test::random_values<X> v(1000, generator);
 796       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 797              v.begin();
 798            it != v.end(); ++it) {
 799         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 800         float b = x.max_load_factor();
 801
 802         iterator pos = x.find(it->first);
 803         bool found = pos != x.end();
 804
 805         typename X::iterator r = x.try_emplace(r.end(), it->first, it->second);
 806         if (found) {
 807           BOOST_TEST(pos == r);
 808         }
 809         BOOST_TEST_EQ(r->first, it->first);
 810         BOOST_TEST_EQ(r->second, it->second);
 811
 812         tracker.insert(*it);
 813         tracker.compare_key(x, *it);
 814
 815         if (static_cast<double>(x.size()) <
 816             b * static_cast<double>(old_bucket_count))
 817           BOOST_TEST(x.bucket_count() == old_bucket_count);
 818       }
 819
 820       test::check_equivalent_keys(x);
 821     }
 822
 823     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 824
 825     UNORDERED_SUB_TEST("try_emplace(pos, key, value)")
 826     {
 827       test::check_instances check_;
 828
 829       X x;
 830       test::ordered<X> tracker = test::create_ordered(x);
 831
 832       test::random_values<X> v(1000, generator);
 833       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 834              v.begin();
 835            it != v.end(); ++it) {
 836         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 837         float b = x.max_load_factor();
 838
 839         iterator pos = x.find(it->first);
 840         bool found = pos != x.end();
 841
 842         typename X::iterator r = x.try_emplace(pos, it->first, it->second);
 843         if (found) {
 844           BOOST_TEST(pos == r);
 845         }
 846         BOOST_TEST_EQ(r->first, it->first);
 847         BOOST_TEST_EQ(r->second, it->second);
 848
 849         tracker.insert(*it);
 850         tracker.compare_key(x, *it);
 851
 852         if (static_cast<double>(x.size()) <
 853             b * static_cast<double>(old_bucket_count))
 854           BOOST_TEST(x.bucket_count() == old_bucket_count);
 855       }
 856
 857       test::check_equivalent_keys(x);
 858     }
 859   }
 860
 861   // Some tests for when the range's value type doesn't match the container's
 862   // value type.
 863
 864   template <class X>
 865   void map_insert_range_test1(X*, test::random_generator generator)
 866   {
 867     test::check_instances check_;
 868
 869     typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type,
 870       BOOST_DEDUCED_TYPENAME X::mapped_type> >
 871       list;
 872     test::random_values<X> v(1000, generator);
 873     list l(v.begin(), v.end());
 874
 875     X x;
 876     x.insert(l.begin(), l.end());
 877
 878     test::check_equivalent_keys(x);
 879   }
 880
 881   template <class X>
 882   void map_insert_range_test2(X*, test::random_generator generator)
 883   {
 884     test::check_instances check_;
 885
 886     typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type const,
 887       test::implicitly_convertible> >
 888       list;
 889     test::random_values<boost::unordered_map<BOOST_DEDUCED_TYPENAME X::key_type,
 890       test::implicitly_convertible> >
 891       v(1000, generator);
 892     list l(v.begin(), v.end());
 893
 894     X x;
 895     x.insert(l.begin(), l.end());
 896
 897     test::check_equivalent_keys(x);
 898   }
 899
 900   boost::unordered_set<test::movable, test::hash, test::equal_to,
 901     std::allocator<test::movable> >* test_set_std_alloc;
 902   boost::unordered_multimap<test::object, test::object, test::hash,
 903     test::equal_to, std::allocator<test::object> >* test_multimap_std_alloc;
 904
 905   boost::unordered_set<test::object, test::hash, test::equal_to,
 906     test::allocator1<test::object> >* test_set;
 907   boost::unordered_multiset<test::movable, test::hash, test::equal_to,
 908     test::allocator2<test::movable> >* test_multiset;
 909   boost::unordered_map<test::movable, test::movable, test::hash, test::equal_to,
 910     test::allocator2<test::movable> >* test_map;
 911   boost::unordered_multimap<test::object, test::object, test::hash,
 912     test::equal_to, test::allocator1<test::object> >* test_multimap;
 913
 914   using test::default_generator;
 915   using test::generate_collisions;
 916   using test::limited_range;
 917
 918   UNORDERED_TEST(unique_insert_tests1,
 919     ((test_set_std_alloc)(test_set)(test_map))(
 920       (default_generator)(generate_collisions)(limited_range)))
 921
 922   UNORDERED_TEST(equivalent_insert_tests1,
 923     ((test_multimap_std_alloc)(test_multiset)(test_multimap))(
 924       (default_generator)(generate_collisions)(limited_range)))
 925
 926   UNORDERED_TEST(insert_tests2,
 927     ((test_multimap_std_alloc)(test_set)(test_multiset)(test_map)(
 928       test_multimap))((default_generator)(generate_collisions)(limited_range)))
 929
 930   UNORDERED_TEST(unique_emplace_tests1,
 931     ((test_set_std_alloc)(test_set)(test_map))(
 932       (default_generator)(generate_collisions)(limited_range)))
 933
 934   UNORDERED_TEST(equivalent_emplace_tests1,
 935     ((test_multimap_std_alloc)(test_multiset)(test_multimap))(
 936       (default_generator)(generate_collisions)(limited_range)))
 937
 938   UNORDERED_TEST(move_emplace_tests,
 939     ((test_set_std_alloc)(test_multimap_std_alloc)(test_set)(test_map)(
 940       test_multiset)(test_multimap))(
 941       (default_generator)(generate_collisions)(limited_range)))
 942
 943   UNORDERED_TEST(default_emplace_tests,
 944     ((test_set_std_alloc)(test_multimap_std_alloc)(test_set)(test_map)(
 945       test_multiset)(test_multimap))(
 946       (default_generator)(generate_collisions)(limited_range)))
 947
 948   UNORDERED_TEST(map_tests,
 949     ((test_map))((default_generator)(generate_collisions)(limited_range)))
 950
 951   UNORDERED_TEST(
 952     map_tests2, ((test_map))((default_generator)(generate_collisions)))
 953
 954   UNORDERED_TEST(map_insert_range_test1,
 955     ((test_multimap_std_alloc)(test_map)(test_multimap))(
 956       (default_generator)(generate_collisions)(limited_range)))
 957
 958   UNORDERED_TEST(map_insert_range_test2,
 959     ((test_multimap_std_alloc)(test_map)(test_multimap))(
 960       (default_generator)(generate_collisions)(limited_range)))
 961
 962 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 963
 964   struct initialize_from_two_ints
 965   {
 966     int a, b;
 967
 968     friend std::size_t hash_value(initialize_from_two_ints const& x)
 969     {
 970       return static_cast<std::size_t>(x.a + x.b);
 971     }
 972
 973     bool operator==(initialize_from_two_ints const& x) const
 974     {
 975       return a == x.a && b == x.b;
 976     }
 977   };
 978
 979   UNORDERED_AUTO_TEST (insert_initializer_list_set) {
 980     boost::unordered_set<int> set;
 981     set.insert({1, 2, 3, 1});
 982     BOOST_TEST_EQ(set.size(), 3u);
 983     BOOST_TEST(set.find(1) != set.end());
 984     BOOST_TEST(set.find(4) == set.end());
 985
 986     boost::unordered_set<initialize_from_two_ints> set2;
 987
 988 #if defined(__GNUC__) && (__GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 5))
 989     set2.insert({{1, 2}});
 990 #else
 991     set2.insert({1, 2});
 992 #endif
 993     BOOST_TEST(set2.size() == 1);
 994     BOOST_TEST(set2.find({1, 2}) != set2.end());
 995     BOOST_TEST(set2.find({2, 1}) == set2.end());
 996
 997     set2.insert({{3, 4}, {5, 6}, {7, 8}});
 998     BOOST_TEST(set2.size() == 4);
 999     BOOST_TEST(set2.find({1, 2}) != set2.end());
1000     BOOST_TEST(set2.find({3, 4}) != set2.end());
1001     BOOST_TEST(set2.find({5, 6}) != set2.end());
1002     BOOST_TEST(set2.find({7, 8}) != set2.end());
1003     BOOST_TEST(set2.find({8, 7}) == set2.end());
1004
1005     set2.insert({{2, 1}, {3, 4}});
1006     BOOST_TEST(set2.size() == 5);
1007     BOOST_TEST(set2.find({1, 2}) != set2.end());
1008     BOOST_TEST(set2.find({2, 1}) != set2.end());
1009     BOOST_TEST(set2.find({3, 4}) != set2.end());
1010     BOOST_TEST(set2.find({5, 6}) != set2.end());
1011     BOOST_TEST(set2.find({7, 8}) != set2.end());
1012     BOOST_TEST(set2.find({8, 7}) == set2.end());
1013   }
1014
1015 #if !BOOST_WORKAROUND(BOOST_MSVC, == 1800)
1016
1017   UNORDERED_AUTO_TEST (insert_initializer_list_multiset) {
1018     boost::unordered_multiset<std::string> multiset;
1019     // multiset.insert({});
1020     BOOST_TEST(multiset.empty());
1021     multiset.insert({"a"});
1022     BOOST_TEST_EQ(multiset.size(), 1u);
1023     BOOST_TEST(multiset.find("a") != multiset.end());
1024     BOOST_TEST(multiset.find("b") == multiset.end());
1025     multiset.insert({"a", "b"});
1026     BOOST_TEST(multiset.size() == 3);
1027     BOOST_TEST_EQ(multiset.count("a"), 2u);
1028     BOOST_TEST_EQ(multiset.count("b"), 1u);
1029     BOOST_TEST_EQ(multiset.count("c"), 0u);
1030   }
1031
1032 #endif
1033
1034   UNORDERED_AUTO_TEST (insert_initializer_list_map) {
1035     boost::unordered_map<std::string, std::string> map;
1036     // map.insert({});
1037     BOOST_TEST(map.empty());
1038     map.insert({{"a", "b"}, {"a", "b"}, {"d", ""}});
1039     BOOST_TEST_EQ(map.size(), 2u);
1040   }
1041
1042   UNORDERED_AUTO_TEST (insert_initializer_list_multimap) {
1043     boost::unordered_multimap<std::string, std::string> multimap;
1044     // multimap.insert({});
1045     BOOST_TEST(multimap.empty());
1046     multimap.insert({{"a", "b"}, {"a", "b"}, {"d", ""}});
1047     BOOST_TEST_EQ(multimap.size(), 3u);
1048     BOOST_TEST_EQ(multimap.count("a"), 2u);
1049   }
1050
1051 #endif
1052
1053   struct overloaded_constructor
1054   {
1055     overloaded_constructor(int x1_ = 1, int x2_ = 2, int x3_ = 3, int x4_ = 4)
1056         : x1(x1_), x2(x2_), x3(x3_), x4(x4_)
1057     {
1058     }
1059
1060     int x1, x2, x3, x4;
1061
1062     bool operator==(overloaded_constructor const& rhs) const
1063     {
1064       return x1 == rhs.x1 && x2 == rhs.x2 && x3 == rhs.x3 && x4 == rhs.x4;
1065     }
1066
1067     friend std::size_t hash_value(overloaded_constructor const& x)
1068     {
1069       std::size_t hash = 0;
1070       boost::hash_combine(hash, x.x1);
1071       boost::hash_combine(hash, x.x2);
1072       boost::hash_combine(hash, x.x3);
1073       boost::hash_combine(hash, x.x4);
1074       return hash;
1075     }
1076   };
1077
1078   UNORDERED_AUTO_TEST (map_emplace_test) {
1079     {
1080       boost::unordered_map<int, overloaded_constructor, test::hash,
1081         test::equal_to,
1082         test::allocator1<std::pair<int const, overloaded_constructor> > >
1083         x;
1084
1085 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1086       x.emplace();
1087       BOOST_TEST(
1088         x.find(0) != x.end() && x.find(0)->second == overloaded_constructor());
1089 #endif
1090
1091       x.emplace(2, 3);
1092       BOOST_TEST(
1093         x.find(2) != x.end() && x.find(2)->second == overloaded_constructor(3));
1094
1095       x.try_emplace(5);
1096       BOOST_TEST(
1097         x.find(5) != x.end() && x.find(5)->second == overloaded_constructor());
1098     }
1099
1100     {
1101       boost::unordered_multimap<int, overloaded_constructor, test::hash,
1102         test::equal_to,
1103         test::allocator1<std::pair<int const, overloaded_constructor> > >
1104         x;
1105
1106 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1107       x.emplace();
1108       BOOST_TEST(
1109         x.find(0) != x.end() && x.find(0)->second == overloaded_constructor());
1110 #endif
1111
1112       x.emplace(2, 3);
1113       BOOST_TEST(
1114         x.find(2) != x.end() && x.find(2)->second == overloaded_constructor(3));
1115     }
1116   }
1117
1118   UNORDERED_AUTO_TEST (set_emplace_test) {
1119     boost::unordered_set<overloaded_constructor> x;
1120     overloaded_constructor check;
1121
1122 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1123     x.emplace();
1124     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1125 #endif
1126
1127     x.clear();
1128     x.emplace(1);
1129     check = overloaded_constructor(1);
1130     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1131
1132     x.clear();
1133     x.emplace(2, 3);
1134     check = overloaded_constructor(2, 3);
1135     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1136
1137     x.clear();
1138     x.emplace(4, 5, 6);
1139     check = overloaded_constructor(4, 5, 6);
1140     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1141
1142     x.clear();
1143     x.emplace(7, 8, 9, 10);
1144     check = overloaded_constructor(7, 8, 9, 10);
1145     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1146   }
1147
1148   struct derived_from_piecewise_construct_t
1149     : boost::unordered::piecewise_construct_t
1150   {
1151   };
1152
1153   derived_from_piecewise_construct_t piecewise_rvalue()
1154   {
1155     return derived_from_piecewise_construct_t();
1156   }
1157
1158   struct convertible_to_piecewise
1159   {
1160     operator boost::unordered::piecewise_construct_t() const
1161     {
1162       return boost::unordered::piecewise_construct;
1163     }
1164   };
1165
1166   UNORDERED_AUTO_TEST (map_emplace_test2) {
1167     // Emulating piecewise construction with boost::tuple bypasses the
1168     // allocator's construct method, but still uses test destroy method.
1169     test::detail::disable_construction_tracking _scoped;
1170
1171     {
1172       boost::unordered_map<overloaded_constructor, overloaded_constructor,
1173         boost::hash<overloaded_constructor>,
1174         std::equal_to<overloaded_constructor>,
1175         test::allocator1<
1176           std::pair<overloaded_constructor const, overloaded_constructor> > >
1177         x;
1178
1179       x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
1180         boost::make_tuple());
1181       BOOST_TEST(
1182         x.find(overloaded_constructor()) != x.end() &&
1183         x.find(overloaded_constructor())->second == overloaded_constructor());
1184
1185       x.emplace(
1186         convertible_to_piecewise(), boost::make_tuple(1), boost::make_tuple());
1187       BOOST_TEST(
1188         x.find(overloaded_constructor(1)) != x.end() &&
1189         x.find(overloaded_constructor(1))->second == overloaded_constructor());
1190
1191       x.emplace(piecewise_rvalue(), boost::make_tuple(2, 3),
1192         boost::make_tuple(4, 5, 6));
1193       BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1194                  x.find(overloaded_constructor(2, 3))->second ==
1195                    overloaded_constructor(4, 5, 6));
1196
1197       derived_from_piecewise_construct_t d;
1198       x.emplace(d, boost::make_tuple(9, 3, 1), boost::make_tuple(10));
1199       BOOST_TEST(x.find(overloaded_constructor(9, 3, 1)) != x.end() &&
1200                  x.find(overloaded_constructor(9, 3, 1))->second ==
1201                    overloaded_constructor(10));
1202
1203       x.clear();
1204
1205       x.try_emplace(overloaded_constructor());
1206       BOOST_TEST(
1207         x.find(overloaded_constructor()) != x.end() &&
1208         x.find(overloaded_constructor())->second == overloaded_constructor());
1209
1210       x.try_emplace(1);
1211       BOOST_TEST(
1212         x.find(overloaded_constructor(1)) != x.end() &&
1213         x.find(overloaded_constructor(1))->second == overloaded_constructor());
1214
1215       x.try_emplace(overloaded_constructor(2, 3), 4, 5, 6);
1216       BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1217                  x.find(overloaded_constructor(2, 3))->second ==
1218                    overloaded_constructor(4, 5, 6));
1219
1220       x.clear();
1221
1222       x.try_emplace(x.begin(), overloaded_constructor());
1223       BOOST_TEST(
1224         x.find(overloaded_constructor()) != x.end() &&
1225         x.find(overloaded_constructor())->second == overloaded_constructor());
1226
1227       x.try_emplace(x.end(), 1);
1228       BOOST_TEST(
1229         x.find(overloaded_constructor(1)) != x.end() &&
1230         x.find(overloaded_constructor(1))->second == overloaded_constructor());
1231
1232       x.try_emplace(x.begin(), overloaded_constructor(2, 3), 4, 5, 6);
1233       BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1234                  x.find(overloaded_constructor(2, 3))->second ==
1235                    overloaded_constructor(4, 5, 6));
1236     }
1237
1238     {
1239       boost::unordered_multimap<overloaded_constructor, overloaded_constructor,
1240         boost::hash<overloaded_constructor>,
1241         std::equal_to<overloaded_constructor>,
1242         test::allocator1<
1243           std::pair<overloaded_constructor const, overloaded_constructor> > >
1244         x;
1245
1246       x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
1247         boost::make_tuple());
1248       BOOST_TEST(
1249         x.find(overloaded_constructor()) != x.end() &&
1250         x.find(overloaded_constructor())->second == overloaded_constructor());
1251
1252       x.emplace(
1253         convertible_to_piecewise(), boost::make_tuple(1), boost::make_tuple());
1254       BOOST_TEST(
1255         x.find(overloaded_constructor(1)) != x.end() &&
1256         x.find(overloaded_constructor(1))->second == overloaded_constructor());
1257
1258       x.emplace(piecewise_rvalue(), boost::make_tuple(2, 3),
1259         boost::make_tuple(4, 5, 6));
1260       BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1261                  x.find(overloaded_constructor(2, 3))->second ==
1262                    overloaded_constructor(4, 5, 6));
1263
1264       derived_from_piecewise_construct_t d;
1265       x.emplace(d, boost::make_tuple(9, 3, 1), boost::make_tuple(10));
1266       BOOST_TEST(x.find(overloaded_constructor(9, 3, 1)) != x.end() &&
1267                  x.find(overloaded_constructor(9, 3, 1))->second ==
1268                    overloaded_constructor(10));
1269     }
1270   }
1271
1272   UNORDERED_AUTO_TEST (set_emplace_test2) {
1273     boost::unordered_set<
1274       std::pair<overloaded_constructor, overloaded_constructor> >
1275       x;
1276     std::pair<overloaded_constructor, overloaded_constructor> check;
1277
1278     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
1279       boost::make_tuple());
1280     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1281
1282     x.clear();
1283     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(1),
1284       boost::make_tuple(2, 3));
1285     check =
1286       std::make_pair(overloaded_constructor(1), overloaded_constructor(2, 3));
1287     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1288   }
1289
1290 // Use the preprocessor to generate tests using different combinations of
1291 // boost/std piecewise_construct_t/tuple.
1292
1293 #define PIECEWISE_TEST_NAME boost_tuple_piecewise_tests
1294 #define PIECEWISE_NAMESPACE boost::unordered
1295 #define TUPLE_NAMESPACE boost
1296 #define EMULATING_PIECEWISE_CONSTRUCTION 1
1297 #include "./insert_tests.cpp"
1298
1299 #if BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT
1300
1301 #define PIECEWISE_TEST_NAME boost_tuple_std_piecewise_tests
1302 #define PIECEWISE_NAMESPACE std
1303 #define TUPLE_NAMESPACE boost
1304 #define EMULATING_PIECEWISE_CONSTRUCTION 1
1305 #include "./insert_tests.cpp"
1306
1307 #endif
1308
1309 #if !defined(BOOST_NO_CXX11_HDR_TUPLE)
1310
1311 #define PIECEWISE_TEST_NAME std_tuple_boost_piecewise_tests
1312 #define PIECEWISE_NAMESPACE boost::unordered
1313 #define TUPLE_NAMESPACE std
1314 #define EMULATING_PIECEWISE_CONSTRUCTION 0
1315 #include "./insert_tests.cpp"
1316
1317 #endif
1318
1319 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) &&                                      \
1320   BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT
1321
1322 #define PIECEWISE_TEST_NAME std_piecewise_tests
1323 #define PIECEWISE_NAMESPACE std
1324 #define TUPLE_NAMESPACE std
1325 #define EMULATING_PIECEWISE_CONSTRUCTION 0
1326 #include "./insert_tests.cpp"
1327
1328 #endif
1329 }
1330
1331 RUN_TESTS_QUIET()
1332
1333 #else // PIECEWISE_TEST_NAME
1334
1335 UNORDERED_AUTO_TEST (PIECEWISE_TEST_NAME) {
1336 #if EMULATING_PIECEWISE_CONSTRUCTION
1337   test::detail::disable_construction_tracking _scoped;
1338 #endif
1339
1340   {
1341     boost::unordered_map<overloaded_constructor, overloaded_constructor,
1342       boost::hash<overloaded_constructor>,
1343       std::equal_to<overloaded_constructor>,
1344       test::allocator1<
1345         std::pair<overloaded_constructor const, overloaded_constructor> > >
1346       x;
1347
1348     x.emplace(PIECEWISE_NAMESPACE::piecewise_construct,
1349       TUPLE_NAMESPACE::make_tuple(), TUPLE_NAMESPACE::make_tuple());
1350     BOOST_TEST(
1351       x.find(overloaded_constructor()) != x.end() &&
1352       x.find(overloaded_constructor())->second == overloaded_constructor());
1353
1354     x.emplace(convertible_to_piecewise(), TUPLE_NAMESPACE::make_tuple(1),
1355       TUPLE_NAMESPACE::make_tuple());
1356     BOOST_TEST(
1357       x.find(overloaded_constructor(1)) != x.end() &&
1358       x.find(overloaded_constructor(1))->second == overloaded_constructor());
1359
1360     x.emplace(piecewise_rvalue(), TUPLE_NAMESPACE::make_tuple(2, 3),
1361       TUPLE_NAMESPACE::make_tuple(4, 5, 6));
1362     BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1363                x.find(overloaded_constructor(2, 3))->second ==
1364                  overloaded_constructor(4, 5, 6));
1365
1366     derived_from_piecewise_construct_t d;
1367     x.emplace(
1368       d, TUPLE_NAMESPACE::make_tuple(9, 3, 1), TUPLE_NAMESPACE::make_tuple(10));
1369     BOOST_TEST(x.find(overloaded_constructor(9, 3, 1)) != x.end() &&
1370                x.find(overloaded_constructor(9, 3, 1))->second ==
1371                  overloaded_constructor(10));
1372
1373     x.clear();
1374
1375     x.try_emplace(overloaded_constructor());
1376     BOOST_TEST(
1377       x.find(overloaded_constructor()) != x.end() &&
1378       x.find(overloaded_constructor())->second == overloaded_constructor());
1379
1380     x.try_emplace(1);
1381     BOOST_TEST(
1382       x.find(overloaded_constructor(1)) != x.end() &&
1383       x.find(overloaded_constructor(1))->second == overloaded_constructor());
1384
1385     x.try_emplace(overloaded_constructor(2, 3), 4, 5, 6);
1386     BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1387                x.find(overloaded_constructor(2, 3))->second ==
1388                  overloaded_constructor(4, 5, 6));
1389   }
1390   {
1391     boost::unordered_multimap<overloaded_constructor, overloaded_constructor,
1392       boost::hash<overloaded_constructor>,
1393       std::equal_to<overloaded_constructor>,
1394       test::allocator1<
1395         std::pair<overloaded_constructor const, overloaded_constructor> > >
1396       x;
1397
1398     x.emplace(PIECEWISE_NAMESPACE::piecewise_construct,
1399       TUPLE_NAMESPACE::make_tuple(), TUPLE_NAMESPACE::make_tuple());
1400     BOOST_TEST(
1401       x.find(overloaded_constructor()) != x.end() &&
1402       x.find(overloaded_constructor())->second == overloaded_constructor());
1403
1404     x.emplace(convertible_to_piecewise(), TUPLE_NAMESPACE::make_tuple(1),
1405       TUPLE_NAMESPACE::make_tuple());
1406     BOOST_TEST(
1407       x.find(overloaded_constructor(1)) != x.end() &&
1408       x.find(overloaded_constructor(1))->second == overloaded_constructor());
1409
1410     x.emplace(piecewise_rvalue(), TUPLE_NAMESPACE::make_tuple(2, 3),
1411       TUPLE_NAMESPACE::make_tuple(4, 5, 6));
1412     BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1413                x.find(overloaded_constructor(2, 3))->second ==
1414                  overloaded_constructor(4, 5, 6));
1415
1416     derived_from_piecewise_construct_t d;
1417     x.emplace(
1418       d, TUPLE_NAMESPACE::make_tuple(9, 3, 1), TUPLE_NAMESPACE::make_tuple(10));
1419     BOOST_TEST(x.find(overloaded_constructor(9, 3, 1)) != x.end() &&
1420                x.find(overloaded_constructor(9, 3, 1))->second ==
1421                  overloaded_constructor(10));
1422   }
1423 }
1424
1425 UNORDERED_AUTO_TEST (BOOST_PP_CAT(PIECEWISE_TEST_NAME, 2)) {
1426 #if EMULATING_PIECEWISE_CONSTRUCTION
1427   test::detail::disable_construction_tracking _scoped;
1428 #endif
1429
1430   boost::unordered_set<
1431     std::pair<overloaded_constructor, overloaded_constructor> >
1432     x;
1433   std::pair<overloaded_constructor, overloaded_constructor> check;
1434
1435   x.emplace(PIECEWISE_NAMESPACE::piecewise_construct,
1436     TUPLE_NAMESPACE::make_tuple(), TUPLE_NAMESPACE::make_tuple());
1437   BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1438
1439   x.clear();
1440   x.emplace(PIECEWISE_NAMESPACE::piecewise_construct,
1441     TUPLE_NAMESPACE::make_tuple(1), TUPLE_NAMESPACE::make_tuple(2, 3));
1442   check =
1443     std::make_pair(overloaded_constructor(1), overloaded_constructor(2, 3));
1444   BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1445 }
1446
1447 #undef PIECEWISE_TEST_NAME
1448 #undef PIECEWISE_NAMESPACE
1449 #undef TUPLE_NAMESPACE
1450 #undef EMULATING_PIECEWISE_CONSTRUCTION
1451
1452 #endif