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 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;
}
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.
Range-based idioms will often be different from iterator-based idioms.
There is a function splitter() in D's standard library that does
something similar, except that it's lazy - instead of filling a
container with split sequences, it gives you a range that allows you to
examine each item in turn, lazily. Often, this avoids some memory
allocation (very large if the input is large) and also offers you the
ability to copy into a back_insert range if you do want to copy. A lot
of the advantages of ranges is that they allow convenient definition of
various lazy semantic operations.
Anyhow, I'd implement your function like this:
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();
while (!rng.empty())
{
C item;
for (; !rng.empty() && rng.front() != that; rng.popFront())
item.push_back(rng.front());
ret.push_back(move(item));
if( rng.empty() )
break;
rng.popFront(); // skip the separator
}
return ret;
}
This works with input iterators, as it should.
Andrei
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]