1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // <map>
10 
11 // class map
12 
13 //       iterator lower_bound(const key_type& k);
14 // const_iterator lower_bound(const key_type& k) const;
15 
16 #include <map>
17 #include <cassert>
CheckCommonReferenceWith()18 
19 #include "test_macros.h"
20 #include "min_allocator.h"
21 #include "private_constructor.h"
22 #include "is_transparent.h"
23 
24 int main(int, char**)
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 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.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 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 
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   return 0;
374 }
375