1	// Copyright 2021 Christian Mazakas.
2	// Distributed under the Boost Software License, Version 1.0. (See accompanying
3	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
4
5	#include "../helpers/unordered.hpp"
6
7	#include "../helpers/test.hpp"
8
9	#include <boost/container_hash/hash.hpp>
10
11	struct key
12	{
13	int x_;
14	static int count_;
15
16	key(int x) : x_(x) { ++count_; }
17	key(key const& k) : x_(k.x_) { ++count_; }
18	};
19
20	int key::count_;
21
22	std::ostream& operator<<(std::ostream& os, key const& k)
23	{
24	os << "key { x_: " << k.x_ << " }";
25	return os;
26	}
27
28	bool operator==(key const& k, int const x) { return k.x_ == x; }
29	bool operator==(int const x, key const& k) { return k.x_ == x; }
30
31	struct transparent_hasher
32	{
33	typedef void is_transparent;
34
35	std::size_t operator()(key const& k) const
36	{
37	return boost::hash<int>()(k.x_);
38	}
39
40	std::size_t operator()(int const k) const { return boost::hash<int>()(k); }
41	};
42
43	struct transparent_key_equal
44	{
45	typedef void is_transparent;
46
47	bool operator()(key const& k1, key const& k2) const { return k1.x_ == k2.x_; }
48	bool operator()(int const x, key const& k1) const { return k1 == x; }
49	bool operator()(key const& k1, int const x) const { return k1 == x; }
50	};
51
52	struct hasher
53	{
54	std::size_t operator()(key const& k) const
55	{
56	return boost::hash<int>()(k.x_);
57	}
58	};
59
60	struct key_equal
61	{
62	bool operator()(key const& k1, key const& k2) const { return k1.x_ == k2.x_; }
63	};
64
65	void count_reset() { key::count_ = 0; }
66
67	template <class UnorderedMap> void test_map_transparent_count(UnorderedMap*)
68	{
69	count_reset();
70
71	UnorderedMap map;
72
73	map.insert(std::make_pair(x: 0, y: 1337));
74	map.insert(std::make_pair(x: 1, y: 1338));
75	map.insert(std::make_pair(x: 2, y: 1339));
76	map.insert(std::make_pair(x: 0, y: 1340));
77	map.insert(std::make_pair(x: 0, y: 1341));
78	map.insert(std::make_pair(x: 0, y: 1342));
79
80	int const expected_key_count = key::count_;
81
82	std::size_t count = 0;
83	count = map.count(0);
84	BOOST_TEST_EQ(count, map.size() - 2);
85
86	count = map.count(1);
87	BOOST_TEST_EQ(count, 1u);
88
89	count = map.count(1337);
90	BOOST_TEST_EQ(count, 0u);
91
92	BOOST_TEST_EQ(key::count_, expected_key_count);
93	}
94
95	template <class UnorderedMap> void test_map_non_transparent_count(UnorderedMap*)
96	{
97	count_reset();
98
99	UnorderedMap map;
100
101	map.insert(std::make_pair(x: 0, y: 1337));
102	map.insert(std::make_pair(x: 1, y: 1338));
103	map.insert(std::make_pair(x: 2, y: 1339));
104	map.insert(std::make_pair(x: 0, y: 1340));
105	map.insert(std::make_pair(x: 0, y: 1341));
106	map.insert(std::make_pair(x: 0, y: 1342));
107
108	int key_count = key::count_;
109
110	std::size_t count = 0;
111	count = map.count(0);
112	++key_count;
113
114	BOOST_TEST_EQ(count, map.size() - 2);
115	BOOST_TEST_EQ(key::count_, key_count);
116
117	count = map.count(1);
118	++key_count;
119
120	BOOST_TEST_EQ(count, 1u);
121
122	count = map.count(1337);
123	++key_count;
124
125	BOOST_TEST_EQ(count, 0u);
126	BOOST_TEST_EQ(key::count_, key_count);
127	}
128
129	template <class UnorderedSet> void test_set_transparent_count(UnorderedSet*)
130	{
131	count_reset();
132
133	UnorderedSet set;
134
135	set.insert(0);
136	set.insert(1);
137	set.insert(2);
138	set.insert(0);
139	set.insert(0);
140	set.insert(0);
141
142	int const expected_key_count = key::count_;
143
144	std::size_t count = 0;
145	count = set.count(0);
146	BOOST_TEST_EQ(count, set.size() - 2);
147
148	count = set.count(1);
149	BOOST_TEST_EQ(count, 1u);
150
151	count = set.count(1337);
152	BOOST_TEST_EQ(count, 0u);
153
154	BOOST_TEST_EQ(key::count_, expected_key_count);
155	}
156
157	template <class UnorderedSet> void test_set_non_transparent_count(UnorderedSet*)
158	{
159	count_reset();
160
161	UnorderedSet set;
162
163	set.insert(0);
164	set.insert(1);
165	set.insert(2);
166	set.insert(0);
167	set.insert(0);
168	set.insert(0);
169
170	int key_count = key::count_;
171
172	std::size_t count = 0;
173	count = set.count(0);
174	++key_count;
175
176	BOOST_TEST_EQ(count, set.size() - 2);
177	BOOST_TEST_EQ(key::count_, key_count);
178
179	count = set.count(1);
180	++key_count;
181
182	BOOST_TEST_EQ(count, 1u);
183
184	count = set.count(1337);
185	++key_count;
186
187	BOOST_TEST_EQ(count, 0u);
188	BOOST_TEST_EQ(key::count_, key_count);
189	}
190
191	template <class UnorderedMap> void test_map_transparent_find(UnorderedMap*)
192	{
193	count_reset();
194
195	typedef typename UnorderedMap::const_iterator map_iterator;
196	typedef typename UnorderedMap::value_type pair;
197
198	UnorderedMap map;
199
200	int n = 5;
201
202	for (int i = 0; i < n; ++i) {
203	map.insert(std::make_pair(x&: i, y&: i));
204	}
205
206	int const expected_key_count = key::count_;
207
208	// explicitly test `find()` and `find() const` separately
209	//
210
211	{
212	UnorderedMap& m = map;
213
214	for (int i = 0; i < n; ++i) {
215	map_iterator pos = m.find(i);
216	BOOST_TEST(pos != m.end());
217
218	pair const& p = *pos;
219	int const v = p.second;
220
221	BOOST_TEST_EQ(v, i);
222	}
223
224	BOOST_TEST_EQ(key::count_, expected_key_count);
225
226	map_iterator pos = m.find(1337);
227	BOOST_TEST(pos == m.end());
228	BOOST_TEST_EQ(key::count_, expected_key_count);
229	}
230
231	{
232	UnorderedMap const& m = map;
233
234	for (int i = 0; i < n; ++i) {
235	map_iterator pos = m.find(i);
236	BOOST_TEST(pos != m.end());
237
238	pair const& p = *pos;
239	int const v = p.second;
240
241	BOOST_TEST(v == i);
242	}
243
244	BOOST_TEST_EQ(key::count_, expected_key_count);
245
246	map_iterator pos = m.find(1337);
247	BOOST_TEST(pos == m.end());
248	BOOST_TEST_EQ(key::count_, expected_key_count);
249	}
250	}
251
252	template <class UnorderedMap> void test_map_non_transparent_find(UnorderedMap*)
253	{
254	count_reset();
255
256	typedef typename UnorderedMap::const_iterator map_iterator;
257	typedef typename UnorderedMap::value_type pair;
258
259	UnorderedMap map;
260
261	int n = 5;
262
263	for (int i = 0; i < n; ++i) {
264	map.insert(std::make_pair(x&: i, y&: i));
265	}
266
267	int key_count = key::count_;
268
269	// explicitly test `find()` and `find() const` separately
270	//
271
272	{
273	UnorderedMap& m = map;
274
275	for (int i = 0; i < n; ++i) {
276	map_iterator pos = m.find(i);
277	BOOST_TEST(pos != m.end());
278
279	pair const& p = *pos;
280	int const v = p.second;
281
282	BOOST_TEST_EQ(v, i);
283	}
284	BOOST_TEST_EQ(key::count_, n + key_count);
285
286	map_iterator pos = m.find(1337);
287	BOOST_TEST(pos == m.end());
288	BOOST_TEST_EQ(key::count_, 1 + n + key_count);
289
290	key_count = key::count_;
291	}
292
293	{
294	UnorderedMap const& m = map;
295
296	for (int i = 0; i < n; ++i) {
297	map_iterator pos = m.find(i);
298	BOOST_TEST(pos != m.end());
299
300	pair const& p = *pos;
301	int const v = p.second;
302
303	BOOST_TEST_EQ(v, i);
304	}
305	BOOST_TEST_EQ(key::count_, n + key_count);
306
307	map_iterator pos = m.find(1337);
308	BOOST_TEST(pos == m.end());
309	BOOST_TEST_EQ(key::count_, 1 + n + key_count);
310	}
311	}
312
313	template <class UnorderedSet> void test_set_transparent_find(UnorderedSet*)
314	{
315	count_reset();
316
317	typedef typename UnorderedSet::const_iterator set_iterator;
318
319	UnorderedSet set;
320
321	int n = 5;
322
323	for (int i = 0; i < n; ++i) {
324	set.insert(i);
325	}
326
327	int const expected_key_count = key::count_;
328
329	// explicitly test `find()` and `find() const` separately
330	//
331
332	{
333	UnorderedSet& m = set;
334
335	for (int i = 0; i < n; ++i) {
336	set_iterator pos = m.find(i);
337	BOOST_TEST(pos != m.end());
338	BOOST_TEST_EQ(*pos, i);
339	}
340
341	BOOST_TEST_EQ(key::count_, expected_key_count);
342
343	set_iterator pos = m.find(1337);
344	BOOST_TEST(pos == m.end());
345	BOOST_TEST_EQ(key::count_, expected_key_count);
346	}
347
348	{
349	UnorderedSet const& m = set;
350
351	for (int i = 0; i < n; ++i) {
352	set_iterator pos = m.find(i);
353	BOOST_TEST(pos != m.end());
354	BOOST_TEST_EQ(*pos, i);
355	}
356
357	BOOST_TEST_EQ(key::count_, expected_key_count);
358
359	set_iterator pos = m.find(1337);
360	BOOST_TEST(pos == m.end());
361	BOOST_TEST_EQ(key::count_, expected_key_count);
362	}
363	}
364
365	template <class UnorderedSet> void test_set_non_transparent_find(UnorderedSet*)
366	{
367	count_reset();
368
369	typedef typename UnorderedSet::const_iterator set_iterator;
370
371	UnorderedSet set;
372
373	int n = 5;
374
375	for (int i = 0; i < n; ++i) {
376	set.insert(i);
377	}
378
379	int key_count = key::count_;
380
381	// explicitly test `find()` and `find() const` separately
382	//
383
384	{
385	UnorderedSet& m = set;
386
387	for (int i = 0; i < n; ++i) {
388	set_iterator pos = m.find(i);
389	++key_count;
390
391	BOOST_TEST(pos != m.end());
392	BOOST_TEST_EQ(*pos, i);
393	}
394
395	BOOST_TEST_EQ(key::count_, key_count);
396
397	set_iterator pos = m.find(1337);
398	++key_count;
399
400	BOOST_TEST(pos == m.end());
401	BOOST_TEST_EQ(key::count_, key_count);
402	}
403
404	{
405	UnorderedSet const& m = set;
406
407	for (int i = 0; i < n; ++i) {
408	set_iterator pos = m.find(i);
409	++key_count;
410
411	BOOST_TEST(pos != m.end());
412	BOOST_TEST_EQ(*pos, i);
413	}
414
415	BOOST_TEST_EQ(key::count_, key_count);
416
417	set_iterator pos = m.find(1337);
418	++key_count;
419
420	BOOST_TEST(pos == m.end());
421	BOOST_TEST_EQ(key::count_, key_count);
422	}
423	}
424
425	template <class UnorderedMap>
426	void test_map_transparent_equal_range(UnorderedMap*)
427	{
428	count_reset();
429
430	UnorderedMap unordered_map;
431
432	// empty tests
433	//
434	// explicitly test `equal_range()` vs `equal_range() const`
435	//
436	{
437	typedef typename UnorderedMap::iterator iterator;
438	typedef std::pair<iterator, iterator> iterator_pair;
439
440	UnorderedMap& map = unordered_map;
441	BOOST_TEST(map.empty());
442
443	iterator_pair iters = map.equal_range(0);
444
445	iterator begin = iters.first;
446	iterator end = iters.second;
447
448	BOOST_TEST(begin == end);
449	BOOST_TEST(begin == map.end());
450	BOOST_TEST_EQ(std::distance(begin, end), 0);
451	}
452
453	{
454	typedef typename UnorderedMap::const_iterator iterator;
455	typedef std::pair<iterator, iterator> iterator_pair;
456
457	UnorderedMap const& map = unordered_map;
458	BOOST_TEST(map.empty());
459
460	iterator_pair iters = map.equal_range(0);
461
462	iterator begin = iters.first;
463	iterator end = iters.second;
464
465	BOOST_TEST(begin == end);
466	BOOST_TEST(begin == map.end());
467	BOOST_TEST_EQ(std::distance(begin, end), 0);
468	}
469
470	BOOST_TEST_EQ(key::count_, 0);
471
472	unordered_map.insert(std::make_pair(x: 0, y: 1337));
473	unordered_map.insert(std::make_pair(x: 1, y: 1338));
474	unordered_map.insert(std::make_pair(x: 2, y: 1339));
475	unordered_map.insert(std::make_pair(x: 0, y: 1340));
476	unordered_map.insert(std::make_pair(x: 0, y: 1341));
477	unordered_map.insert(std::make_pair(x: 0, y: 1342));
478
479	int const expected_key_count = key::count_;
480
481	// do this so that multimap tests actually test a range with len > 1
482	//
483	int const expected_range_len = static_cast<int>(unordered_map.size() - 2);
484
485	typedef typename UnorderedMap::value_type value_type;
486
487	// explicitly test `equal_range()` vs `equal_range() const`
488	//
489	{
490	typedef typename UnorderedMap::iterator iterator;
491	typedef std::pair<iterator, iterator> iterator_pair;
492
493	UnorderedMap& map = unordered_map;
494
495	iterator_pair iters = map.equal_range(0);
496
497	iterator begin = iters.first;
498	iterator end = iters.second;
499
500	BOOST_TEST(begin != end);
501	BOOST_TEST(begin != map.end());
502	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
503
504	for (iterator pos = begin; pos != end; ++pos) {
505	value_type const& val = *pos;
506	BOOST_TEST_EQ(val.first.x_, 0);
507	}
508
509	iters = map.equal_range(1);
510
511	begin = iters.first;
512	end = iters.second;
513
514	BOOST_TEST(begin != end);
515	BOOST_TEST(begin != map.end());
516	BOOST_TEST_EQ(std::distance(begin, end), 1);
517
518	value_type const& val = *begin;
519	BOOST_TEST_EQ(val.first, 1);
520	BOOST_TEST_EQ(val.second, 1338);
521
522	iters = map.equal_range(1337);
523
524	begin = iters.first;
525	end = iters.second;
526
527	BOOST_TEST(begin == end);
528	BOOST_TEST(begin == map.end());
529	BOOST_TEST_EQ(std::distance(begin, end), 0);
530
531	BOOST_TEST_EQ(key::count_, expected_key_count);
532	}
533
534	{
535	typedef typename UnorderedMap::const_iterator iterator;
536	typedef std::pair<iterator, iterator> iterator_pair;
537
538	UnorderedMap const& map = unordered_map;
539
540	iterator_pair iters = map.equal_range(0);
541
542	iterator begin = iters.first;
543	iterator end = iters.second;
544
545	BOOST_TEST(begin != end);
546	BOOST_TEST(begin != map.end());
547	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
548
549	for (iterator pos = begin; pos != end; ++pos) {
550	value_type const& val = *begin;
551	BOOST_TEST_EQ(val.first.x_, 0);
552	}
553
554	iters = map.equal_range(1);
555
556	begin = iters.first;
557	end = iters.second;
558
559	BOOST_TEST(begin != end);
560	BOOST_TEST(begin != map.end());
561	BOOST_TEST_EQ(std::distance(begin, end), 1);
562
563	value_type const& val = *begin;
564	BOOST_TEST_EQ(val.first, 1);
565	BOOST_TEST_EQ(val.second, 1338);
566
567	iters = map.equal_range(1337);
568
569	begin = iters.first;
570	end = iters.second;
571
572	BOOST_TEST(begin == end);
573	BOOST_TEST(begin == map.end());
574	BOOST_TEST_EQ(std::distance(begin, end), 0);
575
576	BOOST_TEST_EQ(key::count_, expected_key_count);
577	}
578	}
579
580	template <class UnorderedMap>
581	void test_map_non_transparent_equal_range(UnorderedMap*)
582	{
583	count_reset();
584
585	UnorderedMap unordered_map;
586
587	// empty tests
588	//
589	// explicitly test `equal_range()` vs `equal_range() const`
590	//
591	{
592	typedef typename UnorderedMap::iterator iterator;
593	typedef std::pair<iterator, iterator> iterator_pair;
594
595	UnorderedMap& map = unordered_map;
596	BOOST_TEST(map.empty());
597
598	iterator_pair iters = map.equal_range(0);
599
600	iterator begin = iters.first;
601	iterator end = iters.second;
602
603	BOOST_TEST(begin == end);
604	BOOST_TEST(begin == map.end());
605	BOOST_TEST_EQ(std::distance(begin, end), 0);
606	}
607
608	{
609	typedef typename UnorderedMap::const_iterator iterator;
610	typedef std::pair<iterator, iterator> iterator_pair;
611
612	UnorderedMap const& map = unordered_map;
613	BOOST_TEST(map.empty());
614
615	iterator_pair iters = map.equal_range(0);
616
617	iterator begin = iters.first;
618	iterator end = iters.second;
619
620	BOOST_TEST(begin == end);
621	BOOST_TEST(begin == map.end());
622	BOOST_TEST_EQ(std::distance(begin, end), 0);
623	}
624
625	BOOST_TEST_EQ(key::count_, 2);
626
627	unordered_map.insert(std::make_pair(x: 0, y: 1337));
628	unordered_map.insert(std::make_pair(x: 1, y: 1338));
629	unordered_map.insert(std::make_pair(x: 2, y: 1339));
630	unordered_map.insert(std::make_pair(x: 0, y: 1340));
631	unordered_map.insert(std::make_pair(x: 0, y: 1341));
632	unordered_map.insert(std::make_pair(x: 0, y: 1342));
633
634	int key_count = key::count_;
635
636	// do this so that multimap tests actually test a range with len > 1
637	//
638	int const expected_range_len = static_cast<int>(unordered_map.size() - 2);
639
640	typedef typename UnorderedMap::value_type value_type;
641
642	// explicitly test `equal_range()` vs `equal_range() const`
643	//
644	{
645	typedef typename UnorderedMap::iterator iterator;
646	typedef std::pair<iterator, iterator> iterator_pair;
647
648	UnorderedMap& map = unordered_map;
649
650	iterator_pair iters = map.equal_range(0);
651
652	iterator begin = iters.first;
653	iterator end = iters.second;
654
655	BOOST_TEST(begin != end);
656	BOOST_TEST(begin != map.end());
657	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
658
659	for (iterator pos = begin; pos != end; ++pos) {
660	value_type const& val = *begin;
661	BOOST_TEST_EQ(val.first.x_, 0);
662	}
663
664	iters = map.equal_range(1);
665
666	begin = iters.first;
667	end = iters.second;
668
669	BOOST_TEST(begin != end);
670	BOOST_TEST(begin != map.end());
671	BOOST_TEST_EQ(std::distance(begin, end), 1);
672
673	value_type const& val = *begin;
674	BOOST_TEST_EQ(val.first, 1);
675	BOOST_TEST_EQ(val.second, 1338);
676
677	iters = map.equal_range(1337);
678
679	begin = iters.first;
680	end = iters.second;
681
682	BOOST_TEST(begin == end);
683	BOOST_TEST(begin == map.end());
684	BOOST_TEST_EQ(std::distance(begin, end), 0);
685
686	BOOST_TEST_EQ(key::count_, 3 + key_count);
687	key_count += 3;
688	}
689
690	{
691	typedef typename UnorderedMap::const_iterator iterator;
692	typedef std::pair<iterator, iterator> iterator_pair;
693
694	UnorderedMap const& map = unordered_map;
695
696	iterator_pair iters = map.equal_range(0);
697
698	iterator begin = iters.first;
699	iterator end = iters.second;
700
701	BOOST_TEST(begin != end);
702	BOOST_TEST(begin != map.end());
703	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
704
705	for (iterator pos = begin; pos != end; ++pos) {
706	value_type const& val = *pos;
707	BOOST_TEST_EQ(val.first.x_, 0);
708	}
709
710	iters = map.equal_range(1);
711
712	begin = iters.first;
713	end = iters.second;
714
715	BOOST_TEST(begin != end);
716	BOOST_TEST(begin != map.end());
717	BOOST_TEST_EQ(std::distance(begin, end), 1);
718
719	value_type const& val = *begin;
720	BOOST_TEST_EQ(val.first, 1);
721	BOOST_TEST_EQ(val.second, 1338);
722
723	iters = map.equal_range(1337);
724
725	begin = iters.first;
726	end = iters.second;
727
728	BOOST_TEST(begin == end);
729	BOOST_TEST(begin == map.end());
730	BOOST_TEST_EQ(std::distance(begin, end), 0);
731
732	BOOST_TEST_EQ(key::count_, 3 + key_count);
733	}
734	}
735
736	template <class UnorderedSet>
737	void test_set_transparent_equal_range(UnorderedSet*)
738	{
739	count_reset();
740
741	UnorderedSet unordered_set;
742
743	// empty tests
744	//
745	// explicitly test `equal_range()` vs `equal_range() const`
746	//
747	{
748	typedef typename UnorderedSet::iterator iterator;
749	typedef std::pair<iterator, iterator> iterator_pair;
750
751	UnorderedSet& set = unordered_set;
752	BOOST_TEST(set.empty());
753
754	iterator_pair iters = set.equal_range(0);
755
756	iterator begin = iters.first;
757	iterator end = iters.second;
758
759	BOOST_TEST(begin == end);
760	BOOST_TEST(begin == set.end());
761	BOOST_TEST_EQ(std::distance(begin, end), 0);
762	}
763
764	{
765	typedef typename UnorderedSet::const_iterator iterator;
766	typedef std::pair<iterator, iterator> iterator_pair;
767
768	UnorderedSet const& set = unordered_set;
769	BOOST_TEST(set.empty());
770
771	iterator_pair iters = set.equal_range(0);
772
773	iterator begin = iters.first;
774	iterator end = iters.second;
775
776	BOOST_TEST(begin == end);
777	BOOST_TEST(begin == set.end());
778	BOOST_TEST_EQ(std::distance(begin, end), 0);
779	}
780
781	BOOST_TEST_EQ(key::count_, 0);
782
783	unordered_set.insert(0);
784	unordered_set.insert(1);
785	unordered_set.insert(2);
786	unordered_set.insert(0);
787	unordered_set.insert(0);
788	unordered_set.insert(0);
789
790	int const expected_key_count = key::count_;
791
792	// do this so that multiset tests actually test a range with len > 1
793	//
794	int const expected_range_len = static_cast<int>(unordered_set.size() - 2);
795
796	typedef typename UnorderedSet::value_type value_type;
797
798	// explicitly test `equal_range()` vs `equal_range() const`
799	//
800	{
801	typedef typename UnorderedSet::iterator iterator;
802	typedef std::pair<iterator, iterator> iterator_pair;
803
804	UnorderedSet& set = unordered_set;
805
806	iterator_pair iters = set.equal_range(0);
807
808	iterator begin = iters.first;
809	iterator end = iters.second;
810
811	BOOST_TEST(begin != end);
812	BOOST_TEST(begin != set.end());
813	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
814
815	for (iterator pos = begin; pos != end; ++pos) {
816	value_type const& val = *pos;
817	BOOST_TEST_EQ(val, 0);
818	}
819
820	iters = set.equal_range(1);
821	begin = iters.first;
822	end = iters.second;
823
824	BOOST_TEST(begin != end);
825	BOOST_TEST(begin != set.end());
826	BOOST_TEST_EQ(std::distance(begin, end), 1);
827
828	value_type const& val = *begin;
829	BOOST_TEST_EQ(val, 1);
830
831	iters = set.equal_range(1337);
832
833	begin = iters.first;
834	end = iters.second;
835
836	BOOST_TEST(begin == end);
837	BOOST_TEST(begin == set.end());
838	BOOST_TEST_EQ(std::distance(begin, end), 0);
839
840	BOOST_TEST_EQ(key::count_, expected_key_count);
841	}
842
843	{
844	typedef typename UnorderedSet::const_iterator iterator;
845	typedef std::pair<iterator, iterator> iterator_pair;
846
847	UnorderedSet const& set = unordered_set;
848
849	iterator_pair iters = set.equal_range(0);
850
851	iterator begin = iters.first;
852	iterator end = iters.second;
853
854	BOOST_TEST(begin != end);
855	BOOST_TEST(begin != set.end());
856	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
857
858	for (iterator pos = begin; pos != end; ++pos) {
859	value_type const& val = *begin;
860	BOOST_TEST_EQ(val, 0);
861	}
862
863	iters = set.equal_range(1);
864	begin = iters.first;
865	end = iters.second;
866
867	BOOST_TEST(begin != end);
868	BOOST_TEST(begin != set.end());
869	BOOST_TEST_EQ(std::distance(begin, end), 1);
870
871	value_type const& val = *begin;
872	BOOST_TEST_EQ(val, 1);
873
874	iters = set.equal_range(1337);
875
876	begin = iters.first;
877	end = iters.second;
878
879	BOOST_TEST(begin == end);
880	BOOST_TEST(begin == set.end());
881	BOOST_TEST_EQ(std::distance(begin, end), 0);
882
883	BOOST_TEST_EQ(key::count_, expected_key_count);
884	}
885	}
886
887	template <class UnorderedSet>
888	void test_set_non_transparent_equal_range(UnorderedSet*)
889	{
890	count_reset();
891
892	UnorderedSet unordered_set;
893
894	// empty tests
895	//
896	// explicitly test `equal_range()` vs `equal_range() const`
897	//
898	{
899	typedef typename UnorderedSet::iterator iterator;
900	typedef std::pair<iterator, iterator> iterator_pair;
901
902	UnorderedSet& set = unordered_set;
903	BOOST_TEST(set.empty());
904
905	iterator_pair iters = set.equal_range(0);
906
907	iterator begin = iters.first;
908	iterator end = iters.second;
909
910	BOOST_TEST(begin == end);
911	BOOST_TEST(begin == set.end());
912	BOOST_TEST_EQ(std::distance(begin, end), 0);
913	}
914
915	{
916	typedef typename UnorderedSet::const_iterator iterator;
917	typedef std::pair<iterator, iterator> iterator_pair;
918
919	UnorderedSet const& set = unordered_set;
920	BOOST_TEST(set.empty());
921
922	iterator_pair iters = set.equal_range(0);
923
924	iterator begin = iters.first;
925	iterator end = iters.second;
926
927	BOOST_TEST(begin == end);
928	BOOST_TEST(begin == set.end());
929	BOOST_TEST_EQ(std::distance(begin, end), 0);
930	}
931
932	BOOST_TEST_EQ(key::count_, 2);
933
934	unordered_set.insert(0);
935	unordered_set.insert(1);
936	unordered_set.insert(2);
937	unordered_set.insert(0);
938	unordered_set.insert(0);
939	unordered_set.insert(0);
940
941	int key_count = key::count_;
942
943	// do this so that multiset tests actually test a range with len > 1
944	//
945	int const expected_range_len = static_cast<int>(unordered_set.size() - 2);
946
947	typedef typename UnorderedSet::value_type value_type;
948
949	// explicitly test `equal_range()` vs `equal_range() const`
950	//
951	{
952	typedef typename UnorderedSet::iterator iterator;
953	typedef std::pair<iterator, iterator> iterator_pair;
954
955	UnorderedSet& set = unordered_set;
956
957	iterator_pair iters = set.equal_range(0);
958
959	iterator begin = iters.first;
960	iterator end = iters.second;
961
962	BOOST_TEST(begin != end);
963	BOOST_TEST(begin != set.end());
964	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
965
966	for (iterator pos = begin; pos != end; ++pos) {
967	value_type const& val = *begin;
968	BOOST_TEST_EQ(val, 0);
969	}
970
971	iters = set.equal_range(1);
972	begin = iters.first;
973	end = iters.second;
974
975	BOOST_TEST(begin != end);
976	BOOST_TEST(begin != set.end());
977	BOOST_TEST_EQ(std::distance(begin, end), 1);
978
979	value_type const& val = *begin;
980	BOOST_TEST_EQ(val, 1);
981
982	iters = set.equal_range(1337);
983
984	begin = iters.first;
985	end = iters.second;
986
987	BOOST_TEST(begin == end);
988	BOOST_TEST(begin == set.end());
989	BOOST_TEST_EQ(std::distance(begin, end), 0);
990
991	BOOST_TEST_EQ(key::count_, 3 + key_count);
992	key_count += 3;
993	}
994
995	{
996	typedef typename UnorderedSet::const_iterator iterator;
997	typedef std::pair<iterator, iterator> iterator_pair;
998
999	UnorderedSet const& set = unordered_set;
1000
1001	iterator_pair iters = set.equal_range(0);
1002
1003	iterator begin = iters.first;
1004	iterator end = iters.second;
1005
1006	BOOST_TEST(begin != end);
1007	BOOST_TEST(begin != set.end());
1008	BOOST_TEST_EQ(std::distance(begin, end), expected_range_len);
1009
1010	for (iterator pos = begin; pos != end; ++pos) {
1011	value_type const& val = *pos;
1012	BOOST_TEST_EQ(val, 0);
1013	}
1014
1015	iters = set.equal_range(1);
1016	begin = iters.first;
1017	end = iters.second;
1018
1019	BOOST_TEST(begin != end);
1020	BOOST_TEST(begin != set.end());
1021	BOOST_TEST_EQ(std::distance(begin, end), 1);
1022
1023	value_type const& val = *begin;
1024	BOOST_TEST_EQ(val, 1);
1025
1026	iters = set.equal_range(1337);
1027
1028	begin = iters.first;
1029	end = iters.second;
1030
1031	BOOST_TEST(begin == end);
1032	BOOST_TEST(begin == set.end());
1033	BOOST_TEST_EQ(std::distance(begin, end), 0);
1034
1035	BOOST_TEST_EQ(key::count_, 3 + key_count);
1036	}
1037	}
1038
1039	template <class UnorderedMap> struct convertible_to_iterator
1040	{
1041	operator typename UnorderedMap::iterator()
1042	{
1043	return typename UnorderedMap::iterator();
1044	}
1045	};
1046
1047	template <class UnorderedMap> struct convertible_to_const_iterator
1048	{
1049	operator typename UnorderedMap::const_iterator()
1050	{
1051	return typename UnorderedMap::const_iterator();
1052	}
1053	};
1054
1055	#ifdef BOOST_UNORDERED_FOA_TESTS
1056	typedef boost::unordered_flat_map<int, int, transparent_hasher,
1057	transparent_key_equal>
1058	transparent_unordered_map;
1059	#else
1060	typedef boost::unordered_map<int, int, transparent_hasher,
1061	transparent_key_equal>
1062	transparent_unordered_map;
1063	#endif
1064
1065	// test that in the presence of the member function template `erase()`, we still
1066	// invoke the correct iterator overloads when the type is implicitly convertible
1067	//
1068	transparent_unordered_map::iterator
1069	map_erase_overload_compile_test()
1070	{
1071	convertible_to_iterator<transparent_unordered_map> c;
1072	transparent_unordered_map map;
1073	transparent_unordered_map::iterator pos = map.begin();
1074	pos = c;
1075	return map.erase(position: c);
1076	}
1077
1078	transparent_unordered_map::const_iterator
1079	map_erase_const_overload_compile_test()
1080	{
1081	convertible_to_const_iterator<transparent_unordered_map> c;
1082	transparent_unordered_map map;
1083	transparent_unordered_map::const_iterator pos = map.begin();
1084	pos = c;
1085	return map.erase(position: c);
1086	}
1087
1088	#ifndef BOOST_UNORDERED_FOA_TESTS
1089	typedef boost::unordered_multimap<int, int, transparent_hasher,
1090	transparent_key_equal>
1091	transparent_unordered_multimap;
1092
1093	transparent_unordered_multimap::iterator multimap_erase_overload_compile_test()
1094	{
1095	convertible_to_iterator<transparent_unordered_multimap> c;
1096	transparent_unordered_multimap map;
1097	transparent_unordered_multimap::iterator pos = map.begin();
1098	pos = c;
1099	return map.erase(position: c);
1100	}
1101
1102	transparent_unordered_multimap::const_iterator
1103	multimap_erase_const_overload_compile_test()
1104	{
1105	convertible_to_const_iterator<transparent_unordered_multimap> c;
1106	transparent_unordered_multimap map;
1107	transparent_unordered_multimap::const_iterator pos = map.begin();
1108	pos = c;
1109	return map.erase(position: c);
1110	}
1111	#endif
1112
1113	template <class UnorderedMap> void test_map_transparent_erase(UnorderedMap*)
1114	{
1115	count_reset();
1116
1117	UnorderedMap map;
1118
1119	std::size_t num_erased = 0;
1120
1121	num_erased = map.erase(0);
1122	BOOST_TEST(map.empty());
1123	BOOST_TEST_EQ(num_erased, 0u);
1124	BOOST_TEST_EQ(key::count_, 0);
1125
1126	map.insert(std::make_pair(x: 0, y: 1337));
1127	map.insert(std::make_pair(x: 1, y: 1338));
1128	map.insert(std::make_pair(x: 2, y: 1339));
1129	map.insert(std::make_pair(x: 0, y: 1340));
1130	map.insert(std::make_pair(x: 0, y: 1341));
1131	map.insert(std::make_pair(x: 0, y: 1342));
1132
1133	BOOST_TEST(map.find(0) != map.end());
1134
1135	int const expected_key_count = key::count_;
1136	std::size_t const expected_num_erased = map.size() - 2;
1137
1138	num_erased = map.erase(0);
1139	BOOST_TEST_EQ(num_erased, expected_num_erased);
1140	BOOST_TEST_EQ(map.size(), 2u);
1141	BOOST_TEST(map.find(0) == map.end());
1142
1143	num_erased = map.erase(1);
1144	BOOST_TEST_EQ(num_erased, 1u);
1145	BOOST_TEST_EQ(map.size(), 1u);
1146	BOOST_TEST(map.find(1) == map.end());
1147
1148	num_erased = map.erase(1337);
1149	BOOST_TEST_EQ(num_erased, 0u);
1150	BOOST_TEST_EQ(map.size(), 1u);
1151
1152	BOOST_TEST_EQ(key::count_, expected_key_count);
1153	}
1154
1155	template <class UnorderedMap> void test_map_non_transparent_erase(UnorderedMap*)
1156	{
1157	count_reset();
1158
1159	UnorderedMap map;
1160
1161	std::size_t num_erased = 0;
1162
1163	num_erased = map.erase(0);
1164	BOOST_TEST(map.empty());
1165	BOOST_TEST_EQ(num_erased, 0u);
1166	BOOST_TEST_EQ(key::count_, 1);
1167
1168	map.insert(std::make_pair(x: 0, y: 1337));
1169	map.insert(std::make_pair(x: 1, y: 1338));
1170	map.insert(std::make_pair(x: 2, y: 1339));
1171	map.insert(std::make_pair(x: 0, y: 1340));
1172	map.insert(std::make_pair(x: 0, y: 1341));
1173	map.insert(std::make_pair(x: 0, y: 1342));
1174
1175	std::size_t const expected_num_erased = map.size() - 2;
1176
1177	BOOST_TEST(map.find(0) != map.end());
1178
1179	int key_count = key::count_;
1180
1181	num_erased = map.erase(0);
1182	++key_count;
1183	BOOST_TEST_EQ(key::count_, key_count);
1184	BOOST_TEST_EQ(num_erased, expected_num_erased);
1185	BOOST_TEST_EQ(map.size(), 2u);
1186
1187	BOOST_TEST(map.find(0) == map.end());
1188	++key_count;
1189
1190	BOOST_TEST_EQ(key::count_, key_count);
1191
1192	num_erased = map.erase(1);
1193	++key_count;
1194	BOOST_TEST_EQ(num_erased, 1u);
1195	BOOST_TEST_EQ(map.size(), 1u);
1196
1197	BOOST_TEST(map.find(1) == map.end());
1198	++key_count;
1199
1200	num_erased = map.erase(1337);
1201	++key_count;
1202	BOOST_TEST_EQ(num_erased, 0u);
1203	BOOST_TEST_EQ(map.size(), 1u);
1204
1205	BOOST_TEST_EQ(key::count_, key_count);
1206	}
1207
1208	#if BOOST_UNORDERED_FOA_TESTS
1209	typedef boost::unordered_flat_set<int, transparent_hasher,
1210	transparent_key_equal>
1211	transparent_unordered_set;
1212	#else
1213	typedef boost::unordered_set<int, transparent_hasher, transparent_key_equal>
1214	transparent_unordered_set;
1215
1216	typedef boost::unordered_multiset<int, transparent_hasher,
1217	transparent_key_equal>
1218	transparent_unordered_multiset;
1219	#endif
1220
1221	transparent_unordered_set::iterator
1222	set_erase_overload_compile_test()
1223	{
1224	convertible_to_iterator<transparent_unordered_set> c;
1225	transparent_unordered_set set;
1226	transparent_unordered_set::iterator pos = set.begin();
1227	pos = c;
1228	return set.erase(position: c);
1229	}
1230
1231	transparent_unordered_set::const_iterator
1232	set_erase_const_overload_compile_test()
1233	{
1234	convertible_to_const_iterator<transparent_unordered_set> c;
1235	transparent_unordered_set set;
1236	transparent_unordered_set::const_iterator pos = set.begin();
1237	pos = c;
1238	return set.erase(position: c);
1239	}
1240
1241	#ifndef BOOST_UNORDERED_FOA_TESTS
1242	transparent_unordered_multiset::iterator multiset_erase_overload_compile_test()
1243	{
1244	convertible_to_iterator<transparent_unordered_multiset> c;
1245	transparent_unordered_multiset set;
1246	transparent_unordered_multiset::iterator pos = set.begin();
1247	pos = c;
1248	return set.erase(position: c);
1249	}
1250
1251	transparent_unordered_multiset::const_iterator
1252	multiset_erase_const_overload_compile_test()
1253	{
1254	convertible_to_const_iterator<transparent_unordered_multiset> c;
1255	transparent_unordered_multiset set;
1256	transparent_unordered_multiset::const_iterator pos = set.begin();
1257	pos = c;
1258	return set.erase(position: c);
1259	}
1260	#endif
1261
1262	template <class UnorderedSet> void test_set_transparent_erase(UnorderedSet*)
1263	{
1264	count_reset();
1265
1266	UnorderedSet set;
1267
1268	std::size_t num_erased = 0;
1269
1270	num_erased = set.erase(0);
1271	BOOST_TEST(set.empty());
1272	BOOST_TEST_EQ(num_erased, 0u);
1273	BOOST_TEST_EQ(key::count_, 0);
1274
1275	set.insert(0);
1276	set.insert(1);
1277	set.insert(2);
1278	set.insert(0);
1279	set.insert(0);
1280	set.insert(0);
1281
1282	BOOST_TEST(set.find(0) != set.end());
1283
1284	int const expected_key_count = key::count_;
1285	std::size_t const expected_num_erased = set.size() - 2;
1286
1287	num_erased = set.erase(0);
1288	BOOST_TEST_EQ(num_erased, expected_num_erased);
1289	BOOST_TEST_EQ(set.size(), 2u);
1290	BOOST_TEST(set.find(0) == set.end());
1291
1292	num_erased = set.erase(1);
1293	BOOST_TEST_EQ(num_erased, 1u);
1294	BOOST_TEST_EQ(set.size(), 1u);
1295	BOOST_TEST(set.find(1) == set.end());
1296
1297	num_erased = set.erase(1337);
1298	BOOST_TEST_EQ(num_erased, 0u);
1299	BOOST_TEST_EQ(set.size(), 1u);
1300
1301	BOOST_TEST_EQ(key::count_, expected_key_count);
1302	}
1303
1304	template <class UnorderedSet> void test_set_non_transparent_erase(UnorderedSet*)
1305	{
1306	count_reset();
1307
1308	UnorderedSet set;
1309
1310	std::size_t num_erased = 0;
1311
1312	num_erased = set.erase(0);
1313	BOOST_TEST(set.empty());
1314	BOOST_TEST_EQ(num_erased, 0u);
1315	BOOST_TEST_EQ(key::count_, 1);
1316
1317	set.insert(0);
1318	set.insert(1);
1319	set.insert(2);
1320	set.insert(0);
1321	set.insert(0);
1322	set.insert(0);
1323
1324	std::size_t const expected_num_erased = set.size() - 2;
1325
1326	BOOST_TEST(set.find(0) != set.end());
1327
1328	int key_count = key::count_;
1329
1330	num_erased = set.erase(0);
1331	++key_count;
1332	BOOST_TEST_EQ(key::count_, key_count);
1333	BOOST_TEST_EQ(num_erased, expected_num_erased);
1334	BOOST_TEST_EQ(set.size(), 2u);
1335
1336	BOOST_TEST(set.find(0) == set.end());
1337	++key_count;
1338
1339	BOOST_TEST_EQ(key::count_, key_count);
1340
1341	num_erased = set.erase(1);
1342	++key_count;
1343	BOOST_TEST_EQ(num_erased, 1u);
1344	BOOST_TEST_EQ(set.size(), 1u);
1345
1346	BOOST_TEST(set.find(1) == set.end());
1347	++key_count;
1348
1349	num_erased = set.erase(1337);
1350	++key_count;
1351	BOOST_TEST_EQ(num_erased, 0u);
1352	BOOST_TEST_EQ(set.size(), 1u);
1353
1354	BOOST_TEST_EQ(key::count_, key_count);
1355	}
1356
1357	#ifndef BOOST_UNORDERED_FOA_TESTS
1358	// test that in the presence of the member function template `extract()`, we
1359	// still invoke the correct iterator overloads when the type is implicitly
1360	// convertible
1361	//
1362	transparent_unordered_map::node_type map_extract_const_overload_compile_test()
1363	{
1364	convertible_to_const_iterator<transparent_unordered_map> c;
1365	transparent_unordered_map map;
1366	transparent_unordered_map::const_iterator pos = map.begin();
1367	pos = c;
1368	return map.extract(position: c);
1369	}
1370
1371	transparent_unordered_multimap::node_type
1372	multimap_extract_const_overload_compile_test()
1373	{
1374	convertible_to_const_iterator<transparent_unordered_multimap> c;
1375	transparent_unordered_multimap map;
1376	transparent_unordered_multimap::const_iterator pos = map.begin();
1377	pos = c;
1378	return map.extract(position: c);
1379	}
1380	#endif
1381
1382	template <class UnorderedMap> void test_map_transparent_extract(UnorderedMap*)
1383	{
1384	typedef typename UnorderedMap::node_type node_type;
1385	typedef typename UnorderedMap::const_iterator const_iterator;
1386	typedef std::pair<const_iterator, const_iterator> const_iterator_pair;
1387
1388	count_reset();
1389
1390	UnorderedMap map;
1391
1392	node_type nh = map.extract(0);
1393	BOOST_TEST(nh.empty());
1394	BOOST_TEST_EQ(key::count_, 0);
1395
1396	map.insert(std::make_pair(x: 0, y: 1337));
1397	map.insert(std::make_pair(x: 1, y: 1338));
1398	map.insert(std::make_pair(x: 2, y: 1339));
1399	map.insert(std::make_pair(x: 0, y: 1340));
1400	map.insert(std::make_pair(x: 0, y: 1341));
1401	map.insert(std::make_pair(x: 0, y: 1342));
1402
1403	std::size_t const map_size = map.size();
1404	int const expected_key_count = key::count_;
1405
1406	nh = map.extract(0);
1407	BOOST_TEST_EQ(map.size(), map_size - 1);
1408	BOOST_TEST_EQ(nh.key().x_, 0);
1409
1410	const_iterator_pair rng = map.equal_range(0);
1411	for (const_iterator pos = rng.first; pos != rng.second; ++pos) {
1412	BOOST_TEST_NE(pos->second, nh.mapped());
1413	}
1414
1415	nh = map.extract(1337);
1416	BOOST_TEST(nh.empty());
1417
1418	BOOST_TEST_EQ(key::count_, expected_key_count);
1419	}
1420
1421	template <class UnorderedMap>
1422	void test_map_non_transparent_extract(UnorderedMap*)
1423	{
1424	typedef typename UnorderedMap::node_type node_type;
1425	typedef typename UnorderedMap::const_iterator const_iterator;
1426	typedef std::pair<const_iterator, const_iterator> const_iterator_pair;
1427
1428	count_reset();
1429
1430	UnorderedMap map;
1431
1432	node_type nh = map.extract(0);
1433	BOOST_TEST(nh.empty());
1434	BOOST_TEST_EQ(key::count_, 1);
1435
1436	map.insert(std::make_pair(x: 0, y: 1337));
1437	map.insert(std::make_pair(x: 1, y: 1338));
1438	map.insert(std::make_pair(x: 2, y: 1339));
1439	map.insert(std::make_pair(x: 0, y: 1340));
1440	map.insert(std::make_pair(x: 0, y: 1341));
1441	map.insert(std::make_pair(x: 0, y: 1342));
1442
1443	std::size_t const map_size = map.size();
1444	int key_count = key::count_;
1445
1446	nh = map.extract(0);
1447	++key_count;
1448
1449	BOOST_TEST_EQ(map.size(), map_size - 1);
1450	BOOST_TEST_EQ(nh.key().x_, 0);
1451	BOOST_TEST_EQ(key::count_, key_count);
1452
1453	const_iterator_pair rng = map.equal_range(0);
1454	++key_count;
1455
1456	for (const_iterator pos = rng.first; pos != rng.second; ++pos) {
1457	BOOST_TEST_NE(pos->second, nh.mapped());
1458	}
1459
1460	nh = map.extract(1337);
1461	++key_count;
1462	BOOST_TEST(nh.empty());
1463	BOOST_TEST_EQ(key::count_, key_count);
1464	}
1465
1466	template <class UnorderedMap>
1467	void test_map_transparent_try_emplace(UnorderedMap*)
1468	{
1469	count_reset();
1470
1471	typedef typename UnorderedMap::iterator iterator;
1472
1473	UnorderedMap map;
1474
1475	map.insert(std::make_pair(x: 0, y: 1337));
1476	map.insert(std::make_pair(x: 1, y: 1338));
1477	map.insert(std::make_pair(x: 2, y: 1339));
1478	map.insert(std::make_pair(x: 0, y: 1340));
1479	map.insert(std::make_pair(x: 0, y: 1341));
1480	map.insert(std::make_pair(x: 0, y: 1342));
1481
1482	int key_count = key::count_;
1483
1484	std::pair<iterator, bool> r = map.try_emplace(0, 7331);
1485	BOOST_TEST(r.first == map.find(0));
1486	BOOST_TEST_NOT(r.second);
1487	BOOST_TEST_EQ(key::count_, key_count);
1488
1489	r = map.try_emplace(4, 7331);
1490	BOOST_TEST(r.first == map.find(4));
1491	BOOST_TEST(r.second);
1492	BOOST_TEST_EQ(key::count_, key_count + 1);
1493
1494	key_count = key::count_;
1495
1496	iterator p = map.try_emplace(map.cbegin(), 0, 7331);
1497	BOOST_TEST(p == map.find(0));
1498	BOOST_TEST_EQ(key::count_, key_count);
1499
1500	p = map.try_emplace(map.begin(), 5, 7331);
1501	BOOST_TEST(p == map.find(5));
1502	BOOST_TEST_EQ(key::count_, key_count + 1);
1503	}
1504
1505	template <class UnorderedMap>
1506	void test_map_non_transparent_try_emplace(UnorderedMap*)
1507	{
1508	count_reset();
1509
1510	typedef typename UnorderedMap::iterator iterator;
1511
1512	UnorderedMap map;
1513
1514	map.insert(std::make_pair(x: 0, y: 1337));
1515	map.insert(std::make_pair(x: 1, y: 1338));
1516	map.insert(std::make_pair(x: 2, y: 1339));
1517	map.insert(std::make_pair(x: 0, y: 1340));
1518	map.insert(std::make_pair(x: 0, y: 1341));
1519	map.insert(std::make_pair(x: 0, y: 1342));
1520
1521	int key_count = key::count_;
1522
1523	std::pair<iterator, bool> r = map.try_emplace(0, 7331);
1524	BOOST_TEST_EQ(key::count_, key_count + 1);
1525	BOOST_TEST(r.first == map.find(0));
1526	BOOST_TEST_NOT(r.second);
1527
1528	key_count = key::count_;
1529	r = map.try_emplace(4, 7331);
1530	BOOST_TEST_EQ(key::count_, key_count + 2);
1531	BOOST_TEST(r.first == map.find(4));
1532	BOOST_TEST(r.second);
1533
1534	key_count = key::count_;
1535	iterator p = map.try_emplace(map.cbegin(), 0, 7331);
1536	BOOST_TEST_EQ(key::count_, key_count + 1);
1537	BOOST_TEST(p == map.find(0));
1538
1539	key_count = key::count_;
1540	p = map.try_emplace(map.begin(), 5, 7331);
1541	BOOST_TEST_EQ(key::count_, key_count + 2);
1542	BOOST_TEST(p == map.find(5));
1543	}
1544
1545	template <class UnorderedMap>
1546	void test_map_transparent_insert_or_assign(UnorderedMap*)
1547	{
1548	count_reset();
1549
1550	typedef typename UnorderedMap::iterator iterator;
1551
1552	UnorderedMap map;
1553
1554	map.insert(std::make_pair(x: 0, y: 1337));
1555	map.insert(std::make_pair(x: 1, y: 1338));
1556	map.insert(std::make_pair(x: 2, y: 1339));
1557	map.insert(std::make_pair(x: 0, y: 1340));
1558	map.insert(std::make_pair(x: 0, y: 1341));
1559	map.insert(std::make_pair(x: 0, y: 1342));
1560
1561	int key_count = key::count_;
1562
1563	std::pair<iterator, bool> r = map.insert_or_assign(0, 7331);
1564	BOOST_TEST(r.first == map.find(0));
1565	BOOST_TEST_EQ(r.first->second, 7331);
1566	BOOST_TEST_NOT(r.second);
1567	BOOST_TEST_EQ(key::count_, key_count);
1568
1569	r = map.insert_or_assign(4, 7331);
1570	BOOST_TEST(r.first == map.find(4));
1571	BOOST_TEST(r.second);
1572	BOOST_TEST_EQ(key::count_, key_count + 1);
1573
1574	key_count = key::count_;
1575
1576	iterator p = map.insert_or_assign(map.cbegin(), 0, 1111);
1577	BOOST_TEST(p == map.find(0));
1578	BOOST_TEST_EQ(p->second, 1111);
1579	BOOST_TEST_EQ(key::count_, key_count);
1580
1581	p = map.insert_or_assign(map.begin(), 5, 7331);
1582	BOOST_TEST(p == map.find(5));
1583	BOOST_TEST_EQ(key::count_, key_count + 1);
1584	}
1585
1586	template <class UnorderedMap>
1587	void test_map_non_transparent_insert_or_assign(UnorderedMap*)
1588	{
1589	count_reset();
1590
1591	typedef typename UnorderedMap::iterator iterator;
1592
1593	UnorderedMap map;
1594
1595	map.insert(std::make_pair(x: 0, y: 1337));
1596	map.insert(std::make_pair(x: 1, y: 1338));
1597	map.insert(std::make_pair(x: 2, y: 1339));
1598	map.insert(std::make_pair(x: 0, y: 1340));
1599	map.insert(std::make_pair(x: 0, y: 1341));
1600	map.insert(std::make_pair(x: 0, y: 1342));
1601
1602	int key_count = key::count_;
1603
1604	std::pair<iterator, bool> r = map.insert_or_assign(0, 7331);
1605	BOOST_TEST_EQ(key::count_, key_count + 1);
1606	BOOST_TEST(r.first == map.find(0));
1607	BOOST_TEST_EQ(r.first->second, 7331);
1608	BOOST_TEST_NOT(r.second);
1609
1610	key_count = key::count_;
1611	r = map.insert_or_assign(4, 7331);
1612	BOOST_TEST_EQ(key::count_, key_count + 2);
1613	BOOST_TEST(r.first == map.find(4));
1614	BOOST_TEST(r.second);
1615
1616	key_count = key::count_;
1617	iterator p = map.insert_or_assign(map.cbegin(), 0, 1111);
1618	BOOST_TEST_EQ(key::count_, key_count + 1);
1619	BOOST_TEST(p == map.find(0));
1620	BOOST_TEST_EQ(p->second, 1111);
1621
1622	key_count = key::count_;
1623	p = map.insert_or_assign(map.begin(), 5, 7331);
1624	BOOST_TEST_EQ(key::count_, key_count + 2);
1625	BOOST_TEST(p == map.find(5));
1626	}
1627
1628	template <class UnorderedMap> void test_map_transparent_subscript(UnorderedMap*)
1629	{
1630	count_reset();
1631
1632	UnorderedMap map;
1633
1634	map[0] = 1337;
1635	map[1] = 1338;
1636	map[2] = 1339;
1637	map[0] = 1340;
1638	map[0] = 1341;
1639	map[0] = 1342;
1640
1641	int key_count = key::count_;
1642
1643	map[0] = 7331;
1644	BOOST_TEST_EQ(key::count_, key_count);
1645
1646	map[4] = 7331;
1647	BOOST_TEST_EQ(key::count_, key_count + 1);
1648	}
1649
1650	template <class UnorderedMap>
1651	void test_map_non_transparent_subscript(UnorderedMap*)
1652	{
1653	count_reset();
1654
1655	UnorderedMap map;
1656
1657	map[0] = 1337;
1658	map[1] = 1338;
1659	map[2] = 1339;
1660	map[0] = 1340;
1661	map[0] = 1341;
1662	map[0] = 1342;
1663
1664	int key_count = key::count_;
1665
1666	map[0] = 7331;
1667	BOOST_TEST_EQ(key::count_, key_count + 1);
1668
1669	key_count = key::count_;
1670	map[4] = 7331;
1671	BOOST_TEST_EQ(key::count_, key_count + 2);
1672	}
1673
1674	template <class UnorderedMap> void test_map_transparent_at(UnorderedMap*)
1675	{
1676	count_reset();
1677
1678	UnorderedMap map;
1679
1680	map.insert(std::make_pair(x: 0, y: 1337));
1681	map.insert(std::make_pair(x: 1, y: 1338));
1682	map.insert(std::make_pair(x: 2, y: 1339));
1683	map.insert(std::make_pair(x: 0, y: 1340));
1684	map.insert(std::make_pair(x: 0, y: 1341));
1685	map.insert(std::make_pair(x: 0, y: 1342));
1686
1687	int key_count = key::count_;
1688
1689	map.at(0) = 7331;
1690	BOOST_TEST_EQ(key::count_, key_count);
1691
1692	BOOST_TEST_THROWS(map.at(4), std::out_of_range)
1693	BOOST_TEST_EQ(key::count_, key_count);
1694
1695	UnorderedMap const& m = map;
1696	BOOST_TEST_EQ(m.at(0), 7331);
1697	BOOST_TEST_EQ(key::count_, key_count);
1698
1699	BOOST_TEST_THROWS(m.at(4), std::out_of_range)
1700	BOOST_TEST_EQ(key::count_, key_count);
1701	}
1702
1703	template <class UnorderedMap> void test_map_non_transparent_at(UnorderedMap*)
1704	{
1705	count_reset();
1706
1707	UnorderedMap map;
1708
1709	map.insert(std::make_pair(x: 0, y: 1337));
1710	map.insert(std::make_pair(x: 1, y: 1338));
1711	map.insert(std::make_pair(x: 2, y: 1339));
1712	map.insert(std::make_pair(x: 0, y: 1340));
1713	map.insert(std::make_pair(x: 0, y: 1341));
1714	map.insert(std::make_pair(x: 0, y: 1342));
1715
1716	int key_count = key::count_;
1717
1718	map.at(0) = 7331;
1719	BOOST_TEST_EQ(key::count_, key_count + 1);
1720
1721	key_count = key::count_;
1722	BOOST_TEST_THROWS(map.at(4), std::out_of_range)
1723	BOOST_TEST_EQ(key::count_, key_count + 1);
1724
1725	key_count = key::count_;
1726	UnorderedMap const& m = map;
1727	BOOST_TEST_EQ(m.at(0), 7331);
1728	BOOST_TEST_EQ(key::count_, key_count + 1);
1729
1730	key_count = key::count_;
1731	BOOST_TEST_THROWS(m.at(4), std::out_of_range)
1732	BOOST_TEST_EQ(key::count_, key_count + 1);
1733	}
1734
1735	template <class UnorderedMap> void test_map_transparent_bucket(UnorderedMap*)
1736	{
1737	#ifndef BOOST_UNORDERED_FOA_TESTS
1738	count_reset();
1739
1740	UnorderedMap map;
1741
1742	map.insert(std::make_pair(x: 0, y: 1337));
1743	map.insert(std::make_pair(x: 1, y: 1338));
1744	map.insert(std::make_pair(x: 2, y: 1339));
1745	map.insert(std::make_pair(x: 0, y: 1340));
1746	map.insert(std::make_pair(x: 0, y: 1341));
1747	map.insert(std::make_pair(x: 0, y: 1342));
1748
1749	int key_count = key::count_;
1750	map.bucket(0);
1751	map.bucket(4);
1752	BOOST_TEST_EQ(key::count_, key_count);
1753	#endif
1754	}
1755
1756	template <class UnorderedMap>
1757	void test_map_non_transparent_bucket(UnorderedMap*)
1758	{
1759	#ifndef BOOST_UNORDERED_FOA_TESTS
1760	count_reset();
1761
1762	UnorderedMap map;
1763
1764	map.insert(std::make_pair(x: 0, y: 1337));
1765	map.insert(std::make_pair(x: 1, y: 1338));
1766	map.insert(std::make_pair(x: 2, y: 1339));
1767	map.insert(std::make_pair(x: 0, y: 1340));
1768	map.insert(std::make_pair(x: 0, y: 1341));
1769	map.insert(std::make_pair(x: 0, y: 1342));
1770
1771	int key_count = key::count_;
1772	map.bucket(0);
1773	map.bucket(4);
1774	BOOST_TEST_EQ(key::count_, key_count + 2);
1775	#endif
1776	}
1777
1778	#ifndef BOOST_UNORDERED_FOA_TESTS
1779	transparent_unordered_set::node_type set_extract_overload_compile_test()
1780	{
1781	convertible_to_iterator<transparent_unordered_set> c;
1782	transparent_unordered_set set;
1783	transparent_unordered_set::iterator pos = set.begin();
1784	pos = c;
1785	return set.extract(position: c);
1786	}
1787
1788	transparent_unordered_set::node_type set_extract_const_overload_compile_test()
1789	{
1790	convertible_to_const_iterator<transparent_unordered_set> c;
1791	transparent_unordered_set set;
1792	transparent_unordered_set::const_iterator pos = set.begin();
1793	pos = c;
1794	return set.extract(position: c);
1795	}
1796
1797	transparent_unordered_multiset::node_type
1798	multiset_extract_overload_compile_test()
1799	{
1800	convertible_to_iterator<transparent_unordered_multiset> c;
1801	transparent_unordered_multiset set;
1802	transparent_unordered_multiset::iterator pos = set.begin();
1803	pos = c;
1804	return set.extract(position: c);
1805	}
1806
1807	transparent_unordered_multiset::node_type
1808	multiset_extract_const_overload_compile_test()
1809	{
1810	convertible_to_const_iterator<transparent_unordered_multiset> c;
1811	transparent_unordered_multiset set;
1812	transparent_unordered_multiset::const_iterator pos = set.begin();
1813	pos = c;
1814	return set.extract(position: c);
1815	}
1816	#endif
1817
1818	template <class UnorderedSet> void test_set_transparent_extract(UnorderedSet*)
1819	{
1820	typedef typename UnorderedSet::node_type node_type;
1821
1822	count_reset();
1823
1824	UnorderedSet set;
1825
1826	node_type nh = set.extract(0);
1827	BOOST_TEST(nh.empty());
1828	BOOST_TEST_EQ(key::count_, 0);
1829
1830	set.insert(0);
1831	set.insert(1);
1832	set.insert(2);
1833	set.insert(0);
1834	set.insert(0);
1835	set.insert(0);
1836
1837	std::size_t const set_size = set.size();
1838	int const expected_key_count = key::count_;
1839
1840	std::size_t count = 0;
1841
1842	nh = set.extract(0);
1843	count = set.count(0);
1844	BOOST_TEST_EQ(set.size(), set_size - 1);
1845	BOOST_TEST_EQ(nh.value(), 0);
1846	BOOST_TEST_EQ(count, set_size - 3);
1847
1848	set.insert(std::move(nh));
1849
1850	nh = set.extract(1);
1851	count = set.count(1);
1852	BOOST_TEST_EQ(set.size(), set_size - 1);
1853	BOOST_TEST_EQ(nh.value(), 1);
1854	BOOST_TEST_EQ(count, 0u);
1855
1856	set.insert(std::move(nh));
1857
1858	nh = set.extract(1337);
1859	BOOST_TEST(nh.empty());
1860	BOOST_TEST_EQ(set.size(), set_size);
1861
1862	BOOST_TEST_EQ(key::count_, expected_key_count);
1863	}
1864
1865	template <class UnorderedSet>
1866	void test_set_non_transparent_extract(UnorderedSet*)
1867	{
1868	typedef typename UnorderedSet::node_type node_type;
1869
1870	count_reset();
1871
1872	UnorderedSet set;
1873
1874	node_type nh = set.extract(0);
1875	BOOST_TEST(nh.empty());
1876	BOOST_TEST_EQ(key::count_, 1);
1877
1878	set.insert(0);
1879	set.insert(1);
1880	set.insert(2);
1881	set.insert(0);
1882	set.insert(0);
1883	set.insert(0);
1884
1885	std::size_t const set_size = set.size();
1886
1887	int key_count = key::count_;
1888	std::size_t count = 0;
1889
1890	nh = set.extract(0);
1891	++key_count;
1892
1893	count = set.count(0);
1894	++key_count;
1895
1896	BOOST_TEST_EQ(set.size(), set_size - 1);
1897	BOOST_TEST_EQ(nh.value(), 0);
1898	BOOST_TEST_EQ(count, set_size - 3);
1899
1900	set.insert(std::move(nh));
1901
1902	nh = set.extract(1);
1903	++key_count;
1904
1905	count = set.count(1);
1906	++key_count;
1907
1908	BOOST_TEST_EQ(set.size(), set_size - 1);
1909	BOOST_TEST_EQ(nh.value(), 1);
1910	BOOST_TEST_EQ(count, 0u);
1911
1912	set.insert(std::move(nh));
1913
1914	nh = set.extract(1337);
1915	++key_count;
1916
1917	BOOST_TEST(nh.empty());
1918	BOOST_TEST_EQ(set.size(), set_size);
1919
1920	BOOST_TEST_EQ(key::count_, key_count);
1921	}
1922
1923	template <class UnorderedSet> void test_set_transparent_bucket(UnorderedSet*)
1924	{
1925	#ifndef BOOST_UNORDERED_FOA_TESTS
1926	count_reset();
1927
1928	UnorderedSet set;
1929
1930	set.insert(0);
1931	set.insert(1);
1932	set.insert(2);
1933	set.insert(0);
1934	set.insert(0);
1935	set.insert(0);
1936
1937	int key_count = key::count_;
1938	set.bucket(0);
1939	set.bucket(4);
1940	BOOST_TEST_EQ(key::count_, key_count);
1941	#endif
1942	}
1943
1944	template <class UnorderedSet>
1945	void test_set_non_transparent_bucket(UnorderedSet*)
1946	{
1947	#ifndef BOOST_UNORDERED_FOA_TESTS
1948	count_reset();
1949
1950	UnorderedSet set;
1951
1952	set.insert(0);
1953	set.insert(1);
1954	set.insert(2);
1955	set.insert(0);
1956	set.insert(0);
1957	set.insert(0);
1958
1959	int key_count = key::count_;
1960	set.bucket(0);
1961	set.bucket(4);
1962	BOOST_TEST_EQ(key::count_, key_count + 2);
1963	#endif
1964	}
1965
1966	template <class UnorderedSet> void test_set_transparent_insert(UnorderedSet*)
1967	{
1968	count_reset();
1969
1970	typedef typename UnorderedSet::iterator iterator;
1971
1972	UnorderedSet set;
1973
1974	set.insert(0);
1975	set.insert(1);
1976	set.insert(2);
1977	set.insert(0);
1978	set.insert(0);
1979	set.insert(0);
1980
1981	int key_count = key::count_;
1982
1983	std::pair<iterator, bool> p = set.insert(0);
1984	BOOST_TEST(p.first == set.find(0));
1985	BOOST_TEST_NOT(p.second);
1986	BOOST_TEST_EQ(key::count_, key_count);
1987
1988	key_count = key::count_;
1989	p = set.insert(4);
1990	BOOST_TEST(p.first == set.find(4));
1991	BOOST_TEST(p.second);
1992	BOOST_TEST_EQ(key::count_, key_count + 1);
1993
1994	key_count = key::count_;
1995	iterator pos = set.insert(set.begin(), 0);
1996	BOOST_TEST(pos == set.find(0));
1997	BOOST_TEST_EQ(key::count_, key_count);
1998
1999	key_count = key::count_;
2000	pos = set.insert(set.begin(), 5);
2001	BOOST_TEST(pos == set.find(5));
2002	BOOST_TEST_EQ(key::count_, key_count + 1);
2003
2004	// check for collisions with insert(iterator, iterator)
2005	// note: this precludes Key from being convertible to an iterator which isn't
2006	// explicitly stated by p2363r3
2007	//
2008	set.insert(set.begin(), set.end());
2009	}
2010
2011	template <class UnorderedSet>
2012	void test_set_non_transparent_insert(UnorderedSet*)
2013	{
2014	count_reset();
2015
2016	typedef typename UnorderedSet::iterator iterator;
2017
2018	UnorderedSet set;
2019
2020	set.insert(0);
2021	set.insert(1);
2022	set.insert(2);
2023	set.insert(0);
2024	set.insert(0);
2025	set.insert(0);
2026
2027	int key_count = key::count_;
2028
2029	std::pair<iterator, bool> p = set.insert(0);
2030	BOOST_TEST_EQ(key::count_, key_count + 1);
2031	BOOST_TEST(p.first == set.find(0));
2032	BOOST_TEST_NOT(p.second);
2033
2034	key_count = key::count_;
2035	p = set.insert(4);
2036	BOOST_TEST_EQ(key::count_, key_count + 2);
2037	BOOST_TEST(p.first == set.find(4));
2038	BOOST_TEST(p.second);
2039
2040	key_count = key::count_;
2041	iterator pos = set.insert(set.begin(), 0);
2042	BOOST_TEST_EQ(key::count_, key_count + 1);
2043	BOOST_TEST(pos == set.find(0));
2044
2045	key_count = key::count_;
2046	pos = set.insert(set.begin(), 5);
2047	BOOST_TEST_EQ(key::count_, key_count + 2);
2048	BOOST_TEST(pos == set.find(5));
2049
2050	set.insert(set.begin(), set.end());
2051	}
2052
2053	template <class Key, class T, class Hash, class KeyEqual> struct map_type
2054	{
2055	#ifdef BOOST_UNORDERED_FOA_TESTS
2056	typedef boost::unordered_flat_map<Key, T, Hash, KeyEqual> type;
2057	#else
2058	typedef boost::unordered_map<Key, T, Hash, KeyEqual> type;
2059	#endif
2060	};
2061
2062	#ifdef BOOST_UNORDERED_FOA_TESTS
2063	static boost::unordered_flat_map<key, int, transparent_hasher,
2064	transparent_key_equal>* test_trans_map;
2065	static boost::unordered_flat_map<key, int, hasher, key_equal>* test_map1;
2066	static boost::unordered_flat_map<key, int, transparent_hasher, key_equal>*
2067	test_map2;
2068	static boost::unordered_flat_map<key, int, hasher, transparent_key_equal>*
2069	test_map3;
2070
2071	static boost::unordered_node_map<key, int, transparent_hasher,
2072	transparent_key_equal>* test_trans_node_map;
2073	static boost::unordered_node_map<key, int, hasher, key_equal>* test_node_map1;
2074	static boost::unordered_node_map<key, int, transparent_hasher, key_equal>*
2075	test_node_map2;
2076	static boost::unordered_node_map<key, int, hasher, transparent_key_equal>*
2077	test_node_map3;
2078
2079	// clang-format off
2080	UNORDERED_TEST(test_map_transparent_count,
2081	((test_trans_map)(test_trans_node_map)))
2082
2083	UNORDERED_TEST(test_map_transparent_find,
2084	((test_trans_map)(test_trans_node_map)))
2085
2086	UNORDERED_TEST(test_map_transparent_equal_range,
2087	((test_trans_map)(test_trans_node_map)))
2088
2089	UNORDERED_TEST(test_map_transparent_erase,
2090	((test_trans_map)(test_trans_node_map)))
2091
2092	UNORDERED_TEST(test_map_transparent_extract,
2093	((test_trans_node_map)))
2094
2095	UNORDERED_TEST(test_map_transparent_try_emplace,
2096	((test_trans_map)(test_trans_node_map)))
2097
2098	UNORDERED_TEST(test_map_transparent_insert_or_assign,
2099	((test_trans_map)(test_trans_node_map)))
2100
2101	UNORDERED_TEST(test_map_transparent_subscript,
2102	((test_trans_map)(test_trans_node_map)))
2103
2104	UNORDERED_TEST(test_map_transparent_at,
2105	((test_trans_map)(test_trans_node_map)))
2106
2107	UNORDERED_TEST(test_map_transparent_bucket,
2108	((test_trans_map)(test_trans_node_map)))
2109
2110	UNORDERED_TEST(test_map_non_transparent_count,
2111	((test_map1)(test_map2)(test_map3)
2112	(test_node_map1)(test_node_map2)(test_node_map3)))
2113
2114	UNORDERED_TEST(test_map_non_transparent_find,
2115	((test_map1)(test_map2)(test_map3)
2116	(test_node_map1)(test_node_map2)(test_node_map3)))
2117
2118	UNORDERED_TEST(test_map_non_transparent_equal_range,
2119	((test_map1)(test_map2)(test_map3)
2120	(test_node_map1)(test_node_map2)(test_node_map3)))
2121
2122	UNORDERED_TEST(test_map_non_transparent_erase,
2123	((test_map1)(test_map2)(test_map3)
2124	(test_node_map1)(test_node_map2)(test_node_map3)))
2125
2126	UNORDERED_TEST(test_map_non_transparent_extract,
2127	((test_node_map1)(test_node_map2)(test_node_map3)))
2128
2129	UNORDERED_TEST(test_map_non_transparent_try_emplace,
2130	((test_map1)(test_map2)(test_map3)
2131	(test_node_map1)(test_node_map2)(test_node_map3)))
2132
2133	UNORDERED_TEST(test_map_non_transparent_insert_or_assign,
2134	((test_map1)(test_map2)(test_map3)
2135	(test_node_map1)(test_node_map2)(test_node_map3)))
2136
2137	UNORDERED_TEST(test_map_non_transparent_subscript,
2138	((test_map1)(test_map2)(test_map3)
2139	(test_node_map1)(test_node_map2)(test_node_map3)))
2140
2141	UNORDERED_TEST(test_map_non_transparent_at,
2142	((test_map1)(test_map2)(test_map3)
2143	(test_node_map1)(test_node_map2)(test_node_map3)))
2144
2145	UNORDERED_TEST(test_map_non_transparent_bucket,
2146	((test_map1)(test_map2)(test_map3)
2147	(test_node_map1)(test_node_map2)(test_node_map3)))
2148	// clang-format on
2149	#else
2150	static boost::unordered_map<key, int, transparent_hasher,
2151	transparent_key_equal>* test_trans_map;
2152	static boost::unordered_map<key, int, hasher, key_equal>* test_map1;
2153	static boost::unordered_map<key, int, transparent_hasher, key_equal>* test_map2;
2154	static boost::unordered_map<key, int, hasher, transparent_key_equal>* test_map3;
2155
2156	static boost::unordered_multimap<key, int, transparent_hasher,
2157	transparent_key_equal>* test_trans_multimap;
2158	static boost::unordered_multimap<key, int, hasher, key_equal>* test_multimap1;
2159	static boost::unordered_multimap<key, int, transparent_hasher, key_equal>*
2160	test_multimap2;
2161	static boost::unordered_multimap<key, int, hasher, transparent_key_equal>*
2162	test_multimap3;
2163
2164	// clang-format off
2165	UNORDERED_TEST(test_map_transparent_count,
2166	((test_trans_map)(test_trans_multimap)))
2167
2168	UNORDERED_TEST(test_map_transparent_find,
2169	((test_trans_map)(test_trans_multimap)))
2170
2171	UNORDERED_TEST(test_map_transparent_equal_range,
2172	((test_trans_map)(test_trans_multimap)))
2173
2174	UNORDERED_TEST(test_map_transparent_erase,
2175	((test_trans_map)(test_trans_multimap)))
2176
2177	UNORDERED_TEST(test_map_transparent_extract,
2178	((test_trans_map)(test_trans_multimap)))
2179
2180	UNORDERED_TEST(test_map_transparent_try_emplace,
2181	((test_trans_map)))
2182
2183	UNORDERED_TEST(test_map_transparent_insert_or_assign,
2184	((test_trans_map)))
2185
2186	UNORDERED_TEST(test_map_transparent_subscript,
2187	((test_trans_map)))
2188
2189	UNORDERED_TEST(test_map_transparent_at,
2190	((test_trans_map)))
2191
2192	UNORDERED_TEST(test_map_transparent_bucket,
2193	((test_trans_map)(test_trans_multimap)))
2194
2195	UNORDERED_TEST(test_map_non_transparent_count,
2196	((test_map1)(test_map2)(test_map3)
2197	(test_multimap1)(test_multimap2)(test_multimap3)))
2198
2199	UNORDERED_TEST(test_map_non_transparent_find,
2200	((test_map1)(test_map2)(test_map3)
2201	(test_multimap1)(test_multimap2)(test_multimap3)))
2202
2203	UNORDERED_TEST(test_map_non_transparent_equal_range,
2204	((test_map1)(test_map2)(test_map3)
2205	(test_multimap1)(test_multimap2)(test_multimap3)))
2206
2207	UNORDERED_TEST(test_map_non_transparent_erase,
2208	((test_map1)(test_map2)(test_map3)
2209	(test_multimap1)(test_multimap2)(test_multimap3)))
2210
2211	UNORDERED_TEST(test_map_non_transparent_extract,
2212	((test_map1)(test_map2)(test_map3)
2213	(test_multimap1)(test_multimap2)(test_multimap3)))
2214
2215	UNORDERED_TEST(test_map_non_transparent_try_emplace,
2216	((test_map1)(test_map2)(test_map3)))
2217
2218	UNORDERED_TEST(test_map_non_transparent_insert_or_assign,
2219	((test_map1)(test_map2)(test_map3)))
2220
2221	UNORDERED_TEST(test_map_non_transparent_subscript,
2222	((test_map1)(test_map2)(test_map3)))
2223
2224	UNORDERED_TEST(test_map_non_transparent_at,
2225	((test_map1)(test_map2)(test_map3)))
2226
2227	UNORDERED_TEST(test_map_non_transparent_bucket,
2228	((test_map1)(test_map2)(test_map3)
2229	(test_multimap1)(test_multimap2)(test_multimap3)))
2230	// clang-format on
2231	#endif
2232
2233	#ifdef BOOST_UNORDERED_FOA_TESTS
2234	static boost::unordered_flat_set<key, transparent_hasher,
2235	transparent_key_equal>* test_trans_set;
2236	static boost::unordered_node_set<key, transparent_hasher,
2237	transparent_key_equal>* test_trans_node_set;
2238
2239	static boost::unordered_flat_set<key, hasher, key_equal>* test_set1;
2240	static boost::unordered_flat_set<key, transparent_hasher, key_equal>* test_set2;
2241	static boost::unordered_flat_set<key, hasher, transparent_key_equal>* test_set3;
2242	static boost::unordered_node_set<key, hasher, key_equal>* test_node_set1;
2243	static boost::unordered_node_set<key, transparent_hasher, key_equal>*
2244	test_node_set2;
2245	static boost::unordered_node_set<key, hasher, transparent_key_equal>*
2246	test_node_set3;
2247
2248	// clang-format off
2249	UNORDERED_TEST(test_set_transparent_count,
2250	((test_trans_set)(test_trans_node_set)))
2251
2252	UNORDERED_TEST(test_set_transparent_find,
2253	((test_trans_set)(test_trans_node_set)))
2254
2255	UNORDERED_TEST(test_set_transparent_erase,
2256	((test_trans_set)(test_trans_node_set)))
2257
2258	UNORDERED_TEST(test_set_transparent_equal_range,
2259	((test_trans_set)(test_trans_node_set)))
2260
2261	UNORDERED_TEST(test_set_transparent_extract,
2262	((test_trans_node_set)))
2263
2264	UNORDERED_TEST(test_set_transparent_bucket,
2265	((test_trans_set)(test_trans_node_set)))
2266
2267	UNORDERED_TEST(test_set_transparent_insert,
2268	((test_trans_set)(test_trans_node_set)))
2269
2270	UNORDERED_TEST(test_set_non_transparent_count,
2271	((test_set1)(test_set2)(test_set3)
2272	(test_node_set1)(test_node_set2)(test_node_set3)))
2273
2274	UNORDERED_TEST(test_set_non_transparent_find,
2275	((test_set1)(test_set2)(test_set3)
2276	(test_node_set1)(test_node_set2)(test_node_set3)))
2277
2278	UNORDERED_TEST(test_set_non_transparent_erase,
2279	((test_set1)(test_set2)(test_set3)
2280	(test_node_set1)(test_node_set2)(test_node_set3)))
2281
2282	UNORDERED_TEST(test_set_non_transparent_equal_range,
2283	((test_set1)(test_set2)(test_set3)
2284	(test_node_set1)(test_node_set2)(test_node_set3)))
2285
2286	UNORDERED_TEST(test_set_non_transparent_extract,
2287	((test_node_set1)(test_node_set2)(test_node_set3)))
2288
2289	UNORDERED_TEST(test_set_non_transparent_bucket,
2290	((test_set1)(test_set2)(test_set3)
2291	(test_node_set1)(test_node_set2)(test_node_set3)))
2292
2293	UNORDERED_TEST(test_set_non_transparent_insert,
2294	((test_set1)(test_set2)(test_set3)
2295	(test_node_set1)(test_node_set2)(test_node_set3)))
2296	// clang-format on
2297	#else
2298	static boost::unordered_set<key, transparent_hasher, transparent_key_equal>*
2299	test_trans_set;
2300	static boost::unordered_multiset<key, transparent_hasher,
2301	transparent_key_equal>* test_trans_multiset;
2302
2303	static boost::unordered_set<key, hasher, key_equal>* test_set1;
2304	static boost::unordered_set<key, transparent_hasher, key_equal>* test_set2;
2305	static boost::unordered_set<key, hasher, transparent_key_equal>* test_set3;
2306	static boost::unordered_multiset<key, hasher, key_equal>* test_multiset1;
2307	static boost::unordered_multiset<key, transparent_hasher, key_equal>*
2308	test_multiset2;
2309	static boost::unordered_multiset<key, hasher, transparent_key_equal>*
2310	test_multiset3;
2311
2312	// clang-format off
2313	UNORDERED_TEST(test_set_transparent_count,
2314	((test_trans_set)(test_trans_multiset)))
2315
2316	UNORDERED_TEST(test_set_transparent_find,
2317	((test_trans_set)(test_trans_multiset)))
2318
2319	UNORDERED_TEST(test_set_transparent_erase,
2320	((test_trans_set)(test_trans_multiset)))
2321
2322	UNORDERED_TEST(test_set_transparent_equal_range,
2323	((test_trans_set)(test_trans_multiset)))
2324
2325	UNORDERED_TEST(test_set_transparent_extract,
2326	((test_trans_set)(test_trans_multiset)))
2327
2328	UNORDERED_TEST(test_set_transparent_bucket,
2329	((test_trans_set)(test_trans_multiset)))
2330
2331	UNORDERED_TEST(test_set_transparent_insert,
2332	((test_trans_set)))
2333
2334	UNORDERED_TEST(test_set_non_transparent_count,
2335	((test_set1)(test_set2)(test_set3)
2336	(test_multiset1)(test_multiset2)(test_multiset3)))
2337
2338	UNORDERED_TEST(test_set_non_transparent_find,
2339	((test_set1)(test_set2)(test_set3)
2340	(test_multiset1)(test_multiset2)(test_multiset3)))
2341
2342	UNORDERED_TEST(test_set_non_transparent_erase,
2343	((test_set1)(test_set2)(test_set3)
2344	(test_multiset1)(test_multiset2)(test_multiset3)))
2345
2346	UNORDERED_TEST(test_set_non_transparent_equal_range,
2347	((test_set1)(test_set2)(test_set3)
2348	(test_multiset1)(test_multiset2)(test_multiset3)))
2349
2350	UNORDERED_TEST(test_set_non_transparent_extract,
2351	((test_set1)(test_set2)(test_set3)
2352	(test_multiset1)(test_multiset2)(test_multiset3)))
2353
2354	UNORDERED_TEST(test_set_non_transparent_bucket,
2355	((test_set1)(test_set2)(test_set3)
2356	(test_multiset1)(test_multiset2)(test_multiset3)))
2357
2358	UNORDERED_TEST(test_set_non_transparent_insert,
2359	((test_set1)(test_set2)(test_set3)))
2360	// clang-format on
2361	#endif
2362
2363	RUN_TESTS()
2364