Mixing
Moving elements satisfying a predicate from one container to another
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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.
c++ algorithm c++11 collections
edited 34 mins ago
200_success
126k14146407
asked 1 hour ago
CrushedPixel
304
add a comment |Â
up vote
1
down vote
favorite
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.
c++ algorithm c++11 collections
edited 34 mins ago
200_success
126k14146407
asked 1 hour ago
CrushedPixel
304
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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.
c++ algorithm c++11 collections
edited 34 mins ago
200_success
126k14146407
asked 1 hour ago
CrushedPixel
304
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.
c++ algorithm c++11 collections
c++ algorithm c++11 collections
edited 34 mins ago
200_success
126k14146407
asked 1 hour ago
CrushedPixel
304
edited 34 mins ago
200_success
126k14146407
asked 1 hour ago
CrushedPixel
304
edited 34 mins ago
200_success
126k14146407
edited 34 mins ago
200_success
126k14146407
edited 34 mins ago
200_success
126k14146407
126k14146407
asked 1 hour ago
CrushedPixel
304
asked 1 hour ago
CrushedPixel
304
asked 1 hour ago
CrushedPixel
304
304
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
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.
answered 1 hour ago
vnp
37.6k12995
std::partitionis exactly what I was looking for. Thank you very much!
– CrushedPixel
1 hour ago
Or usestable_partitionto keep insertion order.
– Calak
1 hour ago
add a comment |Â
up vote
0
down vote
Complexity
std::sort has at runtime complexity of at least $mathcalO(n logn)$, 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. Why not use a simple linear loop with std::find_if?
for(auto iter = std::find_if(in.begin(), in.end(), predicate);
iter != in.end();
iter = std::find_if(iter, in.end(), predicate)
out.push_back(std::move(*iter));
iter = in.erase(iter);
This has linear time complexity, and works with all types of iterators/containers!
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::listto astd::vectorisn't possible).Values can only ever be move to the back of out, requiring the container to have a
push_backmember function.
Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.
To accomplish this, the algorithm could take an output iterator instead.
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);
iter = in.erase(iter);
return out;
Additinally, it would be nice to check at compile time whether
Container::value_typematchesstd::iterator_traits<OutIter>::value_typeand whetherUnaryPredicateaccepts an argument of typeContainer::value_type. This could be done with SFINAE orstatic_asserts.
answered 1 hour ago
hoffmale
5,192835
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element ofinonce. Did you overlook theiterparameter in the second call tostd::find_if?
– hoffmale
19 mins ago
in.erase(iter)is not O(1) for most containers.
– Deduplicator
18 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of arestd::vectorandstd::deque. If that matters, those could be special cased.
– hoffmale
15 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
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.
answered 1 hour ago
vnp
37.6k12995
std::partitionis exactly what I was looking for. Thank you very much!
– CrushedPixel
1 hour ago
Or usestable_partitionto keep insertion order.
– Calak
1 hour ago
add a comment |Â
up vote
3
down vote
accepted
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.
answered 1 hour ago
vnp
37.6k12995
std::partitionis exactly what I was looking for. Thank you very much!
– CrushedPixel
1 hour ago
Or usestable_partitionto keep insertion order.
– Calak
1 hour ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
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.
answered 1 hour ago
vnp
37.6k12995
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.
answered 1 hour ago
vnp
37.6k12995
answered 1 hour ago
vnp
37.6k12995
answered 1 hour ago
vnp
37.6k12995
answered 1 hour ago
vnp
37.6k12995
37.6k12995
std::partitionis exactly what I was looking for. Thank you very much!
– CrushedPixel
1 hour ago
Or usestable_partitionto keep insertion order.
– Calak
1 hour ago
add a comment |Â
std::partitionis exactly what I was looking for. Thank you very much!
– CrushedPixel
1 hour ago
Or usestable_partitionto keep insertion order.
– Calak
1 hour ago
std::partition is exactly what I was looking for. Thank you very much!– CrushedPixel
1 hour ago
std::partition is exactly what I was looking for. Thank you very much!– CrushedPixel
1 hour ago
Or use
stable_partition to keep insertion order.– Calak
1 hour ago
Or use
stable_partition to keep insertion order.– Calak
1 hour ago
add a comment |Â
up vote
0
down vote
Complexity
std::sort has at runtime complexity of at least $mathcalO(n logn)$, 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. Why not use a simple linear loop with std::find_if?
for(auto iter = std::find_if(in.begin(), in.end(), predicate);
iter != in.end();
iter = std::find_if(iter, in.end(), predicate)
out.push_back(std::move(*iter));
iter = in.erase(iter);
This has linear time complexity, and works with all types of iterators/containers!
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::listto astd::vectorisn't possible).Values can only ever be move to the back of out, requiring the container to have a
push_backmember function.
Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.
To accomplish this, the algorithm could take an output iterator instead.
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);
iter = in.erase(iter);
return out;
Additinally, it would be nice to check at compile time whether
Container::value_typematchesstd::iterator_traits<OutIter>::value_typeand whetherUnaryPredicateaccepts an argument of typeContainer::value_type. This could be done with SFINAE orstatic_asserts.
answered 1 hour ago
hoffmale
5,192835
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element ofinonce. Did you overlook theiterparameter in the second call tostd::find_if?
– hoffmale
19 mins ago
in.erase(iter)is not O(1) for most containers.
– Deduplicator
18 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of arestd::vectorandstd::deque. If that matters, those could be special cased.
– hoffmale
15 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
 |Â
show 1 more comment
up vote
0
down vote
Complexity
std::sort has at runtime complexity of at least $mathcalO(n logn)$, 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. Why not use a simple linear loop with std::find_if?
for(auto iter = std::find_if(in.begin(), in.end(), predicate);
iter != in.end();
iter = std::find_if(iter, in.end(), predicate)
out.push_back(std::move(*iter));
iter = in.erase(iter);
This has linear time complexity, and works with all types of iterators/containers!
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::listto astd::vectorisn't possible).Values can only ever be move to the back of out, requiring the container to have a
push_backmember function.
Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.
To accomplish this, the algorithm could take an output iterator instead.
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);
iter = in.erase(iter);
return out;
Additinally, it would be nice to check at compile time whether
Container::value_typematchesstd::iterator_traits<OutIter>::value_typeand whetherUnaryPredicateaccepts an argument of typeContainer::value_type. This could be done with SFINAE orstatic_asserts.
answered 1 hour ago
hoffmale
5,192835
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element ofinonce. Did you overlook theiterparameter in the second call tostd::find_if?
– hoffmale
19 mins ago
in.erase(iter)is not O(1) for most containers.
– Deduplicator
18 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of arestd::vectorandstd::deque. If that matters, those could be special cased.
– hoffmale
15 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
 |Â
show 1 more comment
up vote
0
down vote
up vote
0
down vote
Complexity
std::sort has at runtime complexity of at least $mathcalO(n logn)$, 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. Why not use a simple linear loop with std::find_if?
for(auto iter = std::find_if(in.begin(), in.end(), predicate);
iter != in.end();
iter = std::find_if(iter, in.end(), predicate)
out.push_back(std::move(*iter));
iter = in.erase(iter);
This has linear time complexity, and works with all types of iterators/containers!
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::listto astd::vectorisn't possible).Values can only ever be move to the back of out, requiring the container to have a
push_backmember function.
Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.
To accomplish this, the algorithm could take an output iterator instead.
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);
iter = in.erase(iter);
return out;
Additinally, it would be nice to check at compile time whether
Container::value_typematchesstd::iterator_traits<OutIter>::value_typeand whetherUnaryPredicateaccepts an argument of typeContainer::value_type. This could be done with SFINAE orstatic_asserts.
answered 1 hour ago
hoffmale
5,192835
Complexity
std::sort has at runtime complexity of at least $mathcalO(n logn)$, 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. Why not use a simple linear loop with std::find_if?
for(auto iter = std::find_if(in.begin(), in.end(), predicate);
iter != in.end();
iter = std::find_if(iter, in.end(), predicate)
out.push_back(std::move(*iter));
iter = in.erase(iter);
This has linear time complexity, and works with all types of iterators/containers!
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::listto astd::vectorisn't possible).Values can only ever be move to the back of out, requiring the container to have a
push_backmember function.
Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.
To accomplish this, the algorithm could take an output iterator instead.
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);
iter = in.erase(iter);
return out;
Additinally, it would be nice to check at compile time whether
Container::value_typematchesstd::iterator_traits<OutIter>::value_typeand whetherUnaryPredicateaccepts an argument of typeContainer::value_type. This could be done with SFINAE orstatic_asserts.
answered 1 hour ago
hoffmale
5,192835
answered 1 hour ago
hoffmale
5,192835
answered 1 hour ago
hoffmale
5,192835
answered 1 hour ago
hoffmale
5,192835
5,192835
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element ofinonce. Did you overlook theiterparameter in the second call tostd::find_if?
– hoffmale
19 mins ago
in.erase(iter)is not O(1) for most containers.
– Deduplicator
18 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of arestd::vectorandstd::deque. If that matters, those could be special cased.
– hoffmale
15 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
 |Â
show 1 more comment
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element ofinonce. Did you overlook theiterparameter in the second call tostd::find_if?
– hoffmale
19 mins ago
in.erase(iter)is not O(1) for most containers.
– Deduplicator
18 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of arestd::vectorandstd::deque. If that matters, those could be special cased.
– hoffmale
15 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
That's O(n * O(erase)), likely O(n²). Inefficient.
– Deduplicator
22 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of
in once. Did you overlook the iter parameter in the second call to std::find_if?– hoffmale
19 mins ago
@Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of
in once. Did you overlook the iter parameter in the second call to std::find_if?– hoffmale
19 mins ago
in.erase(iter) is not O(1) for most containers.– Deduplicator
18 mins ago
in.erase(iter) is not O(1) for most containers.– Deduplicator
18 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are
std::vector and std::deque. If that matters, those could be special cased.– hoffmale
15 mins ago
@Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are
std::vector and std::deque. If that matters, those could be special cased.– hoffmale
15 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
If you only look at the standard containers… But QT for example has its own.
– Deduplicator
14 mins ago
 |Â
show 1 more comment
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206221%2fmoving-elements-satisfying-a-predicate-from-one-container-to-another%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
