libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc

   1 // Copyright (C) 2016-2025 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 3, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING3.  If not see
  16 // <http://www.gnu.org/licenses/>.
  17
  18 // { dg-do run { target c++17 } }
  19
  20 #include <string>
  21 #include <functional>
  22 #include <unordered_map>
  23 #include <algorithm>
  24 #include <testsuite_hooks.h>
  25
  26 using test_type = std::unordered_map<int, int>;
  27
  28 template<typename T>
  29   struct xhash
  30   {
  31     auto operator()(const T& i) const noexcept
  32     { return ~std::hash<T>()(i); }
  33   };
  34
  35
  36 namespace std
  37 {
  38   template<typename T>
  39     struct __is_fast_hash<xhash<T>> : __is_fast_hash<std::hash<T>>
  40     { };
  41 }
  42
  43 struct equal : std::equal_to<> { };
  44
  45 template<typename C1, typename C2>
  46 bool equal_elements(const C1& c1, const C2& c2)
  47 {
  48   if (c2.size() != c1.size())
  49     return false;
  50   for (auto& i : c1)
  51     if (c2.count(i.first) != c1.count(i.first))
  52       return false;
  53   return true;
  54 }
  55
  56 void
  57 test01()
  58 {
  59   const test_type c0{ {1, 10}, {2, 20}, {3, 30} };
  60   test_type c1 = c0, c2 = c0;
  61
  62   c1.merge(c2);
  63   VERIFY( c1 == c0 );
  64   VERIFY( c2 == c0 );
  65
  66   c1.clear();
  67   c1.merge(c2);
  68   VERIFY( c1 == c0 );
  69   VERIFY( c2.empty() );
  70
  71   c2.merge(std::move(c1));
  72   VERIFY( c1.empty() );
  73   VERIFY( c2 == c0 );
  74 }
  75
  76 void
  77 test02()
  78 {
  79   const test_type c0{ {1, 10}, {2, 20}, {3, 30} };
  80   test_type c1 = c0;
  81   std::unordered_map<int, int, xhash<int>, equal> c2( c0.begin(), c0.end() );
  82
  83   c1.merge(c2);
  84   VERIFY( c1 == c0 );
  85   VERIFY( equal_elements(c2, c0) );
  86
  87   c1.clear();
  88   c1.merge(c2);
  89   VERIFY( c1 == c0 );
  90   VERIFY( c2.empty() );
  91
  92   c2.merge(c1);
  93   VERIFY( c1.empty() );
  94   VERIFY( equal_elements(c2, c0) );
  95
  96   c1.merge(std::move(c2));
  97   VERIFY( c2.empty() );
  98   VERIFY( c1 == c0 );
  99 }
 100
 101 void
 102 test03()
 103 {
 104   const test_type c0{ {1, 10}, {2, 20}, {3, 30} };
 105   test_type c1 = c0;
 106   std::unordered_multimap<int, int, xhash<int>, equal> c2( c0.begin(), c0.end() );
 107   c1.merge(c2);
 108   VERIFY( c1 == c0 );
 109   VERIFY( equal_elements(c2, c0) );
 110
 111   c1.clear();
 112   c1.merge(c2);
 113   VERIFY( c1 == c0 );
 114   VERIFY( c2.empty() );
 115
 116   c2.merge(c1);
 117   VERIFY( c1.empty() );
 118   VERIFY( equal_elements(c2, c0) );
 119
 120   c1 = c0;
 121   c2.merge(c1);
 122   VERIFY( c1.empty() );
 123   VERIFY( c2.size() == (2 * c0.size()) );
 124   VERIFY( c2.count(1) == 2 );
 125   VERIFY( c2.count(2) == 2 );
 126   VERIFY( c2.count(3) == 2 );
 127
 128   c1.merge(c2);
 129   VERIFY( c1 == c0 );
 130   VERIFY( equal_elements(c2, c0) );
 131
 132   c1.merge(std::move(c2));
 133   VERIFY( c1 == c0 );
 134   VERIFY( equal_elements(c2, c0) );
 135
 136   c1.clear();
 137   c1.merge(std::move(c2));
 138   VERIFY( c1 == c0 );
 139   VERIFY( c2.empty() );
 140 }
 141
 142 void
 143 test04()
 144 {
 145   const std::unordered_map<std::string, int> c0
 146     { {"one", 10}, {"two", 20}, {"three", 30} };
 147
 148   std::unordered_map<std::string, int> c1 = c0;
 149   std::unordered_multimap<std::string, int> c2( c0.begin(), c0.end() );
 150   c1.merge(c2);
 151   VERIFY( c1 == c0 );
 152   VERIFY( equal_elements(c2, c0) );
 153
 154   c1.clear();
 155   c1.merge(c2);
 156   VERIFY( c1 == c0 );
 157   VERIFY( c2.empty() );
 158
 159   c2.merge(c1);
 160   VERIFY( c1.empty() );
 161   VERIFY( equal_elements(c2, c0) );
 162
 163   c1 = c0;
 164   c2.merge(c1);
 165   VERIFY( c1.empty() );
 166   VERIFY( c2.size() == (2 * c0.size()) );
 167   VERIFY( c2.count("one") == 2 );
 168   VERIFY( c2.count("two") == 2 );
 169   VERIFY( c2.count("three") == 2 );
 170
 171   c1.merge(c2);
 172   VERIFY( c1 == c0 );
 173   VERIFY( equal_elements(c2, c0) );
 174
 175   c1.merge(std::move(c2));
 176   VERIFY( c1 == c0 );
 177   VERIFY( equal_elements(c2, c0) );
 178
 179   c1.clear();
 180   c1.merge(std::move(c2));
 181   VERIFY( c1 == c0 );
 182   VERIFY( c2.empty() );
 183 }
 184
 185 void
 186 test05()
 187 {
 188   const std::unordered_map<std::string, int> c0
 189     { {"one", 10}, {"two", 20}, {"three", 30} };
 190
 191   std::unordered_map<std::string, int> c1 = c0;
 192   std::unordered_multimap<std::string, int, xhash<std::string>, equal> c2( c0.begin(), c0.end() );
 193   c1.merge(c2);
 194   VERIFY( c1 == c0 );
 195   VERIFY( equal_elements(c2, c0) );
 196
 197   c1.clear();
 198   c1.merge(c2);
 199   VERIFY( c1 == c0 );
 200   VERIFY( c2.empty() );
 201
 202   c2.merge(c1);
 203   VERIFY( c1.empty() );
 204   VERIFY( equal_elements(c2, c0) );
 205
 206   c1 = c0;
 207   c2.merge(c1);
 208   VERIFY( c1.empty() );
 209   VERIFY( c2.size() == (2 * c0.size()) );
 210   VERIFY( c2.count("one") == 2 );
 211   VERIFY( c2.count("two") == 2 );
 212   VERIFY( c2.count("three") == 2 );
 213
 214   c1.merge(c2);
 215   VERIFY( c1 == c0 );
 216   VERIFY( equal_elements(c2, c0) );
 217
 218   c1.merge(std::move(c2));
 219   VERIFY( c1 == c0 );
 220   VERIFY( equal_elements(c2, c0) );
 221
 222   c1.clear();
 223   c1.merge(std::move(c2));
 224   VERIFY( c1 == c0 );
 225   VERIFY( c2.empty() );
 226 }
 227
 228 template<typename T>
 229   using hash_f =
 230     std::function<std::size_t(const T&)>;
 231
 232 std::size_t
 233 hash_func(const std::string& str)
 234 { return std::hash<std::string>{}(str);  }
 235
 236 std::size_t
 237 xhash_func(const std::string& str)
 238 { return xhash<std::string>{}(str); }
 239
 240 namespace std
 241 {
 242   template<typename T>
 243     struct __is_fast_hash<hash_f<T>> : __is_fast_hash<std::hash<T>>
 244     { };
 245 }
 246
 247 void
 248 test06()
 249 {
 250   const std::unordered_map<std::string, int, hash_f<std::string>, equal>
 251     c0({ {"one", 10}, {"two", 20}, {"three", 30} }, 3, &hash_func);
 252
 253   std::unordered_map<std::string, int, hash_f<std::string>, equal>
 254     c1(3, &hash_func);
 255   c1 = c0;
 256   std::unordered_multimap<std::string, int, hash_f<std::string>, equal>
 257     c2(c0.begin(), c0.end(), 3, &xhash_func);
 258   c1.merge(c2);
 259   VERIFY( c1 == c0 );
 260   VERIFY( equal_elements(c2, c0) );
 261
 262   c1.clear();
 263   c1.merge(c2);
 264   VERIFY( c1 == c0 );
 265   VERIFY( c2.empty() );
 266
 267   c2.merge(c1);
 268   VERIFY( c1.empty() );
 269   VERIFY( equal_elements(c2, c0) );
 270
 271   c1 = c0;
 272   c2.merge(c1);
 273   VERIFY( c1.empty() );
 274   VERIFY( c2.size() == (2 * c0.size()) );
 275   VERIFY( c2.count("one") == 2 );
 276   VERIFY( c2.count("two") == 2 );
 277   VERIFY( c2.count("three") == 2 );
 278
 279   c1.merge(c2);
 280   VERIFY( c1 == c0 );
 281   VERIFY( equal_elements(c2, c0) );
 282
 283   c1.merge(std::move(c2));
 284   VERIFY( c1 == c0 );
 285   VERIFY( equal_elements(c2, c0) );
 286
 287   c1.clear();
 288   c1.merge(std::move(c2));
 289   VERIFY( c1 == c0 );
 290   VERIFY( c2.empty() );
 291 }
 292
 293 void
 294 test07()
 295 {
 296   test_type c1{ {1, 1}, {3, 3}, {5, 5} };
 297   test_type c2{ {2, 2}, {4, 4}, {6, 6} };
 298   const test_type c3 = c2;
 299
 300   c1.merge(c2);
 301   VERIFY( c1.size() == 6 );
 302   VERIFY( c2.empty() );
 303   const test_type c4 = c1;
 304
 305   c2 = c3;
 306   c1.clear();
 307   c1.merge(std::move(c2));
 308   VERIFY( c1 == c3 );
 309   VERIFY( c2.empty() );
 310
 311   c2.merge(std::move(c1));
 312   VERIFY( c1.empty() );
 313   VERIFY( c2 == c3 );
 314
 315   c2.merge(c1);
 316   VERIFY( c1.empty() );
 317   VERIFY( c2 == c3 );
 318
 319   c2.merge(c2);
 320   VERIFY( c2 == c3 );
 321
 322   test_type c5 = c3;
 323   c2.merge(c5);
 324   VERIFY( c2 == c3 );
 325   VERIFY( c5 == c3 );
 326
 327   c5.emplace(9, 9);
 328   c2.merge(c5);
 329   VERIFY( c2.size() == c3.size() + 1 );
 330   VERIFY( c5 == c3 );
 331 }
 332
 333 void
 334 test08()
 335 {
 336   test_type c1{ {1, 1}, {3, 3}, {5, 5} };
 337   std::unordered_map<int, int, xhash<int>, equal> c2{ {2, 2}, {4, 4}, {6, 6} };
 338   const auto c3 = c2;
 339
 340   c1.merge(c2);
 341   VERIFY( c1.size() == 6 );
 342   VERIFY( c2.empty() );
 343   const test_type c4 = c1;
 344
 345   c2 = c3;
 346   c1.clear();
 347   c1.merge(std::move(c2));
 348   VERIFY( equal_elements(c1, c3) );
 349   VERIFY( c2.empty() );
 350
 351   c2.merge(std::move(c1));
 352   VERIFY( c1.empty() );
 353   VERIFY( c2 == c3 );
 354
 355   c2.merge(c1);
 356   VERIFY( c1.empty() );
 357   VERIFY( c2 == c3 );
 358
 359   c2.merge(c2);
 360   VERIFY( c2 == c3 );
 361
 362   auto c5 = c3;
 363   c2.merge(c5);
 364   VERIFY( c2 == c3 );
 365   VERIFY( c5 == c3 );
 366
 367   c5.emplace(9, 9);
 368   c2.merge(c5);
 369   VERIFY( c2.size() == c3.size() + 1 );
 370   VERIFY( c5 == c3 );
 371 }
 372
 373 void
 374 test09()
 375 {
 376   struct stateful_hash
 377   {
 378     size_t seed = 0;
 379
 380     auto operator()(const int& i) const noexcept
 381     { return std::hash<int>()(i) + seed; }
 382   };
 383
 384   using map_type = std::unordered_map<int, int, stateful_hash>;
 385   map_type c1({ {1, 1}, {3, 3}, {5, 5} }, 0, stateful_hash{1});
 386   map_type c2({ {2, 2}, {4, 4}, {6, 6} }, 0, stateful_hash{2});
 387   const auto c3 = c2;
 388
 389   c1.merge(c2);
 390   VERIFY( c1.size() == 6 );
 391   VERIFY( c2.empty() );
 392
 393   c2 = c3;
 394   c1.clear();
 395   c1.merge(std::move(c2));
 396   VERIFY( c1 == c3 );
 397   VERIFY( c2.empty() );
 398
 399   c2.merge(std::move(c1));
 400   VERIFY( c1.empty() );
 401   VERIFY( c2 == c3 );
 402
 403   c2.merge(c1);
 404   VERIFY( c1.empty() );
 405   VERIFY( c2 == c3 );
 406
 407   c2.merge(c2);
 408   VERIFY( c2 == c3 );
 409
 410   test_type c5{ {-1, 1}, {-3, 3}, {-5, 5} };
 411   c2.merge(c5);
 412   VERIFY( c2.size() == 6 );
 413   VERIFY( c5.empty() );
 414   auto c6 = c3;
 415   c6.merge(c2);
 416   VERIFY( c6.size() == 6 );
 417   VERIFY( c2.size() == 3 );
 418 }
 419
 420 int
 421 main()
 422 {
 423   test01();
 424   test02();
 425   test03();
 426   test04();
 427   test05();
 428   test06();
 429   test07();
 430   test08();
 431   test09();
 432 }