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
> 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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk