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