Re: [boost] Query regarding time complexity requirements of iterators in custom container

Subject: Re: [boost] Query regarding time complexity requirements of iterators in custom container
From: Soul Studios (matt_at_[hidden])
Date: 2016-01-25 17:15:31

>> 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.