"in" everywhere

[Stanislav Blinov]

Jonathan M Davis wrote:
> On Friday 08 October 2010 03:06:01 Stanislav Blinov wrote:

>> [...]
>> What I mean is you'll always have algorithms that will perform
>> differently for different containers, and you'll always have to choose
>> containers that best fit your needs [...]

> 
> All true. However, the point is that operations need to have a know complexity. 
> If in is known to be O(1), the algorithms can safely use it, knowing that it's 
> O(1). Any container that can't do it in O(1) doesn't implement in. You could, on 
> the other hand, have in be O(n) (which doesn't stop containers from implementing 
> it as O(1) since that's better than O(n)), and then any algorithm that uses it 
> has to assume that it could be O(n) and therfore may need to avoid it. The real 
> question is what complexity we want to define it as. At the moment, the only 
> container to use it are the built-in associative arrays, and for them, it's 
> O(1). Since find() is already going to be O(n), it seems to me that in should be 
> better than O(n) - be it O(1) or O(log n) - and Andrei appears to agree, but 
> others don't, hence this long discussion...
> 

Ahh, I think I get the perspective now, though I had to reread the whole 
thread two times. Thank you.