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// <set>
11
12// class multiset
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 <set>
18#include <cassert>
19
20#include "min_allocator.h"
21#include "private_constructor.hpp"
22
23int main()
24{
25    {
26    typedef int V;
27    typedef std::multiset<int> M;
28    {
29        typedef std::pair<M::iterator, M::iterator> R;
30        V ar[] =
31        {
32            5,
33            5,
34            5,
35            7,
36            7,
37            7,
38            9,
39            9,
40            9
41        };
42        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
43        R r = m.equal_range(4);
44        assert(r.first  == next(m.begin(), 0));
45        assert(r.second == next(m.begin(), 0));
46        r = m.equal_range(5);
47        assert(r.first  == next(m.begin(), 0));
48        assert(r.second == next(m.begin(), 3));
49        r = m.equal_range(6);
50        assert(r.first  == next(m.begin(), 3));
51        assert(r.second == next(m.begin(), 3));
52        r = m.equal_range(7);
53        assert(r.first  == next(m.begin(), 3));
54        assert(r.second == next(m.begin(), 6));
55        r = m.equal_range(8);
56        assert(r.first  == next(m.begin(), 6));
57        assert(r.second == next(m.begin(), 6));
58        r = m.equal_range(9);
59        assert(r.first  == next(m.begin(), 6));
60        assert(r.second == next(m.begin(), 9));
61        r = m.equal_range(10);
62        assert(r.first  == next(m.begin(), 9));
63        assert(r.second == next(m.begin(), 9));
64    }
65    {
66        typedef std::pair<M::const_iterator, M::const_iterator> R;
67        V ar[] =
68        {
69            5,
70            5,
71            5,
72            7,
73            7,
74            7,
75            9,
76            9,
77            9
78        };
79        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
80        R r = m.equal_range(4);
81        assert(r.first  == next(m.begin(), 0));
82        assert(r.second == next(m.begin(), 0));
83        r = m.equal_range(5);
84        assert(r.first  == next(m.begin(), 0));
85        assert(r.second == next(m.begin(), 3));
86        r = m.equal_range(6);
87        assert(r.first  == next(m.begin(), 3));
88        assert(r.second == next(m.begin(), 3));
89        r = m.equal_range(7);
90        assert(r.first  == next(m.begin(), 3));
91        assert(r.second == next(m.begin(), 6));
92        r = m.equal_range(8);
93        assert(r.first  == next(m.begin(), 6));
94        assert(r.second == next(m.begin(), 6));
95        r = m.equal_range(9);
96        assert(r.first  == next(m.begin(), 6));
97        assert(r.second == next(m.begin(), 9));
98        r = m.equal_range(10);
99        assert(r.first  == next(m.begin(), 9));
100        assert(r.second == next(m.begin(), 9));
101    }
102    }
103#if __cplusplus >= 201103L
104    {
105    typedef int V;
106    typedef std::multiset<int, std::less<int>, min_allocator<int>> M;
107    {
108        typedef std::pair<M::iterator, M::iterator> R;
109        V ar[] =
110        {
111            5,
112            5,
113            5,
114            7,
115            7,
116            7,
117            9,
118            9,
119            9
120        };
121        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
122        R r = m.equal_range(4);
123        assert(r.first  == next(m.begin(), 0));
124        assert(r.second == next(m.begin(), 0));
125        r = m.equal_range(5);
126        assert(r.first  == next(m.begin(), 0));
127        assert(r.second == next(m.begin(), 3));
128        r = m.equal_range(6);
129        assert(r.first  == next(m.begin(), 3));
130        assert(r.second == next(m.begin(), 3));
131        r = m.equal_range(7);
132        assert(r.first  == next(m.begin(), 3));
133        assert(r.second == next(m.begin(), 6));
134        r = m.equal_range(8);
135        assert(r.first  == next(m.begin(), 6));
136        assert(r.second == next(m.begin(), 6));
137        r = m.equal_range(9);
138        assert(r.first  == next(m.begin(), 6));
139        assert(r.second == next(m.begin(), 9));
140        r = m.equal_range(10);
141        assert(r.first  == next(m.begin(), 9));
142        assert(r.second == next(m.begin(), 9));
143    }
144    {
145        typedef std::pair<M::const_iterator, M::const_iterator> R;
146        V ar[] =
147        {
148            5,
149            5,
150            5,
151            7,
152            7,
153            7,
154            9,
155            9,
156            9
157        };
158        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
159        R r = m.equal_range(4);
160        assert(r.first  == next(m.begin(), 0));
161        assert(r.second == next(m.begin(), 0));
162        r = m.equal_range(5);
163        assert(r.first  == next(m.begin(), 0));
164        assert(r.second == next(m.begin(), 3));
165        r = m.equal_range(6);
166        assert(r.first  == next(m.begin(), 3));
167        assert(r.second == next(m.begin(), 3));
168        r = m.equal_range(7);
169        assert(r.first  == next(m.begin(), 3));
170        assert(r.second == next(m.begin(), 6));
171        r = m.equal_range(8);
172        assert(r.first  == next(m.begin(), 6));
173        assert(r.second == next(m.begin(), 6));
174        r = m.equal_range(9);
175        assert(r.first  == next(m.begin(), 6));
176        assert(r.second == next(m.begin(), 9));
177        r = m.equal_range(10);
178        assert(r.first  == next(m.begin(), 9));
179        assert(r.second == next(m.begin(), 9));
180    }
181    }
182#endif
183#if _LIBCPP_STD_VER > 11
184    {
185    typedef int V;
186    typedef std::multiset<V, std::less<>> M;
187    typedef std::pair<M::iterator, M::iterator> R;
188    V ar[] =
189    {
190        5,
191        5,
192        5,
193        7,
194        7,
195        7,
196        9,
197        9,
198        9
199    };
200    M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
201    R r = m.equal_range(4);
202    assert(r.first  == next(m.begin(), 0));
203    assert(r.second == next(m.begin(), 0));
204    r = m.equal_range(5);
205    assert(r.first  == next(m.begin(), 0));
206    assert(r.second == next(m.begin(), 3));
207    r = m.equal_range(6);
208    assert(r.first  == next(m.begin(), 3));
209    assert(r.second == next(m.begin(), 3));
210    r = m.equal_range(7);
211    assert(r.first  == next(m.begin(), 3));
212    assert(r.second == next(m.begin(), 6));
213    r = m.equal_range(8);
214    assert(r.first  == next(m.begin(), 6));
215    assert(r.second == next(m.begin(), 6));
216    r = m.equal_range(9);
217    assert(r.first  == next(m.begin(), 6));
218    assert(r.second == next(m.begin(), 9));
219    r = m.equal_range(10);
220    assert(r.first  == next(m.begin(), 9));
221    assert(r.second == next(m.begin(), 9));
222    }
223
224    {
225    typedef PrivateConstructor V;
226    typedef std::multiset<V, std::less<>> M;
227    typedef std::pair<M::iterator, M::iterator> R;
228
229    M m;
230    m.insert ( V::make ( 5 ));
231    m.insert ( V::make ( 5 ));
232    m.insert ( V::make ( 5 ));
233    m.insert ( V::make ( 7 ));
234    m.insert ( V::make ( 7 ));
235    m.insert ( V::make ( 7 ));
236    m.insert ( V::make ( 9 ));
237    m.insert ( V::make ( 9 ));
238    m.insert ( V::make ( 9 ));
239
240    R r = m.equal_range(4);
241    assert(r.first  == next(m.begin(), 0));
242    assert(r.second == next(m.begin(), 0));
243    r = m.equal_range(5);
244    assert(r.first  == next(m.begin(), 0));
245    assert(r.second == next(m.begin(), 3));
246    r = m.equal_range(6);
247    assert(r.first  == next(m.begin(), 3));
248    assert(r.second == next(m.begin(), 3));
249    r = m.equal_range(7);
250    assert(r.first  == next(m.begin(), 3));
251    assert(r.second == next(m.begin(), 6));
252    r = m.equal_range(8);
253    assert(r.first  == next(m.begin(), 6));
254    assert(r.second == next(m.begin(), 6));
255    r = m.equal_range(9);
256    assert(r.first  == next(m.begin(), 6));
257    assert(r.second == next(m.begin(), 9));
258    r = m.equal_range(10);
259    assert(r.first  == next(m.begin(), 9));
260    assert(r.second == next(m.begin(), 9));
261    }
262#endif
263}
264