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// <unordered_map>
11
12// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
13//           class Alloc = allocator<pair<const Key, T>>>
14// class unordered_multimap
15
16// size_type erase(const key_type& k);
17
18#include <unordered_map>
19#include <string>
20#include <cassert>
21
22#include "min_allocator.h"
23
24#if __cplusplus >= 201103L
25template <typename Unordered>
26bool only_deletions ( const Unordered &whole, const Unordered &part ) {
27    typename Unordered::const_iterator w = whole.begin();
28    typename Unordered::const_iterator p = part.begin();
29
30    while ( w != whole.end () && p != part.end()) {
31        if ( *w == *p )
32            p++;
33        w++;
34        }
35
36    return p == part.end();
37}
38#endif
39
40int main()
41{
42    {
43        typedef std::unordered_multimap<int, std::string> C;
44        typedef std::pair<int, std::string> P;
45        P a[] =
46        {
47            P(1, "one"),
48            P(2, "two"),
49            P(3, "three"),
50            P(4, "four"),
51            P(1, "four"),
52            P(2, "four"),
53        };
54        C c(a, a + sizeof(a)/sizeof(a[0]));
55        assert(c.erase(5) == 0);
56        assert(c.size() == 6);
57        typedef std::pair<C::const_iterator, C::const_iterator> Eq;
58        Eq eq = c.equal_range(1);
59        assert(std::distance(eq.first, eq.second) == 2);
60        C::const_iterator k = eq.first;
61        assert(k->first == 1);
62        assert(k->second == "one");
63        ++k;
64        assert(k->first == 1);
65        assert(k->second == "four");
66        eq = c.equal_range(2);
67        assert(std::distance(eq.first, eq.second) == 2);
68        k = eq.first;
69        assert(k->first == 2);
70        assert(k->second == "two");
71        ++k;
72        assert(k->first == 2);
73        assert(k->second == "four");
74        eq = c.equal_range(3);
75        assert(std::distance(eq.first, eq.second) == 1);
76        k = eq.first;
77        assert(k->first == 3);
78        assert(k->second == "three");
79        eq = c.equal_range(4);
80        assert(std::distance(eq.first, eq.second) == 1);
81        k = eq.first;
82        assert(k->first == 4);
83        assert(k->second == "four");
84        assert(std::distance(c.begin(), c.end()) == c.size());
85        assert(std::distance(c.cbegin(), c.cend()) == c.size());
86
87        assert(c.erase(2) == 2);
88        assert(c.size() == 4);
89        eq = c.equal_range(1);
90        assert(std::distance(eq.first, eq.second) == 2);
91        k = eq.first;
92        assert(k->first == 1);
93        assert(k->second == "one");
94        ++k;
95        assert(k->first == 1);
96        assert(k->second == "four");
97        eq = c.equal_range(3);
98        assert(std::distance(eq.first, eq.second) == 1);
99        k = eq.first;
100        assert(k->first == 3);
101        assert(k->second == "three");
102        eq = c.equal_range(4);
103        assert(std::distance(eq.first, eq.second) == 1);
104        k = eq.first;
105        assert(k->first == 4);
106        assert(k->second == "four");
107        assert(std::distance(c.begin(), c.end()) == c.size());
108        assert(std::distance(c.cbegin(), c.cend()) == c.size());
109
110        assert(c.erase(2) == 0);
111        assert(c.size() == 4);
112        eq = c.equal_range(1);
113        assert(std::distance(eq.first, eq.second) == 2);
114        k = eq.first;
115        assert(k->first == 1);
116        assert(k->second == "one");
117        ++k;
118        assert(k->first == 1);
119        assert(k->second == "four");
120        eq = c.equal_range(3);
121        assert(std::distance(eq.first, eq.second) == 1);
122        k = eq.first;
123        assert(k->first == 3);
124        assert(k->second == "three");
125        eq = c.equal_range(4);
126        assert(std::distance(eq.first, eq.second) == 1);
127        k = eq.first;
128        assert(k->first == 4);
129        assert(k->second == "four");
130        assert(std::distance(c.begin(), c.end()) == c.size());
131        assert(std::distance(c.cbegin(), c.cend()) == c.size());
132
133        assert(c.erase(4) == 1);
134        assert(c.size() == 3);
135        eq = c.equal_range(1);
136        assert(std::distance(eq.first, eq.second) == 2);
137        k = eq.first;
138        assert(k->first == 1);
139        assert(k->second == "one");
140        ++k;
141        assert(k->first == 1);
142        assert(k->second == "four");
143        eq = c.equal_range(3);
144        assert(std::distance(eq.first, eq.second) == 1);
145        k = eq.first;
146        assert(k->first == 3);
147        assert(k->second == "three");
148        assert(std::distance(c.begin(), c.end()) == c.size());
149        assert(std::distance(c.cbegin(), c.cend()) == c.size());
150
151        assert(c.erase(4) == 0);
152        assert(c.size() == 3);
153        eq = c.equal_range(1);
154        assert(std::distance(eq.first, eq.second) == 2);
155        k = eq.first;
156        assert(k->first == 1);
157        assert(k->second == "one");
158        ++k;
159        assert(k->first == 1);
160        assert(k->second == "four");
161        eq = c.equal_range(3);
162        assert(std::distance(eq.first, eq.second) == 1);
163        k = eq.first;
164        assert(k->first == 3);
165        assert(k->second == "three");
166        assert(std::distance(c.begin(), c.end()) == c.size());
167        assert(std::distance(c.cbegin(), c.cend()) == c.size());
168
169        assert(c.erase(1) == 2);
170        assert(c.size() == 1);
171        eq = c.equal_range(3);
172        assert(std::distance(eq.first, eq.second) == 1);
173        k = eq.first;
174        assert(k->first == 3);
175        assert(k->second == "three");
176        assert(std::distance(c.begin(), c.end()) == c.size());
177        assert(std::distance(c.cbegin(), c.cend()) == c.size());
178
179        assert(c.erase(1) == 0);
180        assert(c.size() == 1);
181        eq = c.equal_range(3);
182        assert(std::distance(eq.first, eq.second) == 1);
183        k = eq.first;
184        assert(k->first == 3);
185        assert(k->second == "three");
186        assert(std::distance(c.begin(), c.end()) == c.size());
187        assert(std::distance(c.cbegin(), c.cend()) == c.size());
188
189        assert(c.erase(3) == 1);
190        assert(c.size() == 0);
191        eq = c.equal_range(3);
192        assert(std::distance(eq.first, eq.second) == 0);
193        assert(std::distance(c.begin(), c.end()) == c.size());
194        assert(std::distance(c.cbegin(), c.cend()) == c.size());
195
196        assert(c.erase(3) == 0);
197        assert(c.size() == 0);
198        eq = c.equal_range(3);
199        assert(std::distance(eq.first, eq.second) == 0);
200        assert(std::distance(c.begin(), c.end()) == c.size());
201        assert(std::distance(c.cbegin(), c.cend()) == c.size());
202    }
203#if __cplusplus >= 201103L
204    {
205        typedef std::unordered_multimap<int, std::string, std::hash<int>, std::equal_to<int>,
206                            min_allocator<std::pair<const int, std::string>>> C;
207        typedef std::pair<int, std::string> P;
208        P a[] =
209        {
210            P(1, "one"),
211            P(2, "two"),
212            P(3, "three"),
213            P(4, "four"),
214            P(1, "four"),
215            P(2, "four"),
216        };
217        C c(a, a + sizeof(a)/sizeof(a[0]));
218        assert(c.erase(5) == 0);
219        assert(c.size() == 6);
220        typedef std::pair<C::const_iterator, C::const_iterator> Eq;
221        Eq eq = c.equal_range(1);
222        assert(std::distance(eq.first, eq.second) == 2);
223        C::const_iterator k = eq.first;
224        assert(k->first == 1);
225        assert(k->second == "one");
226        ++k;
227        assert(k->first == 1);
228        assert(k->second == "four");
229        eq = c.equal_range(2);
230        assert(std::distance(eq.first, eq.second) == 2);
231        k = eq.first;
232        assert(k->first == 2);
233        assert(k->second == "two");
234        ++k;
235        assert(k->first == 2);
236        assert(k->second == "four");
237        eq = c.equal_range(3);
238        assert(std::distance(eq.first, eq.second) == 1);
239        k = eq.first;
240        assert(k->first == 3);
241        assert(k->second == "three");
242        eq = c.equal_range(4);
243        assert(std::distance(eq.first, eq.second) == 1);
244        k = eq.first;
245        assert(k->first == 4);
246        assert(k->second == "four");
247        assert(std::distance(c.begin(), c.end()) == c.size());
248        assert(std::distance(c.cbegin(), c.cend()) == c.size());
249
250        assert(c.erase(2) == 2);
251        assert(c.size() == 4);
252        eq = c.equal_range(1);
253        assert(std::distance(eq.first, eq.second) == 2);
254        k = eq.first;
255        assert(k->first == 1);
256        assert(k->second == "one");
257        ++k;
258        assert(k->first == 1);
259        assert(k->second == "four");
260        eq = c.equal_range(3);
261        assert(std::distance(eq.first, eq.second) == 1);
262        k = eq.first;
263        assert(k->first == 3);
264        assert(k->second == "three");
265        eq = c.equal_range(4);
266        assert(std::distance(eq.first, eq.second) == 1);
267        k = eq.first;
268        assert(k->first == 4);
269        assert(k->second == "four");
270        assert(std::distance(c.begin(), c.end()) == c.size());
271        assert(std::distance(c.cbegin(), c.cend()) == c.size());
272
273        assert(c.erase(2) == 0);
274        assert(c.size() == 4);
275        eq = c.equal_range(1);
276        assert(std::distance(eq.first, eq.second) == 2);
277        k = eq.first;
278        assert(k->first == 1);
279        assert(k->second == "one");
280        ++k;
281        assert(k->first == 1);
282        assert(k->second == "four");
283        eq = c.equal_range(3);
284        assert(std::distance(eq.first, eq.second) == 1);
285        k = eq.first;
286        assert(k->first == 3);
287        assert(k->second == "three");
288        eq = c.equal_range(4);
289        assert(std::distance(eq.first, eq.second) == 1);
290        k = eq.first;
291        assert(k->first == 4);
292        assert(k->second == "four");
293        assert(std::distance(c.begin(), c.end()) == c.size());
294        assert(std::distance(c.cbegin(), c.cend()) == c.size());
295
296        assert(c.erase(4) == 1);
297        assert(c.size() == 3);
298        eq = c.equal_range(1);
299        assert(std::distance(eq.first, eq.second) == 2);
300        k = eq.first;
301        assert(k->first == 1);
302        assert(k->second == "one");
303        ++k;
304        assert(k->first == 1);
305        assert(k->second == "four");
306        eq = c.equal_range(3);
307        assert(std::distance(eq.first, eq.second) == 1);
308        k = eq.first;
309        assert(k->first == 3);
310        assert(k->second == "three");
311        assert(std::distance(c.begin(), c.end()) == c.size());
312        assert(std::distance(c.cbegin(), c.cend()) == c.size());
313
314        assert(c.erase(4) == 0);
315        assert(c.size() == 3);
316        eq = c.equal_range(1);
317        assert(std::distance(eq.first, eq.second) == 2);
318        k = eq.first;
319        assert(k->first == 1);
320        assert(k->second == "one");
321        ++k;
322        assert(k->first == 1);
323        assert(k->second == "four");
324        eq = c.equal_range(3);
325        assert(std::distance(eq.first, eq.second) == 1);
326        k = eq.first;
327        assert(k->first == 3);
328        assert(k->second == "three");
329        assert(std::distance(c.begin(), c.end()) == c.size());
330        assert(std::distance(c.cbegin(), c.cend()) == c.size());
331
332        assert(c.erase(1) == 2);
333        assert(c.size() == 1);
334        eq = c.equal_range(3);
335        assert(std::distance(eq.first, eq.second) == 1);
336        k = eq.first;
337        assert(k->first == 3);
338        assert(k->second == "three");
339        assert(std::distance(c.begin(), c.end()) == c.size());
340        assert(std::distance(c.cbegin(), c.cend()) == c.size());
341
342        assert(c.erase(1) == 0);
343        assert(c.size() == 1);
344        eq = c.equal_range(3);
345        assert(std::distance(eq.first, eq.second) == 1);
346        k = eq.first;
347        assert(k->first == 3);
348        assert(k->second == "three");
349        assert(std::distance(c.begin(), c.end()) == c.size());
350        assert(std::distance(c.cbegin(), c.cend()) == c.size());
351
352        assert(c.erase(3) == 1);
353        assert(c.size() == 0);
354        eq = c.equal_range(3);
355        assert(std::distance(eq.first, eq.second) == 0);
356        assert(std::distance(c.begin(), c.end()) == c.size());
357        assert(std::distance(c.cbegin(), c.cend()) == c.size());
358
359        assert(c.erase(3) == 0);
360        assert(c.size() == 0);
361        eq = c.equal_range(3);
362        assert(std::distance(eq.first, eq.second) == 0);
363        assert(std::distance(c.begin(), c.end()) == c.size());
364        assert(std::distance(c.cbegin(), c.cend()) == c.size());
365    }
366    {
367    typedef std::unordered_multimap<int, int> C;
368    C m, m2;
369    for ( int i = 0; i < 10; ++i ) {
370        for (int j = 0; j < 2; ++j ) {
371            m.insert (std::make_pair(i,j));
372            m2.insert(std::make_pair(i,j));
373            }
374        }
375
376    C::iterator i = m2.begin();
377    int ctr = 0;
378    while (i != m2.end()) {
379        if (ctr++ % 2 == 0)
380            m2.erase(i++);
381        else
382            ++i;
383        }
384
385    assert (only_deletions (m, m2));
386    }
387#endif
388}
389