Re: Andrei's "iterators must go" presentation
Hakusa wrote:
Sorry, this is in reply to no particular one, but...
I hacked out a function earlier today and, thinking of this thread,
wanted to see how it would look with ranges. But, either due to my
misunderstanding with ranges, or the nature of ranges, or my problem,
the range version can't do what the random access iterator version
can.
Here's the code for the iterator version (one of).
// Split container 'what' by 'that'.
// ex: split( string("two words"), ' ' ) ==> { string("two"), string
("words") }
template< typename C, typename T > static
std::vector<C> split_disp( const C& what, const T& that,
std::random_access_iterator_tag )
{
typedef typename C::const_iterator CIt;
std::vector<C> ret;
CIt from = what.begin(), end = what.end();
while( from < end )
{
CIt to = std::find( from, end, that );
ret.push_back( C(from,to) );
from = ++to; // ++to to skip the 'that' to should be pointing
to.
}
return ret;
}
This can easily be written without the need for operator< or the ability
to iterate past the end:
// Split container 'what' by 'that'.
// ex: split( string("two words"), ' ' ) ==> { string("two"), string
// ("words") }
template< typename C, typename T > static
std::vector<C> split_disp( const C& what, const T& that)
{
typedef typename C::const_iterator CIt;
std::vector<C> ret;
CIt from = what.begin(), end = what.end();
while( from != end )
{
CIt to = std::find( from, end, that );
ret.push_back( C(from,to) );
if (to != end) ++to; // skip 'that'
from = to;
}
if (ret.empty())
ret.push_back( what );
return ret;
}
I removed the random_access_iterator_tag from the signature, because
this rewrite can work efficiently with input iterators.
This is actually the implementation of the function. The callable
version used tag dispatching because C::iterators might not allow <
comparisons unless they're random access (my algorithm requires the
ability to go past end). The other version of this function, using
input_iterators, contains redundant code to honor not going past end.
Obviously, with ranges, one should never have to worry about whether
one is past the end because it is either an empty range or not. But,
my algorithm, for the sake of not having redundant code, REQUIRES that
one CAN go past the end. In the slide, popFront() actually does assert
that the range is not empty before incrementing the pointer, so my
algorithm would not work if ranges are to be as they are in the slide.
So, this is what I came up with for the range version and it looks
something like the input_iterator version:
template< typename C, typename T >
vector<C> split_disp( const C& what, const T& that )
{
typedef typename C::const_range Rng;
vector<C> ret;
Rng rng = what.all();
if( rng.empty() )
return ret;
Rng rng2 = std::find( rng, that );
ret.push_back( C(rng-rng2) );
rng = rng2;
while( !rng.empty() )
{
rng.popFront();
rng2 = std::find( rng, that );
ret.push_back( C(rng-rng2) );
rng = rng2;
}
return ret;
}
If I rewrite my version to use ranges, I end up with:
template< typename C, typename T > static
std::vector<C> split_disp( const C& what, const T& that)
{
typedef typename C::const_range Range;
std::vector<C> ret;
Range range = what.all();
while( !range.empty() )
{
Range range2 = std::find( range, that );
ret.push_back( C(range-range2) );
if (!range2.empty()) range2.popFront(); // skip 'that'
range = range2;
}
if (ret.empty())
ret.push_back( what );
return ret;
}
The only 'problem' that I have with this code is that the range-
arithmetic (range - range2) could be confusing. For example, what would
be the result if the two ranges do not have a common start or end point?
I don't see how its possible for me to do my random access version
with ranges. If ranges DO allow one to go past the end, then a method
of testing that this has happened must to be available, at least for
random access ranges.
Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]