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