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//       iterator lower_bound(const key_type& k);
15// const_iterator lower_bound(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 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.lower_bound(4);
44            assert(r == next(m.begin(), 0));
45            r = m.lower_bound(5);
46            assert(r == next(m.begin(), 0));
47            r = m.lower_bound(6);
48            assert(r == next(m.begin(), 3));
49            r = m.lower_bound(7);
50            assert(r == next(m.begin(), 3));
51            r = m.lower_bound(8);
52            assert(r == next(m.begin(), 6));
53            r = m.lower_bound(9);
54            assert(r == next(m.begin(), 6));
55            r = m.lower_bound(11);
56            assert(r == next(m.begin(), 9));
57        }
58        {
59            typedef M::const_iterator R;
60            V ar[] =
61            {
62                5,
63                5,
64                5,
65                7,
66                7,
67                7,
68                9,
69                9,
70                9
71            };
72            const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
73            R r = m.lower_bound(4);
74            assert(r == next(m.begin(), 0));
75            r = m.lower_bound(5);
76            assert(r == next(m.begin(), 0));
77            r = m.lower_bound(6);
78            assert(r == next(m.begin(), 3));
79            r = m.lower_bound(7);
80            assert(r == next(m.begin(), 3));
81            r = m.lower_bound(8);
82            assert(r == next(m.begin(), 6));
83            r = m.lower_bound(9);
84            assert(r == next(m.begin(), 6));
85            r = m.lower_bound(11);
86            assert(r == next(m.begin(), 9));
87        }
88    }
89#if __cplusplus >= 201103L
90    {
91        typedef int V;
92        typedef std::multiset<int, std::less<int>, min_allocator<int>> M;
93        {
94            typedef M::iterator R;
95            V ar[] =
96            {
97                5,
98                5,
99                5,
100                7,
101                7,
102                7,
103                9,
104                9,
105                9
106            };
107            M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
108            R r = m.lower_bound(4);
109            assert(r == next(m.begin(), 0));
110            r = m.lower_bound(5);
111            assert(r == next(m.begin(), 0));
112            r = m.lower_bound(6);
113            assert(r == next(m.begin(), 3));
114            r = m.lower_bound(7);
115            assert(r == next(m.begin(), 3));
116            r = m.lower_bound(8);
117            assert(r == next(m.begin(), 6));
118            r = m.lower_bound(9);
119            assert(r == next(m.begin(), 6));
120            r = m.lower_bound(11);
121            assert(r == next(m.begin(), 9));
122        }
123        {
124            typedef M::const_iterator R;
125            V ar[] =
126            {
127                5,
128                5,
129                5,
130                7,
131                7,
132                7,
133                9,
134                9,
135                9
136            };
137            const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
138            R r = m.lower_bound(4);
139            assert(r == next(m.begin(), 0));
140            r = m.lower_bound(5);
141            assert(r == next(m.begin(), 0));
142            r = m.lower_bound(6);
143            assert(r == next(m.begin(), 3));
144            r = m.lower_bound(7);
145            assert(r == next(m.begin(), 3));
146            r = m.lower_bound(8);
147            assert(r == next(m.begin(), 6));
148            r = m.lower_bound(9);
149            assert(r == next(m.begin(), 6));
150            r = m.lower_bound(11);
151            assert(r == next(m.begin(), 9));
152        }
153    }
154#endif
155#if _LIBCPP_STD_VER > 11
156    {
157    typedef int V;
158    typedef std::multiset<V, std::less<>> M;
159
160    typedef M::iterator R;
161    V ar[] =
162    {
163        5,
164        5,
165        5,
166        7,
167        7,
168        7,
169        9,
170        9,
171        9
172    };
173    M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
174
175    R r = m.lower_bound(4);
176    assert(r == next(m.begin(), 0));
177    r = m.lower_bound(5);
178    assert(r == next(m.begin(), 0));
179    r = m.lower_bound(6);
180    assert(r == next(m.begin(), 3));
181    r = m.lower_bound(7);
182    assert(r == next(m.begin(), 3));
183    r = m.lower_bound(8);
184    assert(r == next(m.begin(), 6));
185    r = m.lower_bound(9);
186    assert(r == next(m.begin(), 6));
187    r = m.lower_bound(11);
188    assert(r == next(m.begin(), 9));
189    }
190
191    {
192    typedef PrivateConstructor V;
193    typedef std::multiset<V, std::less<>> M;
194    typedef M::iterator R;
195
196    M m;
197    m.insert ( V::make ( 5 ));
198    m.insert ( V::make ( 5 ));
199    m.insert ( V::make ( 5 ));
200    m.insert ( V::make ( 7 ));
201    m.insert ( V::make ( 7 ));
202    m.insert ( V::make ( 7 ));
203    m.insert ( V::make ( 9 ));
204    m.insert ( V::make ( 9 ));
205    m.insert ( V::make ( 9 ));
206
207    R r = m.lower_bound(4);
208    assert(r == next(m.begin(), 0));
209    r = m.lower_bound(5);
210    assert(r == next(m.begin(), 0));
211    r = m.lower_bound(6);
212    assert(r == next(m.begin(), 3));
213    r = m.lower_bound(7);
214    assert(r == next(m.begin(), 3));
215    r = m.lower_bound(8);
216    assert(r == next(m.begin(), 6));
217    r = m.lower_bound(9);
218    assert(r == next(m.begin(), 6));
219    r = m.lower_bound(11);
220    assert(r == next(m.begin(), 9));
221    }
222#endif
223}
224