Re: [boost] [Range] Expected complexity constraints

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2006-05-08 17:33:38

David Abrahams wrote:

 > I note that the range library still supports the following:
 >
 >   * treating null-terminated strings as Ranges where the complexity of
 >     end(s) is O(N)
 >
 >   * treating pairs of non-random-access iterators as Ranges where the
 >     complexity of size(p) is O(N)
 >
 > In my view both of these would ideally be eliminated.  The argument
 > for the latter is slightly weaker because of prcedent in the std,
 > although the LWG is considering removing it.

They are both eliminated in the new version.

 > 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?

 > 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 ?

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?

-Thorsten