Re: [Boost-users] [iterators][range][rangeex] range concatenation

Subject: Re: [Boost-users] [iterators][range][rangeex] range concatenation
From: Dmitry Vinogradov (sraider_at_[hidden])
Date: 2009-04-06 20:31:50

Thorsten Ottosen wrote:
> Dmitry Vinogradov skrev:
>> Regarding efficiency, can you look thru my rough concat() 
>> implementation attached to discover any its disadvantages?
> 
> Wow. Nice work!
> 
> Some comments:
> 
> 0. I prefer to use unsigned instead of std::size_t. std::size_t can be 
> larger than a word IIRC.
> 
> 1.
> You can call Stabilize() in increment().
> 
> 2.
> You should probably check It == End1 before Range == 0, because
> Range == 0 will be true most of the time during the iteration through 
> the first range.

Thanks, I'll use these hints.

> 3. How can you avoid to store the second end iterator?

I need to store three iterators: current state (It) - it's for sure, and
the "gap" between ranges - Range1.end() and Range2.begin() for backward
and forward jumping between Range1 and Range2. These iterators is all
that I store. I can store Range1.end() and Range2.begin() as usual
iterators, not as variants. Currently they are stored as variants just
for simple comparision with `It' variant.

It's possible to get rid of Range member and use It.which() instead, but
I think it's hard to control `which' member of variant while having
typeof(TIterator1)==typeof(TIterator2), because "It = SomeIterator;"
statement will lead always to It.which()==0. Self-invented variant could
help here.

> How does the performace compare to creating a vector of references?
> (remember to call reserve()).

I think it's anyway very useful to have concat(). One can make his own
decision between concat() and vector of references for every particular
case. Creating vector will always lead to heap allocation and IFAIK it's
not time-cheap. Add time for copying references. Summary time will
depend a lot of particular algorithm is used for a range, so again I
think everyone must have a choice.

> If the performance is good,this baby should be included in the range 
> library asap.

In additional for all, my implementation miss one big thing: it doesn't
have an auto-detection of ConcatIterator traversal category. So, I bet
for Neil's implementation he noticed in this thread ;)