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 // clang-format off
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_set.hpp>
   9 #include <boost/unordered_map.hpp>
  10 #include "../helpers/postfix.hpp"
  11 // clang-format on
  12
  13 #include "../helpers/test.hpp"
  14 #include "../objects/test.hpp"
  15 #include "../helpers/random_values.hpp"
  16 #include "../helpers/tracker.hpp"
  17 #include "../helpers/equivalent.hpp"
  18 #include "../helpers/invariants.hpp"
  19 #include "../helpers/input_iterator.hpp"
  20 #include "../helpers/helpers.hpp"
  21
  22 #include <iostream>
  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     std::cerr << "insert(value) tests for containers with unique keys.\n";
  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 = v.begin();
  44          it != v.end(); ++it) {
  45
  46         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
  47         float b = x.max_load_factor();
  48
  49         std::pair<iterator, bool> r1 = x.insert(*it);
  50         std::pair<BOOST_DEDUCED_TYPENAME ordered::iterator, bool> r2 =
  51             tracker.insert(*it);
  52
  53         BOOST_TEST(r1.second == r2.second);
  54         BOOST_TEST(*r1.first == *r2.first);
  55
  56         tracker.compare_key(x, *it);
  57
  58         if (static_cast<double>(x.size()) <=
  59             b * static_cast<double>(old_bucket_count))
  60             BOOST_TEST(x.bucket_count() == old_bucket_count);
  61     }
  62
  63     test::check_equivalent_keys(x);
  64 }
  65
  66 template <class X>
  67 void equivalent_insert_tests1(X*, test::random_generator generator)
  68 {
  69     std::cerr << "insert(value) tests for containers with equivalent keys.\n";
  70
  71     test::check_instances check_;
  72
  73     X x;
  74     test::ordered<X> tracker = test::create_ordered(x);
  75
  76     test::random_values<X> v(1000, generator);
  77     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
  78          it != v.end(); ++it) {
  79         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
  80         float b = x.max_load_factor();
  81
  82         BOOST_DEDUCED_TYPENAME X::iterator r1 = x.insert(*it);
  83         BOOST_DEDUCED_TYPENAME test::ordered<X>::iterator r2 =
  84             tracker.insert(*it);
  85
  86         BOOST_TEST(*r1 == *r2);
  87
  88         tracker.compare_key(x, *it);
  89
  90         if (static_cast<double>(x.size()) <=
  91             b * static_cast<double>(old_bucket_count))
  92             BOOST_TEST(x.bucket_count() == old_bucket_count);
  93     }
  94
  95     test::check_equivalent_keys(x);
  96 }
  97
  98 template <class X> void insert_tests2(X*, test::random_generator generator)
  99 {
 100     typedef BOOST_DEDUCED_TYPENAME test::ordered<X> tracker_type;
 101     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 102     typedef BOOST_DEDUCED_TYPENAME X::const_iterator const_iterator;
 103     typedef BOOST_DEDUCED_TYPENAME tracker_type::iterator tracker_iterator;
 104
 105     std::cerr << "insert(begin(), value) tests.\n";
 106
 107     {
 108         test::check_instances check_;
 109
 110         X x;
 111         tracker_type tracker = test::create_ordered(x);
 112
 113         test::random_values<X> v(1000, generator);
 114         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 115                  v.begin();
 116              it != v.end(); ++it) {
 117             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 118                 x.bucket_count();
 119             float b = x.max_load_factor();
 120
 121             iterator r1 = x.insert(x.begin(), *it);
 122             tracker_iterator r2 = tracker.insert(tracker.begin(), *it);
 123             BOOST_TEST(*r1 == *r2);
 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         tracker.compare(x);
 132         test::check_equivalent_keys(x);
 133     }
 134
 135     std::cerr << "insert(end(), value) tests.\n";
 136
 137     {
 138         test::check_instances check_;
 139
 140         X x;
 141         X const& x_const = x;
 142         tracker_type tracker = test::create_ordered(x);
 143
 144         test::random_values<X> v(100, generator);
 145         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 146                  v.begin();
 147              it != v.end(); ++it) {
 148             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 149                 x.bucket_count();
 150             float b = x.max_load_factor();
 151
 152             const_iterator r1 = x.insert(x_const.end(), *it);
 153             tracker_iterator r2 = tracker.insert(tracker.end(), *it);
 154             BOOST_TEST(*r1 == *r2);
 155             tracker.compare_key(x, *it);
 156
 157             if (static_cast<double>(x.size()) <=
 158                 b * static_cast<double>(old_bucket_count))
 159                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 160         }
 161
 162         tracker.compare(x);
 163         test::check_equivalent_keys(x);
 164     }
 165
 166     std::cerr << "insert(pos, value) tests.\n";
 167
 168     {
 169         test::check_instances check_;
 170
 171         X x;
 172         const_iterator pos = x.begin();
 173         tracker_type tracker = test::create_ordered(x);
 174
 175         test::random_values<X> v(1000, generator);
 176         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 177                  v.begin();
 178              it != v.end(); ++it) {
 179             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 180                 x.bucket_count();
 181             float b = x.max_load_factor();
 182
 183             pos = x.insert(pos, *it);
 184             tracker_iterator r2 = tracker.insert(tracker.begin(), *it);
 185             BOOST_TEST(*pos == *r2);
 186             tracker.compare_key(x, *it);
 187
 188             if (static_cast<double>(x.size()) <=
 189                 b * static_cast<double>(old_bucket_count))
 190                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 191         }
 192
 193         tracker.compare(x);
 194         test::check_equivalent_keys(x);
 195     }
 196
 197     std::cerr << "insert single item range tests.\n";
 198
 199     {
 200         test::check_instances check_;
 201
 202         X x;
 203         tracker_type tracker = test::create_ordered(x);
 204
 205         test::random_values<X> v(1000, generator);
 206         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 207                  v.begin();
 208              it != v.end(); ++it) {
 209             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 210                 x.bucket_count();
 211             float b = x.max_load_factor();
 212
 213             x.insert(it, test::next(it));
 214             tracker.insert(*it);
 215             tracker.compare_key(x, *it);
 216
 217             if (static_cast<double>(x.size()) <=
 218                 b * static_cast<double>(old_bucket_count))
 219                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 220         }
 221
 222         tracker.compare(x);
 223         test::check_equivalent_keys(x);
 224     }
 225
 226     std::cerr << "insert range tests.\n";
 227
 228     {
 229         test::check_instances check_;
 230
 231         X x;
 232
 233         test::random_values<X> v(1000, generator);
 234         x.insert(v.begin(), v.end());
 235
 236         test::check_container(x, v);
 237         test::check_equivalent_keys(x);
 238     }
 239
 240     std::cerr << "insert range with rehash tests.\n";
 241
 242     {
 243         test::check_instances check_;
 244
 245         X x;
 246
 247         test::random_values<X> v(1000, generator);
 248
 249         x.insert(*v.begin());
 250         x.clear();
 251
 252         x.insert(v.begin(), v.end());
 253
 254         test::check_container(x, v);
 255         test::check_equivalent_keys(x);
 256     }
 257
 258     std::cerr << "insert input iterator range tests.\n";
 259
 260     {
 261         test::check_instances check_;
 262
 263         X x;
 264
 265         test::random_values<X> v(1000, generator);
 266         BOOST_DEDUCED_TYPENAME test::random_values<X>::const_iterator
 267             begin = v.begin(),
 268             end = v.end();
 269         x.insert(test::input_iterator(begin), test::input_iterator(end));
 270         test::check_container(x, v);
 271
 272         test::check_equivalent_keys(x);
 273     }
 274
 275     std::cerr << "insert copy iterator range tests.\n";
 276
 277     {
 278         test::check_instances check_;
 279
 280         X x;
 281
 282         test::random_values<X> v(1000, generator);
 283         x.insert(test::copy_iterator(v.begin()), test::copy_iterator(v.end()));
 284         test::check_container(x, v);
 285
 286         test::check_equivalent_keys(x);
 287     }
 288
 289     std::cerr << "insert copy iterator range test 2.\n";
 290
 291     {
 292         test::check_instances check_;
 293
 294         X x;
 295
 296         test::random_values<X> v1(500, generator);
 297         test::random_values<X> v2(500, generator);
 298         x.insert(
 299             test::copy_iterator(v1.begin()), test::copy_iterator(v1.end()));
 300         x.insert(
 301             test::copy_iterator(v2.begin()), test::copy_iterator(v2.end()));
 302
 303         test::check_equivalent_keys(x);
 304     }
 305
 306     std::cerr << "insert various ranges.\n";
 307
 308     {
 309         for (int i = 0; i < 100; ++i) {
 310             X x;
 311             test::ordered<X> tracker = test::create_ordered(x);
 312
 313             test::random_values<X> v(1000, generator);
 314
 315             for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 316                      v.begin();
 317                  it != v.end();) {
 318                 BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 319                     x.bucket_count();
 320                 float b = x.max_load_factor();
 321
 322                 BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator next =
 323                     it;
 324                 for (std::size_t j = test::random_value(20); j > 0; ++j) {
 325                     ++next;
 326                     if (next == v.end()) {
 327                         break;
 328                     }
 329                 }
 330
 331                 x.insert(it, next);
 332                 tracker.insert(it, next);
 333                 it = next;
 334
 335                 tracker.compare(x); // Slow, but I can't see any other way.
 336
 337                 if (static_cast<double>(x.size()) <=
 338                     b * static_cast<double>(old_bucket_count))
 339                     BOOST_TEST(x.bucket_count() == old_bucket_count);
 340             }
 341
 342             test::check_equivalent_keys(x);
 343         }
 344     }
 345 }
 346
 347 template <class X>
 348 void unique_emplace_tests1(X*, test::random_generator generator)
 349 {
 350     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 351     typedef test::ordered<X> ordered;
 352
 353     std::cerr << "emplace(value) tests for containers with unique keys.\n";
 354
 355     X x;
 356     test::ordered<X> tracker = test::create_ordered(x);
 357
 358     test::random_values<X> v(1000, generator);
 359
 360     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 361          it != v.end(); ++it) {
 362
 363         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 364         float b = x.max_load_factor();
 365
 366         std::pair<iterator, bool> r1 = x.emplace(*it);
 367         std::pair<BOOST_DEDUCED_TYPENAME ordered::iterator, bool> r2 =
 368             tracker.insert(*it);
 369
 370         BOOST_TEST(r1.second == r2.second);
 371         BOOST_TEST(*r1.first == *r2.first);
 372
 373         tracker.compare_key(x, *it);
 374
 375         if (static_cast<double>(x.size()) <=
 376             b * static_cast<double>(old_bucket_count))
 377             BOOST_TEST(x.bucket_count() == old_bucket_count);
 378     }
 379
 380     tracker.compare(x);
 381     test::check_equivalent_keys(x);
 382 }
 383
 384 template <class X>
 385 void equivalent_emplace_tests1(X*, test::random_generator generator)
 386 {
 387     std::cerr << "emplace(value) tests for containers with equivalent keys.\n";
 388
 389     X x;
 390     test::ordered<X> tracker = test::create_ordered(x);
 391
 392     test::random_values<X> v(1000, generator);
 393     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 394          it != v.end(); ++it) {
 395         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 396         float b = x.max_load_factor();
 397
 398         BOOST_DEDUCED_TYPENAME X::iterator r1 = x.emplace(*it);
 399         BOOST_DEDUCED_TYPENAME test::ordered<X>::iterator r2 =
 400             tracker.insert(*it);
 401
 402         BOOST_TEST(*r1 == *r2);
 403
 404         tracker.compare_key(x, *it);
 405
 406         if (static_cast<double>(x.size()) <=
 407             b * static_cast<double>(old_bucket_count))
 408             BOOST_TEST(x.bucket_count() == old_bucket_count);
 409     }
 410
 411     tracker.compare(x);
 412     test::check_equivalent_keys(x);
 413 }
 414
 415 template <class X> void move_emplace_tests(X*, test::random_generator generator)
 416 {
 417     std::cerr
 418         << "emplace(move(value)) tests for containers with unique keys.\n";
 419
 420     X x;
 421     test::ordered<X> tracker = test::create_ordered(x);
 422
 423     test::random_values<X> v(1000, generator);
 424
 425     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 426          it != v.end(); ++it) {
 427
 428         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 429         float b = x.max_load_factor();
 430
 431         typename X::value_type value = *it;
 432         x.emplace(boost::move(value));
 433         tracker.insert(*it);
 434         tracker.compare_key(x, *it);
 435
 436         if (static_cast<double>(x.size()) <=
 437             b * static_cast<double>(old_bucket_count))
 438             BOOST_TEST(x.bucket_count() == old_bucket_count);
 439     }
 440
 441     tracker.compare(x);
 442     test::check_equivalent_keys(x);
 443 }
 444
 445 template <class X> void default_emplace_tests(X*, test::random_generator)
 446 {
 447 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
 448     std::cerr << "emplace() tests.\n";
 449     bool is_unique = test::has_unique_keys<X>::value;
 450
 451     X x;
 452
 453     x.emplace();
 454     BOOST_TEST(x.size() == 1);
 455     x.emplace();
 456     BOOST_TEST(x.size() == (is_unique ? 1u : 2u));
 457     x.emplace();
 458     BOOST_TEST(x.size() == (is_unique ? 1u : 3u));
 459
 460     typename X::value_type y;
 461     BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 3u));
 462     BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
 463
 464     x.emplace(y);
 465     BOOST_TEST(x.size() == (is_unique ? 1u : 4u));
 466     BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 4u));
 467     BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
 468
 469     x.clear();
 470     BOOST_TEST(x.empty());
 471     x.emplace(y);
 472     BOOST_TEST(x.size() == 1);
 473     x.emplace(y);
 474     BOOST_TEST(x.size() == (is_unique ? 1u : 2u));
 475
 476     BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 2u));
 477     BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
 478 #endif
 479 }
 480
 481 template <class X> void map_tests(X*, test::random_generator generator)
 482 {
 483     std::cerr << "map tests.\n";
 484
 485     X x;
 486     test::ordered<X> tracker = test::create_ordered(x);
 487
 488     test::random_values<X> v(1000, generator);
 489     for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
 490          it != v.end(); ++it) {
 491         BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
 492         float b = x.max_load_factor();
 493
 494         x[it->first] = it->second;
 495         tracker[it->first] = it->second;
 496
 497         tracker.compare_key(x, *it);
 498
 499         if (static_cast<double>(x.size()) <=
 500             b * static_cast<double>(old_bucket_count))
 501             BOOST_TEST(x.bucket_count() == old_bucket_count);
 502     }
 503
 504     tracker.compare(x);
 505     test::check_equivalent_keys(x);
 506 }
 507
 508 template <class X> void map_tests2(X*, test::random_generator generator)
 509 {
 510     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 511     std::cerr << "insert_or_assign\n";
 512
 513     {
 514         test::check_instances check_;
 515
 516         X x;
 517         test::ordered<X> tracker = test::create_ordered(x);
 518
 519         test::random_values<X> v(1000, generator);
 520         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 521                  v.begin();
 522              it != v.end(); ++it) {
 523             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 524                 x.bucket_count();
 525             float b = x.max_load_factor();
 526
 527             std::pair<iterator, bool> r =
 528                 x.insert_or_assign(it->first, it->second);
 529             BOOST_TEST(*r.first == *it);
 530
 531             tracker[it->first] = it->second;
 532             tracker.compare_key(x, *it);
 533
 534             if (static_cast<double>(x.size()) <
 535                 b * static_cast<double>(old_bucket_count))
 536                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 537         }
 538
 539         tracker.compare(x);
 540         test::check_equivalent_keys(x);
 541     }
 542
 543     std::cerr << "insert_or_assign(begin)\n";
 544
 545     {
 546         test::check_instances check_;
 547
 548         X x;
 549         test::ordered<X> tracker = test::create_ordered(x);
 550
 551         test::random_values<X> v(1000, generator);
 552         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 553                  v.begin();
 554              it != v.end(); ++it) {
 555             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 556                 x.bucket_count();
 557             float b = x.max_load_factor();
 558
 559             iterator r = x.insert_or_assign(x.begin(), it->first, it->second);
 560             BOOST_TEST(*r == *it);
 561
 562             tracker[it->first] = it->second;
 563             tracker.compare_key(x, *it);
 564
 565             if (static_cast<double>(x.size()) <
 566                 b * static_cast<double>(old_bucket_count))
 567                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 568         }
 569
 570         tracker.compare(x);
 571         test::check_equivalent_keys(x);
 572     }
 573
 574     std::cerr << "insert_or_assign(end)\n";
 575
 576     {
 577         test::check_instances check_;
 578
 579         X x;
 580         test::ordered<X> tracker = test::create_ordered(x);
 581
 582         test::random_values<X> v(1000, generator);
 583         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 584                  v.begin();
 585              it != v.end(); ++it) {
 586             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 587                 x.bucket_count();
 588             float b = x.max_load_factor();
 589
 590             iterator r = x.insert_or_assign(x.end(), it->first, it->second);
 591             BOOST_TEST(*r == *it);
 592
 593             tracker[it->first] = it->second;
 594             tracker.compare_key(x, *it);
 595
 596             if (static_cast<double>(x.size()) <
 597                 b * static_cast<double>(old_bucket_count))
 598                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 599         }
 600
 601         tracker.compare(x);
 602         test::check_equivalent_keys(x);
 603     }
 604
 605     std::cerr << "insert_or_assign(last)\n";
 606
 607     {
 608         test::check_instances check_;
 609
 610         X x;
 611         test::ordered<X> tracker = test::create_ordered(x);
 612         iterator last = x.begin();
 613
 614         test::random_values<X> v(1000, generator);
 615         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 616                  v.begin();
 617              it != v.end(); ++it) {
 618             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 619                 x.bucket_count();
 620             float b = x.max_load_factor();
 621
 622             iterator r = x.insert_or_assign(last, it->first, it->second);
 623             BOOST_TEST(*r == *it);
 624
 625             tracker[it->first] = it->second;
 626             tracker.compare_key(x, *it);
 627
 628             if (static_cast<double>(x.size()) <
 629                 b * static_cast<double>(old_bucket_count))
 630                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 631
 632             last = r;
 633         }
 634
 635         tracker.compare(x);
 636         test::check_equivalent_keys(x);
 637     }
 638 }
 639
 640 template <class X> void try_emplace_tests(X*, test::random_generator generator)
 641 {
 642     std::cerr << "try_emplace(key, value)\n";
 643
 644     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 645
 646     {
 647         test::check_instances check_;
 648
 649         X x;
 650         test::ordered<X> tracker = test::create_ordered(x);
 651
 652         test::random_values<X> v(1000, generator);
 653         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 654                  v.begin();
 655              it != v.end(); ++it) {
 656             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 657                 x.bucket_count();
 658             float b = x.max_load_factor();
 659
 660             iterator pos = x.find(it->first);
 661             bool found = pos != x.end();
 662
 663             std::pair<typename X::iterator, bool> r =
 664                 x.try_emplace(it->first, it->second);
 665             if (found) {
 666                 BOOST_TEST(pos == r.first);
 667                 BOOST_TEST(!r.second);
 668             } else {
 669                 BOOST_TEST(r.second);
 670             }
 671             BOOST_TEST_EQ(r.first->first, it->first);
 672             BOOST_TEST_EQ(r.first->second, it->second);
 673
 674             tracker.insert(*it);
 675             tracker.compare_key(x, *it);
 676
 677             if (static_cast<double>(x.size()) <
 678                 b * static_cast<double>(old_bucket_count))
 679                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 680         }
 681
 682         test::check_equivalent_keys(x);
 683     }
 684
 685     std::cerr << "try_emplace(begin(), key, value)\n";
 686
 687     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 688
 689     {
 690         test::check_instances check_;
 691
 692         X x;
 693         test::ordered<X> tracker = test::create_ordered(x);
 694
 695         test::random_values<X> v(1000, generator);
 696         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 697                  v.begin();
 698              it != v.end(); ++it) {
 699             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 700                 x.bucket_count();
 701             float b = x.max_load_factor();
 702
 703             iterator pos = x.find(it->first);
 704             bool found = pos != x.end();
 705
 706             typename X::iterator r =
 707                 x.try_emplace(r.begin(), it->first, it->second);
 708             if (found) {
 709                 BOOST_TEST(pos == r);
 710             }
 711             BOOST_TEST_EQ(r->first, it->first);
 712             BOOST_TEST_EQ(r->second, it->second);
 713
 714             tracker.insert(*it);
 715             tracker.compare_key(x, *it);
 716
 717             if (static_cast<double>(x.size()) <
 718                 b * static_cast<double>(old_bucket_count))
 719                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 720         }
 721
 722         test::check_equivalent_keys(x);
 723     }
 724
 725     std::cerr << "try_emplace(end(), key, value)\n";
 726
 727     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 728
 729     {
 730         test::check_instances check_;
 731
 732         X x;
 733         test::ordered<X> tracker = test::create_ordered(x);
 734
 735         test::random_values<X> v(1000, generator);
 736         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 737                  v.begin();
 738              it != v.end(); ++it) {
 739             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 740                 x.bucket_count();
 741             float b = x.max_load_factor();
 742
 743             iterator pos = x.find(it->first);
 744             bool found = pos != x.end();
 745
 746             typename X::iterator r =
 747                 x.try_emplace(r.end(), it->first, it->second);
 748             if (found) {
 749                 BOOST_TEST(pos == r);
 750             }
 751             BOOST_TEST_EQ(r->first, it->first);
 752             BOOST_TEST_EQ(r->second, it->second);
 753
 754             tracker.insert(*it);
 755             tracker.compare_key(x, *it);
 756
 757             if (static_cast<double>(x.size()) <
 758                 b * static_cast<double>(old_bucket_count))
 759                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 760         }
 761
 762         test::check_equivalent_keys(x);
 763     }
 764
 765     std::cerr << "try_emplace(pos, key, value)\n";
 766
 767     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
 768
 769     {
 770         test::check_instances check_;
 771
 772         X x;
 773         test::ordered<X> tracker = test::create_ordered(x);
 774
 775         test::random_values<X> v(1000, generator);
 776         for (BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it =
 777                  v.begin();
 778              it != v.end(); ++it) {
 779             BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count =
 780                 x.bucket_count();
 781             float b = x.max_load_factor();
 782
 783             iterator pos = x.find(it->first);
 784             bool found = pos != x.end();
 785
 786             typename X::iterator r = x.try_emplace(pos, it->first, it->second);
 787             if (found) {
 788                 BOOST_TEST(pos == r);
 789             }
 790             BOOST_TEST_EQ(r->first, it->first);
 791             BOOST_TEST_EQ(r->second, it->second);
 792
 793             tracker.insert(*it);
 794             tracker.compare_key(x, *it);
 795
 796             if (static_cast<double>(x.size()) <
 797                 b * static_cast<double>(old_bucket_count))
 798                 BOOST_TEST(x.bucket_count() == old_bucket_count);
 799         }
 800
 801         test::check_equivalent_keys(x);
 802     }
 803 }
 804
 805 // Some tests for when the range's value type doesn't match the container's
 806 // value type.
 807
 808 template <class X>
 809 void map_insert_range_test1(X*, test::random_generator generator)
 810 {
 811     std::cerr << "map_insert_range_test1\n";
 812
 813     test::check_instances check_;
 814
 815     typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type,
 816         BOOST_DEDUCED_TYPENAME X::mapped_type> >
 817         list;
 818     test::random_values<X> v(1000, generator);
 819     list l(v.begin(), v.end());
 820
 821     X x;
 822     x.insert(l.begin(), l.end());
 823
 824     test::check_equivalent_keys(x);
 825 }
 826
 827 template <class X>
 828 void map_insert_range_test2(X*, test::random_generator generator)
 829 {
 830     std::cerr << "map_insert_range_test2\n";
 831
 832     test::check_instances check_;
 833
 834     typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type const,
 835         test::implicitly_convertible> >
 836         list;
 837     test::random_values<boost::unordered_map<BOOST_DEDUCED_TYPENAME X::key_type,
 838         test::implicitly_convertible> >
 839         v(1000, generator);
 840     list l(v.begin(), v.end());
 841
 842     X x;
 843     x.insert(l.begin(), l.end());
 844
 845     test::check_equivalent_keys(x);
 846 }
 847
 848 boost::unordered_set<test::movable, test::hash, test::equal_to,
 849     std::allocator<test::movable> >* test_set_std_alloc;
 850 boost::unordered_multimap<test::object, test::object, test::hash,
 851     test::equal_to, std::allocator<test::object> >* test_multimap_std_alloc;
 852
 853 boost::unordered_set<test::object, test::hash, test::equal_to,
 854     test::allocator1<test::object> >* test_set;
 855 boost::unordered_multiset<test::movable, test::hash, test::equal_to,
 856     test::allocator2<test::movable> >* test_multiset;
 857 boost::unordered_map<test::movable, test::movable, test::hash, test::equal_to,
 858     test::allocator2<test::movable> >* test_map;
 859 boost::unordered_multimap<test::object, test::object, test::hash,
 860     test::equal_to, test::allocator1<test::object> >* test_multimap;
 861
 862 using test::default_generator;
 863 using test::generate_collisions;
 864 using test::limited_range;
 865
 866 UNORDERED_TEST(unique_insert_tests1,
 867     ((test_set_std_alloc)(test_set)(test_map))(
 868                    (default_generator)(generate_collisions)(limited_range)))
 869
 870 UNORDERED_TEST(equivalent_insert_tests1,
 871     ((test_multimap_std_alloc)(test_multiset)(test_multimap))(
 872                    (default_generator)(generate_collisions)(limited_range)))
 873
 874 UNORDERED_TEST(
 875     insert_tests2, ((test_multimap_std_alloc)(test_set)(test_multiset)(
 876                        test_map)(test_multimap))(
 877                        (default_generator)(generate_collisions)(limited_range)))
 878
 879 UNORDERED_TEST(unique_emplace_tests1,
 880     ((test_set_std_alloc)(test_set)(test_map))(
 881                    (default_generator)(generate_collisions)(limited_range)))
 882
 883 UNORDERED_TEST(equivalent_emplace_tests1,
 884     ((test_multimap_std_alloc)(test_multiset)(test_multimap))(
 885                    (default_generator)(generate_collisions)(limited_range)))
 886
 887 UNORDERED_TEST(move_emplace_tests,
 888     ((test_set_std_alloc)(test_multimap_std_alloc)(test_set)(test_map)(
 889         test_multiset)(test_multimap))(
 890                    (default_generator)(generate_collisions)(limited_range)))
 891
 892 UNORDERED_TEST(default_emplace_tests,
 893     ((test_set_std_alloc)(test_multimap_std_alloc)(test_set)(test_map)(
 894         test_multiset)(test_multimap))(
 895                    (default_generator)(generate_collisions)(limited_range)))
 896
 897 UNORDERED_TEST(map_tests,
 898     ((test_map))((default_generator)(generate_collisions)(limited_range)))
 899
 900 UNORDERED_TEST(
 901     map_tests2, ((test_map))((default_generator)(generate_collisions)))
 902
 903 UNORDERED_TEST(map_insert_range_test1,
 904     ((test_multimap_std_alloc)(test_map)(test_multimap))(
 905                    (default_generator)(generate_collisions)(limited_range)))
 906
 907 UNORDERED_TEST(map_insert_range_test2,
 908     ((test_multimap_std_alloc)(test_map)(test_multimap))(
 909                    (default_generator)(generate_collisions)(limited_range)))
 910
 911 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 912
 913 struct initialize_from_two_ints
 914 {
 915     int a, b;
 916
 917     friend std::size_t hash_value(initialize_from_two_ints const& x)
 918     {
 919         return static_cast<std::size_t>(x.a + x.b);
 920     }
 921
 922     bool operator==(initialize_from_two_ints const& x) const
 923     {
 924         return a == x.a && b == x.b;
 925     }
 926 };
 927
 928 UNORDERED_AUTO_TEST(insert_initializer_list_set)
 929 {
 930     boost::unordered_set<int> set;
 931     set.insert({1, 2, 3, 1});
 932     BOOST_TEST_EQ(set.size(), 3u);
 933     BOOST_TEST(set.find(1) != set.end());
 934     BOOST_TEST(set.find(4) == set.end());
 935
 936     boost::unordered_set<initialize_from_two_ints> set2;
 937
 938 #if defined(__GNUC__) && (__GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 5))
 939     set2.insert({{1, 2}});
 940 #else
 941     set2.insert({1, 2});
 942 #endif
 943     BOOST_TEST(set2.size() == 1);
 944     BOOST_TEST(set2.find({1, 2}) != set2.end());
 945     BOOST_TEST(set2.find({2, 1}) == set2.end());
 946
 947     set2.insert({{3, 4}, {5, 6}, {7, 8}});
 948     BOOST_TEST(set2.size() == 4);
 949     BOOST_TEST(set2.find({1, 2}) != set2.end());
 950     BOOST_TEST(set2.find({3, 4}) != set2.end());
 951     BOOST_TEST(set2.find({5, 6}) != set2.end());
 952     BOOST_TEST(set2.find({7, 8}) != set2.end());
 953     BOOST_TEST(set2.find({8, 7}) == set2.end());
 954
 955     set2.insert({{2, 1}, {3, 4}});
 956     BOOST_TEST(set2.size() == 5);
 957     BOOST_TEST(set2.find({1, 2}) != set2.end());
 958     BOOST_TEST(set2.find({2, 1}) != set2.end());
 959     BOOST_TEST(set2.find({3, 4}) != set2.end());
 960     BOOST_TEST(set2.find({5, 6}) != set2.end());
 961     BOOST_TEST(set2.find({7, 8}) != set2.end());
 962     BOOST_TEST(set2.find({8, 7}) == set2.end());
 963 }
 964
 965 #if !BOOST_WORKAROUND(BOOST_MSVC, == 1800)
 966
 967 UNORDERED_AUTO_TEST(insert_initializer_list_multiset)
 968 {
 969     boost::unordered_multiset<std::string> multiset;
 970     // multiset.insert({});
 971     BOOST_TEST(multiset.empty());
 972     multiset.insert({"a"});
 973     BOOST_TEST_EQ(multiset.size(), 1u);
 974     BOOST_TEST(multiset.find("a") != multiset.end());
 975     BOOST_TEST(multiset.find("b") == multiset.end());
 976     multiset.insert({"a", "b"});
 977     BOOST_TEST(multiset.size() == 3);
 978     BOOST_TEST_EQ(multiset.count("a"), 2u);
 979     BOOST_TEST_EQ(multiset.count("b"), 1u);
 980     BOOST_TEST_EQ(multiset.count("c"), 0u);
 981 }
 982
 983 #endif
 984
 985 UNORDERED_AUTO_TEST(insert_initializer_list_map)
 986 {
 987     boost::unordered_map<std::string, std::string> map;
 988     // map.insert({});
 989     BOOST_TEST(map.empty());
 990     map.insert({{"a", "b"}, {"a", "b"}, {"d", ""}});
 991     BOOST_TEST_EQ(map.size(), 2u);
 992 }
 993
 994 UNORDERED_AUTO_TEST(insert_initializer_list_multimap)
 995 {
 996     boost::unordered_multimap<std::string, std::string> multimap;
 997     // multimap.insert({});
 998     BOOST_TEST(multimap.empty());
 999     multimap.insert({{"a", "b"}, {"a", "b"}, {"d", ""}});
1000     BOOST_TEST_EQ(multimap.size(), 3u);
1001     BOOST_TEST_EQ(multimap.count("a"), 2u);
1002 }
1003
1004 #endif
1005
1006 struct overloaded_constructor
1007 {
1008     overloaded_constructor(int x1_ = 1, int x2_ = 2, int x3_ = 3, int x4_ = 4)
1009         : x1(x1_), x2(x2_), x3(x3_), x4(x4_)
1010     {
1011     }
1012
1013     int x1, x2, x3, x4;
1014
1015     bool operator==(overloaded_constructor const& rhs) const
1016     {
1017         return x1 == rhs.x1 && x2 == rhs.x2 && x3 == rhs.x3 && x4 == rhs.x4;
1018     }
1019
1020     friend std::size_t hash_value(overloaded_constructor const& x)
1021     {
1022         std::size_t hash = 0;
1023         boost::hash_combine(hash, x.x1);
1024         boost::hash_combine(hash, x.x2);
1025         boost::hash_combine(hash, x.x3);
1026         boost::hash_combine(hash, x.x4);
1027         return hash;
1028     }
1029 };
1030
1031 UNORDERED_AUTO_TEST(map_emplace_test)
1032 {
1033     boost::unordered_map<int, overloaded_constructor> x;
1034
1035 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
1036     x.emplace();
1037     BOOST_TEST(
1038         x.find(0) != x.end() && x.find(0)->second == overloaded_constructor());
1039 #endif
1040
1041     x.emplace(2, 3);
1042     BOOST_TEST(
1043         x.find(2) != x.end() && x.find(2)->second == overloaded_constructor(3));
1044
1045     x.try_emplace(5);
1046     BOOST_TEST(
1047         x.find(5) != x.end() && x.find(5)->second == overloaded_constructor());
1048 }
1049
1050 UNORDERED_AUTO_TEST(set_emplace_test)
1051 {
1052     boost::unordered_set<overloaded_constructor> x;
1053     overloaded_constructor check;
1054
1055 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
1056     x.emplace();
1057     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1058 #endif
1059
1060     x.clear();
1061     x.emplace(1);
1062     check = overloaded_constructor(1);
1063     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1064
1065     x.clear();
1066     x.emplace(2, 3);
1067     check = overloaded_constructor(2, 3);
1068     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1069
1070     x.clear();
1071     x.emplace(4, 5, 6);
1072     check = overloaded_constructor(4, 5, 6);
1073     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1074
1075     x.clear();
1076     x.emplace(7, 8, 9, 10);
1077     check = overloaded_constructor(7, 8, 9, 10);
1078     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1079 }
1080
1081 struct derived_from_piecewise_construct_t
1082     : boost::unordered::piecewise_construct_t
1083 {
1084 };
1085
1086 derived_from_piecewise_construct_t piecewise_rvalue()
1087 {
1088     return derived_from_piecewise_construct_t();
1089 }
1090
1091 struct convertible_to_piecewise
1092 {
1093     operator boost::unordered::piecewise_construct_t() const
1094     {
1095         return boost::unordered::piecewise_construct;
1096     }
1097 };
1098
1099 UNORDERED_AUTO_TEST(map_emplace_test2)
1100 {
1101     boost::unordered_map<overloaded_constructor, overloaded_constructor> x;
1102
1103     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
1104         boost::make_tuple());
1105     BOOST_TEST(
1106         x.find(overloaded_constructor()) != x.end() &&
1107         x.find(overloaded_constructor())->second == overloaded_constructor());
1108
1109     x.emplace(
1110         convertible_to_piecewise(), boost::make_tuple(1), boost::make_tuple());
1111     BOOST_TEST(
1112         x.find(overloaded_constructor(1)) != x.end() &&
1113         x.find(overloaded_constructor(1))->second == overloaded_constructor());
1114
1115     x.emplace(piecewise_rvalue(), boost::make_tuple(2, 3),
1116         boost::make_tuple(4, 5, 6));
1117     BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1118                x.find(overloaded_constructor(2, 3))->second ==
1119                    overloaded_constructor(4, 5, 6));
1120
1121     derived_from_piecewise_construct_t d;
1122     x.emplace(d, boost::make_tuple(9, 3, 1), boost::make_tuple(10));
1123     BOOST_TEST(x.find(overloaded_constructor(9, 3, 1)) != x.end() &&
1124                x.find(overloaded_constructor(9, 3, 1))->second ==
1125                    overloaded_constructor(10));
1126
1127     x.clear();
1128
1129     x.try_emplace(overloaded_constructor());
1130     BOOST_TEST(
1131         x.find(overloaded_constructor()) != x.end() &&
1132         x.find(overloaded_constructor())->second == overloaded_constructor());
1133
1134     x.try_emplace(1);
1135     BOOST_TEST(
1136         x.find(overloaded_constructor(1)) != x.end() &&
1137         x.find(overloaded_constructor(1))->second == overloaded_constructor());
1138
1139     x.try_emplace(overloaded_constructor(2, 3), 4, 5, 6);
1140     BOOST_TEST(x.find(overloaded_constructor(2, 3)) != x.end() &&
1141                x.find(overloaded_constructor(2, 3))->second ==
1142                    overloaded_constructor(4, 5, 6));
1143 }
1144
1145 UNORDERED_AUTO_TEST(set_emplace_test2)
1146 {
1147     boost::unordered_set<
1148         std::pair<overloaded_constructor, overloaded_constructor> >
1149         x;
1150     std::pair<overloaded_constructor, overloaded_constructor> check;
1151
1152     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
1153         boost::make_tuple());
1154     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1155
1156     x.clear();
1157     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(1),
1158         boost::make_tuple(2, 3));
1159     check =
1160         std::make_pair(overloaded_constructor(1), overloaded_constructor(2, 3));
1161     ;
1162     BOOST_TEST(x.find(check) != x.end() && *x.find(check) == check);
1163 }
1164 }
1165
1166 RUN_TESTS()