Is there a STL algorithm or a C++ idiom that moves an item from one std::list to another based on a predicate?

user_3666612 0
Viewed 123

I have a workflow in which I start with a std::list of movable objects and I want to traverse this list, MOVING elements which meet a certain condition (i.e. a unary predicate returns true) to a different std::list (e.g. using back_inserter to an existing list or even constructing a new list).

I've considered std::list::remove_if, but that just destructs elements if the condition is met, and returns the total number of elements removed -- but those elements are lost forever.

I've also considered std::remove_copy_if, but that COPIES the elements if the condition is not met and leaves the elements in the original list.

My hope/assumption was that splitting one list into two based on a predicate would be such a common use-case that std::list would have a member function to do it as a one-liner, or that a STL algorithm would be available to do it via iterators... but I'm not finding anything. Am I missing something obvious, or has this just not yet been implemented in the STL?

Pseudo-code for what I'm hoping the solution would look like is along the lines of this contrived "move_if" std::list member function:

std::list<T> source{ /* some objects of type T */ };
std::list<T> removed{};
source.move_if(std::back_inserter(removed), [&](const auto& e){ /* test e and return a bool */ });

or this one which constructs and returns a new list for the removed elements:

std::list<T> removed = source.move_if([&](const auto& e){ /* test e and return a bool */ });

If there isn't a canned solution already in the STL, is there a preferred idiom for doing this 'manually' (e.g. in a raw loop) that compilers are most likely able to optimize relative to other manual methods? And furthermore, is there a technical reason why this isn't already a supported library function or do I have an inflated view of how useful it would be to others? Thanks!

stdlist move predicate algorithm c++
3 Answers

Probably the shortest way to accomplish this with what already exists is a combination of std::partition (or std::stable_partition if you care to preserve order) and std::list::splice:

std::list<T> source{ ... };
std::list<T> destination;
auto it = std::stable_partition(source.begin(), source.end(), [&](const auto& e) { ... });
destination.splice(destination.end(), source, source.begin(), it);
user_27795300

Unfortunately there's no existing algorithm for this in the standard library.

Given that you're dealing with lists a std::list::splice()-based implementation would most likely be optimal, e.g.:

template<class T, class Pred>
requires std::is_invocable_r_v<bool, Pred, T const&>
void splice_if(std::list<T>& source, std::list<T>& dest, Pred&& predicate) {
    for(auto it = source.begin(); it != source.end();) {
        if(predicate(*it)) dest.splice(dest.end(), source, it++);
        else ++it;
    }
}

Example: (try it on godbolt)

std::list<int> source{1, 2, 3, 4, 5};
std::list<int> dest;

splice_if(source, dest, [](int x) { return x > 3; });

This will transfer all elements matching the predicate in a single pass, without allocating any extra memory.

The other proposed answers

  • The move_if function from @Remy Lebeau is a more generalized version of this algorithm - it'll also work with other containers and not just lists.
    However it'll need to allocate a new list element and move the original element to the new list for each item that matches the predicate - so for lists it's not as efficient as it could be.
    If you need an algorithm that works with all container types i'd recommend the move_if function instead of my splice_if.
  • The std::partition / std::stable_partition approach from @Kyle
    • I'd recommend to use std::partition over std::stable_partition whenever possible. std::stable_partition usually is implemented using a temporary buffer into which all elements matching the predicate are copied over (while the ones not matching the predicate remain in the container). So in the worst case this function will allocate a buffer that's as large as the list - which could be quite a lot if you have a long list or a list of large elements. (libcxx implementation)
    • The list needs to be iterated twice - once to partition it and once to splice the matching elements into the new container
user_84114060

I don't think there is a standard algorithm for this particular use-case scenario, but it wouldn't be hard to write your own function, eg:

template<typename Container, typename Callable>
void move_if(Container &source, Container &dest, Callable pred)
{
    auto iter = source.begin();
    while (iter != source.end())
    {
        if (pred(*iter))
        {
            dest.push_back(std::move(*iter));
            iter = source.erase(iter);
        }
        else
            ++iter;
    }
}

std::list<T> source{ /* some objects of type T */ };
std::list<T> dest{};
move_if(source, dest, [&](const auto& e){ /* test e and return a bool */ });
user_658630
Related