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 multimap
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
23int main()
24{
25    typedef std::pair<const int, double> V;
26    {
27    typedef std::multimap<int, double> M;
28    {
29        typedef M::iterator R;
30        V ar[] =
31        {
32            V(5, 1),
33            V(5, 2),
34            V(5, 3),
35            V(7, 1),
36            V(7, 2),
37            V(7, 3),
38            V(9, 1),
39            V(9, 2),
40            V(9, 3)
41        };
42        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
43        R r = m.lower_bound(4);
44        assert(r == m.begin());
45        r = m.lower_bound(5);
46        assert(r == m.begin());
47        r = m.lower_bound(6);
48        assert(r == next(m.begin(), 3));
49        r = m.lower_bound(7);
50        assert(r == next(m.begin(), 3));
51        r = m.lower_bound(8);
52        assert(r == next(m.begin(), 6));
53        r = m.lower_bound(9);
54        assert(r == next(m.begin(), 6));
55        r = m.lower_bound(10);
56        assert(r == m.end());
57    }
58    {
59        typedef M::const_iterator R;
60        V ar[] =
61        {
62            V(5, 1),
63            V(5, 2),
64            V(5, 3),
65            V(7, 1),
66            V(7, 2),
67            V(7, 3),
68            V(9, 1),
69            V(9, 2),
70            V(9, 3)
71        };
72        const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
73        R r = m.lower_bound(4);
74        assert(r == m.begin());
75        r = m.lower_bound(5);
76        assert(r == m.begin());
77        r = m.lower_bound(6);
78        assert(r == next(m.begin(), 3));
79        r = m.lower_bound(7);
80        assert(r == next(m.begin(), 3));
81        r = m.lower_bound(8);
82        assert(r == next(m.begin(), 6));
83        r = m.lower_bound(9);
84        assert(r == next(m.begin(), 6));
85        r = m.lower_bound(10);
86        assert(r == m.end());
87    }
88    }
89#if __cplusplus >= 201103L
90    {
91    typedef std::multimap<int, double, std::less<int>, min_allocator<std::pair<const int, double>>> M;
92    {
93        typedef M::iterator R;
94        V ar[] =
95        {
96            V(5, 1),
97            V(5, 2),
98            V(5, 3),
99            V(7, 1),
100            V(7, 2),
101            V(7, 3),
102            V(9, 1),
103            V(9, 2),
104            V(9, 3)
105        };
106        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
107        R r = m.lower_bound(4);
108        assert(r == m.begin());
109        r = m.lower_bound(5);
110        assert(r == m.begin());
111        r = m.lower_bound(6);
112        assert(r == next(m.begin(), 3));
113        r = m.lower_bound(7);
114        assert(r == next(m.begin(), 3));
115        r = m.lower_bound(8);
116        assert(r == next(m.begin(), 6));
117        r = m.lower_bound(9);
118        assert(r == next(m.begin(), 6));
119        r = m.lower_bound(10);
120        assert(r == m.end());
121    }
122    {
123        typedef M::const_iterator R;
124        V ar[] =
125        {
126            V(5, 1),
127            V(5, 2),
128            V(5, 3),
129            V(7, 1),
130            V(7, 2),
131            V(7, 3),
132            V(9, 1),
133            V(9, 2),
134            V(9, 3)
135        };
136        const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
137        R r = m.lower_bound(4);
138        assert(r == m.begin());
139        r = m.lower_bound(5);
140        assert(r == m.begin());
141        r = m.lower_bound(6);
142        assert(r == next(m.begin(), 3));
143        r = m.lower_bound(7);
144        assert(r == next(m.begin(), 3));
145        r = m.lower_bound(8);
146        assert(r == next(m.begin(), 6));
147        r = m.lower_bound(9);
148        assert(r == next(m.begin(), 6));
149        r = m.lower_bound(10);
150        assert(r == m.end());
151    }
152    }
153#endif
154#if _LIBCPP_STD_VER > 11
155    {
156    typedef std::pair<const int, double> V;
157    typedef std::multimap<int, double, std::less<>> M;
158    typedef M::iterator R;
159    V ar[] =
160    {
161        V(5, 1),
162        V(5, 2),
163        V(5, 3),
164        V(7, 1),
165        V(7, 2),
166        V(7, 3),
167        V(9, 1),
168        V(9, 2),
169        V(9, 3)
170    };
171    M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
172    R r = m.lower_bound(4);
173    assert(r == m.begin());
174    r = m.lower_bound(5);
175    assert(r == m.begin());
176    r = m.lower_bound(6);
177    assert(r == next(m.begin(), 3));
178    r = m.lower_bound(7);
179    assert(r == next(m.begin(), 3));
180    r = m.lower_bound(8);
181    assert(r == next(m.begin(), 6));
182    r = m.lower_bound(9);
183    assert(r == next(m.begin(), 6));
184    r = m.lower_bound(10);
185    assert(r == m.end());
186    }
187
188    {
189    typedef PrivateConstructor PC;
190    typedef std::multimap<PC, double, std::less<>> M;
191    typedef M::iterator R;
192
193    M m;
194    m.insert ( std::make_pair<PC, double> ( PC::make(5), 1 ));
195    m.insert ( std::make_pair<PC, double> ( PC::make(5), 2 ));
196    m.insert ( std::make_pair<PC, double> ( PC::make(5), 3 ));
197    m.insert ( std::make_pair<PC, double> ( PC::make(7), 1 ));
198    m.insert ( std::make_pair<PC, double> ( PC::make(7), 2 ));
199    m.insert ( std::make_pair<PC, double> ( PC::make(7), 3 ));
200    m.insert ( std::make_pair<PC, double> ( PC::make(9), 1 ));
201    m.insert ( std::make_pair<PC, double> ( PC::make(9), 2 ));
202    m.insert ( std::make_pair<PC, double> ( PC::make(9), 3 ));
203
204    R r = m.lower_bound(4);
205    assert(r == m.begin());
206    r = m.lower_bound(5);
207    assert(r == m.begin());
208    r = m.lower_bound(6);
209    assert(r == next(m.begin(), 3));
210    r = m.lower_bound(7);
211    assert(r == next(m.begin(), 3));
212    r = m.lower_bound(8);
213    assert(r == next(m.begin(), 6));
214    r = m.lower_bound(9);
215    assert(r == next(m.begin(), 6));
216    r = m.lower_bound(10);
217    assert(r == m.end());
218    }
219
220#endif
221}
222