• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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