Re: [boost] [Range] Expected complexity constraints

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2006-05-09 08:42:43

David Abrahams wrote:
> Thorsten Ottosen <thorsten.ottosen_at_[hidden]> writes:

>> > Possible alternatives distinguish the ranges that actually give the
>> > expected complexity:
>> >
>> >   a. Provide separate concepts for O1EndRange and O1SizeRange
>> >
>> >   b. Provide traits to detect has_o1_end and has_o1_size
>> >
>> > Probably you'd want to do both.
>>
>>
>>These are a separate issue, I think, I'll give it some thought. We can't 
>>portable detect O(1) size for list, because it varies with 
>>implementations, rigth?
> 
> 
> Right.  You return false by default and true on implementations where
> you know that to be the answer.

I might as well just say up front that I don't have time for this. But 
I'd be happy to include something if someone submits it.

> 
>> > By the way, you can get back O(1) for end(s) where s is a
>> > null-terminated string if you allow the end iterator to have a
>> > different type from the begin iterator... but those ranges don't play
>> > well with the standard algorithms.
>>
>>By implementing iterator compaison as *valid_it == 0 ?
> 
> 
> Yes.
> 
> 
>>The new version will feature special functions for generating ranges for
>>the string library. We could probably wrap char* iterators in
>>boost::string_iterator<char>. Are you sure we need the end iterator to 
>>be a different type?
> 
> 
> No, you don't, in fact.  Comparisons just get a little more expensive
> than they'd need to be otherwise.

You mean more expensive because you have to see which irerator that is 
the valid one?

In that case it might be reasoable to always mandate the left argument 
to be the valid iterator:

bool operator!=( string_iterator<Char> l, string_iterator<Char> r )
{
   BOOST_ASSERT( l.base() != 0 && "left iterator of != must be valid" );
   BOOST_ASSERT( r.base() == 0 && "right iterator of != must be inval.");
   return *l != 0;
}

-Thorsten