libstdc++: unordered_set.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#ifndef _UNORDERED_SET_H
31#define _UNORDERED_SET_H
32
37
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
42
43
44 template<bool _Cache>
45 using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
46
47 template<typename _Value,
52 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
53 __detail::_Identity, _Pred, _Hash,
54 __detail::_Mod_range_hashing,
55 __detail::_Default_ranged_hash,
56 __detail::_Prime_rehash_policy, _Tr>;
57
58
59 template<bool _Cache>
60 using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
61
62 template<typename _Value,
67 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
68 __detail::_Identity,
69 _Pred, _Hash,
70 __detail::_Mod_range_hashing,
71 __detail::_Default_ranged_hash,
72 __detail::_Prime_rehash_policy, _Tr>;
73
74 template<class _Value, class _Hash, class _Pred, class _Alloc>
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100 template<typename _Value,
105 {
106 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
107 _Hashtable _M_h;
108
109 public:
110
111
112
113 typedef typename _Hashtable::key_type key_type;
114 typedef typename _Hashtable::value_type value_type;
115 typedef typename _Hashtable::hasher hasher;
116 typedef typename _Hashtable::key_equal key_equal;
118
119
120
121
122 typedef typename _Hashtable::pointer pointer;
124 typedef typename _Hashtable::reference reference;
126 typedef typename _Hashtable::iterator iterator;
130 typedef typename _Hashtable::size_type size_type;
132
133
134#if __cplusplus > 201402L
135 using node_type = typename _Hashtable::node_type;
136 using insert_return_type = typename _Hashtable::insert_return_type;
137#endif
138
139
140
141
143
144
145
146
147
148
149
150
151 explicit
156 : _M_h(__n, __hf, __eql, __a)
157 { }
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172 template<typename _InputIterator>
178 : _M_h(__first, __last, __n, __hf, __eql, __a)
179 { }
180
181
183
184
186
187
188
189
190
191 explicit
193 : _M_h(__a)
194 { }
195
196
197
198
199
200
203 : _M_h(__uset._M_h, __a)
204 { }
205
206
207
208
209
210
213 noexcept( noexcept(_Hashtable(std::move(__uset._M_h), __a)) )
214 : _M_h(std::move(__uset._M_h), __a)
215 { }
216
217
218
219
220
221
222
223
224
225
226
227
233 : _M_h(__l, __n, __hf, __eql, __a)
234 { }
235
238 { }
239
243 { }
244
245 template<typename _InputIterator>
246 unordered_set(_InputIterator __first, _InputIterator __last,
250 { }
251
252 template<typename _InputIterator>
253 unordered_set(_InputIterator __first, _InputIterator __last,
257 { }
258
263 { }
264
269 { }
270
271
274
275
278
279
280
281
282
283
284
285
286
287
288
289
292 {
293 _M_h = __l;
294 return *this;
295 }
296
297
300 { return _M_h.get_allocator(); }
301
302
303
304
305 _GLIBCXX_NODISCARD bool
307 { return _M_h.empty(); }
308
309
312 { return _M_h.size(); }
313
314
317 { return _M_h.max_size(); }
318
319
320
321
322
323
324
325
328 { return _M_h.begin(); }
329
332 { return _M_h.begin(); }
333
334
335
336
337
338
339
342 { return _M_h.end(); }
343
346 { return _M_h.end(); }
347
348
349
350
351
352
355 { return _M_h.begin(); }
356
357
358
359
360
363 { return _M_h.end(); }
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382 template<typename... _Args>
385 { return _M_h.emplace(std::forward<_Args>(__args)...); }
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408 template<typename... _Args>
411 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
429 { return _M_h.insert(__x); }
430
433 { return _M_h.insert(std::move(__x)); }
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
458 { return _M_h.insert(__hint, __x); }
459
462 { return _M_h.insert(__hint, std::move(__x)); }
463
464
465
466
467
468
469
470
471
472
473
474 template<typename _InputIterator>
475 void
476 insert(_InputIterator __first, _InputIterator __last)
477 { _M_h.insert(__first, __last); }
478
479
480
481
482
483
484
485
486 void
488 { _M_h.insert(__l); }
489
490#if __cplusplus > 201402L
491
492 node_type
494 {
495 __glibcxx_assert(__pos != end());
496 return _M_h.extract(__pos);
497 }
498
499
500 node_type
502 { return _M_h.extract(__key); }
503
504
505 insert_return_type
507 { return _M_h._M_reinsert_node(std::move(__nh)); }
508
509
512 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
513#endif
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
531 { return _M_h.erase(__position); }
532
533
536 { return _M_h.erase(__position); }
537
538
539
540
541
542
543
544
545
546
547
548
549
550
553 { return _M_h.erase(__x); }
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
571 { return _M_h.erase(__first, __last); }
572
573
574
575
576
577
578
579 void
581 { _M_h.clear(); }
582
583
584
585
586
587
588
589
590
591
592 void
594 noexcept( noexcept(_M_h.swap(__x._M_h)) )
595 { _M_h.swap(__x._M_h); }
596
597#if __cplusplus > 201402L
598 template<typename, typename, typename>
599 friend class std::_Hash_merge_helper;
600
601 template<typename _H2, typename _P2>
602 void
604 {
605 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
606 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
607 }
608
609 template<typename _H2, typename _P2>
610 void
611 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
612 { merge(__source); }
613
614 template<typename _H2, typename _P2>
615 void
616 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
617 {
618 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
619 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
620 }
621
622 template<typename _H2, typename _P2>
623 void
624 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
625 { merge(__source); }
626#endif
627
628
629
630
631
634 { return _M_h.hash_function(); }
635
636
637
640 { return _M_h.key_eq(); }
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
658 { return _M_h.find(__x); }
659
660#if __cplusplus > 201703L
661 template<typename _Kt>
662 auto
664 -> decltype(_M_h._M_find_tr(__k))
665 { return _M_h._M_find_tr(__k); }
666#endif
667
670 { return _M_h.find(__x); }
671
672#if __cplusplus > 201703L
673 template<typename _Kt>
674 auto
675 find(const _Kt& __k) const
676 -> decltype(_M_h._M_find_tr(__k))
677 { return _M_h._M_find_tr(__k); }
678#endif
679
680
681
682
683
684
685
686
687
688
689
690
693 { return _M_h.count(__x); }
694
695#if __cplusplus > 201703L
696 template<typename _Kt>
697 auto
699 -> decltype(_M_h._M_count_tr(__k))
700 { return _M_h._M_count_tr(__k); }
701#endif
702
703
704#if __cplusplus > 201703L
705
706
707
708
709
710
711 bool
713 { return _M_h.find(__x) != _M_h.end(); }
714
715 template<typename _Kt>
716 auto
718 -> decltype(_M_h._M_find_tr(__k), void(), true)
719 { return _M_h._M_find_tr(__k) != _M_h.end(); }
720
721#endif
722
723
724
725
726
727
728
729
730
731
734 { return _M_h.equal_range(__x); }
735
736#if __cplusplus > 201703L
737 template<typename _Kt>
738 auto
740 -> decltype(_M_h._M_equal_range_tr(__k))
741 { return _M_h._M_equal_range_tr(__k); }
742#endif
743
746 { return _M_h.equal_range(__x); }
747
748#if __cplusplus > 201703L
749 template<typename _Kt>
750 auto
752 -> decltype(_M_h._M_equal_range_tr(__k))
753 { return _M_h._M_equal_range_tr(__k); }
754#endif
755
756
757
758
759
762 { return _M_h.bucket_count(); }
763
764
767 { return _M_h.max_bucket_count(); }
768
769
770
771
772
773
776 { return _M_h.bucket_size(__n); }
777
778
779
780
781
782
784 bucket(const key_type& __key) const
785 { return _M_h.bucket(__key); }
786
787
788
789
790
791
792
793
796 { return _M_h.begin(__n); }
797
800 { return _M_h.begin(__n); }
801
804 { return _M_h.cbegin(__n); }
805
806
807
808
809
810
811
812
813
816 { return _M_h.end(__n); }
817
820 { return _M_h.end(__n); }
821
824 { return _M_h.cend(__n); }
825
826
827
828
829
830 float
832 { return _M_h.load_factor(); }
833
834
835
836 float
838 { return _M_h.max_load_factor(); }
839
840
841
842
843
844 void
846 { _M_h.max_load_factor(__z); }
847
848
849
850
851
852
853
854
855 void
857 { _M_h.rehash(__n); }
858
859
860
861
862
863
864
865
866 void
868 { _M_h.reserve(__n); }
869
870 template<typename _Value1, typename _Hash1, typename _Pred1,
871 typename _Alloc1>
872 friend bool
875 };
876
877#if __cpp_deduction_guides >= 201606
878
879 template<typename _InputIterator,
880 typename _Hash =
881 hash<typename iterator_traits<_InputIterator>::value_type>,
882 typename _Pred =
883 equal_to<typename iterator_traits<_InputIterator>::value_type>,
884 typename _Allocator =
885 allocator<typename iterator_traits<_InputIterator>::value_type>,
886 typename = _RequireInputIter<_InputIterator>,
887 typename = _RequireNotAllocatorOrIntegral<_Hash>,
888 typename = _RequireNotAllocator<_Pred>,
889 typename = _RequireAllocator<_Allocator>>
890 unordered_set(_InputIterator, _InputIterator,
892 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
893 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
894 _Hash, _Pred, _Allocator>;
895
896 template<typename _Tp, typename _Hash = hash<_Tp>,
897 typename _Pred = equal_to<_Tp>,
898 typename _Allocator = allocator<_Tp>,
899 typename = _RequireNotAllocatorOrIntegral<_Hash>,
900 typename = _RequireNotAllocator<_Pred>,
901 typename = _RequireAllocator<_Allocator>>
902 unordered_set(initializer_list<_Tp>,
904 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
905 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
906
907 template<typename _InputIterator, typename _Allocator,
908 typename = _RequireInputIter<_InputIterator>,
909 typename = _RequireAllocator<_Allocator>>
910 unordered_set(_InputIterator, _InputIterator,
912 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
913 hash<
914 typename iterator_traits<_InputIterator>::value_type>,
915 equal_to<
916 typename iterator_traits<_InputIterator>::value_type>,
917 _Allocator>;
918
919 template<typename _InputIterator, typename _Hash, typename _Allocator,
920 typename = _RequireInputIter<_InputIterator>,
921 typename = _RequireNotAllocatorOrIntegral<_Hash>,
922 typename = _RequireAllocator<_Allocator>>
923 unordered_set(_InputIterator, _InputIterator,
925 _Hash, _Allocator)
926 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
927 _Hash,
928 equal_to<
929 typename iterator_traits<_InputIterator>::value_type>,
930 _Allocator>;
931
932 template<typename _Tp, typename _Allocator,
933 typename = _RequireAllocator<_Allocator>>
934 unordered_set(initializer_list<_Tp>,
936 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
937
938 template<typename _Tp, typename _Hash, typename _Allocator,
939 typename = _RequireNotAllocatorOrIntegral<_Hash>,
940 typename = _RequireAllocator<_Allocator>>
941 unordered_set(initializer_list<_Tp>,
943 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
944
945#endif
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968 template<typename _Value,
969 typename _Hash = hash<_Value>,
970 typename _Pred = equal_to<_Value>,
971 typename _Alloc = allocator<_Value>>
973 {
974 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
975 _Hashtable _M_h;
976
977 public:
978
979
980
981 typedef typename _Hashtable::key_type key_type;
982 typedef typename _Hashtable::value_type value_type;
983 typedef typename _Hashtable::hasher hasher;
984 typedef typename _Hashtable::key_equal key_equal;
986
987
988
989
990 typedef typename _Hashtable::pointer pointer;
992 typedef typename _Hashtable::reference reference;
994 typedef typename _Hashtable::iterator iterator;
998 typedef typename _Hashtable::size_type size_type;
1000
1001
1002#if __cplusplus > 201402L
1003 using node_type = typename _Hashtable::node_type;
1004#endif
1005
1006
1007
1008
1010
1011
1012
1013
1014
1015
1016
1017
1018 explicit
1023 : _M_h(__n, __hf, __eql, __a)
1024 { }
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039 template<typename _InputIterator>
1045 : _M_h(__first, __last, __n, __hf, __eql, __a)
1046 { }
1047
1048
1050
1051
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1070 : _M_h(__l, __n, __hf, __eql, __a)
1071 { }
1072
1073
1076
1077
1080
1081
1082
1083
1084
1085 explicit
1087 : _M_h(__a)
1088 { }
1089
1090
1091
1092
1093
1094
1097 : _M_h(__umset._M_h, __a)
1098 { }
1099
1100
1101
1102
1103
1104
1107 noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
1108 : _M_h(std::move(__umset._M_h), __a)
1109 { }
1110
1113 { }
1114
1118 { }
1119
1120 template<typename _InputIterator>
1125 { }
1126
1127 template<typename _InputIterator>
1132 { }
1133
1138 { }
1139
1144 { }
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1159 {
1160 _M_h = __l;
1161 return *this;
1162 }
1163
1164
1167 { return _M_h.get_allocator(); }
1168
1169
1170
1171
1172 _GLIBCXX_NODISCARD bool
1174 { return _M_h.empty(); }
1175
1176
1179 { return _M_h.size(); }
1180
1181
1184 { return _M_h.max_size(); }
1185
1186
1187
1188
1189
1190
1191
1192
1195 { return _M_h.begin(); }
1196
1199 { return _M_h.begin(); }
1200
1201
1202
1203
1204
1205
1206
1209 { return _M_h.end(); }
1210
1213 { return _M_h.end(); }
1214
1215
1216
1217
1218
1219
1222 { return _M_h.begin(); }
1223
1224
1225
1226
1227
1230 { return _M_h.end(); }
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241 template<typename... _Args>
1244 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263 template<typename... _Args>
1266 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1267
1268
1269
1270
1271
1272
1273
1274
1275
1278 { return _M_h.insert(__x); }
1279
1282 { return _M_h.insert(std::move(__x)); }
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1304 { return _M_h.insert(__hint, __x); }
1305
1308 { return _M_h.insert(__hint, std::move(__x)); }
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319 template<typename _InputIterator>
1320 void
1321 insert(_InputIterator __first, _InputIterator __last)
1322 { _M_h.insert(__first, __last); }
1323
1324
1325
1326
1327
1328
1329
1330
1331 void
1333 { _M_h.insert(__l); }
1334
1335#if __cplusplus > 201402L
1336
1337 node_type
1339 {
1340 __glibcxx_assert(__pos != end());
1341 return _M_h.extract(__pos);
1342 }
1343
1344
1345 node_type
1347 { return _M_h.extract(__key); }
1348
1349
1352 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1353
1354
1357 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1358#endif
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1377 { return _M_h.erase(__position); }
1378
1379
1382 { return _M_h.erase(__position); }
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1400 { return _M_h.erase(__x); }
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1420 { return _M_h.erase(__first, __last); }
1421
1422
1423
1424
1425
1426
1427
1428
1429 void
1431 { _M_h.clear(); }
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442 void
1444 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1445 { _M_h.swap(__x._M_h); }
1446
1447#if __cplusplus > 201402L
1448 template<typename, typename, typename>
1449 friend class std::_Hash_merge_helper;
1450
1451 template<typename _H2, typename _P2>
1452 void
1454 {
1455 using _Merge_helper
1456 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1457 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1458 }
1459
1460 template<typename _H2, typename _P2>
1461 void
1462 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1463 { merge(__source); }
1464
1465 template<typename _H2, typename _P2>
1466 void
1467 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1468 {
1469 using _Merge_helper
1470 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1471 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1472 }
1473
1474 template<typename _H2, typename _P2>
1475 void
1476 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1477 { merge(__source); }
1478#endif
1479
1480
1481
1482
1483
1486 { return _M_h.hash_function(); }
1487
1488
1489
1492 { return _M_h.key_eq(); }
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1510 { return _M_h.find(__x); }
1511
1512#if __cplusplus > 201703L
1513 template<typename _Kt>
1514 auto
1516 -> decltype(_M_h._M_find_tr(__x))
1517 { return _M_h._M_find_tr(__x); }
1518#endif
1519
1522 { return _M_h.find(__x); }
1523
1524#if __cplusplus > 201703L
1525 template<typename _Kt>
1526 auto
1528 -> decltype(_M_h._M_find_tr(__x))
1529 { return _M_h._M_find_tr(__x); }
1530#endif
1531
1532
1533
1534
1535
1536
1537
1538
1541 { return _M_h.count(__x); }
1542
1543#if __cplusplus > 201703L
1544 template<typename _Kt>
1545 auto
1546 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1547 { return _M_h._M_count_tr(__x); }
1548#endif
1549
1550
1551#if __cplusplus > 201703L
1552
1553
1554
1555
1556
1557
1558 bool
1560 { return _M_h.find(__x) != _M_h.end(); }
1561
1562 template<typename _Kt>
1563 auto
1565 -> decltype(_M_h._M_find_tr(__x), void(), true)
1566 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1567
1568#endif
1569
1570
1571
1572
1573
1574
1575
1576
1579 { return _M_h.equal_range(__x); }
1580
1581#if __cplusplus > 201703L
1582 template<typename _Kt>
1583 auto
1585 -> decltype(_M_h._M_equal_range_tr(__x))
1586 { return _M_h._M_equal_range_tr(__x); }
1587#endif
1588
1591 { return _M_h.equal_range(__x); }
1592
1593#if __cplusplus > 201703L
1594 template<typename _Kt>
1595 auto
1597 -> decltype(_M_h._M_equal_range_tr(__x))
1598 { return _M_h._M_equal_range_tr(__x); }
1599#endif
1600
1601
1602
1603
1604
1607 { return _M_h.bucket_count(); }
1608
1609
1612 { return _M_h.max_bucket_count(); }
1613
1614
1615
1616
1617
1618
1620 bucket_size(size_type __n) const
1621 { return _M_h.bucket_size(__n); }
1622
1623
1624
1625
1626
1627
1629 bucket(const key_type& __key) const
1630 { return _M_h.bucket(__key); }
1631
1632
1633
1634
1635
1636
1637
1638
1641 { return _M_h.begin(__n); }
1642
1645 { return _M_h.begin(__n); }
1646
1649 { return _M_h.cbegin(__n); }
1650
1651
1652
1653
1654
1655
1656
1657
1658
1661 { return _M_h.end(__n); }
1662
1665 { return _M_h.end(__n); }
1666
1669 { return _M_h.cend(__n); }
1670
1671
1672
1673
1674
1675 float
1677 { return _M_h.load_factor(); }
1678
1679
1680
1681 float
1683 { return _M_h.max_load_factor(); }
1684
1685
1686
1687
1688
1689 void
1691 { _M_h.max_load_factor(__z); }
1692
1693
1694
1695
1696
1697
1698
1699
1700 void
1702 { _M_h.rehash(__n); }
1703
1704
1705
1706
1707
1708
1709
1710
1711 void
1713 { _M_h.reserve(__n); }
1714
1715 template<typename _Value1, typename _Hash1, typename _Pred1,
1716 typename _Alloc1>
1717 friend bool
1720 };
1721
1722
1723#if __cpp_deduction_guides >= 201606
1724
1725 template<typename _InputIterator,
1726 typename _Hash =
1727 hash<typename iterator_traits<_InputIterator>::value_type>,
1728 typename _Pred =
1729 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1730 typename _Allocator =
1731 allocator<typename iterator_traits<_InputIterator>::value_type>,
1732 typename = _RequireInputIter<_InputIterator>,
1733 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1734 typename = _RequireNotAllocator<_Pred>,
1735 typename = _RequireAllocator<_Allocator>>
1736 unordered_multiset(_InputIterator, _InputIterator,
1738 _Hash = _Hash(), _Pred = _Pred(),
1739 _Allocator = _Allocator())
1740 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1741 _Hash, _Pred, _Allocator>;
1742
1743 template<typename _Tp, typename _Hash = hash<_Tp>,
1744 typename _Pred = equal_to<_Tp>,
1745 typename _Allocator = allocator<_Tp>,
1746 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1747 typename = _RequireNotAllocator<_Pred>,
1748 typename = _RequireAllocator<_Allocator>>
1749 unordered_multiset(initializer_list<_Tp>,
1751 _Hash = _Hash(), _Pred = _Pred(),
1752 _Allocator = _Allocator())
1753 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1754
1755 template<typename _InputIterator, typename _Allocator,
1756 typename = _RequireInputIter<_InputIterator>,
1757 typename = _RequireAllocator<_Allocator>>
1758 unordered_multiset(_InputIterator, _InputIterator,
1760 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1761 hash<typename
1762 iterator_traits<_InputIterator>::value_type>,
1763 equal_to<typename
1764 iterator_traits<_InputIterator>::value_type>,
1765 _Allocator>;
1766
1767 template<typename _InputIterator, typename _Hash, typename _Allocator,
1768 typename = _RequireInputIter<_InputIterator>,
1769 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1770 typename = _RequireAllocator<_Allocator>>
1771 unordered_multiset(_InputIterator, _InputIterator,
1773 _Hash, _Allocator)
1774 -> unordered_multiset<typename
1775 iterator_traits<_InputIterator>::value_type,
1776 _Hash,
1777 equal_to<
1778 typename
1779 iterator_traits<_InputIterator>::value_type>,
1780 _Allocator>;
1781
1782 template<typename _Tp, typename _Allocator,
1783 typename = _RequireAllocator<_Allocator>>
1784 unordered_multiset(initializer_list<_Tp>,
1786 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1787
1788 template<typename _Tp, typename _Hash, typename _Allocator,
1789 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1790 typename = _RequireAllocator<_Allocator>>
1791 unordered_multiset(initializer_list<_Tp>,
1793 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1794
1795#endif
1796
1797 template<class _Value, class _Hash, class _Pred, class _Alloc>
1798 inline void
1799 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1800 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1801 noexcept(noexcept(__x.swap(__y)))
1802 { __x.swap(__y); }
1803
1804 template<class _Value, class _Hash, class _Pred, class _Alloc>
1805 inline void
1806 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1807 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1808 noexcept(noexcept(__x.swap(__y)))
1809 { __x.swap(__y); }
1810
1811 template<class _Value, class _Hash, class _Pred, class _Alloc>
1812 inline bool
1813 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1814 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1815 { return __x._M_h._M_equal(__y._M_h); }
1816
1817#if __cpp_impl_three_way_comparison < 201907L
1818 template<class _Value, class _Hash, class _Pred, class _Alloc>
1819 inline bool
1820 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1821 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1822 { return !(__x == __y); }
1823#endif
1824
1825 template<class _Value, class _Hash, class _Pred, class _Alloc>
1826 inline bool
1827 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1828 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1829 { return __x._M_h._M_equal(__y._M_h); }
1830
1831#if __cpp_impl_three_way_comparison < 201907L
1832 template<class _Value, class _Hash, class _Pred, class _Alloc>
1833 inline bool
1834 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1835 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1836 { return !(__x == __y); }
1837#endif
1838
1839_GLIBCXX_END_NAMESPACE_CONTAINER
1840
1841#if __cplusplus > 201402L
1842
1843 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1844 typename _Hash2, typename _Eq2>
1845 struct _Hash_merge_helper<
1846 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1847 {
1848 private:
1849 template<typename... _Tp>
1850 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1851 template<typename... _Tp>
1852 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1853
1854 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1855
1856 static auto&
1857 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1858 { return __set._M_h; }
1859
1860 static auto&
1861 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1862 { return __set._M_h; }
1863 };
1864
1865
1866 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1867 typename _Hash2, typename _Eq2>
1868 struct _Hash_merge_helper<
1869 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1870 _Hash2, _Eq2>
1871 {
1872 private:
1873 template<typename... _Tp>
1874 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1875 template<typename... _Tp>
1876 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1877
1878 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1879
1880 static auto&
1881 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1882 { return __set._M_h; }
1883
1884 static auto&
1885 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1886 { return __set._M_h; }
1887 };
1888#endif
1889
1890_GLIBCXX_END_NAMESPACE_VERSION
1891}
1892
1893#endif
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
__detail::_Hashtable_traits< _Cache, true, true > __uset_traits
Base types for unordered_set.
__detail::_Hashtable_traits< _Cache, true, false > __umset_traits
Base types for unordered_multiset.
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
One of the comparison functors.
Struct holding two objects of arbitrary type.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multiset.
iterator begin() noexcept
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multiset.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts an element into the unordered_multiset.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Inserts a list of elements into the unordered_multiset.
_Hashtable::pointer pointer
Iterator-related typedefs.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
void rehash(size_type __n)
May rehash the unordered_multiset.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multiset.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multiset tries to keep the load factor less than or equa...
bool empty() const noexcept
Returns true if the unordered_multiset is empty.
const_iterator cend() const noexcept
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
node_type extract(const key_type &__key)
Extract a node.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator emplace(_Args &&... __args)
Builds and insert an element into the unordered_multiset.
unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from a range.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_multiset(const allocator_type &__a)
Creates an unordered_multiset with no elements.
_Hashtable::allocator_type allocator_type
Public typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
_Hashtable::value_type value_type
Public typedefs.
unordered_multiset & operator=(unordered_multiset &&)=default
Move assignment operator.
float load_factor() const noexcept
Returns the average number of elements per bucket.
unordered_multiset()=default
Default constructor.
iterator insert(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node.
_Hashtable::size_type size_type
Iterator-related typedefs.
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
_Hashtable::key_type key_type
Public typedefs.
unordered_multiset & operator=(const unordered_multiset &)=default
Copy assignment operator.
hasher hash_function() const
Returns the hash functor object with which the unordered_multiset was constructed.
unordered_multiset(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from an initializer_list.
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
size_type count(const key_type &__x) const
Finds the number of elements.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
unordered_multiset(unordered_multiset &&)=default
Move constructor.
_Hashtable::reference reference
Iterator-related typedefs.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Inserts an element into the unordered_multiset.
void swap(unordered_multiset &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multiset.
const_iterator begin() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multiset.
const_iterator cbegin() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that inserts a range of elements.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
const_iterator end() const noexcept
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts an element into the unordered_multiset.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_multiset.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multiset.
iterator insert(node_type &&__nh)
Re-insert an extracted node.
_Hashtable::hasher hasher
Public typedefs.
unordered_multiset(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
unordered_multiset & operator=(initializer_list< value_type > __l)
Unordered_multiset list assignment operator.
size_type size() const noexcept
Returns the size of the unordered_multiset.
_Hashtable::iterator iterator
Iterator-related typedefs.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
node_type extract(const_iterator __pos)
Extract a node.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multiset.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multiset(const unordered_multiset &)=default
Copy constructor.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multiset.
_Hashtable::key_equal key_equal
Public typedefs.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
_Hashtable::iterator iterator
Iterator-related typedefs.
unordered_set(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from an initializer_list.
void max_load_factor(float __z)
Change the unordered_set maximum load factor.
_Hashtable::reference reference
Iterator-related typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::value_type value_type
Public typedefs.
const_iterator cend() const noexcept
auto find(const _Kt &__k) -> decltype(_M_h._M_find_tr(__k))
Tries to locate an element in an unordered_set.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
_Hashtable::key_type key_type
Public typedefs.
size_type count(const key_type &__x) const
Finds the number of elements.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto equal_range(const _Kt &__k) -> decltype(_M_h._M_equal_range_tr(__k))
Finds a subsequence matching given key.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto count(const _Kt &__k) const -> decltype(_M_h._M_count_tr(__k))
Finds the number of elements.
const_iterator begin() const noexcept
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
insert_return_type insert(node_type &&__nh)
Re-insert an extracted node.
_Hashtable::size_type size_type
Iterator-related typedefs.
const_iterator cbegin() const noexcept
bool empty() const noexcept
Returns true if the unordered_set is empty.
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
iterator erase(iterator __position)
Erases an element from an unordered_set.
unordered_set(unordered_set &&)=default
Move constructor.
unordered_set(const allocator_type &__a)
Creates an unordered_set with no elements.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
auto contains(const _Kt &__k) const -> decltype(_M_h._M_find_tr(__k), void(), true)
Finds whether an element with the given key exists.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
void swap(unordered_set &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_set.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert an element into the unordered_set.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert an element into the unordered_set.
float load_factor() const noexcept
Returns the average number of elements per bucket.
void rehash(size_type __n)
May rehash the unordered_set.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::key_equal key_equal
Public typedefs.
size_type size() const noexcept
Returns the size of the unordered_set.
iterator insert(const_iterator, node_type &&__nh)
Re-insert an extracted node.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
hasher hash_function() const
Returns the hash functor object with which the unordered_set was constructed.
unordered_set(const unordered_set &)=default
Copy constructor.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
auto find(const _Kt &__k) const -> decltype(_M_h._M_find_tr(__k))
Tries to locate an element in an unordered_set.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to insert an element into the unordered_set.
key_equal key_eq() const
Returns the key comparison object with which the unordered_set was constructed.
_Hashtable::allocator_type allocator_type
Public typedefs.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
const_iterator end() const noexcept
node_type extract(const key_type &__key)
Extract a node.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_set()=default
Default constructor.
unordered_set & operator=(unordered_set &&)=default
Move assignment operator.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
float max_load_factor() const noexcept
Returns a positive number that the unordered_set tries to keep the load factor less than or equal to.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the unordered_set.
unordered_set & operator=(const unordered_set &)=default
Copy assignment operator.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
unordered_set(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_set.
iterator erase(const_iterator __position)
Erases an element from an unordered_set.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_set.
auto equal_range(const _Kt &__k) const -> decltype(_M_h._M_equal_range_tr(__k))
Finds a subsequence matching given key.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_set.
unordered_set(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from a range.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_set.
void reserve(size_type __n)
Prepare the unordered_set for a specified number of elements.
node_type extract(const_iterator __pos)
Extract a node.
_Hashtable::pointer pointer
Iterator-related typedefs.
iterator begin() noexcept
iterator find(const key_type &__x)
Tries to locate an element in an unordered_set.
size_type max_size() const noexcept
Returns the maximum size of the unordered_set.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_set.