everytime I read this it make me mad

Discussion in 'C++' started by John Harrison, Jan 24, 2007.

  1. 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.
    John Harrison, Jan 24, 2007
    #1
    1. Advertising

  2. 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.
    Gianni Mariani, Jan 24, 2007
    #2
    1. Advertising

  3. John Harrison

    John Carson Guest

    "Gianni Mariani" <> wrote in message
    news:45b7168c$0$7966$
    > 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
    John Carson, Jan 24, 2007
    #3
  4. John Carson wrote:
    > "Gianni Mariani" <> wrote in message
    > news:45b7168c$0$7966$
    >
    >>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.
    Gianni Mariani, Jan 24, 2007
    #4
  5. John Harrison

    Daniel T. Guest

    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)


    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.)
    Daniel T., Jan 24, 2007
    #5
  6. John Harrison

    Guest

    On 24 Jan, 14:28, "Daniel T." <> wrote:
    > 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)


    > 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.
    , Jan 24, 2007
    #6
  7. John Harrison

    W Karas Guest

    On Jan 24, 2:45 am, 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)
    >
    > <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.
    W Karas, Jan 24, 2007
    #7
  8. W Karas wrote:
    >
    > On Jan 24, 2:45 am, 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)

    >
    > 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!
    John Harrison, Jan 24, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. alanb
    Replies:
    2
    Views:
    516
    alanb
    Apr 23, 2004
  2. =?Utf-8?B?V2ViTWF0cml4?=

    Is server cache reloaded everytime when web.config changes?

    =?Utf-8?B?V2ViTWF0cml4?=, Jan 27, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    403
    =?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=
    Jan 27, 2006
  3. chris
    Replies:
    5
    Views:
    922
    Jukka K. Korpela
    Feb 16, 2004
  4. Alitaia

    File::Find make me mad

    Alitaia, Dec 3, 2007, in forum: Perl Misc
    Replies:
    7
    Views:
    79
    Dr.Ruud
    Dec 5, 2007
  5. johannes falcone

    is agile scrum stuff just to make people mad?

    johannes falcone, May 15, 2013, in forum: Perl Misc
    Replies:
    0
    Views:
    154
    johannes falcone
    May 15, 2013
Loading...

Share This Page