Hi Arthur,

Thank you for the detailed feedback and for pointing to the earlier history of `unstable_remove`.

I think your point about the relationship between `unstable_remove` and `unstable_erase` is right. Looking at this only as a container-level `unstable_erase` facility makes the proposal too narrow. I now think the proposal should include both the unstable remove and unstable erase sides of the facility: `unstable_remove` and `unstable_remove_if` as the fundamental algorithms, and `unstable_erase` and `unstable_erase_if` as the container convenience layer analogous to the existing `std::erase` and `std::erase_if`.

I also think the history is useful rather than discouraging. It shows that this design space has existed for a long time at the algorithm level. What seems different now is that the standard library also has the modern container-level `std::erase` / `std::erase_if` interface, so there is a natural question of whether the unstable counterpart should be considered for the same removal/erasure family rather than only as an isolated vector optimization.

I agree that the performance case needs much stronger evidence. Earlier discussions seem to have suffered from insufficiently convincing measurements, and I do not want the paper to rely on intuition or a small motivating example. I plan to spend the next few days building a broader benchmark suite that measures both relocation counts and wall-clock performance across element types, removal densities, distributions, containers, and implementations. I also want to run the primary measurements on controlled, non-shared machines, with CI results used mainly for portability and supplementary trend checking.

I also find your point about the overload set persuasive. If the facility is named at namespace scope as `std::unstable_erase`, then it should probably mirror the existing `std::erase` / `std::erase_if` interface as much as practical. Otherwise, we would create a new teaching problem where users have to remember that `std::erase(c, x)` works broadly, but `std::unstable_erase(c, x)` only works for a small subset of containers.

That said, I think it is important to separate API coverage from guaranteed performance improvement. My current thinking is that the API can cover the existing standard containers in a way analogous to `std::erase`, while optimized implementations are initially focused on containers where the benefit is clear, such as vector-like containers and possibly `deque`. For containers where no useful unstable optimization is known, the function could be specified in terms of ordinary erase and should not imply a better complexity bound. In that sense, `unstable_erase` would express a semantic permission — that the relative order of retained elements need not be preserved — rather than a universal performance guarantee.

So my current plan for the next revision is:

* reframe the proposal around the unstable removal/erasure family rather than only `unstable_erase`;
* add `unstable_remove` and `unstable_remove_if` as the fundamental algorithms;
* add `unstable_erase` and `unstable_erase_if` as convenience wrappers analogous to `std::erase` and `std::erase_if`;
* consider mirroring the existing `std::erase` overload set, with ordinary-erase fallback where no optimized unstable implementation is meaningful;
* explicitly discuss prior work and the earlier lack of convincing performance data;
* add broader benchmark data before making any strong performance claim.

I will follow up on the list once I have more data and a clearer revised direction.

Thanks again. Your comments helped clarify that the proposal should not be defended as a narrow container optimization, but should instead be evaluated as a possible completion of the existing remove/erase family with an order-not-preserved semantic option.

Best,
Xisheng Liu

Original
From: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date: 2026-05-23 22:06
To: std-proposals <std-proposals@lists.isocpp.org>
Cc: Xisheng Liu <bfzgsz@foxmail.com>
Subject: Re: [std-proposals] Proposal draft: unstable erase operations for std::vector

On Sat, May 23, 2026 at 8:51 AM Xisheng Liu wrote:

[unstable_erase]

I think this is the first time anyone's proposed `unstable_erase` à la `std::erase`; but there is a very long tradition of proposing `unstable_remove` à la `std::remove`. See

Brent Friedman, 2015:
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0041r0.html
Brent Friedman, 2016:
https://iterator.wordpress.com/2016/01/31/algorithms_0/ (archived <https://archive.is/pd5v6>)
Eric Niebler et al., 2019:
https://github.com/ericniebler/range-v3/pull/1010
Arthur O'Dwyer, 2023-ish:
https://github.com/Quuxplusone/SG14?tab=readme-ov-file#efficient-removal-algorithms-future--c14
Ted Lyngmo, 2025:
https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335
https://lists.isocpp.org/std-proposals/2025/02/12297.php

In https://lists.isocpp.org/std-proposals/2025/02/12297.php Jens Maurer had written:
>> It was discussed in LEWG in Kona 2015.
>>
>> The poll said "nay", partly because the performance numbers in the paper
>> were unconvincing. Maybe the testcase wasn't good, or the size of the
>> array wasn't large enough or whatever.
>>
>> So, if you can demonstrate an actual (measurable) benefit compared to
>> the alternatives, LEWG ought to get interested (again).

Ted Lyngmo replied:
I created a few simple test cases to be able to show what would be
gained by using the set of unstable_* functions since I didn’t have my
old tests saved.
I’m not sure what’s changed since I wrote the functions, but their
performance is really bad. Only with very contrived data sets will they
outperform the “stable” versions. I assume cache locality explains most
of the difference. I must have been testing them with some bias back
then or used an ancient computer :)
Anyway, I no longer think they are such a good idea.

You wrote:
I can see the appeal of a fallback for generic code. It would make it easier to write code that says “erase this element, and I do not care about preserving order” without having to special-case every container.

However, I am also a little concerned that a silent fallback to ordinary `erase` could make the meaning of `unstable_erase` less clear. My original motivation was not only to express that order need not be preserved, but also to expose the common vector-like optimization where allowing reordering reduces element relocation. If `unstable_erase` simply falls back to order-preserving `erase` for some containers, users may reasonably expect a relocation or complexity benefit that is not actually present.

For `std::erase`, the value proposition is "You no longer have to remember the incantation to erase from each different species of container; just write `std::erase` and overload resolution will figure it out." The general-case incantation,
    for (auto it = c.begin(); it != c.end(); it = pred(*it) ? c.erase(it) : std::next(it)) { }
, is the best you can do for e.g. std::set, but we still provide `std::erase(set&, ...)` because the incantation is difficult to remember exactly. The value proposition is that `std::erase` is easier to write, not that it makes your program any faster.

Question: What is the value proposition of `unstable_erase`?
It seems like the only benefit of typing `std::unstable_erase(c, x)` instead of `std::erase(c, x)` is that you hope the former will be faster, right? But then you'll have to demonstrate that the unstable version is any faster. Ted Lyngmo reported in 2025 that it really wasn't (because, maybe, cache effects). Now, Ted's report surprised me; but you should recognize that your job isn't starting from "neutral" but rather starting from "the performance argument has already allegedly been refuted" and you now have an uphill battle to counter-refute it.

If you do find a performance benefit, then I'll ask why you propose only the non-generic `unstable_erase`, when a generic `unstable_remove` algorithm would be just as fast (by inspection: it'd be the same code) and would fit better into the classic STL. I don't think there's any possible justification for adding `unstable_erase` without `unstable_remove`. Add both, or add just `unstable_remove`, or add neither; but the path you've chosen right now is the worst of all possible paths.

You wrote:
[...]
* provide `unstable_erase` only where the operation can provide a meaningful reduced-relocation or complexity benefit; or
* provide a generic fallback for convenience, but make it clear that the fallback does not imply better complexity than ordinary `erase`.

Re the first bullet: Then you should include `deque`, as Jens said. Obviously swap-and-pop avoids just as many relocations/shifts for `deque` as it does for `vector`.

Re the second bullet: If your goal is that the programmer can just write `std::unstable_erase(ctr, x)` and not have to think about how it's implemented, then it would defeat your goal if for some containers `std::unstable_erase` didn't work and the programmer had to Just Know to write `std::erase(ctr, x)` instead. We'd end up having to teach "The best way to unstable-erase from a container? For these containers, write... [unstable_erase...] and for these other containers, write... [regular erase]." That's exactly the teaching-antipattern that the original `std::erase` was supposed to save us from!  So IMO it's obvious that (if this proposal is a good idea at all; I'm not convinced) you ought to propose `std::unstable_erase` for all the same containers that currently provide `std::erase`.

Now, thinking about `deque` makes me wonder: The swap-and-pop idiom assumes single-element removal is the common case. (And, I suppose, it is the common case.) But the STL likes to work with consecutive ranges. Consider
    vector<T>::erase(const_iterator first, const_iterator last);
        // snip out [first,last) and shift the remaining elements down
Shouldn't the "unstable" version of that member function be
    vector<T>::unstable_erase(const_iterator first, const_iterator last);
        // replace [first,last) with the last N elements of the vector, then erase the end

- vector::erase'ing {4,5} from {1,2,3,4,5,6,7,8,9} gives {1,2,3,6,7,8,9} with a single memcpy of 4 elements.
- std::erase'ing {4,5} from {1,2,3,4,5,6,7,8,9} gives {1,2,3,6,7,8,9} with a lot of predicate evaluations intermixed, and no memcpy. (This would be a contrived situation.)
- std::unstable_erase'ing {4,5} from {1,2,3,4,5,6,7,8,9} using your algorithm would give {1,2,3,9,8,6,7} with a lot of predicate evaluations intermixed, and no memcpy. (This would be a contrived situation.)
- vector::unstable_erase'ing {4,5} from {1,2,3,4,5,6,7,8,9} would give {1,2,3,8,9,6,7} with a single memcpy of 2 elements.

But of course the reply to my above two paragraphs could be "Nobody's ever needed to remove a range of elements in an unstable way. `std::unstable_remove_if(pred) is useful; vector::unstable_remove(first, last) is useless." I wouldn't argue against that.

Another as-yet-informal proposal you should look at is Alexey Sidorin's `displace_heap`:
https://lists.isocpp.org/std-proposals/2026/03/17319.php
It might or might not be relevant to your interests.

Cheers,
Arthur

P.S., nitpick: Your sample implementation uses std::invoke. It should use plain old pred(x) instead, to match what std::erase does.