1//===----------------------------------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is dual licensed under the MIT and the University of Illinois Open
6// Source Licenses. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10// <unordered_set>
11
12// template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
13//           class Alloc = allocator<Value>>
14// class unordered_multiset
15
16// local_iterator       begin (size_type n);
17// local_iterator       end   (size_type n);
18// const_local_iterator begin (size_type n) const;
19// const_local_iterator end   (size_type n) const;
20// const_local_iterator cbegin(size_type n) const;
21// const_local_iterator cend  (size_type n) const;
22
23#include <unordered_set>
24#include <cassert>
25
26#include "min_allocator.h"
27
28int main()
29{
30    {
31        typedef std::unordered_multiset<int> C;
32        typedef int P;
33        typedef C::local_iterator I;
34        P a[] =
35        {
36            P(1),
37            P(2),
38            P(3),
39            P(4),
40            P(1),
41            P(2)
42        };
43        C c(a, a + sizeof(a)/sizeof(a[0]));
44        assert(c.bucket_count() >= 7);
45        C::size_type b = c.bucket(0);
46        I i = c.begin(b);
47        I j = c.end(b);
48        assert(std::distance(i, j) == 0);
49
50        b = c.bucket(1);
51        i = c.begin(b);
52        j = c.end(b);
53        assert(std::distance(i, j) == 2);
54        assert(*i == 1);
55        ++i;
56        assert(*i == 1);
57
58        b = c.bucket(2);
59        i = c.begin(b);
60        j = c.end(b);
61        assert(std::distance(i, j) == 2);
62        assert(*i == 2);
63        ++i;
64        assert(*i == 2);
65
66        b = c.bucket(3);
67        i = c.begin(b);
68        j = c.end(b);
69        assert(std::distance(i, j) == 1);
70        assert(*i == 3);
71
72        b = c.bucket(4);
73        i = c.begin(b);
74        j = c.end(b);
75        assert(std::distance(i, j) == 1);
76        assert(*i == 4);
77
78        b = c.bucket(5);
79        i = c.begin(b);
80        j = c.end(b);
81        assert(std::distance(i, j) == 0);
82
83        b = c.bucket(6);
84        i = c.begin(b);
85        j = c.end(b);
86        assert(std::distance(i, j) == 0);
87    }
88    {
89        typedef std::unordered_multiset<int> C;
90        typedef int P;
91        typedef C::const_local_iterator I;
92        P a[] =
93        {
94            P(1),
95            P(2),
96            P(3),
97            P(4),
98            P(1),
99            P(2)
100        };
101        const C c(a, a + sizeof(a)/sizeof(a[0]));
102        assert(c.bucket_count() >= 7);
103        C::size_type b = c.bucket(0);
104        I i = c.begin(b);
105        I j = c.end(b);
106        assert(std::distance(i, j) == 0);
107
108        b = c.bucket(1);
109        i = c.begin(b);
110        j = c.end(b);
111        assert(std::distance(i, j) == 2);
112        assert(*i == 1);
113        ++i;
114        assert(*i == 1);
115
116        b = c.bucket(2);
117        i = c.begin(b);
118        j = c.end(b);
119        assert(std::distance(i, j) == 2);
120        assert(*i == 2);
121        ++i;
122        assert(*i == 2);
123
124        b = c.bucket(3);
125        i = c.begin(b);
126        j = c.end(b);
127        assert(std::distance(i, j) == 1);
128        assert(*i == 3);
129
130        b = c.bucket(4);
131        i = c.begin(b);
132        j = c.end(b);
133        assert(std::distance(i, j) == 1);
134        assert(*i == 4);
135
136        b = c.bucket(5);
137        i = c.begin(b);
138        j = c.end(b);
139        assert(std::distance(i, j) == 0);
140
141        b = c.bucket(6);
142        i = c.begin(b);
143        j = c.end(b);
144        assert(std::distance(i, j) == 0);
145    }
146    {
147        typedef std::unordered_multiset<int> C;
148        typedef int P;
149        typedef C::const_local_iterator I;
150        P a[] =
151        {
152            P(1),
153            P(2),
154            P(3),
155            P(4),
156            P(1),
157            P(2)
158        };
159        C c(a, a + sizeof(a)/sizeof(a[0]));
160        assert(c.bucket_count() >= 7);
161        C::size_type b = c.bucket(0);
162        I i = c.cbegin(b);
163        I j = c.cend(b);
164        assert(std::distance(i, j) == 0);
165
166        b = c.bucket(1);
167        i = c.cbegin(b);
168        j = c.cend(b);
169        assert(std::distance(i, j) == 2);
170        assert(*i == 1);
171        ++i;
172        assert(*i == 1);
173
174        b = c.bucket(2);
175        i = c.cbegin(b);
176        j = c.cend(b);
177        assert(std::distance(i, j) == 2);
178        assert(*i == 2);
179        ++i;
180        assert(*i == 2);
181
182        b = c.bucket(3);
183        i = c.cbegin(b);
184        j = c.cend(b);
185        assert(std::distance(i, j) == 1);
186        assert(*i == 3);
187
188        b = c.bucket(4);
189        i = c.cbegin(b);
190        j = c.cend(b);
191        assert(std::distance(i, j) == 1);
192        assert(*i == 4);
193
194        b = c.bucket(5);
195        i = c.cbegin(b);
196        j = c.cend(b);
197        assert(std::distance(i, j) == 0);
198
199        b = c.bucket(6);
200        i = c.cbegin(b);
201        j = c.cend(b);
202        assert(std::distance(i, j) == 0);
203    }
204    {
205        typedef std::unordered_multiset<int> C;
206        typedef int P;
207        typedef C::const_local_iterator I;
208        P a[] =
209        {
210            P(1),
211            P(2),
212            P(3),
213            P(4),
214            P(1),
215            P(2)
216        };
217        const C c(a, a + sizeof(a)/sizeof(a[0]));
218        assert(c.bucket_count() >= 7);
219        C::size_type b = c.bucket(0);
220        I i = c.cbegin(b);
221        I j = c.cend(b);
222        assert(std::distance(i, j) == 0);
223
224        b = c.bucket(1);
225        i = c.cbegin(b);
226        j = c.cend(b);
227        assert(std::distance(i, j) == 2);
228        assert(*i == 1);
229        ++i;
230        assert(*i == 1);
231
232        b = c.bucket(2);
233        i = c.cbegin(b);
234        j = c.cend(b);
235        assert(std::distance(i, j) == 2);
236        assert(*i == 2);
237        ++i;
238        assert(*i == 2);
239
240        b = c.bucket(3);
241        i = c.cbegin(b);
242        j = c.cend(b);
243        assert(std::distance(i, j) == 1);
244        assert(*i == 3);
245
246        b = c.bucket(4);
247        i = c.cbegin(b);
248        j = c.cend(b);
249        assert(std::distance(i, j) == 1);
250        assert(*i == 4);
251
252        b = c.bucket(5);
253        i = c.cbegin(b);
254        j = c.cend(b);
255        assert(std::distance(i, j) == 0);
256
257        b = c.bucket(6);
258        i = c.cbegin(b);
259        j = c.cend(b);
260        assert(std::distance(i, j) == 0);
261    }
262#if TEST_STD_VER >= 11
263    {
264        typedef std::unordered_multiset<int, std::hash<int>,
265                                      std::equal_to<int>, min_allocator<int>> C;
266        typedef int P;
267        typedef C::local_iterator I;
268        P a[] =
269        {
270            P(1),
271            P(2),
272            P(3),
273            P(4),
274            P(1),
275            P(2)
276        };
277        C c(a, a + sizeof(a)/sizeof(a[0]));
278        assert(c.bucket_count() >= 7);
279        C::size_type b = c.bucket(0);
280        I i = c.begin(b);
281        I j = c.end(b);
282        assert(std::distance(i, j) == 0);
283
284        b = c.bucket(1);
285        i = c.begin(b);
286        j = c.end(b);
287        assert(std::distance(i, j) == 2);
288        assert(*i == 1);
289        ++i;
290        assert(*i == 1);
291
292        b = c.bucket(2);
293        i = c.begin(b);
294        j = c.end(b);
295        assert(std::distance(i, j) == 2);
296        assert(*i == 2);
297        ++i;
298        assert(*i == 2);
299
300        b = c.bucket(3);
301        i = c.begin(b);
302        j = c.end(b);
303        assert(std::distance(i, j) == 1);
304        assert(*i == 3);
305
306        b = c.bucket(4);
307        i = c.begin(b);
308        j = c.end(b);
309        assert(std::distance(i, j) == 1);
310        assert(*i == 4);
311
312        b = c.bucket(5);
313        i = c.begin(b);
314        j = c.end(b);
315        assert(std::distance(i, j) == 0);
316
317        b = c.bucket(6);
318        i = c.begin(b);
319        j = c.end(b);
320        assert(std::distance(i, j) == 0);
321    }
322    {
323        typedef std::unordered_multiset<int, std::hash<int>,
324                                      std::equal_to<int>, min_allocator<int>> C;
325        typedef int P;
326        typedef C::const_local_iterator I;
327        P a[] =
328        {
329            P(1),
330            P(2),
331            P(3),
332            P(4),
333            P(1),
334            P(2)
335        };
336        const C c(a, a + sizeof(a)/sizeof(a[0]));
337        assert(c.bucket_count() >= 7);
338        C::size_type b = c.bucket(0);
339        I i = c.begin(b);
340        I j = c.end(b);
341        assert(std::distance(i, j) == 0);
342
343        b = c.bucket(1);
344        i = c.begin(b);
345        j = c.end(b);
346        assert(std::distance(i, j) == 2);
347        assert(*i == 1);
348        ++i;
349        assert(*i == 1);
350
351        b = c.bucket(2);
352        i = c.begin(b);
353        j = c.end(b);
354        assert(std::distance(i, j) == 2);
355        assert(*i == 2);
356        ++i;
357        assert(*i == 2);
358
359        b = c.bucket(3);
360        i = c.begin(b);
361        j = c.end(b);
362        assert(std::distance(i, j) == 1);
363        assert(*i == 3);
364
365        b = c.bucket(4);
366        i = c.begin(b);
367        j = c.end(b);
368        assert(std::distance(i, j) == 1);
369        assert(*i == 4);
370
371        b = c.bucket(5);
372        i = c.begin(b);
373        j = c.end(b);
374        assert(std::distance(i, j) == 0);
375
376        b = c.bucket(6);
377        i = c.begin(b);
378        j = c.end(b);
379        assert(std::distance(i, j) == 0);
380    }
381    {
382        typedef std::unordered_multiset<int, std::hash<int>,
383                                      std::equal_to<int>, min_allocator<int>> C;
384        typedef int P;
385        typedef C::const_local_iterator I;
386        P a[] =
387        {
388            P(1),
389            P(2),
390            P(3),
391            P(4),
392            P(1),
393            P(2)
394        };
395        C c(a, a + sizeof(a)/sizeof(a[0]));
396        assert(c.bucket_count() >= 7);
397        C::size_type b = c.bucket(0);
398        I i = c.cbegin(b);
399        I j = c.cend(b);
400        assert(std::distance(i, j) == 0);
401
402        b = c.bucket(1);
403        i = c.cbegin(b);
404        j = c.cend(b);
405        assert(std::distance(i, j) == 2);
406        assert(*i == 1);
407        ++i;
408        assert(*i == 1);
409
410        b = c.bucket(2);
411        i = c.cbegin(b);
412        j = c.cend(b);
413        assert(std::distance(i, j) == 2);
414        assert(*i == 2);
415        ++i;
416        assert(*i == 2);
417
418        b = c.bucket(3);
419        i = c.cbegin(b);
420        j = c.cend(b);
421        assert(std::distance(i, j) == 1);
422        assert(*i == 3);
423
424        b = c.bucket(4);
425        i = c.cbegin(b);
426        j = c.cend(b);
427        assert(std::distance(i, j) == 1);
428        assert(*i == 4);
429
430        b = c.bucket(5);
431        i = c.cbegin(b);
432        j = c.cend(b);
433        assert(std::distance(i, j) == 0);
434
435        b = c.bucket(6);
436        i = c.cbegin(b);
437        j = c.cend(b);
438        assert(std::distance(i, j) == 0);
439    }
440    {
441        typedef std::unordered_multiset<int, std::hash<int>,
442                                      std::equal_to<int>, min_allocator<int>> C;
443        typedef int P;
444        typedef C::const_local_iterator I;
445        P a[] =
446        {
447            P(1),
448            P(2),
449            P(3),
450            P(4),
451            P(1),
452            P(2)
453        };
454        const C c(a, a + sizeof(a)/sizeof(a[0]));
455        assert(c.bucket_count() >= 7);
456        C::size_type b = c.bucket(0);
457        I i = c.cbegin(b);
458        I j = c.cend(b);
459        assert(std::distance(i, j) == 0);
460
461        b = c.bucket(1);
462        i = c.cbegin(b);
463        j = c.cend(b);
464        assert(std::distance(i, j) == 2);
465        assert(*i == 1);
466        ++i;
467        assert(*i == 1);
468
469        b = c.bucket(2);
470        i = c.cbegin(b);
471        j = c.cend(b);
472        assert(std::distance(i, j) == 2);
473        assert(*i == 2);
474        ++i;
475        assert(*i == 2);
476
477        b = c.bucket(3);
478        i = c.cbegin(b);
479        j = c.cend(b);
480        assert(std::distance(i, j) == 1);
481        assert(*i == 3);
482
483        b = c.bucket(4);
484        i = c.cbegin(b);
485        j = c.cend(b);
486        assert(std::distance(i, j) == 1);
487        assert(*i == 4);
488
489        b = c.bucket(5);
490        i = c.cbegin(b);
491        j = c.cend(b);
492        assert(std::distance(i, j) == 0);
493
494        b = c.bucket(6);
495        i = c.cbegin(b);
496        j = c.cend(b);
497        assert(std::distance(i, j) == 0);
498    }
499#endif
500}
501