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 set
13 
14 //       iterator upper_bound(const key_type& k);
15 // const_iterator upper_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 
main()23 int main()
24 {
25     {
26     typedef int V;
27     typedef std::set<int> M;
28     {
29         typedef M::iterator R;
30         V ar[] =
31         {
32             5,
33             7,
34             9,
35             11,
36             13,
37             15,
38             17,
39             19
40         };
41         M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
42         R r = m.upper_bound(5);
43         assert(r == next(m.begin(), 1));
44         r = m.upper_bound(7);
45         assert(r == next(m.begin(), 2));
46         r = m.upper_bound(9);
47         assert(r == next(m.begin(), 3));
48         r = m.upper_bound(11);
49         assert(r == next(m.begin(), 4));
50         r = m.upper_bound(13);
51         assert(r == next(m.begin(), 5));
52         r = m.upper_bound(15);
53         assert(r == next(m.begin(), 6));
54         r = m.upper_bound(17);
55         assert(r == next(m.begin(), 7));
56         r = m.upper_bound(19);
57         assert(r == next(m.begin(), 8));
58         r = m.upper_bound(4);
59         assert(r == next(m.begin(), 0));
60         r = m.upper_bound(6);
61         assert(r == next(m.begin(), 1));
62         r = m.upper_bound(8);
63         assert(r == next(m.begin(), 2));
64         r = m.upper_bound(10);
65         assert(r == next(m.begin(), 3));
66         r = m.upper_bound(12);
67         assert(r == next(m.begin(), 4));
68         r = m.upper_bound(14);
69         assert(r == next(m.begin(), 5));
70         r = m.upper_bound(16);
71         assert(r == next(m.begin(), 6));
72         r = m.upper_bound(18);
73         assert(r == next(m.begin(), 7));
74         r = m.upper_bound(20);
75         assert(r == next(m.begin(), 8));
76     }
77     {
78         typedef M::const_iterator R;
79         V ar[] =
80         {
81             5,
82             7,
83             9,
84             11,
85             13,
86             15,
87             17,
88             19
89         };
90         const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
91         R r = m.upper_bound(5);
92         assert(r == next(m.begin(), 1));
93         r = m.upper_bound(7);
94         assert(r == next(m.begin(), 2));
95         r = m.upper_bound(9);
96         assert(r == next(m.begin(), 3));
97         r = m.upper_bound(11);
98         assert(r == next(m.begin(), 4));
99         r = m.upper_bound(13);
100         assert(r == next(m.begin(), 5));
101         r = m.upper_bound(15);
102         assert(r == next(m.begin(), 6));
103         r = m.upper_bound(17);
104         assert(r == next(m.begin(), 7));
105         r = m.upper_bound(19);
106         assert(r == next(m.begin(), 8));
107         r = m.upper_bound(4);
108         assert(r == next(m.begin(), 0));
109         r = m.upper_bound(6);
110         assert(r == next(m.begin(), 1));
111         r = m.upper_bound(8);
112         assert(r == next(m.begin(), 2));
113         r = m.upper_bound(10);
114         assert(r == next(m.begin(), 3));
115         r = m.upper_bound(12);
116         assert(r == next(m.begin(), 4));
117         r = m.upper_bound(14);
118         assert(r == next(m.begin(), 5));
119         r = m.upper_bound(16);
120         assert(r == next(m.begin(), 6));
121         r = m.upper_bound(18);
122         assert(r == next(m.begin(), 7));
123         r = m.upper_bound(20);
124         assert(r == next(m.begin(), 8));
125     }
126     }
127 #if __cplusplus >= 201103L
128     {
129     typedef int V;
130     typedef std::set<int, std::less<int>, min_allocator<int>> M;
131     {
132         typedef M::iterator R;
133         V ar[] =
134         {
135             5,
136             7,
137             9,
138             11,
139             13,
140             15,
141             17,
142             19
143         };
144         M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
145         R r = m.upper_bound(5);
146         assert(r == next(m.begin(), 1));
147         r = m.upper_bound(7);
148         assert(r == next(m.begin(), 2));
149         r = m.upper_bound(9);
150         assert(r == next(m.begin(), 3));
151         r = m.upper_bound(11);
152         assert(r == next(m.begin(), 4));
153         r = m.upper_bound(13);
154         assert(r == next(m.begin(), 5));
155         r = m.upper_bound(15);
156         assert(r == next(m.begin(), 6));
157         r = m.upper_bound(17);
158         assert(r == next(m.begin(), 7));
159         r = m.upper_bound(19);
160         assert(r == next(m.begin(), 8));
161         r = m.upper_bound(4);
162         assert(r == next(m.begin(), 0));
163         r = m.upper_bound(6);
164         assert(r == next(m.begin(), 1));
165         r = m.upper_bound(8);
166         assert(r == next(m.begin(), 2));
167         r = m.upper_bound(10);
168         assert(r == next(m.begin(), 3));
169         r = m.upper_bound(12);
170         assert(r == next(m.begin(), 4));
171         r = m.upper_bound(14);
172         assert(r == next(m.begin(), 5));
173         r = m.upper_bound(16);
174         assert(r == next(m.begin(), 6));
175         r = m.upper_bound(18);
176         assert(r == next(m.begin(), 7));
177         r = m.upper_bound(20);
178         assert(r == next(m.begin(), 8));
179     }
180     {
181         typedef M::const_iterator R;
182         V ar[] =
183         {
184             5,
185             7,
186             9,
187             11,
188             13,
189             15,
190             17,
191             19
192         };
193         const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
194         R r = m.upper_bound(5);
195         assert(r == next(m.begin(), 1));
196         r = m.upper_bound(7);
197         assert(r == next(m.begin(), 2));
198         r = m.upper_bound(9);
199         assert(r == next(m.begin(), 3));
200         r = m.upper_bound(11);
201         assert(r == next(m.begin(), 4));
202         r = m.upper_bound(13);
203         assert(r == next(m.begin(), 5));
204         r = m.upper_bound(15);
205         assert(r == next(m.begin(), 6));
206         r = m.upper_bound(17);
207         assert(r == next(m.begin(), 7));
208         r = m.upper_bound(19);
209         assert(r == next(m.begin(), 8));
210         r = m.upper_bound(4);
211         assert(r == next(m.begin(), 0));
212         r = m.upper_bound(6);
213         assert(r == next(m.begin(), 1));
214         r = m.upper_bound(8);
215         assert(r == next(m.begin(), 2));
216         r = m.upper_bound(10);
217         assert(r == next(m.begin(), 3));
218         r = m.upper_bound(12);
219         assert(r == next(m.begin(), 4));
220         r = m.upper_bound(14);
221         assert(r == next(m.begin(), 5));
222         r = m.upper_bound(16);
223         assert(r == next(m.begin(), 6));
224         r = m.upper_bound(18);
225         assert(r == next(m.begin(), 7));
226         r = m.upper_bound(20);
227         assert(r == next(m.begin(), 8));
228     }
229     }
230 #endif
231 #if _LIBCPP_STD_VER > 11
232     {
233     typedef int V;
234     typedef std::set<V, std::less<>> M;
235     typedef M::iterator R;
236 
237     V ar[] =
238     {
239         5,
240         7,
241         9,
242         11,
243         13,
244         15,
245         17,
246         19
247     };
248     M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
249     R r = m.upper_bound(5);
250     assert(r == next(m.begin(), 1));
251     r = m.upper_bound(7);
252     assert(r == next(m.begin(), 2));
253     r = m.upper_bound(9);
254     assert(r == next(m.begin(), 3));
255     r = m.upper_bound(11);
256     assert(r == next(m.begin(), 4));
257     r = m.upper_bound(13);
258     assert(r == next(m.begin(), 5));
259     r = m.upper_bound(15);
260     assert(r == next(m.begin(), 6));
261     r = m.upper_bound(17);
262     assert(r == next(m.begin(), 7));
263     r = m.upper_bound(19);
264     assert(r == next(m.begin(), 8));
265     r = m.upper_bound(4);
266     assert(r == next(m.begin(), 0));
267     r = m.upper_bound(6);
268     assert(r == next(m.begin(), 1));
269     r = m.upper_bound(8);
270     assert(r == next(m.begin(), 2));
271     r = m.upper_bound(10);
272     assert(r == next(m.begin(), 3));
273     r = m.upper_bound(12);
274     assert(r == next(m.begin(), 4));
275     r = m.upper_bound(14);
276     assert(r == next(m.begin(), 5));
277     r = m.upper_bound(16);
278     assert(r == next(m.begin(), 6));
279     r = m.upper_bound(18);
280     assert(r == next(m.begin(), 7));
281     r = m.upper_bound(20);
282     assert(r == next(m.begin(), 8));
283     }
284 
285     {
286     typedef PrivateConstructor V;
287     typedef std::set<V, std::less<>> M;
288     typedef M::iterator R;
289 
290     M m;
291     m.insert ( V::make ( 5 ));
292     m.insert ( V::make ( 7 ));
293     m.insert ( V::make ( 9 ));
294     m.insert ( V::make ( 11 ));
295     m.insert ( V::make ( 13 ));
296     m.insert ( V::make ( 15 ));
297     m.insert ( V::make ( 17 ));
298     m.insert ( V::make ( 19 ));
299 
300     R r = m.upper_bound(5);
301     assert(r == next(m.begin(), 1));
302     r = m.upper_bound(7);
303     assert(r == next(m.begin(), 2));
304     r = m.upper_bound(9);
305     assert(r == next(m.begin(), 3));
306     r = m.upper_bound(11);
307     assert(r == next(m.begin(), 4));
308     r = m.upper_bound(13);
309     assert(r == next(m.begin(), 5));
310     r = m.upper_bound(15);
311     assert(r == next(m.begin(), 6));
312     r = m.upper_bound(17);
313     assert(r == next(m.begin(), 7));
314     r = m.upper_bound(19);
315     assert(r == next(m.begin(), 8));
316     r = m.upper_bound(4);
317     assert(r == next(m.begin(), 0));
318     r = m.upper_bound(6);
319     assert(r == next(m.begin(), 1));
320     r = m.upper_bound(8);
321     assert(r == next(m.begin(), 2));
322     r = m.upper_bound(10);
323     assert(r == next(m.begin(), 3));
324     r = m.upper_bound(12);
325     assert(r == next(m.begin(), 4));
326     r = m.upper_bound(14);
327     assert(r == next(m.begin(), 5));
328     r = m.upper_bound(16);
329     assert(r == next(m.begin(), 6));
330     r = m.upper_bound(18);
331     assert(r == next(m.begin(), 7));
332     r = m.upper_bound(20);
333     assert(r == next(m.begin(), 8));
334     }
335 #endif
336 }
337