On Wed, 21 Mar 2012 20:53:42 -0400, Jonathan M Davis <jmdavisp...@gmx.com>
wrote:
On Wednesday, March 21, 2012 20:46:05 Jonathan M Davis wrote:
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.
Actually, it looks like std.container _does_ guarantee that length is
O(1),
unlike C++'s STL, in which case it's not the same issue that it is in
C++. I'd
still tend to argue that checking for empty is better, but I guess that
it's
not as big a deal. In C++, it's a definite problem when programmers keep
checking that size() == 0, since inevitably, it ends up happening with
linked
lists and the like, making for inefficient code, and simply being in the
habit
of using empty() rather than size() == 0 avoids such problems.
Yes, that was my point.
Note that the default std::list has O(1) length (as does dcollections'
LinkedList). It's not as inevitable as you think.
-Steve
