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
<https://github.com/BaiJin0224/unstable-erase/blob/8355936/include/experimental/unstable_erase.hpp#L35>.
It should use plain old pred(x) instead, to match what std::erase does.