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// <map>
11
12// class map
13
14// pair<iterator,iterator>             equal_range(const key_type& k);
15// pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
16
17#include <map>
18#include <cassert>
19
20#include "min_allocator.h"
21#include "private_constructor.hpp"
22
23int main()
24{
25    {
26    typedef std::pair<const int, double> V;
27    typedef std::map<int, double> M;
28    {
29        typedef std::pair<M::iterator, M::iterator> R;
30        V ar[] =
31        {
32            V(5, 5),
33            V(7, 6),
34            V(9, 7),
35            V(11, 8),
36            V(13, 9),
37            V(15, 10),
38            V(17, 11),
39            V(19, 12)
40        };
41        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
42        R r = m.equal_range(5);
43        assert(r.first == next(m.begin(), 0));
44        assert(r.second == next(m.begin(), 1));
45        r = m.equal_range(7);
46        assert(r.first == next(m.begin(), 1));
47        assert(r.second == next(m.begin(), 2));
48        r = m.equal_range(9);
49        assert(r.first == next(m.begin(), 2));
50        assert(r.second == next(m.begin(), 3));
51        r = m.equal_range(11);
52        assert(r.first == next(m.begin(), 3));
53        assert(r.second == next(m.begin(), 4));
54        r = m.equal_range(13);
55        assert(r.first == next(m.begin(), 4));
56        assert(r.second == next(m.begin(), 5));
57        r = m.equal_range(15);
58        assert(r.first == next(m.begin(), 5));
59        assert(r.second == next(m.begin(), 6));
60        r = m.equal_range(17);
61        assert(r.first == next(m.begin(), 6));
62        assert(r.second == next(m.begin(), 7));
63        r = m.equal_range(19);
64        assert(r.first == next(m.begin(), 7));
65        assert(r.second == next(m.begin(), 8));
66        r = m.equal_range(4);
67        assert(r.first == next(m.begin(), 0));
68        assert(r.second == next(m.begin(), 0));
69        r = m.equal_range(6);
70        assert(r.first == next(m.begin(), 1));
71        assert(r.second == next(m.begin(), 1));
72        r = m.equal_range(8);
73        assert(r.first == next(m.begin(), 2));
74        assert(r.second == next(m.begin(), 2));
75        r = m.equal_range(10);
76        assert(r.first == next(m.begin(), 3));
77        assert(r.second == next(m.begin(), 3));
78        r = m.equal_range(12);
79        assert(r.first == next(m.begin(), 4));
80        assert(r.second == next(m.begin(), 4));
81        r = m.equal_range(14);
82        assert(r.first == next(m.begin(), 5));
83        assert(r.second == next(m.begin(), 5));
84        r = m.equal_range(16);
85        assert(r.first == next(m.begin(), 6));
86        assert(r.second == next(m.begin(), 6));
87        r = m.equal_range(18);
88        assert(r.first == next(m.begin(), 7));
89        assert(r.second == next(m.begin(), 7));
90        r = m.equal_range(20);
91        assert(r.first == next(m.begin(), 8));
92        assert(r.second == next(m.begin(), 8));
93    }
94    {
95        typedef std::pair<M::const_iterator, M::const_iterator> R;
96        V ar[] =
97        {
98            V(5, 5),
99            V(7, 6),
100            V(9, 7),
101            V(11, 8),
102            V(13, 9),
103            V(15, 10),
104            V(17, 11),
105            V(19, 12)
106        };
107        const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
108        R r = m.equal_range(5);
109        assert(r.first == next(m.begin(), 0));
110        assert(r.second == next(m.begin(), 1));
111        r = m.equal_range(7);
112        assert(r.first == next(m.begin(), 1));
113        assert(r.second == next(m.begin(), 2));
114        r = m.equal_range(9);
115        assert(r.first == next(m.begin(), 2));
116        assert(r.second == next(m.begin(), 3));
117        r = m.equal_range(11);
118        assert(r.first == next(m.begin(), 3));
119        assert(r.second == next(m.begin(), 4));
120        r = m.equal_range(13);
121        assert(r.first == next(m.begin(), 4));
122        assert(r.second == next(m.begin(), 5));
123        r = m.equal_range(15);
124        assert(r.first == next(m.begin(), 5));
125        assert(r.second == next(m.begin(), 6));
126        r = m.equal_range(17);
127        assert(r.first == next(m.begin(), 6));
128        assert(r.second == next(m.begin(), 7));
129        r = m.equal_range(19);
130        assert(r.first == next(m.begin(), 7));
131        assert(r.second == next(m.begin(), 8));
132        r = m.equal_range(4);
133        assert(r.first == next(m.begin(), 0));
134        assert(r.second == next(m.begin(), 0));
135        r = m.equal_range(6);
136        assert(r.first == next(m.begin(), 1));
137        assert(r.second == next(m.begin(), 1));
138        r = m.equal_range(8);
139        assert(r.first == next(m.begin(), 2));
140        assert(r.second == next(m.begin(), 2));
141        r = m.equal_range(10);
142        assert(r.first == next(m.begin(), 3));
143        assert(r.second == next(m.begin(), 3));
144        r = m.equal_range(12);
145        assert(r.first == next(m.begin(), 4));
146        assert(r.second == next(m.begin(), 4));
147        r = m.equal_range(14);
148        assert(r.first == next(m.begin(), 5));
149        assert(r.second == next(m.begin(), 5));
150        r = m.equal_range(16);
151        assert(r.first == next(m.begin(), 6));
152        assert(r.second == next(m.begin(), 6));
153        r = m.equal_range(18);
154        assert(r.first == next(m.begin(), 7));
155        assert(r.second == next(m.begin(), 7));
156        r = m.equal_range(20);
157        assert(r.first == next(m.begin(), 8));
158        assert(r.second == next(m.begin(), 8));
159    }
160    }
161#if __cplusplus >= 201103L
162    {
163    typedef std::pair<const int, double> V;
164    typedef std::map<int, double, std::less<int>, min_allocator<V>> M;
165    {
166        typedef std::pair<M::iterator, M::iterator> R;
167        V ar[] =
168        {
169            V(5, 5),
170            V(7, 6),
171            V(9, 7),
172            V(11, 8),
173            V(13, 9),
174            V(15, 10),
175            V(17, 11),
176            V(19, 12)
177        };
178        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
179        R r = m.equal_range(5);
180        assert(r.first == next(m.begin(), 0));
181        assert(r.second == next(m.begin(), 1));
182        r = m.equal_range(7);
183        assert(r.first == next(m.begin(), 1));
184        assert(r.second == next(m.begin(), 2));
185        r = m.equal_range(9);
186        assert(r.first == next(m.begin(), 2));
187        assert(r.second == next(m.begin(), 3));
188        r = m.equal_range(11);
189        assert(r.first == next(m.begin(), 3));
190        assert(r.second == next(m.begin(), 4));
191        r = m.equal_range(13);
192        assert(r.first == next(m.begin(), 4));
193        assert(r.second == next(m.begin(), 5));
194        r = m.equal_range(15);
195        assert(r.first == next(m.begin(), 5));
196        assert(r.second == next(m.begin(), 6));
197        r = m.equal_range(17);
198        assert(r.first == next(m.begin(), 6));
199        assert(r.second == next(m.begin(), 7));
200        r = m.equal_range(19);
201        assert(r.first == next(m.begin(), 7));
202        assert(r.second == next(m.begin(), 8));
203        r = m.equal_range(4);
204        assert(r.first == next(m.begin(), 0));
205        assert(r.second == next(m.begin(), 0));
206        r = m.equal_range(6);
207        assert(r.first == next(m.begin(), 1));
208        assert(r.second == next(m.begin(), 1));
209        r = m.equal_range(8);
210        assert(r.first == next(m.begin(), 2));
211        assert(r.second == next(m.begin(), 2));
212        r = m.equal_range(10);
213        assert(r.first == next(m.begin(), 3));
214        assert(r.second == next(m.begin(), 3));
215        r = m.equal_range(12);
216        assert(r.first == next(m.begin(), 4));
217        assert(r.second == next(m.begin(), 4));
218        r = m.equal_range(14);
219        assert(r.first == next(m.begin(), 5));
220        assert(r.second == next(m.begin(), 5));
221        r = m.equal_range(16);
222        assert(r.first == next(m.begin(), 6));
223        assert(r.second == next(m.begin(), 6));
224        r = m.equal_range(18);
225        assert(r.first == next(m.begin(), 7));
226        assert(r.second == next(m.begin(), 7));
227        r = m.equal_range(20);
228        assert(r.first == next(m.begin(), 8));
229        assert(r.second == next(m.begin(), 8));
230    }
231    {
232        typedef std::pair<M::const_iterator, M::const_iterator> R;
233        V ar[] =
234        {
235            V(5, 5),
236            V(7, 6),
237            V(9, 7),
238            V(11, 8),
239            V(13, 9),
240            V(15, 10),
241            V(17, 11),
242            V(19, 12)
243        };
244        const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
245        R r = m.equal_range(5);
246        assert(r.first == next(m.begin(), 0));
247        assert(r.second == next(m.begin(), 1));
248        r = m.equal_range(7);
249        assert(r.first == next(m.begin(), 1));
250        assert(r.second == next(m.begin(), 2));
251        r = m.equal_range(9);
252        assert(r.first == next(m.begin(), 2));
253        assert(r.second == next(m.begin(), 3));
254        r = m.equal_range(11);
255        assert(r.first == next(m.begin(), 3));
256        assert(r.second == next(m.begin(), 4));
257        r = m.equal_range(13);
258        assert(r.first == next(m.begin(), 4));
259        assert(r.second == next(m.begin(), 5));
260        r = m.equal_range(15);
261        assert(r.first == next(m.begin(), 5));
262        assert(r.second == next(m.begin(), 6));
263        r = m.equal_range(17);
264        assert(r.first == next(m.begin(), 6));
265        assert(r.second == next(m.begin(), 7));
266        r = m.equal_range(19);
267        assert(r.first == next(m.begin(), 7));
268        assert(r.second == next(m.begin(), 8));
269        r = m.equal_range(4);
270        assert(r.first == next(m.begin(), 0));
271        assert(r.second == next(m.begin(), 0));
272        r = m.equal_range(6);
273        assert(r.first == next(m.begin(), 1));
274        assert(r.second == next(m.begin(), 1));
275        r = m.equal_range(8);
276        assert(r.first == next(m.begin(), 2));
277        assert(r.second == next(m.begin(), 2));
278        r = m.equal_range(10);
279        assert(r.first == next(m.begin(), 3));
280        assert(r.second == next(m.begin(), 3));
281        r = m.equal_range(12);
282        assert(r.first == next(m.begin(), 4));
283        assert(r.second == next(m.begin(), 4));
284        r = m.equal_range(14);
285        assert(r.first == next(m.begin(), 5));
286        assert(r.second == next(m.begin(), 5));
287        r = m.equal_range(16);
288        assert(r.first == next(m.begin(), 6));
289        assert(r.second == next(m.begin(), 6));
290        r = m.equal_range(18);
291        assert(r.first == next(m.begin(), 7));
292        assert(r.second == next(m.begin(), 7));
293        r = m.equal_range(20);
294        assert(r.first == next(m.begin(), 8));
295        assert(r.second == next(m.begin(), 8));
296    }
297    }
298#endif
299#if _LIBCPP_STD_VER > 11
300    {
301    typedef std::pair<const int, double> V;
302    typedef std::map<int, double, std::less<>> M;
303    typedef std::pair<M::iterator, M::iterator> R;
304
305    V ar[] =
306    {
307        V(5, 5),
308        V(7, 6),
309        V(9, 7),
310        V(11, 8),
311        V(13, 9),
312        V(15, 10),
313        V(17, 11),
314        V(19, 12)
315    };
316    M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
317    R r = m.equal_range(5);
318    assert(r.first == next(m.begin(), 0));
319    assert(r.second == next(m.begin(), 1));
320    r = m.equal_range(7);
321    assert(r.first == next(m.begin(), 1));
322    assert(r.second == next(m.begin(), 2));
323    r = m.equal_range(9);
324    assert(r.first == next(m.begin(), 2));
325    assert(r.second == next(m.begin(), 3));
326    r = m.equal_range(11);
327    assert(r.first == next(m.begin(), 3));
328    assert(r.second == next(m.begin(), 4));
329    r = m.equal_range(13);
330    assert(r.first == next(m.begin(), 4));
331    assert(r.second == next(m.begin(), 5));
332    r = m.equal_range(15);
333    assert(r.first == next(m.begin(), 5));
334    assert(r.second == next(m.begin(), 6));
335    r = m.equal_range(17);
336    assert(r.first == next(m.begin(), 6));
337    assert(r.second == next(m.begin(), 7));
338    r = m.equal_range(19);
339    assert(r.first == next(m.begin(), 7));
340    assert(r.second == next(m.begin(), 8));
341    r = m.equal_range(4);
342    assert(r.first == next(m.begin(), 0));
343    assert(r.second == next(m.begin(), 0));
344    r = m.equal_range(6);
345    assert(r.first == next(m.begin(), 1));
346    assert(r.second == next(m.begin(), 1));
347    r = m.equal_range(8);
348    assert(r.first == next(m.begin(), 2));
349    assert(r.second == next(m.begin(), 2));
350    r = m.equal_range(10);
351    assert(r.first == next(m.begin(), 3));
352    assert(r.second == next(m.begin(), 3));
353    r = m.equal_range(12);
354    assert(r.first == next(m.begin(), 4));
355    assert(r.second == next(m.begin(), 4));
356    r = m.equal_range(14);
357    assert(r.first == next(m.begin(), 5));
358    assert(r.second == next(m.begin(), 5));
359    r = m.equal_range(16);
360    assert(r.first == next(m.begin(), 6));
361    assert(r.second == next(m.begin(), 6));
362    r = m.equal_range(18);
363    assert(r.first == next(m.begin(), 7));
364    assert(r.second == next(m.begin(), 7));
365    r = m.equal_range(20);
366    assert(r.first == next(m.begin(), 8));
367    assert(r.second == next(m.begin(), 8));
368    }
369    {
370    typedef PrivateConstructor PC;
371    typedef std::map<PC, double, std::less<>> M;
372    typedef std::pair<M::iterator, M::iterator> R;
373
374    M m;
375    m [ PC::make(5)  ] = 5;
376    m [ PC::make(7)  ] = 6;
377    m [ PC::make(9)  ] = 7;
378    m [ PC::make(11) ] = 8;
379    m [ PC::make(13) ] = 9;
380    m [ PC::make(15) ] = 10;
381    m [ PC::make(17) ] = 11;
382    m [ PC::make(19) ] = 12;
383
384    R r = m.equal_range(5);
385    assert(r.first == next(m.begin(), 0));
386    assert(r.second == next(m.begin(), 1));
387    r = m.equal_range(7);
388    assert(r.first == next(m.begin(), 1));
389    assert(r.second == next(m.begin(), 2));
390    r = m.equal_range(9);
391    assert(r.first == next(m.begin(), 2));
392    assert(r.second == next(m.begin(), 3));
393    r = m.equal_range(11);
394    assert(r.first == next(m.begin(), 3));
395    assert(r.second == next(m.begin(), 4));
396    r = m.equal_range(13);
397    assert(r.first == next(m.begin(), 4));
398    assert(r.second == next(m.begin(), 5));
399    r = m.equal_range(15);
400    assert(r.first == next(m.begin(), 5));
401    assert(r.second == next(m.begin(), 6));
402    r = m.equal_range(17);
403    assert(r.first == next(m.begin(), 6));
404    assert(r.second == next(m.begin(), 7));
405    r = m.equal_range(19);
406    assert(r.first == next(m.begin(), 7));
407    assert(r.second == next(m.begin(), 8));
408    r = m.equal_range(4);
409    assert(r.first == next(m.begin(), 0));
410    assert(r.second == next(m.begin(), 0));
411    r = m.equal_range(6);
412    assert(r.first == next(m.begin(), 1));
413    assert(r.second == next(m.begin(), 1));
414    r = m.equal_range(8);
415    assert(r.first == next(m.begin(), 2));
416    assert(r.second == next(m.begin(), 2));
417    r = m.equal_range(10);
418    assert(r.first == next(m.begin(), 3));
419    assert(r.second == next(m.begin(), 3));
420    r = m.equal_range(12);
421    assert(r.first == next(m.begin(), 4));
422    assert(r.second == next(m.begin(), 4));
423    r = m.equal_range(14);
424    assert(r.first == next(m.begin(), 5));
425    assert(r.second == next(m.begin(), 5));
426    r = m.equal_range(16);
427    assert(r.first == next(m.begin(), 6));
428    assert(r.second == next(m.begin(), 6));
429    r = m.equal_range(18);
430    assert(r.first == next(m.begin(), 7));
431    assert(r.second == next(m.begin(), 7));
432    r = m.equal_range(20);
433    assert(r.first == next(m.begin(), 8));
434    assert(r.second == next(m.begin(), 8));
435    }
436#endif
437}
438