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 // <deque> 11 12 // iterator erase(const_iterator f, const_iterator l) 13 14 // Erasing items from the beginning or the end of a deque shall not invalidate iterators 15 // to items that were not erased. 16 17 18 #include <deque> 19 #include <cstdint> 20 #include <cassert> 21 22 template <typename C> del_at_start(C c,size_t num)23void del_at_start(C c, size_t num) 24 { 25 typename C::iterator first = c.begin(); 26 typename C::iterator last = first + num; 27 typename C::iterator it1 = last; 28 typename C::iterator it2 = c.end() - 1; 29 30 c.erase (first, last); 31 32 typename C::iterator it3 = c.begin(); 33 typename C::iterator it4 = c.end() - 1; 34 assert( it1 == it3); 35 assert( *it1 == *it3); 36 assert(&*it1 == &*it3); 37 assert( it2 == it4); 38 assert( *it2 == *it4); 39 assert(&*it2 == &*it4); 40 } 41 42 template <typename C> del_at_end(C c,size_t num)43void del_at_end(C c, size_t num) 44 { 45 typename C::iterator last = c.end(); 46 typename C::iterator first = last - num; 47 typename C::iterator it1 = c.begin(); 48 typename C::iterator it2 = first - 1; 49 50 c.erase (first, last); 51 52 typename C::iterator it3 = c.begin(); 53 typename C::iterator it4 = c.end() - 1; 54 assert( it1 == it3); 55 assert( *it1 == *it3); 56 assert(&*it1 == &*it3); 57 assert( it2 == it4); 58 assert( *it2 == *it4); 59 assert(&*it2 == &*it4); 60 } 61 62 main()63int main() 64 { 65 std::deque<int> queue; 66 for (int i = 0; i < 20; ++i) 67 queue.push_back(i); 68 69 while (queue.size() > 1) 70 { 71 for (size_t i = 1; i < queue.size(); ++i) 72 { 73 del_at_start(queue, i); 74 del_at_end (queue, i); 75 } 76 queue.pop_back(); 77 } 78 } 79