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// <set> 11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 12bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// class set 13bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 14bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// size_type erase(const key_type& k); 15bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 16bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <set> 17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <cassert> 18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 19061d0cc4db18d17bf01ed14c5db0be098205bd47Marshall Clow#include "min_allocator.h" 2070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantint main() 22bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 23bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 24bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant typedef std::set<int> M; 25bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant typedef int V; 26bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant typedef M::size_type I; 27bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant V ar[] = 28bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 29bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 1, 30bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 2, 31bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 3, 32bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 4, 33bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 5, 34bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 6, 35bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 7, 36bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 8 37bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant }; 38bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant M m(ar, ar + sizeof(ar)/sizeof(ar[0])); 39bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 8); 40bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant I i = m.erase(9); 41bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 8); 42bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 0); 43bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 1); 44bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 2); 45bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 2) == 3); 46bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 3) == 4); 47bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 4) == 5); 48bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 5) == 6); 49bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 6) == 7); 50bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 7) == 8); 51bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 52bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(4); 53bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 7); 54bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 55bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 1); 56bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 2); 57bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 2) == 3); 58bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 3) == 5); 59bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 4) == 6); 60bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 5) == 7); 61bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 6) == 8); 62bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 63bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(1); 64bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 6); 65bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 66bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 2); 67bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 3); 68bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 2) == 5); 69bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 3) == 6); 70bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 4) == 7); 71bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 5) == 8); 72bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 73bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(8); 74bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 5); 75bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 76bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 2); 77bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 3); 78bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 2) == 5); 79bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 3) == 6); 80bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 4) == 7); 81bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 82bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(3); 83bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 4); 84bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 85bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 2); 86bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 5); 87bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 2) == 6); 88bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 3) == 7); 89bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 90bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(6); 91bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 3); 92bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 93bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 2); 94bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 5); 95bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 2) == 7); 96bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 97bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(7); 98bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 2); 99bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 100bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 2); 101bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 1) == 5); 102bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 103bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(2); 104bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 1); 105bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 106bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(*next(m.begin(), 0) == 5); 107bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 108bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant i = m.erase(5); 109bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(m.size() == 0); 110bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(i == 1); 111bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 11270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant#if __cplusplus >= 201103L 11370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant { 11470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant typedef std::set<int, std::less<int>, min_allocator<int>> M; 11570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant typedef int V; 11670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant typedef M::size_type I; 11770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant V ar[] = 11870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant { 11970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 1, 12070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 2, 12170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 3, 12270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 4, 12370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 5, 12470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 6, 12570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 7, 12670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 8 12770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant }; 12870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant M m(ar, ar + sizeof(ar)/sizeof(ar[0])); 12970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 8); 13070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant I i = m.erase(9); 13170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 8); 13270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 0); 13370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 1); 13470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 2); 13570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 2) == 3); 13670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 3) == 4); 13770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 4) == 5); 13870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 5) == 6); 13970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 6) == 7); 14070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 7) == 8); 14170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 14270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(4); 14370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 7); 14470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 14570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 1); 14670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 2); 14770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 2) == 3); 14870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 3) == 5); 14970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 4) == 6); 15070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 5) == 7); 15170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 6) == 8); 15270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 15370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(1); 15470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 6); 15570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 15670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 2); 15770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 3); 15870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 2) == 5); 15970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 3) == 6); 16070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 4) == 7); 16170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 5) == 8); 16270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 16370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(8); 16470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 5); 16570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 16670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 2); 16770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 3); 16870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 2) == 5); 16970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 3) == 6); 17070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 4) == 7); 17170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 17270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(3); 17370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 4); 17470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 17570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 2); 17670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 5); 17770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 2) == 6); 17870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 3) == 7); 17970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 18070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(6); 18170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 3); 18270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 18370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 2); 18470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 5); 18570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 2) == 7); 18670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 18770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(7); 18870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 2); 18970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 19070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 2); 19170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 1) == 5); 19270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 19370342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(2); 19470342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 1); 19570342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 19670342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(*next(m.begin(), 0) == 5); 19770342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant 19870342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant i = m.erase(5); 19970342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(m.size() == 0); 20070342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant assert(i == 1); 20170342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant } 20270342b99e227912742972b754ad86e75c5d7eefbHoward Hinnant#endif 203bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 204