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.
std::partitioninstead ofstd::sort. \$\endgroup\$