How to create copy_if algorithm?

[silverburgh.meryl]

In STL, there is no copy_if algorithm. But how can I emulate that?
I am thinking about using find_if and then a copy.
But how can I pass the InputIterator (begin and end) to copy so that it
knows the range it tries to copy from.

Thanks for any idea.

[Victor Bazarov]

si***************@gmail.com wrote:

In STL, there is no copy_if algorithm. But how can I emulate that?
What should it do?
I am thinking about using find_if and then a copy.
But how can I pass the InputIterator (begin and end) to copy so that it
knows the range it tries to copy from.

Think of 'copy'...

template<class Iter, class Iter2 class Func>
void copy_if(Iter beg, Iter end, Iter2 beg2, Func f)
{
while (beg != end) {
if (f(*beg))
*beg2++ = *beg;
beg++;
}
}

Here, 'beg2' only grows when something is assigned. If you want different
behaviour, modify the code.

V
--
Please remove capital As from my address when replying by mail

[Ben Pope]

si***************@gmail.com wrote:

In STL, there is no copy_if algorithm. But how can I emulate that?
I am thinking about using find_if and then a copy.
But how can I pass the InputIterator (begin and end) to copy so that it
knows the range it tries to copy from.

What would you like copy_if to do in case of a false? Ignore that
element on the input and output, or just the input? I.e., if it fails,
do you increment the output iterator before the next attempt?

Ben Pope
--
I'm not just a number. To many, I'm known as a string...

[silverburgh.meryl]

In the case of a false, just do not copy (ignore that element on the
input). And i think the output iterator only increment everytime we
add something to the output. So in the case of a false, we ignore the
input element, do not add that to the output, hence the output iterator
should be unchanged. (I think).

Thank you.

[Ben Pope]

si***************@gmail.com wrote:

In the case of a false, just do not copy (ignore that element on the
input). And i think the output iterator only increment everytime we
add something to the output. So in the case of a false, we ignore the
input element, do not add that to the output, hence the output iterator
should be unchanged. (I think).

I think it's debatable as to what's best, try the following:

#include <algorithm>
#include <iostream>
#include <iterator>

template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred)
{
InputIterator currentIn = first;
OutputIterator currentOut = result;
while (currentIn != last) {
if (pred(*currentIn)) {
*currentOut = *currentIn;
++currentOut;
++currentIn;
} else {
++currentIn;
}
}
return currentOut;
}

template <class T>
bool is_not_3(T val) {
return val != 3;
}

int main()
{
int input[6] = {0,1,2,3,4,5};
int output[6] = {0,0,0,0,0,0};
copy_if(input, input+6, output, is_not_3<int>);
copy_if(input, input+6,
std::ostream_iterator<int>(std::cout,", "), is_not_3<int>);
}
Ben Pope
--
I'm not just a number. To many, I'm known as a string...

[Julián Albo]

si***************@gmail.com wrote:

In STL, there is no copy_if algorithm. But how can I emulate that?

You can use remove_copy_if with the condition negated.

--
Salu2

[Marco Wahl]

>> [...]

In STL, there is no copy_if algorithm. But how can I emulate that?

template<class Iter, class Iter2 class Func>
void copy_if(Iter beg, Iter end, Iter2 beg2, Func f)
{
while (beg != end) {
if (f(*beg))
*beg2++ = *beg;
beg++;
}
}

Here, 'beg2' only grows when something is assigned. [...]

When I would like to use this copy_if in my code should I put it into
namespace std?

[Kai-Uwe Bux]

Marco Wahl wrote:

[...]
In STL, there is no copy_if algorithm. But how can I emulate that?

template<class Iter, class Iter2 class Func>
void copy_if(Iter beg, Iter end, Iter2 beg2, Func f)
{
while (beg != end) {
if (f(*beg))
*beg2++ = *beg;
beg++;
}
}

Here, 'beg2' only grows when something is assigned. [...]

When I would like to use this copy_if in my code should I put it into
namespace std?

No.

"It is undefined for a C + + program to add declarations or definitions to
namespace std or namespaces within namespace std unless otherwise
specified. A program may add template specializations for any standard
library template to namespace std. Such a specialization (complete or
partial) of a standard library template results in undefined behavior
unless the declaration depends on a user-defined name of external linkage
and unless the specialization meets the standard library requirements for
the original template." [17.4.3.1/1]
Best

Kai-Uwe Bux

[Marco Wahl]

>>>> [...]

In STL, there is no copy_if algorithm. But how can I emulate that?

template<class Iter, class Iter2 class Func>
void copy_if(Iter beg, Iter end, Iter2 beg2, Func f)
{ [...]
}

When I would like to use this copy_if in my code should I put it into
namespace std?

No.

"It is undefined for a C + + program to add declarations or definitions to
namespace std or namespaces within namespace std unless otherwise
specified. A program may add template specializations for any standard
library template to namespace std. Such a specialization (complete or
partial) of a standard library template results in undefined behavior
unless the declaration depends on a user-defined name of external linkage
and unless the specialization meets the standard library requirements for
the original template." [17.4.3.1/1]

Thank you very much for the clarification.

[Michiel.Salters]

Ben Pope wrote:

si***************@gmail.com wrote:

In the case of a false, just do not copy (ignore that element on the
input). And i think the output iterator only increment everytime we
add something to the output. So in the case of a false, we ignore the
input element, do not add that to the output, hence the output iterator
should be unchanged. (I think).

I think it's debatable as to what's best, try the following:

#include <algorithm>
#include <iostream>
#include <iterator>

template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred)
{
InputIterator currentIn = first;
OutputIterator currentOut = result;
while (currentIn != last) {
if (pred(*currentIn)) {
*currentOut = *currentIn;
++currentOut;
++currentIn;
} else {
++currentIn;
}
}
return currentOut;
}

You do realize that it won't work for actual Output Iterators? Like
ostream_iterators?
The requirement is pretty clear for those: you must call operator*
before incrementing.

HTH,
Michiel Salters

[Ben Pope]

Mi*************@tomtom.com wrote:

Ben Pope wrote:

#include <algorithm>
#include <iostream>
#include <iterator>

template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred)
{
InputIterator currentIn = first;
OutputIterator currentOut = result;
while (currentIn != last) {
if (pred(*currentIn)) {
*currentOut = *currentIn;
++currentOut;
++currentIn;
} else {
++currentIn;
}
}
return currentOut;
}

You do realize that it won't work for actual Output Iterators? Like
ostream_iterators?
The requirement is pretty clear for those: you must call operator*
before incrementing.

Now that you mention it, it does ring a bell. My example using
ostream_iterator appeared to work in VC8.

I also completely missed Victors implementation, which does what you
suggest.

Thanks for catching that.

Ben Pope
--
I'm not just a number. To many, I'm known as a string...

[Dietmar Kuehl]

si***************@gmail.com wrote:

In STL, there is no copy_if algorithm. But how can I emulate that?
The one and only "correct" way to do this is to use
'std::remove_copy_if()' with a negated predicate. Although this
thread has seen semantically correct implementations of 'copy_if()'
a "real" implementation could do more than just copying the elements
to a destination.
I am thinking about using find_if and then a copy.

You are thinking in the correct direction. Of course, for real input
input iterators 'std::find_if()' can only be used to locate the
next element to be copied. This, unfortunately, may actually result
in a little bit inferior performance when always using
'std::find_if()' to locate the next element if the sequence of
elements to be copied is dense because there is likely a small
overhead when starting an effective search.

If the input sequence is made up of forward iterators, this problem
disappears because in this case you can also search the end of the
sequence to be copied and only rather unlikely setups behave worse
than a trivial approach (those where e.g. the elements to be copied
alternate with those not to be copied).

It is worth noting that a really good implementation of algorithms
could do fancy things. For example, when writing forward iterators
to a 'std::back_inserter()', the algorithm could determine the
number of elements which will be copied and create the necessary
room up front for known containers (e.g. the standard ones).
Typically, the standard algorithms are already specialized for
certain situations in most standard library implementations. This
can, however, be taken much further. On issue which soon arises,
however, is that the generic algorithm has no information on the
actual structures or e.g. the density of objects to be copied. It
would be quite interesting for tuning algorithms to know e.g. the
relative performance of different operations and minimize the use
of the more expensive ones. Likewise, it would be helpful to have
some information about the set up, e.g. whether the amount of
elements to be copied is rather big or rather small.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

[Csaba]

=?ISO-8859-15?Q?Juli=E1n?= Albo <JU********@terra.es> wrote in
news:43********@x-privat.org:

si***************@gmail.com wrote:

In STL, there is no copy_if algorithm. But how can I emulate that?

You can use remove_copy_if with the condition negated.

Scott Meyers in "Effective STL" item 36 (Understand the proper
implementation of copy_if) writes: Implementing copy_if with
return remove_copy_if( begin, end, destBegin, std::not1(pred) )

puts an unnecessary requirement on pred to be an /adaptable/ function
object, like derived from std::unary_function.

He then recommends a simple while loop.

--
Life is complex, with real and imaginary parts.

[Dietmar Kuehl]

Csaba wrote:

Scott Meyers in "Effective STL" item 36 (Understand the proper
implementation of copy_if) writes: Implementing copy_if with

return remove_copy_if( begin, end, destBegin, std::not1(pred) )

puts an unnecessary requirement on pred to be an /adaptable/ function
object, like derived from std::unary_function.
This is, however, a restriction easily lifted: a suitable signature
of the predicate can easily be derived from the iterator's value type
and the fact that the result has to be convertible to 'bool'. Thus,
'std::not1(pred)' might not be the optimal solution, it comes very
close to the optimal solution which uses a specialized negator for
the predicate which does not impose the restriction of the predicate
to be adaptable.
He then recommends a simple while loop.

Due to reasons stated in other articles in this thread, I think this
is a fairly bad recommendation! It may be an appropriate approach
for non-critical code but I think it is entirely inappropriate for
a generic implementation of 'copy_if()' which is used in situations
yet unknown.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

[Csaba]

Dietmar Kuehl <di***********@yahoo.com> wrote in news:45nmm2F7gfacU2
@individual.net:

Csaba wrote:

Scott Meyers in "Effective STL" item 36 (Understand the proper
implementation of copy_if) writes: [snip] He then recommends a simple while loop.

(just like Victor Bazarov did in this post:
RB****************@newsread1.mlpsca01.us.to.verio. net)

Due to reasons stated in other articles in this thread, I think this
is a fairly bad recommendation! It may be an appropriate approach
for non-critical code but I think it is entirely inappropriate for
a generic implementation of 'copy_if()' which is used in situations
yet unknown.

Why ? Half of <algorithm> is little more than

for (; _First != _Last; ++_First)
...
--
Life is complex, with real and imaginary parts.

[Daniel T.]

In article <43**********************@taz.nntpserver.com>,
Ben Pope <be***************@gmail.com> wrote:

Mi*************@tomtom.com wrote:

Ben Pope wrote:

#include <algorithm>
#include <iostream>
#include <iterator>

template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred)
{
InputIterator currentIn = first;
OutputIterator currentOut = result;
while (currentIn != last) {
if (pred(*currentIn)) {
*currentOut = *currentIn;
++currentOut;
++currentIn;
} else {
++currentIn;
}
}
return currentOut;
}

You do realize that it won't work for actual Output Iterators? Like
ostream_iterators?
The requirement is pretty clear for those: you must call operator*
before incrementing.

Now that you mention it, it does ring a bell. My example using
ostream_iterator appeared to work in VC8.

I also completely missed Victors implementation, which does what you
suggest.

Thanks for catching that.

Don't feel bad Ben, your op* *is* called on your output iterator before
each increment.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Daniel T.]

In article <Xn*******************@81.174.50.80>,
Csaba <ro**@localhost.localdomain> wrote:

=?ISO-8859-15?Q?Juli=E1n?= Albo <JU********@terra.es> wrote in
news:43********@x-privat.org:

si***************@gmail.com wrote:

In STL, there is no copy_if algorithm. But how can I emulate that?

You can use remove_copy_if with the condition negated.

Scott Meyers in "Effective STL" item 36 (Understand the proper
implementation of copy_if) writes: Implementing copy_if with
return remove_copy_if( begin, end, destBegin, std::not1(pred) )

puts an unnecessary requirement on pred to be an /adaptable/ function
object, like derived from std::unary_function.

He then recommends a simple while loop.

Just don't make your pred require the not1 wrapper...

return remove_copy_if( begin, end, destBegin, not_pred );

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Dietmar Kuehl]

Csaba wrote:

Dietmar Kuehl <di***********@yahoo.com> wrote in news:45nmm2F7gfacU2
@individual.net:

Csaba wrote:

Scott Meyers in "Effective STL" item 36 (Understand the proper
implementation of copy_if) writes: [snip] He then recommends a simple while loop.
(just like Victor Bazarov did in this post:
RB****************@newsread1.mlpsca01.us.to.verio. net)

Just because more people give it, bad advice does not become better.
Due to reasons stated in other articles in this thread, I think this
is a fairly bad recommendation! It may be an appropriate approach
for non-critical code but I think it is entirely inappropriate for
a generic implementation of 'copy_if()' which is used in situations
yet unknown.

Why ? Half of <algorithm> is little more than

for (; _First != _Last; ++_First)
...

This is true for straight forward implementations of the algorithms.
The primary advantage of creating a simple implementation is that it
suffices for standard compliance, is easily created, and less error
prone. Since the demand for tuned implementations of algorithms is
apparently not [yet?] very high, the algorithms implementations
indeed tend to be fairly simple.

However, this does not change the fact, that even simple algorithms
like 'std::copy()' can be tuned to perform much better than a simple
loop in many situations. Even for the most simple applications, e.g.
when copying a pointer delimited sequence, 'std::copy()' can be
improved over the simple loop, e.g. by unrolling it (of course, like
most optimizations, this is a time vs. executable size trade-off and
the applyability of the optimization depends on the platform used).

You will not benefit from optimizations like this when using a simple
loop instead of an algorithm. Whether these optimizations are present
is, of course, a quality of implementation issue. As far as I can
tell, there is at least some demand for optimized algorithms making
the likelihood to come across an improved algorithms library bigger.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence