Thorsten Ottosen <thorsten.ottosen@dezide.com> 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