1bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 2bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 3f5256e16dfc425c1d466f6308d4026d529ce9e0bHoward Hinnant// The LLVM Compiler Infrastructure 4bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 5b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// This file is dual licensed under the MIT and the University of Illinois Open 6b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// Source Licenses. See LICENSE.TXT for details. 7bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 8bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 9bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 10bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// <unordered_map> 11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 12bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 13bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// class Alloc = allocator<pair<const Key, T>>> 14bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// class unordered_map 15bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 16bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// size_type erase(const key_type& k); 17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <unordered_map> 19bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <string> 20bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <cassert> 21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 22061d0cc4db18d17bf01ed14c5db0be098205bd47Marshall Clow#include "min_allocator.h" 237a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 246dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow#if __cplusplus >= 201103L 256dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clowtemplate <typename Unordered> 266dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clowbool only_deletions ( const Unordered &whole, const Unordered &part ) { 276dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow typename Unordered::const_iterator w = whole.begin(); 286dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow typename Unordered::const_iterator p = part.begin(); 296dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow 306dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow while ( w != whole.end () && p != part.end()) { 316dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow if ( *w == *p ) 326dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow p++; 336dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow w++; 346dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow } 356dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow 366dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow return p == part.end(); 376dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow} 386dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow#endif 396dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow 406dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow 41bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantint main() 42bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 43bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 44bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant typedef std::unordered_map<int, std::string> C; 45bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant typedef std::pair<int, std::string> P; 46bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P a[] = 47bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 48bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P(1, "one"), 49bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P(2, "two"), 50bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P(3, "three"), 51bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P(4, "four"), 52bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P(1, "four"), 53bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant P(2, "four"), 54bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant }; 55bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant C c(a, a + sizeof(a)/sizeof(a[0])); 56bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(5) == 0); 57bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 4); 58bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(1) == "one"); 59bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(2) == "two"); 60bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 61bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(4) == "four"); 62bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 63bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(2) == 1); 64bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 3); 65bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(1) == "one"); 66bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 67bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(4) == "four"); 68bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 69bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(2) == 0); 70bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 3); 71bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(1) == "one"); 72bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 73bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(4) == "four"); 74bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 75bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(4) == 1); 76bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 2); 77bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(1) == "one"); 78bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 79bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 80bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(4) == 0); 81bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 2); 82bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(1) == "one"); 83bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 84bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 85bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(1) == 1); 86bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 1); 87bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 88bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 89bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(1) == 0); 90bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 1); 91bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.at(3) == "three"); 92bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 93bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(3) == 1); 94bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 0); 95bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 96bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.erase(3) == 0); 97bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(c.size() == 0); 98bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 997a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant#if __cplusplus >= 201103L 1007a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant { 1017a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, 1027a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant min_allocator<std::pair<const int, std::string>>> C; 1037a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant typedef std::pair<int, std::string> P; 1047a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P a[] = 1057a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant { 1067a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P(1, "one"), 1077a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P(2, "two"), 1087a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P(3, "three"), 1097a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P(4, "four"), 1107a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P(1, "four"), 1117a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant P(2, "four"), 1127a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant }; 1137a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant C c(a, a + sizeof(a)/sizeof(a[0])); 1147a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(5) == 0); 1157a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 4); 1167a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(1) == "one"); 1177a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(2) == "two"); 1187a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1197a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(4) == "four"); 1207a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1217a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(2) == 1); 1227a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 3); 1237a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(1) == "one"); 1247a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1257a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(4) == "four"); 1267a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1277a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(2) == 0); 1287a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 3); 1297a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(1) == "one"); 1307a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1317a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(4) == "four"); 1327a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1337a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(4) == 1); 1347a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 2); 1357a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(1) == "one"); 1367a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1377a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1387a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(4) == 0); 1397a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 2); 1407a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(1) == "one"); 1417a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1427a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1437a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(1) == 1); 1447a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 1); 1457a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1467a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1477a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(1) == 0); 1487a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 1); 1497a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.at(3) == "three"); 1507a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1517a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(3) == 1); 1527a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 0); 1537a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant 1547a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.erase(3) == 0); 1557a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant assert(c.size() == 0); 1567a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant } 1576dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow { 1586dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow typedef std::unordered_map<int, int> C; 1596dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow C m, m2; 1606dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow for ( int i = 0; i < 10; ++i ) { 1616dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow m[i] = i; 1626dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow m2[i] = i; 1636dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow } 1646dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow 1656dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow C::iterator i = m2.begin(); 1666dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow int ctr = 0; 1676dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow while (i != m2.end()) { 1686dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow if (ctr++ % 2 == 0) 1696dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow m2.erase(i++); 1706dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow else 1716dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow ++i; 1726dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow } 1736dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow 1746dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow assert (only_deletions (m, m2)); 1756dbaaa99a880f356277525c8630491b80d6d2e56Marshall Clow } 1767a6b7cedcb3359ad7d77e355b02ab982d9d2b25bHoward Hinnant#endif 177bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 178