everytime I read this it make me mad

[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.

[Gianni Mariani]

John Harrison wrote:

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)

....reasoning snipped...

>
No question here, I just felt I had to get that off my chest.

Still nothing stopping you from creating your own list container or even
a specialization which is platform dependant that provides a fast size()
method.

I tend to agree with the SGI philosophy of keeping things as simple as
possible and paying for more function when you need it.

It does not always give you the right answer (like in this case) but I
find it the best alternative most of the time - hence the tradeoff SGI made.

[John Carson]

"Gianni Mariani" <gi*******@mariani.wswrote in message
news:45**********************@per-qv1-newsreader-01.iinet.net.au

John Harrison wrote:

>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)

...reasoning snipped...

>>
No question here, I just felt I had to get that off my chest.

Still nothing stopping you from creating your own list container or
even a specialization which is platform dependant that provides a fast
size() method.

I think you missed the part where he says he writes generic algorithms
intended for use (by other people) with any container.

--
John Carson

[Gianni Mariani]

John Carson wrote:

"Gianni Mariani" <gi*******@mariani.wswrote in message
news:45**********************@per-qv1-newsreader-01.iinet.net.au

>>John Harrison wrote:

>>>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)

...reasoning snipped...

>>>No question here, I just felt I had to get that off my chest.

Still nothing stopping you from creating your own list container or
even a specialization which is platform dependant that provides a fast
size() method.

I think you missed the part where he says he writes generic algorithms
intended for use (by other people) with any container.

I think you missed the point altogether.

[Daniel T.]

John Harrison <jo*************@hotmail.comwrote:

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)

They forgot an answer:

A: Because the standard only requires size() to be linear time.

'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.

If you write generic algorithms that assume size() is constant time,
then you are depending on implementation details of the containers
passed to your algorithms.

Between empty() and begin(), end(), I'm having trouble imagining a
generic algorithm that requires the use of size(). Could you help me out
on that with an example? (I'm sure there are some, I just can't think of
any off hand.)

[john_andronicus]

On 24 Jan, 14:28, "Daniel T." <[e-mail]:

John Harrison <[e-mail]:

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)

They forgot an answer:

A: Because the standard only requires size() to be linear time.

Actually I cut that part.

If you write generic algorithms that assume size() is constant time,
then you are depending on implementation details of the containers
passed to your algorithms.

I think it's very likely that the standard was written that way because
they didn't want to break existing implementations not because it was
thought to be a good idea to make an exception of std::list. In other
words mine is a 'in perfect world' argument.

>
Between empty() and begin(), end(), I'm having trouble imagining a
generic algorithm that requires the use of size(). Could you help me out
on that with an example? (I'm sure there are some, I just can't think of
any off hand.)

This situation has only occured for me once, and I can't recall the
details now, sorry.

[W Karas]

On Jan 24, 2:45 am, John Harrison <[e-mail]:

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.

If this makes you mad, you must live a fairly sheltered life,
programming-wise. I reserve my moments of anger/despair for code that
seems to have no rationale whatsoever for its design.

Seems like you could write a class template that
inherits from any STL container and keeps track
of the size (plus partial specilizations like:

template <typename T>
class Counted<std::vector<T
: public std::vector<T>
{ };

for STL containers that already have a size()
member. Or maybe the boost template
meta-programming library has some trick
in it to generally handle the case where
the base container has a size() member.)

If you decide to do this, please make the
result open source, and post us a link.

[John Harrison]

W Karas wrote:

>
On Jan 24, 2:45 am, John Harrison <[e-mail]:

>>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)

If this makes you mad, you must live a fairly sheltered life,
programming-wise. I reserve my moments of anger/despair for code that
seems to have no rationale whatsoever for its design.

No, I think I just get mad fairly easily!