1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // <unordered_map>
10
11 // template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
12 // class Alloc = allocator<pair<const Key, T>>>
13 // class unordered_multimap
14
15 // local_iterator begin (size_type n);
16 // local_iterator end (size_type n);
17 // const_local_iterator begin (size_type n) const;
18 // const_local_iterator end (size_type n) const;
19 // const_local_iterator cbegin(size_type n) const;
20 // const_local_iterator cend (size_type n) const;
21
22 #include <unordered_map>
23 #include <string>
24 #include <set>
25 #include <cassert>
26
27 #include "test_macros.h"
28 #include "min_allocator.h"
29
main(int,char **)30 int main(int, char**)
31 {
32 {
33 typedef std::unordered_multimap<int, std::string> C;
34 typedef std::pair<int, std::string> P;
35 typedef C::local_iterator I;
36 P a[] =
37 {
38 P(1, "one"),
39 P(2, "two"),
40 P(3, "three"),
41 P(4, "four"),
42 P(1, "four"),
43 P(2, "four"),
44 };
45 C c(a, a + sizeof(a)/sizeof(a[0]));
46 assert(c.bucket_count() >= 7);
47 C::size_type b = c.bucket(0);
48 I i = c.begin(b);
49 I j = c.end(b);
50 assert(std::distance(i, j) == 0);
51
52 b = c.bucket(1);
53 i = c.begin(b);
54 j = c.end(b);
55 assert(std::distance(i, j) == 2);
56 {
57 std::set<std::string> s;
58 s.insert("one");
59 s.insert("four");
60 for ( int n = 0; n < 2; ++n )
61 {
62 assert(i->first == 1);
63 assert(s.find(i->second) != s.end());
64 s.erase(s.find(i->second));
65 ++i;
66 }
67 }
68
69 b = c.bucket(2);
70 i = c.begin(b);
71 j = c.end(b);
72 assert(std::distance(i, j) == 2);
73 {
74 std::set<std::string> s;
75 s.insert("two");
76 s.insert("four");
77 for ( int n = 0; n < 2; ++n )
78 {
79 assert(i->first == 2);
80 assert(s.find(i->second) != s.end());
81 s.erase(s.find(i->second));
82 ++i;
83 }
84 }
85
86 b = c.bucket(3);
87 i = c.begin(b);
88 j = c.end(b);
89 assert(std::distance(i, j) == 1);
90 assert(i->first == 3);
91 assert(i->second == "three");
92
93 b = c.bucket(4);
94 i = c.begin(b);
95 j = c.end(b);
96 assert(std::distance(i, j) == 1);
97 assert(i->first == 4);
98 assert(i->second == "four");
99
100 b = c.bucket(5);
101 i = c.begin(b);
102 j = c.end(b);
103 assert(std::distance(i, j) == 0);
104
105 b = c.bucket(6);
106 i = c.begin(b);
107 j = c.end(b);
108 assert(std::distance(i, j) == 0);
109 }
110 {
111 typedef std::unordered_multimap<int, std::string> C;
112 typedef std::pair<int, std::string> P;
113 typedef C::const_local_iterator I;
114 P a[] =
115 {
116 P(1, "one"),
117 P(2, "two"),
118 P(3, "three"),
119 P(4, "four"),
120 P(1, "four"),
121 P(2, "four"),
122 };
123 const C c(a, a + sizeof(a)/sizeof(a[0]));
124 assert(c.bucket_count() >= 7);
125 C::size_type b = c.bucket(0);
126 I i = c.begin(b);
127 I j = c.end(b);
128 assert(std::distance(i, j) == 0);
129
130 b = c.bucket(1);
131 i = c.begin(b);
132 j = c.end(b);
133 assert(std::distance(i, j) == 2);
134 {
135 std::set<std::string> s;
136 s.insert("one");
137 s.insert("four");
138 for ( int n = 0; n < 2; ++n )
139 {
140 assert(i->first == 1);
141 assert(s.find(i->second) != s.end());
142 s.erase(s.find(i->second));
143 ++i;
144 }
145 }
146
147 b = c.bucket(2);
148 i = c.begin(b);
149 j = c.end(b);
150 assert(std::distance(i, j) == 2);
151 {
152 std::set<std::string> s;
153 s.insert("two");
154 s.insert("four");
155 for ( int n = 0; n < 2; ++n )
156 {
157 assert(i->first == 2);
158 assert(s.find(i->second) != s.end());
159 s.erase(s.find(i->second));
160 ++i;
161 }
162 }
163
164 b = c.bucket(3);
165 i = c.begin(b);
166 j = c.end(b);
167 assert(std::distance(i, j) == 1);
168 assert(i->first == 3);
169 assert(i->second == "three");
170
171 b = c.bucket(4);
172 i = c.begin(b);
173 j = c.end(b);
174 assert(std::distance(i, j) == 1);
175 assert(i->first == 4);
176 assert(i->second == "four");
177
178 b = c.bucket(5);
179 i = c.begin(b);
180 j = c.end(b);
181 assert(std::distance(i, j) == 0);
182
183 b = c.bucket(6);
184 i = c.begin(b);
185 j = c.end(b);
186 assert(std::distance(i, j) == 0);
187 }
188 {
189 typedef std::unordered_multimap<int, std::string> C;
190 typedef std::pair<int, std::string> P;
191 typedef C::const_local_iterator I;
192 P a[] =
193 {
194 P(1, "one"),
195 P(2, "two"),
196 P(3, "three"),
197 P(4, "four"),
198 P(1, "four"),
199 P(2, "four"),
200 };
201 C c(a, a + sizeof(a)/sizeof(a[0]));
202 assert(c.bucket_count() >= 7);
203 C::size_type b = c.bucket(0);
204 I i = c.cbegin(b);
205 I j = c.cend(b);
206 assert(std::distance(i, j) == 0);
207
208 b = c.bucket(1);
209 i = c.cbegin(b);
210 j = c.cend(b);
211 assert(std::distance(i, j) == 2);
212 {
213 std::set<std::string> s;
214 s.insert("one");
215 s.insert("four");
216 for ( int n = 0; n < 2; ++n )
217 {
218 assert(i->first == 1);
219 assert(s.find(i->second) != s.end());
220 s.erase(s.find(i->second));
221 ++i;
222 }
223 }
224
225 b = c.bucket(2);
226 i = c.cbegin(b);
227 j = c.cend(b);
228 assert(std::distance(i, j) == 2);
229 {
230 std::set<std::string> s;
231 s.insert("two");
232 s.insert("four");
233 for ( int n = 0; n < 2; ++n )
234 {
235 assert(i->first == 2);
236 assert(s.find(i->second) != s.end());
237 s.erase(s.find(i->second));
238 ++i;
239 }
240 }
241
242 b = c.bucket(3);
243 i = c.cbegin(b);
244 j = c.cend(b);
245 assert(std::distance(i, j) == 1);
246 assert(i->first == 3);
247 assert(i->second == "three");
248
249 b = c.bucket(4);
250 i = c.cbegin(b);
251 j = c.cend(b);
252 assert(std::distance(i, j) == 1);
253 assert(i->first == 4);
254 assert(i->second == "four");
255
256 b = c.bucket(5);
257 i = c.cbegin(b);
258 j = c.cend(b);
259 assert(std::distance(i, j) == 0);
260
261 b = c.bucket(6);
262 i = c.cbegin(b);
263 j = c.cend(b);
264 assert(std::distance(i, j) == 0);
265 }
266 {
267 typedef std::unordered_multimap<int, std::string> C;
268 typedef std::pair<int, std::string> P;
269 typedef C::const_local_iterator I;
270 P a[] =
271 {
272 P(1, "one"),
273 P(2, "two"),
274 P(3, "three"),
275 P(4, "four"),
276 P(1, "four"),
277 P(2, "four"),
278 };
279 const C c(a, a + sizeof(a)/sizeof(a[0]));
280 assert(c.bucket_count() >= 7);
281 C::size_type b = c.bucket(0);
282 I i = c.cbegin(b);
283 I j = c.cend(b);
284 assert(std::distance(i, j) == 0);
285
286 b = c.bucket(1);
287 i = c.cbegin(b);
288 j = c.cend(b);
289 assert(std::distance(i, j) == 2);
290 {
291 std::set<std::string> s;
292 s.insert("one");
293 s.insert("four");
294 for ( int n = 0; n < 2; ++n )
295 {
296 assert(i->first == 1);
297 assert(s.find(i->second) != s.end());
298 s.erase(s.find(i->second));
299 ++i;
300 }
301 }
302
303 b = c.bucket(2);
304 i = c.cbegin(b);
305 j = c.cend(b);
306 assert(std::distance(i, j) == 2);
307 {
308 std::set<std::string> s;
309 s.insert("two");
310 s.insert("four");
311 for ( int n = 0; n < 2; ++n )
312 {
313 assert(i->first == 2);
314 assert(s.find(i->second) != s.end());
315 s.erase(s.find(i->second));
316 ++i;
317 }
318 }
319
320 b = c.bucket(3);
321 i = c.cbegin(b);
322 j = c.cend(b);
323 assert(std::distance(i, j) == 1);
324 assert(i->first == 3);
325 assert(i->second == "three");
326
327 b = c.bucket(4);
328 i = c.cbegin(b);
329 j = c.cend(b);
330 assert(std::distance(i, j) == 1);
331 assert(i->first == 4);
332 assert(i->second == "four");
333
334 b = c.bucket(5);
335 i = c.cbegin(b);
336 j = c.cend(b);
337 assert(std::distance(i, j) == 0);
338
339 b = c.bucket(6);
340 i = c.cbegin(b);
341 j = c.cend(b);
342 assert(std::distance(i, j) == 0);
343 }
344 #if TEST_STD_VER >= 11
345 {
346 typedef std::unordered_multimap<int, std::string, std::hash<int>, std::equal_to<int>,
347 min_allocator<std::pair<const int, std::string>>> C;
348 typedef std::pair<int, std::string> P;
349 typedef C::local_iterator I;
350 P a[] =
351 {
352 P(1, "one"),
353 P(2, "two"),
354 P(3, "three"),
355 P(4, "four"),
356 P(1, "four"),
357 P(2, "four"),
358 };
359 C c(a, a + sizeof(a)/sizeof(a[0]));
360 assert(c.bucket_count() >= 7);
361 C::size_type b = c.bucket(0);
362 I i = c.begin(b);
363 I j = c.end(b);
364 assert(std::distance(i, j) == 0);
365
366 b = c.bucket(1);
367 i = c.begin(b);
368 j = c.end(b);
369 assert(std::distance(i, j) == 2);
370 {
371 std::set<std::string> s;
372 s.insert("one");
373 s.insert("four");
374 for ( int n = 0; n < 2; ++n )
375 {
376 assert(i->first == 1);
377 assert(s.find(i->second) != s.end());
378 s.erase(s.find(i->second));
379 ++i;
380 }
381 }
382
383 b = c.bucket(2);
384 i = c.begin(b);
385 j = c.end(b);
386 assert(std::distance(i, j) == 2);
387 {
388 std::set<std::string> s;
389 s.insert("two");
390 s.insert("four");
391 for ( int n = 0; n < 2; ++n )
392 {
393 assert(i->first == 2);
394 assert(s.find(i->second) != s.end());
395 s.erase(s.find(i->second));
396 ++i;
397 }
398 }
399
400 b = c.bucket(3);
401 i = c.begin(b);
402 j = c.end(b);
403 assert(std::distance(i, j) == 1);
404 assert(i->first == 3);
405 assert(i->second == "three");
406
407 b = c.bucket(4);
408 i = c.begin(b);
409 j = c.end(b);
410 assert(std::distance(i, j) == 1);
411 assert(i->first == 4);
412 assert(i->second == "four");
413
414 b = c.bucket(5);
415 i = c.begin(b);
416 j = c.end(b);
417 assert(std::distance(i, j) == 0);
418
419 b = c.bucket(6);
420 i = c.begin(b);
421 j = c.end(b);
422 assert(std::distance(i, j) == 0);
423 }
424 {
425 typedef std::unordered_multimap<int, std::string, std::hash<int>, std::equal_to<int>,
426 min_allocator<std::pair<const int, std::string>>> C;
427 typedef std::pair<int, std::string> P;
428 typedef C::const_local_iterator I;
429 P a[] =
430 {
431 P(1, "one"),
432 P(2, "two"),
433 P(3, "three"),
434 P(4, "four"),
435 P(1, "four"),
436 P(2, "four"),
437 };
438 const C c(a, a + sizeof(a)/sizeof(a[0]));
439 assert(c.bucket_count() >= 7);
440 C::size_type b = c.bucket(0);
441 I i = c.begin(b);
442 I j = c.end(b);
443 assert(std::distance(i, j) == 0);
444
445 b = c.bucket(1);
446 i = c.begin(b);
447 j = c.end(b);
448 assert(std::distance(i, j) == 2);
449 {
450 std::set<std::string> s;
451 s.insert("one");
452 s.insert("four");
453 for ( int n = 0; n < 2; ++n )
454 {
455 assert(i->first == 1);
456 assert(s.find(i->second) != s.end());
457 s.erase(s.find(i->second));
458 ++i;
459 }
460 }
461
462 b = c.bucket(2);
463 i = c.begin(b);
464 j = c.end(b);
465 assert(std::distance(i, j) == 2);
466 {
467 std::set<std::string> s;
468 s.insert("two");
469 s.insert("four");
470 for ( int n = 0; n < 2; ++n )
471 {
472 assert(i->first == 2);
473 assert(s.find(i->second) != s.end());
474 s.erase(s.find(i->second));
475 ++i;
476 }
477 }
478
479 b = c.bucket(3);
480 i = c.begin(b);
481 j = c.end(b);
482 assert(std::distance(i, j) == 1);
483 assert(i->first == 3);
484 assert(i->second == "three");
485
486 b = c.bucket(4);
487 i = c.begin(b);
488 j = c.end(b);
489 assert(std::distance(i, j) == 1);
490 assert(i->first == 4);
491 assert(i->second == "four");
492
493 b = c.bucket(5);
494 i = c.begin(b);
495 j = c.end(b);
496 assert(std::distance(i, j) == 0);
497
498 b = c.bucket(6);
499 i = c.begin(b);
500 j = c.end(b);
501 assert(std::distance(i, j) == 0);
502 }
503 {
504 typedef std::unordered_multimap<int, std::string, std::hash<int>, std::equal_to<int>,
505 min_allocator<std::pair<const int, std::string>>> C;
506 typedef std::pair<int, std::string> P;
507 typedef C::const_local_iterator I;
508 P a[] =
509 {
510 P(1, "one"),
511 P(2, "two"),
512 P(3, "three"),
513 P(4, "four"),
514 P(1, "four"),
515 P(2, "four"),
516 };
517 C c(a, a + sizeof(a)/sizeof(a[0]));
518 assert(c.bucket_count() >= 7);
519 C::size_type b = c.bucket(0);
520 I i = c.cbegin(b);
521 I j = c.cend(b);
522 assert(std::distance(i, j) == 0);
523
524 b = c.bucket(1);
525 i = c.cbegin(b);
526 j = c.cend(b);
527 assert(std::distance(i, j) == 2);
528 {
529 std::set<std::string> s;
530 s.insert("one");
531 s.insert("four");
532 for ( int n = 0; n < 2; ++n )
533 {
534 assert(i->first == 1);
535 assert(s.find(i->second) != s.end());
536 s.erase(s.find(i->second));
537 ++i;
538 }
539 }
540
541 b = c.bucket(2);
542 i = c.cbegin(b);
543 j = c.cend(b);
544 assert(std::distance(i, j) == 2);
545 {
546 std::set<std::string> s;
547 s.insert("two");
548 s.insert("four");
549 for ( int n = 0; n < 2; ++n )
550 {
551 assert(i->first == 2);
552 assert(s.find(i->second) != s.end());
553 s.erase(s.find(i->second));
554 ++i;
555 }
556 }
557
558 b = c.bucket(3);
559 i = c.cbegin(b);
560 j = c.cend(b);
561 assert(std::distance(i, j) == 1);
562 assert(i->first == 3);
563 assert(i->second == "three");
564
565 b = c.bucket(4);
566 i = c.cbegin(b);
567 j = c.cend(b);
568 assert(std::distance(i, j) == 1);
569 assert(i->first == 4);
570 assert(i->second == "four");
571
572 b = c.bucket(5);
573 i = c.cbegin(b);
574 j = c.cend(b);
575 assert(std::distance(i, j) == 0);
576
577 b = c.bucket(6);
578 i = c.cbegin(b);
579 j = c.cend(b);
580 assert(std::distance(i, j) == 0);
581 }
582 {
583 typedef std::unordered_multimap<int, std::string, std::hash<int>, std::equal_to<int>,
584 min_allocator<std::pair<const int, std::string>>> C;
585 typedef std::pair<int, std::string> P;
586 typedef C::const_local_iterator I;
587 P a[] =
588 {
589 P(1, "one"),
590 P(2, "two"),
591 P(3, "three"),
592 P(4, "four"),
593 P(1, "four"),
594 P(2, "four"),
595 };
596 const C c(a, a + sizeof(a)/sizeof(a[0]));
597 assert(c.bucket_count() >= 7);
598 C::size_type b = c.bucket(0);
599 I i = c.cbegin(b);
600 I j = c.cend(b);
601 assert(std::distance(i, j) == 0);
602
603 b = c.bucket(1);
604 i = c.cbegin(b);
605 j = c.cend(b);
606 assert(std::distance(i, j) == 2);
607 {
608 std::set<std::string> s;
609 s.insert("one");
610 s.insert("four");
611 for ( int n = 0; n < 2; ++n )
612 {
613 assert(i->first == 1);
614 assert(s.find(i->second) != s.end());
615 s.erase(s.find(i->second));
616 ++i;
617 }
618 }
619
620 b = c.bucket(2);
621 i = c.cbegin(b);
622 j = c.cend(b);
623 assert(std::distance(i, j) == 2);
624 {
625 std::set<std::string> s;
626 s.insert("two");
627 s.insert("four");
628 for ( int n = 0; n < 2; ++n )
629 {
630 assert(i->first == 2);
631 assert(s.find(i->second) != s.end());
632 s.erase(s.find(i->second));
633 ++i;
634 }
635 }
636
637 b = c.bucket(3);
638 i = c.cbegin(b);
639 j = c.cend(b);
640 assert(std::distance(i, j) == 1);
641 assert(i->first == 3);
642 assert(i->second == "three");
643
644 b = c.bucket(4);
645 i = c.cbegin(b);
646 j = c.cend(b);
647 assert(std::distance(i, j) == 1);
648 assert(i->first == 4);
649 assert(i->second == "four");
650
651 b = c.bucket(5);
652 i = c.cbegin(b);
653 j = c.cend(b);
654 assert(std::distance(i, j) == 0);
655
656 b = c.bucket(6);
657 i = c.cbegin(b);
658 j = c.cend(b);
659 assert(std::distance(i, j) == 0);
660 }
661 #endif
662
663 return 0;
664 }
665