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
25 template <typename Unordered>
only_deletions(const Unordered & whole,const Unordered & part)26 bool 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
main()40 int 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