J
John Harrison
This is from SGI's FAQ, its the justification for why list<T>::size() is
linear time in their library (and in gcc library too since their code is
based on SGI)
<quote>
Why is list<>::size() linear time?
The size() member function, for list and slist, takes time proportional
to the number of elements in the list. This was a deliberate tradeoff.
The only way to get a constant-time size() for linked lists would be to
maintain an extra member variable containing the list's size. This would
require taking extra time to update that variable (it would make
splice() a linear time operation, for example), and it would also make
the list larger. Many list algorithms don't require that extra word
(algorithms that do require it might do better with vectors than with
lists), and, when it is necessary to maintain an explicit size count,
it's something that users can do themselves.
</quote>
Let's take this apart point by point
'It would make the list larger' - Only by a single word for an entire
list! What planet are these guys on? Four bytes for a list that might
contain hundreds or thousands of items. This is not a valid concern.
'This would require taking extra time to update that variable' - True
but only by a constant amount, a constant time operation would still be
a constant time operation. Whereas the downside is that their decision
means that a potentially constant time operation, size(), has benn
transformed into a linear time operation.
'it would make splice() a linear time operation' - Not the whole list
splice operation, or the single item splice operation, only the very
rarely used partial list splice operation. So we have a commonly used
operation, size(), being sacrificed for the benefit of an operation that
most C++ programmers have probably never used in their entire lives.
'Many list algorithms don't require that extra word' - This is the real
kicker. I often write generic algorithms, ones that operate on any type
of container. It's one of the cool things you can do with C++. But if
those algorithms use size() then I have to think 'what if someone uses
this code with SGI's list. Sunddenly my nice linear time algorithm has
been transformed into a quadratic one. To avoid this I have to add a
size variable to my code, even though every other container, and every
other list implementation already has one. So I end up adding an extra
word, to code that most of the time would not need it, in order to patch
the deficiences of SGI's implmentation.
No question here, I just felt I had to get that off my chest.
linear time in their library (and in gcc library too since their code is
based on SGI)
<quote>
Why is list<>::size() linear time?
The size() member function, for list and slist, takes time proportional
to the number of elements in the list. This was a deliberate tradeoff.
The only way to get a constant-time size() for linked lists would be to
maintain an extra member variable containing the list's size. This would
require taking extra time to update that variable (it would make
splice() a linear time operation, for example), and it would also make
the list larger. Many list algorithms don't require that extra word
(algorithms that do require it might do better with vectors than with
lists), and, when it is necessary to maintain an explicit size count,
it's something that users can do themselves.
</quote>
Let's take this apart point by point
'It would make the list larger' - Only by a single word for an entire
list! What planet are these guys on? Four bytes for a list that might
contain hundreds or thousands of items. This is not a valid concern.
'This would require taking extra time to update that variable' - True
but only by a constant amount, a constant time operation would still be
a constant time operation. Whereas the downside is that their decision
means that a potentially constant time operation, size(), has benn
transformed into a linear time operation.
'it would make splice() a linear time operation' - Not the whole list
splice operation, or the single item splice operation, only the very
rarely used partial list splice operation. So we have a commonly used
operation, size(), being sacrificed for the benefit of an operation that
most C++ programmers have probably never used in their entire lives.
'Many list algorithms don't require that extra word' - This is the real
kicker. I often write generic algorithms, ones that operate on any type
of container. It's one of the cool things you can do with C++. But if
those algorithms use size() then I have to think 'what if someone uses
this code with SGI's list. Sunddenly my nice linear time algorithm has
been transformed into a quadratic one. To avoid this I have to add a
size variable to my code, even though every other container, and every
other list implementation already has one. So I end up adding an extra
word, to code that most of the time would not need it, in order to patch
the deficiences of SGI's implmentation.
No question here, I just felt I had to get that off my chest.