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