[Range] Expected complexity constraints
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. 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. 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. -- Dave Abrahams Boost Consulting www.boost-consulting.com
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
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
David Abrahams wrote:
Thorsten Ottosen <thorsten.ottosen@dezide.com> 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
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
David Abrahams wrote:
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
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?
The checks are more complicated than that, but that's the general idea.
In that case it might be reasoable to always mandate the left argument to be the valid iterator:
No, that violates EqualityComparable, not to mention every reasonable person's expectations. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
You mean more expensive because you have to see which irerator that is the valid one?
The checks are more complicated than that, but that's the general idea.
In that case it might be reasoable to always mandate the left argument to be the valid iterator:
No, that violates EqualityComparable, not to mention every reasonable person's expectations.
In that case I think it's not worth doing. I'll leave it up to Pavol to put it in the string library. -Thorsten
participants (2)
-
David Abrahams -
Thorsten Ottosen