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> 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 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
