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 //       iterator upper_bound(const key_type& k);
15 // const_iterator upper_bound(const key_type& k) const;
16 
17 #include <map>
18 #include <cassert>
19 
20 #include "min_allocator.h"
21 #include "private_constructor.hpp"
22 
main()23 int main()
24 {
25     {
26     typedef std::pair<const int, double> V;
27     typedef std::map<int, double> M;
28     {
29         typedef 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.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             V(5, 5),
82             V(7, 6),
83             V(9, 7),
84             V(11, 8),
85             V(13, 9),
86             V(15, 10),
87             V(17, 11),
88             V(19, 12)
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 std::pair<const int, double> V;
130     typedef std::map<int, double, std::less<int>, min_allocator<V>> M;
131     {
132         typedef M::iterator R;
133         V ar[] =
134         {
135             V(5, 5),
136             V(7, 6),
137             V(9, 7),
138             V(11, 8),
139             V(13, 9),
140             V(15, 10),
141             V(17, 11),
142             V(19, 12)
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             V(5, 5),
185             V(7, 6),
186             V(9, 7),
187             V(11, 8),
188             V(13, 9),
189             V(15, 10),
190             V(17, 11),
191             V(19, 12)
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 std::pair<const int, double> V;
234     typedef std::map<int, double, std::less<>> M;
235     typedef M::iterator R;
236     V ar[] =
237     {
238         V(5, 5),
239         V(7, 6),
240         V(9, 7),
241         V(11, 8),
242         V(13, 9),
243         V(15, 10),
244         V(17, 11),
245         V(19, 12)
246     };
247     M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
248     R r = m.upper_bound(5);
249     assert(r == next(m.begin(), 1));
250     r = m.upper_bound(7);
251     assert(r == next(m.begin(), 2));
252     r = m.upper_bound(9);
253     assert(r == next(m.begin(), 3));
254     r = m.upper_bound(11);
255     assert(r == next(m.begin(), 4));
256     r = m.upper_bound(13);
257     assert(r == next(m.begin(), 5));
258     r = m.upper_bound(15);
259     assert(r == next(m.begin(), 6));
260     r = m.upper_bound(17);
261     assert(r == next(m.begin(), 7));
262     r = m.upper_bound(19);
263     assert(r == next(m.begin(), 8));
264     r = m.upper_bound(4);
265     assert(r == next(m.begin(), 0));
266     r = m.upper_bound(6);
267     assert(r == next(m.begin(), 1));
268     r = m.upper_bound(8);
269     assert(r == next(m.begin(), 2));
270     r = m.upper_bound(10);
271     assert(r == next(m.begin(), 3));
272     r = m.upper_bound(12);
273     assert(r == next(m.begin(), 4));
274     r = m.upper_bound(14);
275     assert(r == next(m.begin(), 5));
276     r = m.upper_bound(16);
277     assert(r == next(m.begin(), 6));
278     r = m.upper_bound(18);
279     assert(r == next(m.begin(), 7));
280     r = m.upper_bound(20);
281     assert(r == next(m.begin(), 8));
282     }
283 
284     {
285     typedef PrivateConstructor PC;
286     typedef std::map<PC, double, std::less<>> M;
287     typedef M::iterator R;
288 
289     M m;
290     m [ PC::make(5)  ] = 5;
291     m [ PC::make(7)  ] = 6;
292     m [ PC::make(9)  ] = 7;
293     m [ PC::make(11) ] = 8;
294     m [ PC::make(13) ] = 9;
295     m [ PC::make(15) ] = 10;
296     m [ PC::make(17) ] = 11;
297     m [ PC::make(19) ] = 12;
298 
299     R r = m.upper_bound(5);
300     assert(r == next(m.begin(), 1));
301     r = m.upper_bound(7);
302     assert(r == next(m.begin(), 2));
303     r = m.upper_bound(9);
304     assert(r == next(m.begin(), 3));
305     r = m.upper_bound(11);
306     assert(r == next(m.begin(), 4));
307     r = m.upper_bound(13);
308     assert(r == next(m.begin(), 5));
309     r = m.upper_bound(15);
310     assert(r == next(m.begin(), 6));
311     r = m.upper_bound(17);
312     assert(r == next(m.begin(), 7));
313     r = m.upper_bound(19);
314     assert(r == next(m.begin(), 8));
315     r = m.upper_bound(4);
316     assert(r == next(m.begin(), 0));
317     r = m.upper_bound(6);
318     assert(r == next(m.begin(), 1));
319     r = m.upper_bound(8);
320     assert(r == next(m.begin(), 2));
321     r = m.upper_bound(10);
322     assert(r == next(m.begin(), 3));
323     r = m.upper_bound(12);
324     assert(r == next(m.begin(), 4));
325     r = m.upper_bound(14);
326     assert(r == next(m.begin(), 5));
327     r = m.upper_bound(16);
328     assert(r == next(m.begin(), 6));
329     r = m.upper_bound(18);
330     assert(r == next(m.begin(), 7));
331     r = m.upper_bound(20);
332     assert(r == next(m.begin(), 8));
333     }
334 #endif
335 }
336