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.
