# Help getting started writing a propsal for \`unstable\_remove\` and friends wanted

**URL:** <https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335>\
**Category:** Library::general\
**Tags:** community\
**Created:** [January 28, 2025, 10:35pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335 "2025-01-28T22:35:16Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![TedLyngmo](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/tedlyngmo/32/206_2.png) [@TedLyngmo](https://discourse.bemanproject.org/u/TedLyngmo)\
**Post date:** [January 28, 2025, 10:35pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/1 "2025-01-28T22:35:16Z")

</div>

Hi, I’m Ted and I’m new here! I love this initiative and watched a very nice Youtube talk by you guys and I got the impression that some of you may be interested in helping out when it comes to writing a proposal for a new feature for inclusion in some future standard.

I’d welcome some help with this idea of adding a number of erase-remove algorithms that aren’t stable. I’ve never written a C++ proposal before.

I wanted this some years ago when was shuffling data back and forth with some filtering an really didn’t care about in what order the data was - and I didn’t want to have to pay for the extra moves that comes with keeping it stable, so I wrote a basic implementation of `unstable_remove_if` which can be used to implement the misc. container specific `unstable_erase_if`s etc. It guarantees at most as many elements moved as the predicate requires to be removed while the stable removal has to move all elements after a removed element.

I’m mostly in C++17 so perhaps a feature like this is obsoleted by `filter` in ranges, but physically removing elements is probably also going to be necessary in the future.

The code I’ve written is absolutely not in shape for being included in any library as-is. I wrote it for my specific needs back then, but I think it could be a good alternative to the stable erasure that is the goto solution right now, so if it sounds interesting, I (or we) could pick it up and finish it along with a proposal.

Please let me know if you think it’s worthy of spending some energy on.

Mini-demo: [Compiler Explorer](https://godbolt.org/z/5Pd4Wj37T)

Kind regards,  
Ted Lyngmo

---

<div class="post-metadata">

**Author:** ![dsankel](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/dsankel/32/5_2.png) [@dsankel](https://discourse.bemanproject.org/u/dsankel)\
**Post date:** [January 31, 2025, 10:12pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/2 "2025-01-31T22:12:51Z")

</div>

Hey @TedLyngmo, welcome!

Can you elaborate on what `unstable_erase_if` does? `remove_if` is described on [cppreference.com](http://cppreference.com) as doing this:

> Removes all elements satisfying specific criteria from the range [first, last) and returns a past-the-end iterator for the new end of the range.  
> 3) Removes all elements for which predicate p returns true.

What would be a likewise description of your `unstable_remove_if`?

---

<div class="post-metadata">

**Author:** ![Jeff-Garland](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/jeff-garland/32/23_2.png) [@Jeff-Garland](https://discourse.bemanproject.org/u/Jeff-Garland)\
**Post date:** [February 2, 2025, 12:08am UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/3 "2025-02-02T00:08:17Z")

</div>

Welcome @TedLyngmo !

> [@dsankel](#):
>
> Can you elaborate on what `unstable_erase_if` does?

Let me take a crack at that based on quick look at the code and the example. It’s the same functionality as `erase_if` and `remove_if` without maintaining the requirements for a [stable algorithm](https://eel.is/c++draft/algorithm.stable)

As a result, in the sample below at least there’s far less moving of data (2 moves versus 23 moves) since the `last` element of the range can simply be swapped with the removed element.

```auto
    std::string stable("abcdefghijklmnoprstuvwxyz");
    std::string unstable = stable;
    
    // 23 moves:
    std::erase_if(stable, [](char ch) { return ch < 'c'; });
    std::cout << "stable: " << stable << '\n';

    // 2 moves: 
    unstable_erase_if(unstable, [](char ch) { return ch < 'c'; });
    std::cout << "unstable: " << unstable << '\n';

// stable: cdefghijklmnoprstuvwxyz
// unstable: zycdefghijklmnoprstuvwx

```

> [@TedLyngmo](#):
>
> a feature like this is obsoleted by `filter` in ranges, but physically removing elements is probably also going to be necessary in the future.

If you used views::filter here with ranges::to you’re going to get a copy for every char that doesn’t meet the criteria - like the stable range. So this is likely even less efficient because of extra allocations.

```auto
    std::string input_range("abcdefghijklmnoprstuvwxyz");

    auto out_string = input_range 
                    | rv::filter([](char ch) { return ch >= 'c'; })
                    | std::ranges::to<std::string>();
    std::cout << "filter: " << out_string << '\n';

```

> **[Compiler Explorer - C++](https://godbolt.org/z/Pacn567q7)**
>
> int main() {
> using namespace lyn::alg;
> namespace rv = std::views;
> 
> std::string stable("abcdefghijklmnoprstuvwxyz");
> std::string unstable = stable;
> std::string input\_range = stable;
>     
> // 23 moves:
> std::erase\_if(stable,...

> [@TedLyngmo](#):
>
> so if it sounds interesting, I (or we) could pick it up and finish it along with a proposal.

I think it’s interesting. I guess the question really is _how common_ is the use case – would enough users find interesting to have in the standard library. One question that every proposal has to answer is _is this something that belongs in the standard_. With the general question of _useful algorithms_ that question was long ago answered: _yes_. Whether this particular algorithm is important enough to include is probably a question only the committee can answer.

My personal take is useful generic algorithms is the bread and butter of the standard library since they simplify code development in every domain c++ covers. At c++now writing algorithms is a perennially popular topic for Library in a Week – because it’s small enough to get something real done in a short time – but super educational because writing algos is way harder than first glance.

Note that some of the committee have outlined what they would like to see in [algo/ranges in P2760](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2760r1.html). Most of this plan will not be achieved as only a few ranges views have been proposed and design freeze for 26 is a couple weeks out. Going forward I’d like to see Beman be a hot-bed for this part of the library.

So @TedLyngmo if you want to go down this path, buckle in for a potentially long ride. Starting now, we’d certainly get some of the evolution groups to look at this in the next 1.5 years or so. Myself, David and others here can teach you the standardization ropes.

---

<div class="post-metadata">

**Author:** ![dsankel](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/dsankel/32/5_2.png) [@dsankel](https://discourse.bemanproject.org/u/dsankel)\
**Post date:** [February 6, 2025, 8:41pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/4 "2025-02-06T20:41:45Z")

</div>

> [@Jeff-Garland](#):
>
> > [@dsankel](#):
> >
> > Can you elaborate on what `unstable_erase_if` does?
> 
> Let me take a crack at that based on quick look at the code and the example.

Thanks Jeff, that helped a lot.

> [@Jeff-Garland](#):
>
> > [@TedLyngmo](#):
> >
> > so if it sounds interesting, I (or we) could pick it up and finish it along with a proposal.
> 
> I think it’s interesting.

I concur.

---

<div class="post-metadata">

**Author:** ![TedLyngmo](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/tedlyngmo/32/206_2.png) [@TedLyngmo](https://discourse.bemanproject.org/u/TedLyngmo)\
**Post date:** [February 6, 2025, 9:07pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/5 "2025-02-06T21:07:08Z")

</div>

Thanks for your replies and offer to help!

I’m a bit ashamed to admit it, but 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.

Until next time,  
Ted

---

<div class="post-metadata">

**Author:** ![Jeff-Garland](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/jeff-garland/32/23_2.png) [@Jeff-Garland](https://discourse.bemanproject.org/u/Jeff-Garland)\
**Post date:** [February 7, 2025, 1:45am UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/6 "2025-02-07T01:45:37Z")

</div>

> [@TedLyngmo](#):
>
> I’m not sure what’s changed since I wrote the functions, but their performance is really bad.

idk how long ago this was, but I can say unequivocally that compilers and libraries are under constant improvement. In my experience it is _difficult_, at best, to beat the smart folks that spend their employed lives doing this. They have all the information about what doesn’t work (bug reports) and have seen what does and hence are continually improving.

That said it can also be the machines – branch prediction, cache locality, etc. The improvements are relentless and impressive.

> [@TedLyngmo](#):
>
> Anyway, I no longer think they are such a good idea.
> 
> Until next time,

It’s a fair conclusion, but of course we’d love to have you stay and participate in other development. If not, thanks for now 🙂

---

<div class="post-metadata">

**Author:** ![dsankel](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/dsankel/32/5_2.png) [@dsankel](https://discourse.bemanproject.org/u/dsankel)\
**Post date:** [February 7, 2025, 9:04pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/7 "2025-02-07T21:04:43Z")

</div>

I think `unstable_remove_if` is essentially the same as `std::partition` with the function result inverted. Credit to Dave Abrahams for pointing this out to me.

---

<div class="post-metadata">

**Author:** ![Jeff-Garland](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/jeff-garland/32/23_2.png) [@Jeff-Garland](https://discourse.bemanproject.org/u/Jeff-Garland)\
**Post date:** [February 7, 2025, 10:27pm UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/8 "2025-02-07T22:27:17Z")

</div>

> [@dsankel](#):
>
> same as `std::partition` with the function result inverted. Credit to Dave Abrahams

Hmm, yeah Dave is right – goes to show that even once you _think_ you understand the library you might not. When prompted properly the _statistical mechanical turk_ basically gets it right.

chatcpt: compare std::ranges\_remove\_if with std::ranges::partition

### **Comparison Summary**

| Feature | `std::ranges::remove_if` | `std::ranges::partition` |
| --- | --- | --- |
| **Purpose** | Moves unwanted elements to the end | Moves elements to separate groups |
| **Removes elements?** | No, requires `erase` to shrink | No, just reorders |
| **Order preserved?** | Yes | No (unstable) |
| **Return value** | Iterator to logical end of remaining elements | Iterator to partition point |
| **Efficiency** | O(n) moves/swaps | O(n) moves/swaps |

Use **`remove_if`** when you want to filter out elements while keeping order.  
Use **`partition`** when you just want to separate elements into two groups.

---

<div class="post-metadata">

**Author:** ![TedLyngmo](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/tedlyngmo/32/206_2.png) [@TedLyngmo](https://discourse.bemanproject.org/u/TedLyngmo)\
**Post date:** [February 8, 2025, 12:07am UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/9 "2025-02-08T00:07:59Z")

</div>

Yes, `partition` is much like `unstable_*` except that `unstable_*` does not promise anything about the moved from’s state other than it’s valid in some sense. Moving from instead of swapping with _should_ be cheaper. Learning from my previous assumption, I’m not going to say that that’s how it is though 🙂

---

<div class="post-metadata">

**Author:** ![TedLyngmo](https://yyz1.discourse-cdn.com/flex029/user_avatar/discourse.bemanproject.org/tedlyngmo/32/206_2.png) [@TedLyngmo](https://discourse.bemanproject.org/u/TedLyngmo)\
**Post date:** [February 8, 2025, 12:28am UTC](https://discourse.bemanproject.org/t/help-getting-started-writing-a-propsal-for-unstable-remove-and-friends-wanted/335/10 "2025-02-08T00:28:19Z")

</div>

I do follow the evolution of the implementations. I follow it mostly on the library side and I do my bit of reporting on behavior that’s not to be expected to the “big three”. I also looked at the actual implementations alive to see what cleverness they have going on that could beat my naive “move as few as possible” idea, but no, there is no fancy stuff. It is straight forward staying in line - and that’s why I believe it being pure hardware that makes that efficient. My algorithm would maybe have made sense before cachelines. 🙂