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
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.lower_bound(5);
43 assert(r == m.begin());
44 r = m.lower_bound(7);
45 assert(r == next(m.begin()));
46 r = m.lower_bound(9);
47 assert(r == next(m.begin(), 2));
48 r = m.lower_bound(11);
49 assert(r == next(m.begin(), 3));
50 r = m.lower_bound(13);
51 assert(r == next(m.begin(), 4));
52 r = m.lower_bound(15);
53 assert(r == next(m.begin(), 5));
54 r = m.lower_bound(17);
55 assert(r == next(m.begin(), 6));
56 r = m.lower_bound(19);
57 assert(r == next(m.begin(), 7));
58 r = m.lower_bound(4);
59 assert(r == next(m.begin(), 0));
60 r = m.lower_bound(6);
61 assert(r == next(m.begin(), 1));
62 r = m.lower_bound(8);
63 assert(r == next(m.begin(), 2));
64 r = m.lower_bound(10);
65 assert(r == next(m.begin(), 3));
66 r = m.lower_bound(12);
67 assert(r == next(m.begin(), 4));
68 r = m.lower_bound(14);
69 assert(r == next(m.begin(), 5));
70 r = m.lower_bound(16);
71 assert(r == next(m.begin(), 6));
72 r = m.lower_bound(18);
73 assert(r == next(m.begin(), 7));
74 r = m.lower_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.lower_bound(5);
92 assert(r == m.begin());
93 r = m.lower_bound(7);
94 assert(r == next(m.begin()));
95 r = m.lower_bound(9);
96 assert(r == next(m.begin(), 2));
97 r = m.lower_bound(11);
98 assert(r == next(m.begin(), 3));
99 r = m.lower_bound(13);
100 assert(r == next(m.begin(), 4));
101 r = m.lower_bound(15);
102 assert(r == next(m.begin(), 5));
103 r = m.lower_bound(17);
104 assert(r == next(m.begin(), 6));
105 r = m.lower_bound(19);
106 assert(r == next(m.begin(), 7));
107 r = m.lower_bound(4);
108 assert(r == next(m.begin(), 0));
109 r = m.lower_bound(6);
110 assert(r == next(m.begin(), 1));
111 r = m.lower_bound(8);
112 assert(r == next(m.begin(), 2));
113 r = m.lower_bound(10);
114 assert(r == next(m.begin(), 3));
115 r = m.lower_bound(12);
116 assert(r == next(m.begin(), 4));
117 r = m.lower_bound(14);
118 assert(r == next(m.begin(), 5));
119 r = m.lower_bound(16);
120 assert(r == next(m.begin(), 6));
121 r = m.lower_bound(18);
122 assert(r == next(m.begin(), 7));
123 r = m.lower_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.lower_bound(5);
146 assert(r == m.begin());
147 r = m.lower_bound(7);
148 assert(r == next(m.begin()));
149 r = m.lower_bound(9);
150 assert(r == next(m.begin(), 2));
151 r = m.lower_bound(11);
152 assert(r == next(m.begin(), 3));
153 r = m.lower_bound(13);
154 assert(r == next(m.begin(), 4));
155 r = m.lower_bound(15);
156 assert(r == next(m.begin(), 5));
157 r = m.lower_bound(17);
158 assert(r == next(m.begin(), 6));
159 r = m.lower_bound(19);
160 assert(r == next(m.begin(), 7));
161 r = m.lower_bound(4);
162 assert(r == next(m.begin(), 0));
163 r = m.lower_bound(6);
164 assert(r == next(m.begin(), 1));
165 r = m.lower_bound(8);
166 assert(r == next(m.begin(), 2));
167 r = m.lower_bound(10);
168 assert(r == next(m.begin(), 3));
169 r = m.lower_bound(12);
170 assert(r == next(m.begin(), 4));
171 r = m.lower_bound(14);
172 assert(r == next(m.begin(), 5));
173 r = m.lower_bound(16);
174 assert(r == next(m.begin(), 6));
175 r = m.lower_bound(18);
176 assert(r == next(m.begin(), 7));
177 r = m.lower_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.lower_bound(5);
195 assert(r == m.begin());
196 r = m.lower_bound(7);
197 assert(r == next(m.begin()));
198 r = m.lower_bound(9);
199 assert(r == next(m.begin(), 2));
200 r = m.lower_bound(11);
201 assert(r == next(m.begin(), 3));
202 r = m.lower_bound(13);
203 assert(r == next(m.begin(), 4));
204 r = m.lower_bound(15);
205 assert(r == next(m.begin(), 5));
206 r = m.lower_bound(17);
207 assert(r == next(m.begin(), 6));
208 r = m.lower_bound(19);
209 assert(r == next(m.begin(), 7));
210 r = m.lower_bound(4);
211 assert(r == next(m.begin(), 0));
212 r = m.lower_bound(6);
213 assert(r == next(m.begin(), 1));
214 r = m.lower_bound(8);
215 assert(r == next(m.begin(), 2));
216 r = m.lower_bound(10);
217 assert(r == next(m.begin(), 3));
218 r = m.lower_bound(12);
219 assert(r == next(m.begin(), 4));
220 r = m.lower_bound(14);
221 assert(r == next(m.begin(), 5));
222 r = m.lower_bound(16);
223 assert(r == next(m.begin(), 6));
224 r = m.lower_bound(18);
225 assert(r == next(m.begin(), 7));
226 r = m.lower_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
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.lower_bound(5);
250 assert(r == m.begin());
251 r = m.lower_bound(7);
252 assert(r == next(m.begin()));
253 r = m.lower_bound(9);
254 assert(r == next(m.begin(), 2));
255 r = m.lower_bound(11);
256 assert(r == next(m.begin(), 3));
257 r = m.lower_bound(13);
258 assert(r == next(m.begin(), 4));
259 r = m.lower_bound(15);
260 assert(r == next(m.begin(), 5));
261 r = m.lower_bound(17);
262 assert(r == next(m.begin(), 6));
263 r = m.lower_bound(19);
264 assert(r == next(m.begin(), 7));
265 r = m.lower_bound(4);
266 assert(r == next(m.begin(), 0));
267 r = m.lower_bound(6);
268 assert(r == next(m.begin(), 1));
269 r = m.lower_bound(8);
270 assert(r == next(m.begin(), 2));
271 r = m.lower_bound(10);
272 assert(r == next(m.begin(), 3));
273 r = m.lower_bound(12);
274 assert(r == next(m.begin(), 4));
275 r = m.lower_bound(14);
276 assert(r == next(m.begin(), 5));
277 r = m.lower_bound(16);
278 assert(r == next(m.begin(), 6));
279 r = m.lower_bound(18);
280 assert(r == next(m.begin(), 7));
281 r = m.lower_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.lower_bound(5);
301 assert(r == m.begin());
302 r = m.lower_bound(7);
303 assert(r == next(m.begin()));
304 r = m.lower_bound(9);
305 assert(r == next(m.begin(), 2));
306 r = m.lower_bound(11);
307 assert(r == next(m.begin(), 3));
308 r = m.lower_bound(13);
309 assert(r == next(m.begin(), 4));
310 r = m.lower_bound(15);
311 assert(r == next(m.begin(), 5));
312 r = m.lower_bound(17);
313 assert(r == next(m.begin(), 6));
314 r = m.lower_bound(19);
315 assert(r == next(m.begin(), 7));
316 r = m.lower_bound(4);
317 assert(r == next(m.begin(), 0));
318 r = m.lower_bound(6);
319 assert(r == next(m.begin(), 1));
320 r = m.lower_bound(8);
321 assert(r == next(m.begin(), 2));
322 r = m.lower_bound(10);
323 assert(r == next(m.begin(), 3));
324 r = m.lower_bound(12);
325 assert(r == next(m.begin(), 4));
326 r = m.lower_bound(14);
327 assert(r == next(m.begin(), 5));
328 r = m.lower_bound(16);
329 assert(r == next(m.begin(), 6));
330 r = m.lower_bound(18);
331 assert(r == next(m.begin(), 7));
332 r = m.lower_bound(20);
333 assert(r == next(m.begin(), 8));
334 }
335 #endif
336 }
337