Document number: N4009 Date: 2014-05-22 Project: Programming Language C++, Library Evolution Working Group Reply-to: Stephan T. Lavavej Uniform Container Erasure I. Introduction This is a proposal to add erase_if(container, pred), making it easier to eliminate unwanted elements correctly and efficiently. II. The Problem It's surprisingly difficult to eliminate unwanted elements from a container, given a predicate that distinguishes "bad" elements from "good" elements. One of the STL's major strengths is that all of its containers have similar interfaces - they have many functions in common and they follow the same conventions. When container interfaces vary, fundamental differences between their data structures are responsible. Even those differences can often be ignored, thanks to the STL's container-iterator-algorithm design. At first glance, it may appear that the containers have a uniform interface for erasure, which is true for single-element and range erasure. However, for the common task of erasing elements that are recognized by a given predicate, the containers have a highly non-uniform interface, filled with traps and pitfalls for the unwary. Trap #1: Repeated single-element erasure is terrible for the vector family. When novices are faced with this task, they usually attempt to call erase() in a loop. In addition to being easy to get wrong, this triggers quadratic complexity for vectors, deques, and basic_strings. The correct response is to use the erase-remove idiom, which is non-obvious and must be taught instead of discovered (it's called an "idiom" for a reason). Trap #2: The erase-remove idiom can suffer from silent typos. Observe: v.erase(remove_if(v.begin(), v.end(), pred), v.end()); // OK v.erase(remove_if(v.begin(), v.end(), pred)); // GOTCHA With this verbose idiom, forgetting to repeat v.end() produces code that will silently compile and misbehave at runtime by calling the single-element overload of erase() that takes one iterator. Trap #3: The erase-remove idiom isn't ideal for the list family. While the remove_if() algorithm takes ForwardIterators and compiles for lists and forward_lists, it requires MoveAssignable elements (25.3.8 [alg.remove]). There's actually a list::remove_if() member function that behaves differently (23.3.5.5 [list.ops]/15-18, and similarly for forward_list). This member function is confusingly named because it changes the list's size (unlike the non-member algorithm). Notably, the member function works with non-MoveAssignable elements, preserves iterators/pointers/references to the remaining elements, and doesn't throw exceptions (except from predicate invocation). Trap #4: The erase-remove idiom doesn't compile for ordered/unordered associative containers. That's because their keys are const. It's good that keys can't be modified in-place, because that would break the data structure's invariants, but the resulting diagnostics can be confusing to programmers who don't eat angle brackets and drink compiler errors for a living. I've seen at least two senior developers within Microsoft who were confused by this issue, and I can only imagine how novices must be suffering. Trap #5: For ordered/unordered associative containers, handwritten erase() loops must be used, but they're easy to get wrong. (Only list and forward_list have remove_if() member functions.) There are at least two ways to implement this incorrectly: erasing the node that you're standing on, and skipping nodes as a result of not paying enough attention to iterator incrementing. III. The Solution To solve this problem, we must provide uniform syntax that selects the proper semantics for each container. This proposal provides erase_if(container, pred), implemented with an overload for each container. Design Decision #1: Member versus non-member? We could provide this functionality through member functions, like how vector::shrink_to_fit() was added to supersede a verbose idiom. Member functions might be more discoverable, especially for users with autocompleting IDEs. However, basic_string is a cautionary tale of what happens to a class when it provides too many member functions that aren't fundamental services. More importantly, because list and forward_list already have remove_if() member functions, adding that to the other containers would increase consistency. But as previously noted, it's a confusing name because the member function alters the container's size while the non-member algorithm doesn't. The Standard Library has other confusingly-different members versus non-members - one example is non-member lower_bound() compiling for maps/sets while being much slower than member lower_bound(), and an even more pernicious example is good non-member getline() versus evil member getline(). I am reluctant to add to this problem, hence the non-member choice in this proposal. However, it could be argued that providing remove_if() member functions would cause the non-member algorithm to fall into deserved obscurity, so there would be little confusion in practice. I would be open to that approach if the LEWG strongly favors it. Design Decision #2: Naming? The Library currently uses two verbs, "erase" and "remove". Ignoring list/forward_list's relatively obscure member functions, "erase" always modifies container sizes, while "remove" never does. Since the ultimate goal of the functionality being considered here is to modify container sizes, that's a point in favor of "erase". Additionally, the Library currently contains no non-member functions named erase(), and nothing at all named erase_if(). (For completeness, remove_if(first, last, pred) could be unambiguously overloaded with remove_if(container, pred) - unambiguous to compilers, but perhaps not to humans.) Another name could be chosen, although good short names are hard to find. (I would favor eliminate_if() as an alternative, or perhaps discard_if().) Design Decision #3: Just predicates, or also values? This is related to naming. Providing eliminate(container, value) and eliminate_if(container, pred) would be perfectly acceptable. However, providing erase(container, value) in addition to erase_if(container, pred) would be problematic, and has therefore been avoided in this proposal. The problem is that the ordered/unordered associative containers have erase(key) member functions that perform efficient lookups. This could lead to confusion about erase(container, value)'s complexity. (It would have to be a linear scan, even for sets - erase(key) works with operator<() equivalence, but erase(container, value) would have to use operator==(), and they are not required to have any particular relationship.) In contrast, erase_if(container, pred) "sounds like" linear complexity (which it is), even for ordered/unordered associative containers. And of course, lambdas (especially C++14's generic lambdas) make it relatively easy to use erase_if() to eliminate all occurrences of a given value. Informally speaking (i.e. without hard data), I've found that having to erase all occurrences of a particular value is a much less common task than having to erase all elements that satisfy some condition. On the other hand, symmetry would be desirable, and it would prevent users from wondering why one flavor was missing. Additional note: These design decisions interact in one more way. If the LEWG wants to provide this functionality with member functions, in both predicate and value flavors, then a verb other than "erase" (due to erase(key) as previously mentioned) and "remove" should be chosen. The problem is that while list::remove_if() is perfectly fine, the signature of the value flavor is list::remove(const T&). That is, it doesn't work transparently with differing element and value types. In contrast, the non-member remove() algorithm has always worked with heterogeneous element and value types. Alternatively, we could keep the container.remove(value) and container.remove_if(pred) names, and simply change list/forward_list's behavior. That could affect the performance and (much less likely) the correctness of existing code, but we could probably get away with it. IV. Questions And Answers Q1. What's the impact on the Standard? A1. This proposal is a pure extension. It doesn't affect user code, except for adding a new name to namespace std. This proposal doesn't interact with any other proposals (it is concerned with runtime-resizable containers only, and dynarray isn't - see [1]), and it doesn't need new Core Language features (in fact, it's implementable in C++98 with minor implementation tweaks). Q2. Are any containers missing here? A2. std::array is fixed-size, so it can't be used here. The implementation for vector works for vector, so it doesn't need to be special-cased. (Implementers are free to optimize erase_if() for vector behind the scenes, just as they are free to optimize count_if() and other algorithms.) The container adaptors aren't containers and don't even provide iterators, much less arbitrary erasure. Q3. Does this proposal have anything to do with ranges? A3. No. Erasure alters a container's size, so it can't be performed with just iterators, even if they're packaged as ranges. erase_if() is a container-based algorithm, not a range-based algorithm. Q4. I looked at the Standardese section, and my brain said, "Too Long; Didn't Standardize". A4. That's not a question. But yes, the Standardese diff is bulky due to the need to edit each synopsis. Your brain will be happier looking at the "namespace std { [...] }" block in the Implementation section. Q5. I saw your "// production code would [...] avoid ADL" comment in the Implementation section. Should the Standardese depict erase_if() calling remove_if() with full qualification? A5. Nope. See 17.6.1.1 [contents]/3: "Whenever a name x defined in the standard library is mentioned, the name x is assumed to be fully qualified as ::std::x, unless explicitly described otherwise. For example, if the Effects section for library function F is described as calling library function G, the function ::std::G is meant." There are some things in the Standard, like qualified mentions of std::pair, that are unnecessary relics of the TR1 era. Q6. Then do you know why the Standard likes to say std::move and std::forward? A6. Nope. Q7. Can you describe your editorial strategy for adding sections, or not adding them? A7. This is a small feature (one overload per container), so I'd like to avoid adding a whole bunch of sections. Non-member erase_if() is similar to non-member swap(), which was the only inhabitant of sections like 23.3.6.6 "vector specialized algorithms" [vector.special]. However, basic_string and the unordered containers were organized differently. Q8. What's going on with this erase_nodes_if() helper? A8. Repeating the erase() loop for the eight ordered/unordered associative containers would be undesirable for editorial maintenance, so I've depicted an "exposition only" helper. I couldn't find a very good home for it (it's common to both the ordered and unordered associative containers, but 23.2.4 [associative.reqmts] and 23.2.5 [unord.req] are separate sections), so I chose the most expedient option of defining it where it's first needed (in map) and then citing it later. It could be moved elsewhere, or the loop could simply be copy-pasted. Q9. What's happening with these template parameter names? You're saying: erase_if(unordered_map& c, Predicate pred) but that's so concise and pretty, it's inconsistent with the rest of the Standard. I want to see the usual template parameter spam, like: erase_if(unordered_map& c, Predicate pred) A9. This is purely editorial (names are sometimes Words Of Power, like 25.1 [algorithms.general]/5 says, but the names chosen here can't possibly allow users to instantiate unordered_map/etc. with bogus arguments, that's controlled by the class definition). There is limited precedent for varying names (the Standard switches between Allocator and Alloc, and 28.11.2 [re.alg.match] uses ST/SA for String Traits and String Allocator). Here, I chose brevity, but I also wanted to avoid any confusion between an unordered container's Pred (a binary predicate for key equality) and erase_if()'s Predicate (a unary predicate given whole elements). Q10. Instead of overloading erase_if() for each container, should you provide a single erase_if(Container&, Predicate) function template that's specified to do the right thing for each container? A10. Such a general function template could be given user-defined containers. There aren't any "container traits", so it's impossible to determine whether a user-defined container is vector-like, list-like, map-like, or something else. User-defined containers could simply be rejected, but then the general function template wouldn't be doing anything differently than the set of specific overloads being proposed here. Note that an author of a user-defined container can overload erase_if() for their container in their namespace. Q11. Could this be added to the container "requirements" tables? A11. Yes, but at what cost in sanity? The vector-like and list-like sequence containers need to do different things, basic_string lives in Clause 21, and std::array is the sequence that is not a sequence. The ordered and unordered associative containers all use erase_nodes_if(), but they have separate tables. Additionally, the tables currently don't cover non-member functions - for example, swap(x, y) is specified for each container individually, even though they're all the same (except for std::array). V. Standardese 1. In 21.3 [string.classes], "Header synopsis", between the "// \ref{string.io}, inserters and extractors:" and "// \tcode{basic_string} typedef names" chunks, add (LaTeX for the convenience of the editors): // \ref{string.erasure}, erasure: template void erase_if(basic_string& c, Predicate pred); 2. Add a new section "Erasure [string.erasure]", as a child of 21.4.8 [string.nonmembers], placed after 21.4.8.9 [string.io], containing: template void erase_if(basic_string& c, Predicate pred); Effects: Equivalent to: c.erase(remove_if(c.begin(), c.end(), pred), c.end()); 3. In 23.3.1 [sequences.general], "Header synopsis", add after swap(): template void erase_if(deque& c, Predicate pred); 4. In 23.3.1 [sequences.general], "Header synopsis", add after swap(): template void erase_if(forward_list& c, Predicate pred); 5. In 23.3.1 [sequences.general], "Header synopsis", add after swap(): template void erase_if(list& c, Predicate pred); 6. In 23.3.1 [sequences.general], "Header synopsis", add after swap(): template void erase_if(vector& c, Predicate pred); 7. In 23.3.3.5 [deque.special], add a new paragraph after swap(): template void erase_if(deque& c, Predicate pred); Effects: Equivalent to: c.erase(remove_if(c.begin(), c.end(), pred), c.end()); 8. In 23.3.4.7 [forwardlist.spec], add a new paragraph after swap(): template void erase_if(forward_list& c, Predicate pred); Effects: Equivalent to: c.remove_if(pred); 9. In 23.3.5.6 [list.special], add a new paragraph after swap(): template void erase_if(list& c, Predicate pred); Effects: Equivalent to: c.remove_if(pred); 10. In 23.3.6.6 [vector.special], add a new paragraph after swap(): template void erase_if(vector& c, Predicate pred); Effects: Equivalent to: c.erase(remove_if(c.begin(), c.end(), pred), c.end()); 11. In 23.4.2 [associative.map.syn], add after swap(map&, map&): template void erase_if(map& c, Predicate pred); 12. In 23.4.2 [associative.map.syn], add after swap(multimap&, multimap&): template void erase_if(multimap& c, Predicate pred); 13. In 23.4.3 [associative.set.syn], add after swap(set&, set&): template void erase_if(set& c, Predicate pred); 14. In 23.4.3 [associative.set.syn], add after swap(multiset&, multiset&): template void erase_if(multiset& c, Predicate pred); 15. In 23.4.4.5 [map.special], add a new paragraph after swap(): template void erase_if(map& c, Predicate pred); Effects: Given the following function template, described for exposition only: template void erase_nodes_if(Container& c, Predicate pred) { // exposition only for (auto i = c.begin(), last = c.end(); i != last; ) { if (pred(*i)) { i = c.erase(i); } else { ++i; } } } Equivalent to: erase_nodes_if(c, pred); 16. In 23.4.5.4 [multimap.special], add a new paragraph after swap(): (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(multimap& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); 17. In 23.4.6.3 [set.special], add a new paragraph after swap(): (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(set& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); 18. In 23.4.7.3 [multiset.special], add a new paragraph after swap(): (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(multiset& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); 19. In 23.5.2 [unord.map.syn], between the swaps and comparisons, add: template void erase_if(unordered_map& c, Predicate pred); template void erase_if(unordered_multimap& c, Predicate pred); 20. In 23.5.3 [unord.set.syn], between the swaps and comparisons, add: template void erase_if(unordered_set& c, Predicate pred); template void erase_if(unordered_multiset& c, Predicate pred); 21. Add a new section "unordered_map erasure [unord.map.erasure]", as a child of 23.5.4 [unord.map], placed after 23.5.4.5 [unord.map.swap], containing: (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(unordered_map& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); 22. Add a new section "unordered_multimap erasure [unord.multimap.erasure]", as a child of 23.5.5 [unord.multimap], placed after 23.5.5.4 [unord.multimap.swap], containing: (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(unordered_multimap& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); 23. Add a new section "unordered_set erasure [unord.set.erasure]", as a child of 23.5.6 [unord.set], placed after 23.5.6.3 [unord.set.swap], containing: (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(unordered_set& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); 24. Add a new section "unordered_multiset erasure [unord.multiset.erasure]", as a child of 23.5.7 [unord.multiset], placed after 23.5.7.3 [unord.multiset.swap], containing: (Note to the editors: [map.special] should be a LaTeX citation.) template void erase_if(unordered_multiset& c, Predicate pred); Effects: Given the erase_nodes_if() function template described for exposition only in [map.special], equivalent to: erase_nodes_if(c, pred); VI. Acknowledgements Thanks to Bruce Dawson, David Cravey, Giovanni Dicanio, Herb Sutter, Kate Gregory, Ken Sykes, Marshall Clow, Michael Goulding, Michael McLaughlin, and Scott Meyers for reviewing this proposal. VII. References All of the Standardese citations in this proposal are to Working Paper N3936: http://www.open-std.org/jtc1/sc22/wg21/prot/14882fdis/n3936.pdf [1] N3820 "Working Draft, Technical Specification - Array Extensions" edited by Lawrence Crowl: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3820.html VIII. Implementation Compiled with Visual C++ 2013 Update 2. C:\Temp>type meow.cpp #include #include #include #include #include #include #include #include #include #include namespace std { // production code would be _Ugly and would avoid ADL template void erase_if(basic_string& c, Predicate pred) { c.erase(remove_if(c.begin(), c.end(), pred), c.end()); } template void erase_if(deque& c, Predicate pred) { c.erase(remove_if(c.begin(), c.end(), pred), c.end()); } template void erase_if(forward_list& c, Predicate pred) { c.remove_if(pred); } template void erase_if(list& c, Predicate pred) { c.remove_if(pred); } template void erase_if(vector& c, Predicate pred) { c.erase(remove_if(c.begin(), c.end(), pred), c.end()); } template void erase_nodes_if(Container& c, Predicate pred) { // exposition only for (auto i = c.begin(), last = c.end(); i != last; ) { if (pred(*i)) { i = c.erase(i); } else { ++i; } } } template void erase_if(map& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(multimap& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(set& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(multiset& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(unordered_map& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(unordered_multimap& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(unordered_set& c, Predicate pred) { erase_nodes_if(c, pred); } template void erase_if(unordered_multiset& c, Predicate pred) { erase_nodes_if(c, pred); } } // namespace std #include #include using namespace std; template void print_elem(const T& t) { cout << t; } template void print_elem(const pair& p) { cout << p.first << "/" << p.second; } template void print(const string& s, const C& c) { cout << s << ": ["; for (auto first = c.begin(), last = c.end(), i = first; i != last; ++i) { if (i != first) { cout << " "; } print_elem(*i); } cout << "]" << endl; } int main() { auto is_vowel = [](const char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }; auto is_odd = [](const int i) { return i % 2 != 0; }; auto is_odd_pair = [](const pair& p) { return p.first % 2 != 0; }; string str("cute fluffy kittens"); cout << "string before: " << str << endl; erase_if(str, is_vowel); cout << "string after: " << str << endl; deque d = { 10, 11, 12, 14, 15, 17, 18, 19 }; print("deque before", d); erase_if(d, is_odd); print("deque after", d); forward_list fl = { 10, 11, 12, 14, 15, 17, 18, 19 }; print("forward_list before", fl); erase_if(fl, is_odd); print("forward_list after", fl); list l = { 10, 11, 12, 14, 15, 17, 18, 19 }; print("list before", l); erase_if(l, is_odd); print("list after", l); vector v = { 10, 11, 12, 14, 15, 17, 18, 19 }; print("vector before", v); erase_if(v, is_odd); print("vector after", v); map m = { { 10, "A" }, { 11, "B" }, { 12, "C" }, { 14, "D" }, { 15, "E" }, { 17, "F" }, { 18, "G" }, { 19, "H" } }; print("map before", m); erase_if(m, is_odd_pair); print("map after", m); multimap mm = { { 20, "S" }, { 21, "T" }, { 22, "U" }, { 22, "V" }, { 23, "W" }, { 23, "X" }, { 24, "Y" }, { 25, "Z" } }; print("multimap before", mm); erase_if(mm, is_odd_pair); print("multimap after", mm); set s = { 10, 11, 12, 14, 15, 17, 18, 19 }; print("set before", s); erase_if(s, is_odd); print("set after", s); multiset ms = { 20, 21, 22, 22, 23, 23, 24, 25 }; print("multiset before", ms); erase_if(ms, is_odd); print("multiset after", ms); unordered_map um = { { 10, "A" }, { 11, "B" }, { 12, "C" }, { 14, "D" }, { 15, "E" }, { 17, "F" }, { 18, "G" }, { 19, "H" } }; print("unordered_map before", um); erase_if(um, is_odd_pair); print("unordered_map after", um); unordered_multimap umm = { { 20, "S" }, { 21, "T" }, { 22, "U" }, { 22, "V" }, { 23, "W" }, { 23, "X" }, { 24, "Y" }, { 25, "Z" } }; print("unordered_multimap before", umm); erase_if(umm, is_odd_pair); print("unordered_multimap after", umm); unordered_set us = { 10, 11, 12, 14, 15, 17, 18, 19 }; print("unordered_set before", us); erase_if(us, is_odd); print("unordered_set after", us); unordered_multiset ums = { 20, 21, 22, 22, 23, 23, 24, 25 }; print("unordered_multiset before", ums); erase_if(ums, is_odd); print("unordered_multiset after", ums); v = { 17, 29, 1729 }; print("vector before erasing everything", v); erase_if(v, is_odd); print("vector after erasing everything", v); v = { 256, 512, 1024 }; print("vector before erasing nothing", v); erase_if(v, is_odd); print("vector after erasing nothing", v); v.clear(); print("empty vector before", v); erase_if(v, is_odd); print("empty vector after", v); l = { 17, 29, 1729 }; print("list before erasing everything", l); erase_if(l, is_odd); print("list after erasing everything", l); l = { 256, 512, 1024 }; print("list before erasing nothing", l); erase_if(l, is_odd); print("list after erasing nothing", l); l.clear(); print("empty list before", l); erase_if(l, is_odd); print("empty list after", l); s = { 17, 29, 1729 }; print("set before erasing everything", s); erase_if(s, is_odd); print("set after erasing everything", s); s = { 256, 512, 1024 }; print("set before erasing nothing", s); erase_if(s, is_odd); print("set after erasing nothing", s); s.clear(); print("empty set before", s); erase_if(s, is_odd); print("empty set after", s); cout << boolalpha; auto is_true = [](const bool b) { return b; }; vector vb = { false, true, false, false, true, true, false, true }; print("vector before", vb); erase_if(vb, is_true); print("vector after", vb); } C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp meow.cpp C:\Temp>meow string before: cute fluffy kittens string after: ct flffy kttns deque before: [10 11 12 14 15 17 18 19] deque after: [10 12 14 18] forward_list before: [10 11 12 14 15 17 18 19] forward_list after: [10 12 14 18] list before: [10 11 12 14 15 17 18 19] list after: [10 12 14 18] vector before: [10 11 12 14 15 17 18 19] vector after: [10 12 14 18] map before: [10/A 11/B 12/C 14/D 15/E 17/F 18/G 19/H] map after: [10/A 12/C 14/D 18/G] multimap before: [20/S 21/T 22/U 22/V 23/W 23/X 24/Y 25/Z] multimap after: [20/S 22/U 22/V 24/Y] set before: [10 11 12 14 15 17 18 19] set after: [10 12 14 18] multiset before: [20 21 22 22 23 23 24 25] multiset after: [20 22 22 24] unordered_map before: [18/G 10/A 19/H 11/B 12/C 14/D 15/E 17/F] unordered_map after: [18/G 10/A 12/C 14/D] unordered_multimap before: [20/S 21/T 22/U 22/V 23/W 23/X 24/Y 25/Z] unordered_multimap after: [20/S 22/U 22/V 24/Y] unordered_set before: [18 10 19 11 12 14 15 17] unordered_set after: [18 10 12 14] unordered_multiset before: [20 21 22 22 23 23 24 25] unordered_multiset after: [20 22 22 24] vector before erasing everything: [17 29 1729] vector after erasing everything: [] vector before erasing nothing: [256 512 1024] vector after erasing nothing: [256 512 1024] empty vector before: [] empty vector after: [] list before erasing everything: [17 29 1729] list after erasing everything: [] list before erasing nothing: [256 512 1024] list after erasing nothing: [256 512 1024] empty list before: [] empty list after: [] set before erasing everything: [17 29 1729] set after erasing everything: [] set before erasing nothing: [256 512 1024] set after erasing nothing: [256 512 1024] empty set before: [] empty set after: [] vector before: [false true false false true true false true] vector after: [false false false false] (end)