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