llvm-project

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
// <set>
10

11
// class set
12

13
//       iterator lower_bound(const key_type& k);
14
// const_iterator lower_bound(const key_type& k) const;
15

16
#include <set>
17
#include <cassert>
18

19
#include "test_macros.h"
20
#include "min_allocator.h"
21
#include "private_constructor.h"
22

23
int main(int, char**)
24
{
25
    {
26
    typedef int V;
27
    typedef std::set<int> M;
28
    {
29
        typedef M::iterator R;
30
        V ar[] =
31
        {
32
            5,
33
            7,
34
            9,
35
            11,
36
            13,
37
            15,
38
            17,
39
            19
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 == std::next(m.begin()));
46
        r = m.lower_bound(9);
47
        assert(r == std::next(m.begin(), 2));
48
        r = m.lower_bound(11);
49
        assert(r == std::next(m.begin(), 3));
50
        r = m.lower_bound(13);
51
        assert(r == std::next(m.begin(), 4));
52
        r = m.lower_bound(15);
53
        assert(r == std::next(m.begin(), 5));
54
        r = m.lower_bound(17);
55
        assert(r == std::next(m.begin(), 6));
56
        r = m.lower_bound(19);
57
        assert(r == std::next(m.begin(), 7));
58
        r = m.lower_bound(4);
59
        assert(r == std::next(m.begin(), 0));
60
        r = m.lower_bound(6);
61
        assert(r == std::next(m.begin(), 1));
62
        r = m.lower_bound(8);
63
        assert(r == std::next(m.begin(), 2));
64
        r = m.lower_bound(10);
65
        assert(r == std::next(m.begin(), 3));
66
        r = m.lower_bound(12);
67
        assert(r == std::next(m.begin(), 4));
68
        r = m.lower_bound(14);
69
        assert(r == std::next(m.begin(), 5));
70
        r = m.lower_bound(16);
71
        assert(r == std::next(m.begin(), 6));
72
        r = m.lower_bound(18);
73
        assert(r == std::next(m.begin(), 7));
74
        r = m.lower_bound(20);
75
        assert(r == std::next(m.begin(), 8));
76
    }
77
    {
78
        typedef M::const_iterator R;
79
        V ar[] =
80
        {
81
            5,
82
            7,
83
            9,
84
            11,
85
            13,
86
            15,
87
            17,
88
            19
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 == std::next(m.begin()));
95
        r = m.lower_bound(9);
96
        assert(r == std::next(m.begin(), 2));
97
        r = m.lower_bound(11);
98
        assert(r == std::next(m.begin(), 3));
99
        r = m.lower_bound(13);
100
        assert(r == std::next(m.begin(), 4));
101
        r = m.lower_bound(15);
102
        assert(r == std::next(m.begin(), 5));
103
        r = m.lower_bound(17);
104
        assert(r == std::next(m.begin(), 6));
105
        r = m.lower_bound(19);
106
        assert(r == std::next(m.begin(), 7));
107
        r = m.lower_bound(4);
108
        assert(r == std::next(m.begin(), 0));
109
        r = m.lower_bound(6);
110
        assert(r == std::next(m.begin(), 1));
111
        r = m.lower_bound(8);
112
        assert(r == std::next(m.begin(), 2));
113
        r = m.lower_bound(10);
114
        assert(r == std::next(m.begin(), 3));
115
        r = m.lower_bound(12);
116
        assert(r == std::next(m.begin(), 4));
117
        r = m.lower_bound(14);
118
        assert(r == std::next(m.begin(), 5));
119
        r = m.lower_bound(16);
120
        assert(r == std::next(m.begin(), 6));
121
        r = m.lower_bound(18);
122
        assert(r == std::next(m.begin(), 7));
123
        r = m.lower_bound(20);
124
        assert(r == std::next(m.begin(), 8));
125
    }
126
    }
127
#if TEST_STD_VER >= 11
128
    {
129
    typedef int V;
130
    typedef std::set<int, std::less<int>, min_allocator<int>> M;
131
    {
132
        typedef M::iterator R;
133
        V ar[] =
134
        {
135
            5,
136
            7,
137
            9,
138
            11,
139
            13,
140
            15,
141
            17,
142
            19
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 == std::next(m.begin()));
149
        r = m.lower_bound(9);
150
        assert(r == std::next(m.begin(), 2));
151
        r = m.lower_bound(11);
152
        assert(r == std::next(m.begin(), 3));
153
        r = m.lower_bound(13);
154
        assert(r == std::next(m.begin(), 4));
155
        r = m.lower_bound(15);
156
        assert(r == std::next(m.begin(), 5));
157
        r = m.lower_bound(17);
158
        assert(r == std::next(m.begin(), 6));
159
        r = m.lower_bound(19);
160
        assert(r == std::next(m.begin(), 7));
161
        r = m.lower_bound(4);
162
        assert(r == std::next(m.begin(), 0));
163
        r = m.lower_bound(6);
164
        assert(r == std::next(m.begin(), 1));
165
        r = m.lower_bound(8);
166
        assert(r == std::next(m.begin(), 2));
167
        r = m.lower_bound(10);
168
        assert(r == std::next(m.begin(), 3));
169
        r = m.lower_bound(12);
170
        assert(r == std::next(m.begin(), 4));
171
        r = m.lower_bound(14);
172
        assert(r == std::next(m.begin(), 5));
173
        r = m.lower_bound(16);
174
        assert(r == std::next(m.begin(), 6));
175
        r = m.lower_bound(18);
176
        assert(r == std::next(m.begin(), 7));
177
        r = m.lower_bound(20);
178
        assert(r == std::next(m.begin(), 8));
179
    }
180
    {
181
        typedef M::const_iterator R;
182
        V ar[] =
183
        {
184
            5,
185
            7,
186
            9,
187
            11,
188
            13,
189
            15,
190
            17,
191
            19
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 == std::next(m.begin()));
198
        r = m.lower_bound(9);
199
        assert(r == std::next(m.begin(), 2));
200
        r = m.lower_bound(11);
201
        assert(r == std::next(m.begin(), 3));
202
        r = m.lower_bound(13);
203
        assert(r == std::next(m.begin(), 4));
204
        r = m.lower_bound(15);
205
        assert(r == std::next(m.begin(), 5));
206
        r = m.lower_bound(17);
207
        assert(r == std::next(m.begin(), 6));
208
        r = m.lower_bound(19);
209
        assert(r == std::next(m.begin(), 7));
210
        r = m.lower_bound(4);
211
        assert(r == std::next(m.begin(), 0));
212
        r = m.lower_bound(6);
213
        assert(r == std::next(m.begin(), 1));
214
        r = m.lower_bound(8);
215
        assert(r == std::next(m.begin(), 2));
216
        r = m.lower_bound(10);
217
        assert(r == std::next(m.begin(), 3));
218
        r = m.lower_bound(12);
219
        assert(r == std::next(m.begin(), 4));
220
        r = m.lower_bound(14);
221
        assert(r == std::next(m.begin(), 5));
222
        r = m.lower_bound(16);
223
        assert(r == std::next(m.begin(), 6));
224
        r = m.lower_bound(18);
225
        assert(r == std::next(m.begin(), 7));
226
        r = m.lower_bound(20);
227
        assert(r == std::next(m.begin(), 8));
228
    }
229
    }
230
#endif
231
#if TEST_STD_VER > 11
232
    {
233
    typedef int V;
234
    typedef std::set<V, std::less<>> M;
235
    typedef M::iterator R;
236

237
    V ar[] =
238
    {
239
        5,
240
        7,
241
        9,
242
        11,
243
        13,
244
        15,
245
        17,
246
        19
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 == std::next(m.begin()));
253
    r = m.lower_bound(9);
254
    assert(r == std::next(m.begin(), 2));
255
    r = m.lower_bound(11);
256
    assert(r == std::next(m.begin(), 3));
257
    r = m.lower_bound(13);
258
    assert(r == std::next(m.begin(), 4));
259
    r = m.lower_bound(15);
260
    assert(r == std::next(m.begin(), 5));
261
    r = m.lower_bound(17);
262
    assert(r == std::next(m.begin(), 6));
263
    r = m.lower_bound(19);
264
    assert(r == std::next(m.begin(), 7));
265
    r = m.lower_bound(4);
266
    assert(r == std::next(m.begin(), 0));
267
    r = m.lower_bound(6);
268
    assert(r == std::next(m.begin(), 1));
269
    r = m.lower_bound(8);
270
    assert(r == std::next(m.begin(), 2));
271
    r = m.lower_bound(10);
272
    assert(r == std::next(m.begin(), 3));
273
    r = m.lower_bound(12);
274
    assert(r == std::next(m.begin(), 4));
275
    r = m.lower_bound(14);
276
    assert(r == std::next(m.begin(), 5));
277
    r = m.lower_bound(16);
278
    assert(r == std::next(m.begin(), 6));
279
    r = m.lower_bound(18);
280
    assert(r == std::next(m.begin(), 7));
281
    r = m.lower_bound(20);
282
    assert(r == std::next(m.begin(), 8));
283
    }
284

285
    {
286
    typedef PrivateConstructor V;
287
    typedef std::set<V, std::less<>> M;
288
    typedef M::iterator R;
289

290
    M m;
291
    m.insert ( V::make ( 5 ));
292
    m.insert ( V::make ( 7 ));
293
    m.insert ( V::make ( 9 ));
294
    m.insert ( V::make ( 11 ));
295
    m.insert ( V::make ( 13 ));
296
    m.insert ( V::make ( 15 ));
297
    m.insert ( V::make ( 17 ));
298
    m.insert ( V::make ( 19 ));
299

300
    R r = m.lower_bound(5);
301
    assert(r == m.begin());
302
    r = m.lower_bound(7);
303
    assert(r == std::next(m.begin()));
304
    r = m.lower_bound(9);
305
    assert(r == std::next(m.begin(), 2));
306
    r = m.lower_bound(11);
307
    assert(r == std::next(m.begin(), 3));
308
    r = m.lower_bound(13);
309
    assert(r == std::next(m.begin(), 4));
310
    r = m.lower_bound(15);
311
    assert(r == std::next(m.begin(), 5));
312
    r = m.lower_bound(17);
313
    assert(r == std::next(m.begin(), 6));
314
    r = m.lower_bound(19);
315
    assert(r == std::next(m.begin(), 7));
316
    r = m.lower_bound(4);
317
    assert(r == std::next(m.begin(), 0));
318
    r = m.lower_bound(6);
319
    assert(r == std::next(m.begin(), 1));
320
    r = m.lower_bound(8);
321
    assert(r == std::next(m.begin(), 2));
322
    r = m.lower_bound(10);
323
    assert(r == std::next(m.begin(), 3));
324
    r = m.lower_bound(12);
325
    assert(r == std::next(m.begin(), 4));
326
    r = m.lower_bound(14);
327
    assert(r == std::next(m.begin(), 5));
328
    r = m.lower_bound(16);
329
    assert(r == std::next(m.begin(), 6));
330
    r = m.lower_bound(18);
331
    assert(r == std::next(m.begin(), 7));
332
    r = m.lower_bound(20);
333
    assert(r == std::next(m.begin(), 8));
334
    }
335
#endif
336

337

338
  return 0;
339
}
340