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
