Query regarding time complexity requirements of iterators in custom container
Hi there- currently working on Colony, last version I'm working on has achieved constant-time(amortised) time-complexity for iterator operations, except for the random-access operators (+, -, +=, -=, [], >, <, >=, <=). It's not possible to make these constant-time due to the nature of the algorithms and structure of container. Ion pointed out to me that there is an obscure C++ requirement for iterators that all operations be constant-time. Given this, is it worth keeping these in Colony before submitting to Boost, or would it be best to remove them and make the iterator bidirectional-only prior? Cheers, Matt
On January 22, 2016 4:50:56 PM EST, Soul Studios <matt@soulstudios.co.nz> wrote:
Ion pointed out to me that there is an obscure C++ requirement for iterators that all operations be constant-time. Given this, is it worth keeping these in Colony before submitting to Boost, or would it be best to remove them and make the iterator bidirectional-only prior?
I don't know anything about Colony, but violating requirements for iterators would not be a good idea. However, if you provide a non-standard means to access the iterators, you could give users the choice to gain random access while not accidentally using the non-conforming random access iterators in normal contexts. IOW, don't use begin() and end(), but some variant thereof. ___ Rob (Sent from my portable computation engine)
I don't know anything about Colony, but violating requirements for iterators would not be a good idea. However, if you provide a non-standard means to access the iterators, you could give users the choice to gain random access while not accidentally using the non-conforming random access iterators in normal contexts. IOW, don't use begin() and end(), but some variant thereof.
I see what you mean, however not sure if providing an additional iterator type would solve the problem from the point of view of the standard - you'd still be giving std::find and the like with an iterator and by definition that iterator must be compliant - which it wouldn't be. m@
On January 24, 2016 4:10:19 PM EST, Soul Studios <matt@soulstudios.co.nz> wrote:
I don't know anything about Colony, but violating requirements for iterators would not be a good idea. However, if you provide a non-standard means to access the iterators, you could give users the choice to gain random access while not accidentally using the non-conforming random access iterators in normal contexts. IOW, don't use begin() and end(), but some variant thereof.
I see what you mean, however not sure if providing an additional iterator type would solve the problem from the point of view of the standard - you'd still be giving std::find and the like with an iterator and by definition that iterator must be compliant - which it wouldn't be.
The difference is that the user is choosing to use the non-conforming iterators with knowledge aforethought. Yes, it can increase std::find()'s complexity, which is non-conforming, but it will work and the user will have selected it. I see it as similar to using insert(begin(), value) when push_front() isn't available. ___ Rob (Sent from my portable computation engine)
I see what you mean, however not sure if providing an additional iterator type would solve the problem from the point of view of the standard - you'd still be giving std::find and the like with an iterator and by definition that iterator must be compliant - which it wouldn't be.
The difference is that the user is choosing to use the non-conforming iterators with knowledge aforethought. Yes, it can increase std::find()'s complexity, which is non-conforming, but it will work and the user will have selected it. I see it as similar to using insert(begin(), value) when push_front() isn't available.
You're missing the point. It still won't conform to the standard, regardless of user knowledge (which could be established via documentation at any rate). Anyway, I've done some testing with bidirectional iterators and I'll be sticking with them. They actually clarify and reinforce the use case for the container, in a way, after checking them against the library I developed. Thanks-
Yes, we lose access to std::find in particular under GCC I think.
std::find requires only input iterators. And even if it did need random access iterators, I don't think it would enable_if on the iterator category. You're sounding a bit confused...
... pardon? That's a bit rude, coming from someone who doesn't understand that std::vector can't have a + operator that isn't O(1). Yes, I conflated the std::find requirement with another bug I had earlier in development... Bye.
On January 25, 2016 5:15:31 PM EST, Soul Studios <matt@soulstudios.co.nz> wrote:
I see what you mean, however not sure if providing an additional iterator type would solve the problem from the point of view of the standard - you'd still be giving std::find and the like with an iterator and by definition that iterator must be compliant - which it wouldn't be.
The difference is that the user is choosing to use the non-conforming iterators with knowledge aforethought. Yes, it can increase std::find()'s complexity, which is non-conforming, but it will work and the user will have selected it. I see it as similar to using insert(begin(), value) when push_front() isn't available.
You're missing the point. It still won't conform to the standard, regardless of user knowledge (which could be established via documentation at any rate).
No. I didn't miss the point. The user, writing standard-conforming code, would not get your random access iterators, because begin() and end() wouldn't provide them, and the range-based for loop wouldn't use them. OTOH, if the user used another means to get your random access iterators and chose to use them with std::find(), the code would be non-conforming, but might do exactly what the user wanted.
Anyway, I've done some testing with bidirectional iterators and I'll be sticking with them. They actually clarify and reinforce the use case for the container, in a way, after checking them against the library I developed.
Okay ___ Rob (Sent from my portable computation engine)
No. I didn't miss the point. The user, writing standard-conforming code, would not get your random access iterators, because begin() and end() wouldn't provide them, and the range-based for loop wouldn't use them. OTOH, if the user used another means to get your random access iterators and chose to use them with std::find(), the code would be non-conforming, but might do exactly what the user wanted.
Okay - but the code I'm writing, in writing the non-conformant code, would be non-conformant, no? Anyway, we're splitting hairs at this point I guess :) A valid alternative would be to have functions separate to the iterator which alter the iterator state, but don't belong to the iterator as such. It's probably worth doing, but would make for fairly ugly code compared to standard operator-based functions.
Soul Studios wrote:
std::vector can't have a + operator that isn't O(1).
I was describing a filtering iterator adaptor over a std::vector::iterator. Advancing such an iterator needs to evaluate its filter predicate for each element, so its operator+ (if it has one) will be O(N). Good luck with your project. Regards, Phil.
Soul Studios wrote:
currently working on Colony,
Links might help for those who don't know what that is :-)
last version I'm working on has achieved constant-time(amortised) time-complexity for iterator operations, except for the random-access operators (+, -, +=, -=, [], >, <, >=, <=). It's not possible to make these constant-time due to the nature of the algorithms and structure of container. Ion pointed out to me that there is an obscure C++ requirement for iterators that all operations be constant-time. Given this, is it worth keeping these in Colony before submitting to Boost, or would it be best to remove them and make the iterator bidirectional-only prior?
IIRC, these operators are O(log N), right? So you can provide an operator+ that is more efficient than std::advance would be, right? I had a similar issue with a filtering iterator adaptor over a std::vector::iterator; is that bidirectional or random access? Its operator< is O(1) but its operator+ is O(N). Perhaps at some point in the future we'll have a more fine-grained set of concepts that allow us to define iterator features more precisely. For the time being, you should definitely implement the operators (if I'm right about them being logarithmic), and then decide whether to declare the iterator to be random-access or not. Weigh up the merits of strict compliance vs. pragmatism. If you don't declare it as random access, what happens? You might like to consider, for example, that some std algorithms are documented to require random access iterators - but typically work in practice with other iterators as long as they implement the required operators. Regards, Phil.
IIRC, these operators are O(log N), right? So you can provide an operator+ that is more efficient than std::advance would be, right?
Close enough - in best case it approximates O(1), in worst case O(N), general case probably closer to O(log N).
I had a similar issue with a filtering iterator adaptor over a std::vector::iterator; is that bidirectional or random access? Its operator< is O(1) but its operator+ is O(N).
Must be a very strange underlying model if the + operator is anything other than O(1)? At any rate, vector iterators are random access.
Perhaps at some point in the future we'll have a more fine-grained set of concepts that allow us to define iterator features more precisely. For the time being, you should definitely implement the operators (if I'm right about them being logarithmic), and then decide whether to declare the iterator to be random-access or not. Weigh up the merits of strict compliance vs. pragmatism. If you don't declare it as random access, what happens? You might like to consider, for example, that some std algorithms are documented to require random access iterators - but typically work in practice with other iterators as long as they implement the required operators.
Yes, we lose access to std::find in particular under GCC I think. I'll remove them for the moment, which's a shame since the code took a long time to write, but I don't see any way around it, unless anybody else has input on the matter.
Soul Studios wrote:
If you don't declare it as random access, what happens? You might like to consider, for example, that some std algorithms are documented to require random access iterators - but typically work in practice with other iterators as long as they implement the required operators.
Yes, we lose access to std::find in particular under GCC I think.
std::find requires only input iterators. And even if it did need random access iterators, I don't think it would enable_if on the iterator category. You're sounding a bit confused... Regards, Phil.
participants (3)
-
Phil Endecott -
Rob Stewart -
Soul Studios