On Wednesday, March 21, 2012 20:17:06 Steven Schveighoffer wrote: > On Wed, 21 Mar 2012 19:56:41 -0400, Jonathan M Davis <jmdavisp...@gmx.com> > > wrote: > > Except that containers shouldn't provide indexing if it's not efficient. > > And > > from what I've seen, it's far too common for programmers to check length > > == 0, > > and they end up doing it on stuff like linked lists where it _is_ > > inefficient. > > Wait, if someone provides inefficient length, what makes you think they > won't provide inefficient indexing?
Both C++'s STL and D's std.container put requirements on the algorithmic complexity of various operations. O(n) indexing would violate them, whereas they allow O(n) length/size. So, as long as you use standard containers, you can rely on the efficiency of indexing but not that of length/size. And I'd argue that 3rd party containers which violate those algorithmic requirements are generally doing something wrong (possibly with some exceptions for specific situations but not in general). So, as long as you use standard containers, it's a non-issue. And if you're dealing with a 3rd party library that doesn't provide appropriate algorithmic guarantees for its containers, you should probably rethink using it. It _is_ true that some languages and libraries are completely idiotic about it though (e.g. Java providing a get function to LinkedList which takes an index - which would be the equivalent of providing horribly efficient indexing if they had operator overloading in Java). Those are broken APIs IMHO though, in which case, you must tread carefully. Well-designed libraries _do_ guarantee efficient indexing. - Jonathan M Davis
