std::partition

[jota]

Is there any more hands on way to make a copy of a vector where pred is
TRUE.(in the code snip)
And I need a copy becourse OnFX might or might not alter List.

typedef std::vector<CS *> LIST;
LIST List;
LIST::iterator et=std:artition(List.begin(),List.end(),pred);
LIST l;
for(LIST::iterator i=List.begin();i !=et;i++)
l.push_back(*i);
std::for_each(l.begin(),l.end(),std::mem_fun(&CS::OnFX));

//thx
//jota

 

[Rolf Magnus]

Is there any more hands on way to make a copy of a vector where pred
is TRUE.(in the code snip)
And I need a copy becourse OnFX might or might not alter List.

typedef std::vector<CS *> LIST;
LIST List;
LIST::iterator et=std:artition(List.begin(),List.end(),pred);
LIST l;
for(LIST::iterator i=List.begin();i !=et;i++)
l.push_back(*i);
std::for_each(l.begin(),l.end(),std::mem_fun(&CS::OnFX));

It seems that a copy_if function was forgotten in the standard library,
but you can easily write your own:

(from TC++PL)

template<class In, class Out, class Pred>
Out copy_if(In first, In last, Out res, Pred p)
{
while (first != last) {
if (p(*first)) *res++ = *first;
++first;
}
return res;
}

Then you can do:

copy_if(List.begin(), List.end(), std::back_inserter(l), pred);

 

[Dietmar Kuehl]

It seems that a copy_if function was forgotten in the standard library,

It is spelled 'std::remove_copy_if()' and you need to negate the predicate.

but you can easily write your own:

Of course, this "easy" implementation is inferior to a really good
implementation. Even for something simple as this it is possible to
implement optimizations, e.g. loop unrolling (what the compiler does
for you is just a small step) and the segmented sequence optimization
(which of course applies only if segmented sequence come into the play).

 

[Rolf Magnus]

It is spelled 'std::remove_copy_if()' and you need to negate the
predicate.

Stroustrup says something else. He writes in his book that copy_if _was_
forgotten, and gives the code that I wrote down as alternative.

 

[jota]

Stroustrup says something else. He writes in his book that copy_if _was_

forgotten, and gives the code that I wrote down as alternative.

And I used it, and it worked just fine!
'std::remove_copy_if()' seems to be backwords of what te real world needs!
//jota

 

[Jonathan Turkanis]

library,

It is spelled 'std::remove_copy_if()' and you need to negate the predicate.

Of course, this "easy" implementation is inferior to a really good
implementation. Even for something simple as this it is possible to
implement optimizations, e.g. loop unrolling (what the compiler does
for you is just a small step) and the segmented sequence optimization
(which of course applies only if segmented sequence come into the

play).

Hi Dietmar,

Would you explain what the segmented sequence optimization is? My
googling only turns up two other references (both by you) which assume
the reader already knows what it is.
It sounds interesting. ...

Jonathan

 

[Dietmar Kuehl]

Would you explain what the segmented sequence optimization is? My
googling only turns up two other references (both by you) which assume
the reader already knows what it is.

I thought I explained it in some Usenet articles already. However, here
we go:

There are a bunch of segmented sequences in the standard library and the
user might provide own containers which might also be segmented. With a
segmented sequence I mean something which is split into some lower level
segments. 'std::deque' is the obvious example: it is a sequence which is
actually represented by an array of subsequences, i.e. an array of segments.
Other examples include 'std::[io]streambuf_iterator's (the segments here are
the internal character buffers), certain hashes (the segments are the
buffers), etc. The problems with these sequences is that iterators typically
need to do additional checks and compilers cannot really remove them because
they don't know about the structure.

The idea of the optimization is rather simple: instead of processing the
sequence uniformly, the segments are individually processed. That is, the
algorithm actually just iterates over the segments and delegates processing
of the segments to an algorithm using lower level iterators. For example,
rather than using 'std::deque<T>::iterator', the segments can be processed
using 'T*' which is much faster on most systems.

The major trick is to define an interface which tells the algorithm that it
is supposed to handle a segmented sequence and how to access the individual
segments. I don't have a complete implementation of this stuff available
but when I used it, I used something like 'segment_traits' which provided
two kinds of iterators:
- an iterator for the segments
- an iterator for the contents of a segment

The segment iterator would be obtained from the passed 'begin()' and 'end()'
iterators and provide access to the begin and end of the current segment. I
just looked at my 'for_each()' which provides this optimization but it is
pretty confusing. You can have a look at it at
<http://cvs.sourceforge.net/viewcvs.py/cxxrt/cxxrt-source/include/cxxrt/for_each.h?view=markup>.
The actual logic is hidden in the '_Cxxrt_iterhelper' (which is also
available from the CVS). Since then I have decided for myself that
optimizations like this cannot really be factored out into class but that
algorithms should aggressively reuse other algorithms and I would implement
the optimization now right in one algorithms which is internally used by
other algorithms.

Matt Austern coined the term "segmented sequences" and gave a presentation
on the idea at a workshop on Generic Programming at Schloß Dagstuhl. He
come up with the idea in the context of hashes he was implementing.