8
\$\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\$
  • 1
    \$\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
15
\$\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
9
\$\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
1
\$\begingroup\$

I did quite a lot of testing and trialling with this. For almost any size of container (both in elements and bytes), despite what one might think, a vector is much faster than a linked list for this job. The linked list move out/in (using something like std::list::splice) should be faster than vector, but the linear search for the elements is far slower.

So I have specialised my template for std::vector.

Also std::sort is comparatively slow, about 10x slower than std:stable_partition. std::partition was only marginally faster again in my testing. So preserving order seems reasonable.

I believe my code may be cleaner and easier to read than @hoffmale version, using 3 standard STL algorithms . I am also not convinced that his version will be faster than stable_partition. That is because he makes N calls to std::move and N calls to std::vector::erase. I make only one "bulk" call to each. CPU L1 cache and all that...

template <typename T, typename F>
void move_append_if(std::vector<T>& vorig, std::vector<T>& vdest, F&& p) {
  auto part_it = std::stable_partition(vorig.begin(), vorig.end(), [p](T e) -> bool { return !p(e); });
  std::move(part_it, vorig.end(), std::back_inserter(vdest));
  vorig.erase(part_it, vorig.end());
}

EDIT: Interesting news!

Did some more testing with list. Firstly I found @hoffmale 's code not to work. I don't think you can do *out = std::move(*iter); because that doesn't match any signature here: and therefore it is just one of these "static casts to rValueReference". And I don't think the list container is properly aware of what is happening. My out ended up with "no content" anyway.

So I did it with std::list::splice which is really the list specific precision missile for this job. Here is the list specialised template (didn't bother to make it generic for the container type):

template <typename T, typename UnaryPredicate>
void move_append_if(std::list<T>& in, std::list<T>& vdest, UnaryPredicate&& predicate) {
  for(auto iter = std::find_if(in.begin(), in.end(), predicate);
      iter != in.end();
      iter = std::find_if(iter, in.end(), predicate))
    {
      auto iter_next = std::next(iter);
      vdest.splice(vdest.end(), in, iter);
      iter = iter_next;
    }
}

And the performance? Very interesting. Despite the many individual calls to std:list:splice we get 40% better performance on move_append_if between 2 lists than between 2 vectors:

size=10
vector=move_append_if=0.002295ms
list  =move_append_if=0.00079ms

size=100
vector=move_append_if=0.00402ms
list  =move_append_if=0.000895ms

size=1000
vector=move_append_if=0.011038ms
list  =move_append_if=0.007606ms

size=10000
vector=move_append_if=0.06839ms
list  =move_append_if=0.07759ms

size=100000
vector=move_append_if=1.2147ms
list  =move_append_if=0.92521ms

size=1000000
vector=move_append_if=9.17283ms
list  =move_append_if=6.51675ms

size=10000000
vector=move_append_if=109.566ms
list  =move_append_if=61.7614ms

size=100000000
vector=move_append_if=1006.51ms
list  =move_append_if=618.1ms

It turns out that the std::move part of the std::vector specific version is exactly the time difference with the list version. If the predicate is true more often and we do more moves, vectors slows down; list doesn't. The above figures are for containers full of random long ints with a 50% probability of the predicate being true.

final code I settled on. A generic version for all Containers and a partially specialised one for lists, which can take advantage of std::list::splice. I thought that was cleaner than all that constexpr std::is_same_v type juggling, since there is zero shared code between them.

template <template <typename...> class Container, typename T, typename UnaryPredicate>
void move_append_if(Container<T>& origin, Container<T>& destination, UnaryPredicate&& predicate) {

  auto part_it = std::stable_partition(origin.begin(), origin.end(), [&](auto&& elem) { return !predicate(elem); });
  std::move(part_it, origin.end(), std::back_inserter(destination));
  origin.erase(part_it, origin.end());
}

template <typename T, typename UnaryPredicate>
void move_append_if(std::list<T>& origin, std::list<T>& destination, UnaryPredicate&& predicate) {

  for(auto iter = std::find_if(origin.begin(), origin.end(), predicate);
      iter != origin.end();
      iter = std::find_if(iter, origin.end(), predicate)) {
    auto iter_next = std::next(iter);
    destination.splice(destination.end(), origin, iter);
    iter = iter_next;
  }
}
\$\endgroup\$

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.