6
\$\begingroup\$

I've implemented a C++ algorithm that moves elements satisfying a given unary predicate from one container into the other, deleting them from the input container.

This is my implementation:

/**
 * Moves all elements in the input container 
 * that satisfy the given predicate
 * into the output container,
 * and erases them from the input container.
 * @tparam Container The container type.
 * @tparam UnaryPredicate The predicate type.
 * @param in The input container.
 * @param out The output container.
 * @param predicate The predicate to satisfy.
 */
template <class Container, class UnaryPredicate>
void move_and_erase_if(Container &in, Container &out, UnaryPredicate predicate) {
    // sort the input container so that all elements that 
    // satisfy the predicate are moved to the end.
    std::sort(in.begin(), in.end(), [=](auto &a, auto &b){
        return !predicate(a) && predicate(b);
    });

    // find the first element in the sorted container 
    // that satisfies the predicate.
    // all elements following that element 
    // also satisfy the predicate.
    auto it = std::find_if(in.begin(), in.end(), [=](auto &val) {
        return predicate(val);
    });

    // move the elements satisfying the predicate 
    // into the output container.
    std::move(it, in.end(), std::back_inserter(out));

    // erase the elements satisfying the predicate
    // from the input container.
    in.erase(it, in.end());
}

Is there a more efficient way to achieve this? Specifically, the call to std::find_if bugs me, as it applies the predicate to all elements a second time, until it finds the first one that satisfies it.

I've written an example application using the algorithm on ideone.

\$\endgroup\$
  • \$\begingroup\$ This is too little to warrant its own answer but consider removing redundant comments. Good comments describe why, whereas code describes the how. Don’t have comments that paraphrase what the code does, they are less than useful. If the code on its own isn’t obvious then make it obvious by refactoring it. In your example, all comments except the first are unnecessary. And the first comment becomes unnecessary once you use std::partition instead of std::sort. \$\endgroup\$ – Konrad Rudolph Oct 25 '18 at 13:40
13
\$\begingroup\$

Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.

If you still want to follow the sorting path, consider std::lower_bound instead of find_if.

\$\endgroup\$
  • \$\begingroup\$ std::partition is exactly what I was looking for. Thank you very much! \$\endgroup\$ – CrushedPixel Oct 24 '18 at 20:36
  • 4
    \$\begingroup\$ Or use stable_partition to keep insertion order. \$\endgroup\$ – Calak Oct 24 '18 at 20:57
  • \$\begingroup\$ I wonder if there is a generic way to use splice instead of move if the container happens to be a list. \$\endgroup\$ – Simon Richter Oct 25 '18 at 6:29
  • \$\begingroup\$ @Calak - good idea if the order is important. If not, then it comes at with a performance cost, so we should choose wisely. \$\endgroup\$ – Toby Speight Oct 25 '18 at 8:14
  • \$\begingroup\$ @Calak In-place stable_partition runs in \$O(n\log n)\$ time, so it is not much better than stable sorting. A non-stable partition is linear. \$\endgroup\$ – vnp Oct 25 '18 at 8:51
7
\$\begingroup\$

Complexity

std::sort has at runtime complexity of at least \$\mathcal{O}(n \log{n})\$, and requires that the given container type provides random access iterators (which are only few of them).

Also, other than further assumptions in the later code, it doesn't seem sorting is actually required.

    auto iter = std::partition(in.begin(), in.end(), [&](auto elem) { return !predicate(elem); });

    std::move(iter, in.end(), std::back_inserter(out));
    in.erase(iter, in.end());

If stability is required, this could be adapted to:

auto insert_pos = std::find_if(in.begin(), in.end(), predicate);

for(auto iter = insert_pos; iter != in.end(); std::advance(iter))
{
    if(predicate(*iter))
    {
        out.push_back(std::move(*iter));
    }
    else
    {
        *insert_pos = std::move(*iter);
        std::advance(insert_pos);
    }
}

in.erase(insert_pos, in.end());

This has linear time complexity, and works with all containers that have random access iterators.

Design

Currently, the algorithms requires the following properties of the output container:

  • It has to be of the exact same type as the input container (so transferring values from a std::list to a std::vector isn't possible).

  • Values can only ever be move to the back of out, requiring the container to have a push_back member function.

Additionally, Container must provide random access iterators in order to use std::sort.

All these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values from any container to any position in another container.

To accomplish this, the algorithm could take an output iterator instead.

For a more generic solution, the following implementation could be used:

template<class Container, class OutIter, class UnaryPredicate>
OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate) {
    for(auto iter = std::find_if(in.begin(), in.end(), predicate);
        iter != in.end();
        iter = std::find_if(iter, in.end(), predicate)
    {
        *out = std::move(*iter);
        std::advance(out);
        iter = in.erase(iter);
    }

    return out;
}

However, this implementation has a worse runtime complexity than the original solution for std::vector/std::deque, since they don't have \$\mathcal{O}(1)\$ erase operations.

The solution would be to use the correct algorithm depending on the containers iterator type. This can be accomplished using SFINAE.

template<class Container, class OutIter, class UnaryPredicate>
typename std::enable_if<
    !std::is_base_of<
        std::random_access_iterator_tag,
        typename std::iterator_traits<typename Container::iterator>::iterator_category
    >::value,
    OutIter
>::type move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate)
{
    for(auto iter = std::find_if(in.begin(), in.end(), predicate);
        iter != in.end();
        iter = std::find_if(iter, in.end(), predicate)
    {
        *out = std::move(*iter);
        std::advance(out);
        iter = in.erase(iter);
    }

    return out;
}

template<typename Container, typename OutIter, typename UnaryPredicate>
typename std::enable_if<
    std::is_base_of<
        std::random_access_iterator_tag,
        typename std::iterator_traits<typename Container::iterator>::iterator_category
    >::value,
    OutIter
>::type move_and_erase_if(Container& in, OutIter out, UnaryPredicate predicate)
{
    auto iter = std::partition(in.begin(), in.end(), [&](auto elem) { return !predicate(elem); });

    out = std::move(iter, in.end(), out);
    in.erase(iter, in.end());

    return out;
}

In C++17 or later, one could use if constexpr instead, simplifying the implementation.

template<typename Container, typename OutIter, typename UnaryPredicate>
OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate predicate)
{
    if constexpr(std::is_base_of_v<std::random_access_iterator_tag,
                 typename std::iterator_traits<typename Container::iterator>::iterator_category>)
    {
        auto iter = std::partition(in.begin(), in.end(), [&](auto&& elem) { return !predicate(elem); });

        out = std::move(iter, in.end(), out);
        in.erase(iter, in.end());
    }
    else
    {
        for(auto iter = std::find_if(in.begin(), in.end(), predicate);
            iter != in.end();
            iter = std::find_if(iter, in.end(), predicate))
        {
            *out = std::move(*iter);
            std::advance(out);
            iter = in.erase(iter);
        }
    }

    return out;
}

Userfriendlyness

It would be nice to check at compile time whether Container::value_type matches std::iterator_traits<OutIter>::value_type and whether UnaryPredicate accepts an argument of type Container::value_type. This could be done with SFINAE or static_asserts.

\$\endgroup\$
  • 1
    \$\begingroup\$ If you want to be most general and efficient, don't use *out++ = …;. Use *out = …; ++out; instead. Anyway, nice one. \$\endgroup\$ – Deduplicator Oct 25 '18 at 0:38
  • \$\begingroup\$ And what about using std::next(out); ? \$\endgroup\$ – Calak Oct 25 '18 at 6:34
  • \$\begingroup\$ @Deduplicator @Calak: To offend all equally, I have changed every iterator increment to std::advance. That said, this is IMO the level of personal preference, unless there are well founded performance reasons (= measurements). \$\endgroup\$ – hoffmale Oct 25 '18 at 11:23
  • \$\begingroup\$ If you want a partition and stability is required, why not use std::stable_partition? \$\endgroup\$ – Jerry Coffin Oct 26 '18 at 7:19
  • \$\begingroup\$ @JerryCoffin: Because std::stable_partition might run with complexity \$\mathcal{O}(n \log n)\$. This solution is \$\mathcal{O}(n)\$. (The standard says std::stable_partition might run in \$\mathcal{O}(n)\$ if there is enough extra memory - but that is not guaranteed.) \$\endgroup\$ – hoffmale Oct 26 '18 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.