On Tuesday, 28 May 2013 at 19:24:05 UTC, Steven Schveighoffer
wrote:
On Tue, 28 May 2013 15:06:53 -0400, Jonathan M Davis
<[email protected]> wrote:
On Tuesday, May 28, 2013 20:51:55 monarch_dodra wrote:
That was in C++03. In C++11, length was reduced to 0(1). And
splice was increased to 0(N) (I think, I don't remember the
exact
details, but it was definitely changed).
I do remember hearing something about that, though that will
actually result
in some nasty performance changes to some of the code out
there (including
code that I've written).
Regardless, you have the choice of making length O(1) or
splicing O(1) and not
both, and C++98/03 made splicing O(1), which I'm inclined to
believe is the
better choice, though having size when it's O(n) was a
definite mistake on
C++'s part IMHO. I hate to think of how many times I've seen
programmer's
write container.size() == 0 instead of empty(), particularly
when size() was
O(n)...
I actually had performance bugs the OTHER way -- I needed the
length of a list, and was using .size() without realizing it
was O(n). In profiling my code, I found that
std::list<T>::iterator::operator++ was the most used function,
and I had no idea why for a LONG time :)
You know, it is trivial to have an O(1) splice O(n) length list
wrapped into an o(n) splice O(1) length list. All you need is
to add a tracked length. And this is a REAL pain when you have
to do it manually. There should just be two list types in
<list>
-Steve
A proper implementation should be able to track length anyway:
provide 0(1) splice, and an "amortized" 0(1) length.
I've always wondered why the standard didn't decide to do *that*?
I think *we* should provide that...
