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