From: David Abrahams (dave_at_[hidden])
Date: 2006-05-08 23:26:38
Thorsten Ottosen <thorsten.ottosen_at_[hidden]> writes:
> 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?
Right. You return false by default and true on implementations where
you know that to be the answer.
> > 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.
-- Dave Abrahams Boost Consulting www.boost-consulting.com