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 "min_allocator.h"
21 #include "private_constructor.hpp"
22 #include "is_transparent.h"
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.lower_bound(5);
44 assert(r == m.begin());
45 r = m.lower_bound(7);
46 assert(r == next(m.begin()));
47 r = m.lower_bound(9);
48 assert(r == next(m.begin(), 2));
49 r = m.lower_bound(11);
50 assert(r == next(m.begin(), 3));
51 r = m.lower_bound(13);
52 assert(r == next(m.begin(), 4));
53 r = m.lower_bound(15);
54 assert(r == next(m.begin(), 5));
55 r = m.lower_bound(17);
56 assert(r == next(m.begin(), 6));
57 r = m.lower_bound(19);
58 assert(r == next(m.begin(), 7));
59 r = m.lower_bound(4);
60 assert(r == next(m.begin(), 0));
61 r = m.lower_bound(6);
62 assert(r == next(m.begin(), 1));
63 r = m.lower_bound(8);
64 assert(r == next(m.begin(), 2));
65 r = m.lower_bound(10);
66 assert(r == next(m.begin(), 3));
67 r = m.lower_bound(12);
68 assert(r == next(m.begin(), 4));
69 r = m.lower_bound(14);
70 assert(r == next(m.begin(), 5));
71 r = m.lower_bound(16);
72 assert(r == next(m.begin(), 6));
73 r = m.lower_bound(18);
74 assert(r == next(m.begin(), 7));
75 r = m.lower_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.lower_bound(5);
93 assert(r == m.begin());
94 r = m.lower_bound(7);
95 assert(r == next(m.begin()));
96 r = m.lower_bound(9);
97 assert(r == next(m.begin(), 2));
98 r = m.lower_bound(11);
99 assert(r == next(m.begin(), 3));
100 r = m.lower_bound(13);
101 assert(r == next(m.begin(), 4));
102 r = m.lower_bound(15);
103 assert(r == next(m.begin(), 5));
104 r = m.lower_bound(17);
105 assert(r == next(m.begin(), 6));
106 r = m.lower_bound(19);
107 assert(r == next(m.begin(), 7));
108 r = m.lower_bound(4);
109 assert(r == next(m.begin(), 0));
110 r = m.lower_bound(6);
111 assert(r == next(m.begin(), 1));
112 r = m.lower_bound(8);
113 assert(r == next(m.begin(), 2));
114 r = m.lower_bound(10);
115 assert(r == next(m.begin(), 3));
116 r = m.lower_bound(12);
117 assert(r == next(m.begin(), 4));
118 r = m.lower_bound(14);
119 assert(r == next(m.begin(), 5));
120 r = m.lower_bound(16);
121 assert(r == next(m.begin(), 6));
122 r = m.lower_bound(18);
123 assert(r == next(m.begin(), 7));
124 r = m.lower_bound(20);
125 assert(r == next(m.begin(), 8));
126 }
127 }
128 #if __cplusplus >= 201103L
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.lower_bound(5);
147 assert(r == m.begin());
148 r = m.lower_bound(7);
149 assert(r == next(m.begin()));
150 r = m.lower_bound(9);
151 assert(r == next(m.begin(), 2));
152 r = m.lower_bound(11);
153 assert(r == next(m.begin(), 3));
154 r = m.lower_bound(13);
155 assert(r == next(m.begin(), 4));
156 r = m.lower_bound(15);
157 assert(r == next(m.begin(), 5));
158 r = m.lower_bound(17);
159 assert(r == next(m.begin(), 6));
160 r = m.lower_bound(19);
161 assert(r == next(m.begin(), 7));
162 r = m.lower_bound(4);
163 assert(r == next(m.begin(), 0));
164 r = m.lower_bound(6);
165 assert(r == next(m.begin(), 1));
166 r = m.lower_bound(8);
167 assert(r == next(m.begin(), 2));
168 r = m.lower_bound(10);
169 assert(r == next(m.begin(), 3));
170 r = m.lower_bound(12);
171 assert(r == next(m.begin(), 4));
172 r = m.lower_bound(14);
173 assert(r == next(m.begin(), 5));
174 r = m.lower_bound(16);
175 assert(r == next(m.begin(), 6));
176 r = m.lower_bound(18);
177 assert(r == next(m.begin(), 7));
178 r = m.lower_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.lower_bound(5);
196 assert(r == m.begin());
197 r = m.lower_bound(7);
198 assert(r == next(m.begin()));
199 r = m.lower_bound(9);
200 assert(r == next(m.begin(), 2));
201 r = m.lower_bound(11);
202 assert(r == next(m.begin(), 3));
203 r = m.lower_bound(13);
204 assert(r == next(m.begin(), 4));
205 r = m.lower_bound(15);
206 assert(r == next(m.begin(), 5));
207 r = m.lower_bound(17);
208 assert(r == next(m.begin(), 6));
209 r = m.lower_bound(19);
210 assert(r == next(m.begin(), 7));
211 r = m.lower_bound(4);
212 assert(r == next(m.begin(), 0));
213 r = m.lower_bound(6);
214 assert(r == next(m.begin(), 1));
215 r = m.lower_bound(8);
216 assert(r == next(m.begin(), 2));
217 r = m.lower_bound(10);
218 assert(r == next(m.begin(), 3));
219 r = m.lower_bound(12);
220 assert(r == next(m.begin(), 4));
221 r = m.lower_bound(14);
222 assert(r == next(m.begin(), 5));
223 r = m.lower_bound(16);
224 assert(r == next(m.begin(), 6));
225 r = m.lower_bound(18);
226 assert(r == next(m.begin(), 7));
227 r = m.lower_bound(20);
228 assert(r == next(m.begin(), 8));
229 }
230 }
231 #endif
232 #if _LIBCPP_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
238 V ar[] =
239 {
240 V(5, 5),
241 V(7, 6),
242 V(9, 7),
243 V(11, 8),
244 V(13, 9),
245 V(15, 10),
246 V(17, 11),
247 V(19, 12)
248 };
249 M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
250 R r = m.lower_bound(5);
251 assert(r == m.begin());
252 r = m.lower_bound(7);
253 assert(r == next(m.begin()));
254 r = m.lower_bound(9);
255 assert(r == next(m.begin(), 2));
256 r = m.lower_bound(11);
257 assert(r == next(m.begin(), 3));
258 r = m.lower_bound(13);
259 assert(r == next(m.begin(), 4));
260 r = m.lower_bound(15);
261 assert(r == next(m.begin(), 5));
262 r = m.lower_bound(17);
263 assert(r == next(m.begin(), 6));
264 r = m.lower_bound(19);
265 assert(r == next(m.begin(), 7));
266 r = m.lower_bound(4);
267 assert(r == next(m.begin(), 0));
268 r = m.lower_bound(6);
269 assert(r == next(m.begin(), 1));
270 r = m.lower_bound(8);
271 assert(r == next(m.begin(), 2));
272 r = m.lower_bound(10);
273 assert(r == next(m.begin(), 3));
274 r = m.lower_bound(12);
275 assert(r == next(m.begin(), 4));
276 r = m.lower_bound(14);
277 assert(r == next(m.begin(), 5));
278 r = m.lower_bound(16);
279 assert(r == next(m.begin(), 6));
280 r = m.lower_bound(18);
281 assert(r == next(m.begin(), 7));
282 r = m.lower_bound(20);
283 assert(r == next(m.begin(), 8));
284
285 r = m.lower_bound(C2Int(5));
286 assert(r == m.begin());
287 r = m.lower_bound(C2Int(7));
288 assert(r == next(m.begin()));
289 r = m.lower_bound(C2Int(9));
290 assert(r == next(m.begin(), 2));
291 r = m.lower_bound(C2Int(11));
292 assert(r == next(m.begin(), 3));
293 r = m.lower_bound(C2Int(13));
294 assert(r == next(m.begin(), 4));
295 r = m.lower_bound(C2Int(15));
296 assert(r == next(m.begin(), 5));
297 r = m.lower_bound(C2Int(17));
298 assert(r == next(m.begin(), 6));
299 r = m.lower_bound(C2Int(19));
300 assert(r == next(m.begin(), 7));
301 r = m.lower_bound(C2Int(4));
302 assert(r == next(m.begin(), 0));
303 r = m.lower_bound(C2Int(6));
304 assert(r == next(m.begin(), 1));
305 r = m.lower_bound(C2Int(8));
306 assert(r == next(m.begin(), 2));
307 r = m.lower_bound(C2Int(10));
308 assert(r == next(m.begin(), 3));
309 r = m.lower_bound(C2Int(12));
310 assert(r == next(m.begin(), 4));
311 r = m.lower_bound(C2Int(14));
312 assert(r == next(m.begin(), 5));
313 r = m.lower_bound(C2Int(16));
314 assert(r == next(m.begin(), 6));
315 r = m.lower_bound(C2Int(18));
316 assert(r == next(m.begin(), 7));
317 r = m.lower_bound(C2Int(20));
318 assert(r == next(m.begin(), 8));
319 }
320
321 {
322 typedef PrivateConstructor PC;
323 typedef std::map<PC, double, std::less<>> M;
324 typedef M::iterator R;
325
326 M m;
327 m [ PC::make(5) ] = 5;
328 m [ PC::make(7) ] = 6;
329 m [ PC::make(9) ] = 7;
330 m [ PC::make(11) ] = 8;
331 m [ PC::make(13) ] = 9;
332 m [ PC::make(15) ] = 10;
333 m [ PC::make(17) ] = 11;
334 m [ PC::make(19) ] = 12;
335
336 R r = m.lower_bound(5);
337 assert(r == m.begin());
338 r = m.lower_bound(7);
339 assert(r == next(m.begin()));
340 r = m.lower_bound(9);
341 assert(r == next(m.begin(), 2));
342 r = m.lower_bound(11);
343 assert(r == next(m.begin(), 3));
344 r = m.lower_bound(13);
345 assert(r == next(m.begin(), 4));
346 r = m.lower_bound(15);
347 assert(r == next(m.begin(), 5));
348 r = m.lower_bound(17);
349 assert(r == next(m.begin(), 6));
350 r = m.lower_bound(19);
351 assert(r == next(m.begin(), 7));
352 r = m.lower_bound(4);
353 assert(r == next(m.begin(), 0));
354 r = m.lower_bound(6);
355 assert(r == next(m.begin(), 1));
356 r = m.lower_bound(8);
357 assert(r == next(m.begin(), 2));
358 r = m.lower_bound(10);
359 assert(r == next(m.begin(), 3));
360 r = m.lower_bound(12);
361 assert(r == next(m.begin(), 4));
362 r = m.lower_bound(14);
363 assert(r == next(m.begin(), 5));
364 r = m.lower_bound(16);
365 assert(r == next(m.begin(), 6));
366 r = m.lower_bound(18);
367 assert(r == next(m.begin(), 7));
368 r = m.lower_bound(20);
369 assert(r == next(m.begin(), 8));
370 }
371 #endif
372 }
373