STL implmementation

Discussion in 'C++' started by Alvin, Apr 28, 2005.

  1. Alvin

    Alvin Guest

    Correct me if I am wrong, but the STL standard only defines the interface
    only and not the implementation, right?

    For example, say I use a std::map. The speed and efficiency of the
    operator[](key) function can vary from library-to-library? For example, one
    implementation of the STL C++ library, say for Linux, could be different
    (slower, faster, larger code, etc.) then say the STL C++ Library for
    Windows?

    If this is the case, then to use the STL in a multiplatform application, it
    would be best to stick with an implementation that has been ported to
    multiple platforms?

    Thanks.

    --
    Alvin
    Alvin, Apr 28, 2005
    #1
    1. Advertising

  2. Alvin wrote:
    > Correct me if I am wrong, but the STL standard only defines the interface
    > only and not the implementation, right?


    Not the implementation itself, but some implementation qualities.

    > For example, say I use a std::map. The speed and efficiency of the
    > operator[](key) function can vary from library-to-library?


    It can vary but it can't be below the requirements.

    > [..]
    > If this is the case, then to use the STL in a multiplatform application, it
    > would be best to stick with an implementation that has been ported to
    > multiple platforms?


    A third-party library is a third-party library. Once you tied yourself
    to it, you become dependent. What does it buy you? Maybe something you
    cannot find elsewhere, maybe nothing.

    Efficiency is a characteristic of an application. It often depends not
    only on *what* you use or *who* implemented it, but also on *how* you use
    it. Decisions on the use of any particular library have to be made based
    on research and comparison, and considering not only the cost of using it
    *now* but the cost of *continuing* to use it or the cost in case of the
    *inability* to continue to use it.

    And, of course, nobody can tell you what's "best" for you. And, also,
    what's best for you is not necessarily best for everybody.

    V
    Victor Bazarov, Apr 28, 2005
    #2
    1. Advertising

  3. Alvin

    Guest

    Alvin wrote on Apr 28, 9:53 am
    > Correct me if I am wrong, but the STL standard only defines the
    > interface only and not the implementation, right?


    > For example, say I use a std::map. The speed and efficiency of the
    > operator[](key) function can vary from library-to-library? For
    > example, one implementation of the STL C++ library, say for
    > Linux, could be different (slower, faster, larger code, etc.)
    > then say the STL C++ Library for Windows?


    Try this page: http://www.sgi.com/tech/stl/table_of_contents.html
    and look especially for 'Complexity guarantees'`.

    Abe
    , Apr 28, 2005
    #3
  4. Alvin wrote:
    > Correct me if I am wrong, but the STL standard only defines the interface
    > only and not the implementation, right?

    Kind of. It places requirements on the implementation.


    > For example, say I use a std::map. The speed and efficiency of the
    > operator[](key) function can vary from library-to-library? For example, one
    > implementation of the STL C++ library, say for Linux, could be different
    > (slower, faster, larger code, etc.) then say the STL C++ Library for
    > Windows?

    There is a minimum efficiency that each STL container and algorithm
    must achieve. They are allowed to be more efficient.
    See: http://www.sgi.com/tech/stl/

    Also, manufacturer's or implementors of the STL will not gain
    much by having sloppy or inefficient containers and algorithms.
    This is what competition is all about. Nobody is going to pay
    money for poor performance when better performance by other
    implementors exists.

    One cannot compare efficiency across platforms without
    considering the underlying hardware and operating system.
    Windows may be more efficient than Linux in some areas,
    others it isn't. A multi-tasking or multi-user machine
    will not be able to dedicate as many resources as a single
    task, single user machine. My programs will run slower
    when I have the CD Music and Seti@Home programs running
    than if I don't.

    Don't worry about efficiency until the program works
    correctly. Search the web for "Premature Optimization".


    > If this is the case, then to use the STL in a multiplatform application, it
    > would be best to stick with an implementation that has been ported to
    > multiple platforms?
    >
    > Thanks.
    >


    Some key points to using the STL:
    1. The stuff is already written.
    You don't have to waste time writing a linked list or
    a queue.

    2. The stuff has been tested.
    You don't have to waste time debugging the algorithms
    or containers.

    In order to write code faster or produce more code, you
    should write less code. Research first.


    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.comeaucomputing.com/learn/faq/
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
    http://www.sgi.com/tech/stl -- Standard Template Library
    Thomas Matthews, Apr 28, 2005
    #4
  5. Alvin

    Alvin Guest

    Thomas Matthews wrote:

    > Alvin wrote:
    >> Correct me if I am wrong, but the STL standard only defines the interface
    >>implementing not the implementation, right?

    > Kind of. It places requirements on the implementation.
    >
    >
    >> For example, say I use a std::map. The speed and efficiency of the
    >> operator[](key) function can vary from library-to-library? For example,
    >> one implementation of the STL C++ library, say for Linux, could be
    >> different (slower, faster, larger code, etc.) then say the STL C++
    >> Library for Windows?

    > There is a minimum efficiency that each STL container and algorithm
    > must achieve. They are allowed to be more efficient.
    > See: http://www.sgi.com/tech/stl/
    >
    > Also, manufacturer's or implementors of the STL will not gain
    > much by having sloppy or inefficient containers and algorithms.
    > This is what competition is all about. Nobody is going to pay
    > money for poor performance when better performance by other
    > implementors exists.
    >
    > One cannot compare efficiency across platforms without
    > considering the underlying hardware and operating system.
    > Windows may be more efficient than Linux in some areas,
    > others it isn't. A multi-tasking or multi-user machine
    > will not be able to dedicate as many resources as a single
    > task, single user machine. My programs will run slower
    > when I have the CD Music and Seti@Home programs running
    > than if I don't.
    >
    > Don't worry about efficiency until the program works
    > correctly. Search the web for "Premature Optimization".
    >
    >
    >> If this is the case, then to use the STL in a multiplatform application,
    >> it would be best to stick with an implementation that has been ported to
    >> multiple platforms?
    >>
    >> Thanks.
    >>

    >
    > Some key points to using the STL:
    > 1. The stuff is already written.
    > You don't have to waste time writing a linked list or
    > a queue.
    >
    > 2. The stuff has been tested.
    > You don't have to waste time debugging the algorithms
    > or containers.
    >
    > In order to write code faster or produce more code, you
    > should write less code. Research first.
    >
    >


    Thanks Thomas.

    Unfortunately, I have wasted my time writing containers by hand. They are
    simple, but I find I spend more time implementing features and inevitably
    debugging those features instead of working on the task at hand.

    Right now I am trying to determine the best way I can port my work to use
    the STL (and possibly boost but that's 3rd party). I have some more reading
    to do. Thanks for the reply.

    --
    Alvin
    Alvin, Apr 28, 2005
    #5
  6. Alvin

    Alvin Guest

    wrote:

    > Alvin wrote on Apr 28, 9:53 am
    >> Correct me if I am wrong, but the STL standard only defines the
    >> interface only and not the implementation, right?

    >
    >> For example, say I use a std::map. The speed and efficiency of the
    >> operator[](key) function can vary from library-to-library? For
    >> example, one implementation of the STL C++ library, say for
    >> Linux, could be different (slower, faster, larger code, etc.)
    >> then say the STL C++ Library for Windows?

    >
    > Try this page: http://www.sgi.com/tech/stl/table_of_contents.html
    > and look especially for 'Complexity guarantees'`.
    >
    > Abe


    Thanks for the link. This is exactly what I was looking for.

    --
    Alvin
    Alvin, Apr 28, 2005
    #6
  7. Alvin

    Alvin Guest

    Victor Bazarov wrote:

    > Alvin wrote:
    >> Correct me if I am wrong, but the STL standard only defines the interface
    >> only and not the implementation, right?

    >
    > Not the implementation itself, but some implementation qualities.
    >
    >> For example, say I use a std::map. The speed and efficiency of the
    >> operator[](key) function can vary from library-to-library?

    >
    > It can vary but it can't be below the requirements.
    >
    > > [..]
    >> If this is the case, then to use the STL in a multiplatform application,
    >> it would be best to stick with an implementation that has been ported to
    >> multiple platforms?

    >
    > A third-party library is a third-party library. Once you tied yourself
    > to it, you become dependent. What does it buy you? Maybe something you
    > cannot find elsewhere, maybe nothing.
    >
    > Efficiency is a characteristic of an application. It often depends not
    > only on *what* you use or *who* implemented it, but also on *how* you use
    > it. Decisions on the use of any particular library have to be made based
    > on research and comparison, and considering not only the cost of using it
    > *now* but the cost of *continuing* to use it or the cost in case of the
    > *inability* to continue to use it.
    >
    > And, of course, nobody can tell you what's "best" for you. And, also,
    > what's best for you is not necessarily best for everybody.
    >
    > V


    I guess my main concern was that one implementation of std::map would use a
    linear search on the key and another implementation would use a hash table
    for representing the map.

    But, from what the replies have said, the the Complexity Specification
    states, the implementation really does not matter. Most (if not all
    operations) have a defined complexity.

    --
    Alvin
    Alvin, Apr 28, 2005
    #7
  8. > Right now I am trying to determine the best way I can port my work to use
    > the STL (and possibly boost but that's 3rd party).


    You can consider boost somewhat like 2.5rd party, because (1) it follows std
    library style closely, (2) parts of it are expected to be added to std
    library, (3) some of the members of boost are in the standarization
    comittee.

    cheers,
    M.
    Marcin Kalicinski, Apr 28, 2005
    #8
  9. Alvin

    Guest

    Alvin wrote on Apr 28, 10:56 am:

    > Unfortunately, I have wasted my time writing containers
    > by hand. They are simple, but I find I spend more time
    > implementing features and inevitably debugging those
    > features instead of working on the task at hand.


    That's not been a waste of time! You certainly have learned a lot about
    C++. Also, STL containers do not serve all purposes. Just try to store
    pointers in a STL container ...

    Abe
    , Apr 28, 2005
    #9

  10. > That's not been a waste of time! You certainly have learned a lot about
    > C++. Also, STL containers do not serve all purposes. Just try to store
    > pointers in a STL container ...


    I just did.. so what's the problem ;) ?

    Jaap
    Jaap Versteegh, Apr 28, 2005
    #10
  11. In article <>,
    <> wrote:
    >Alvin wrote on Apr 28, 10:56 am:
    >
    >> Unfortunately, I have wasted my time writing containers
    >> by hand. They are simple, but I find I spend more time
    >> implementing features and inevitably debugging those
    >> features instead of working on the task at hand.

    >
    >That's not been a waste of time! You certainly have learned a lot about
    >C++. Also, STL containers do not serve all purposes. Just try to store
    >pointers in a STL container ...


    Uh, I do. But sometimes you have to doubly dereference them, e.g.

    for (ptr = list.begin(); ptr != list.end(); ptr++)
    (*ptr)->do_something();

    In this example, ptr is a pointer to a pointer, which I think makes it a
    handle.


    --
    "When the fool walks through the street, in his lack of understanding he
    calls everything foolish." -- Ecclesiastes 10:3, New American Bible
    Gregory L. Hansen, Apr 28, 2005
    #11
  12. <> skrev i en meddelelse
    news:...
    > Alvin wrote on Apr 28, 10:56 am:
    >
    >> Unfortunately, I have wasted my time writing containers
    >> by hand. They are simple, but I find I spend more time
    >> implementing features and inevitably debugging those
    >> features instead of working on the task at hand.

    >
    > That's not been a waste of time! You certainly have learned a lot about
    > C++. Also, STL containers do not serve all purposes. Just try to store
    > pointers in a STL container ...
    >
    > Abe
    >

    They all work perfect with pointers. The requirements for the underlying
    types is specified, and pointers fullfill the requirements of all standard
    containers.

    /Peter
    Peter Koch Larsen, Apr 28, 2005
    #12
  13. Alvin

    Guest

    Gregory L. Hansen wrote:
    >
    > Uh, I do. But sometimes you have to doubly dereference them, e.g.
    >
    > for (ptr = list.begin(); ptr != list.end(); ptr++)
    > (*ptr)->do_something();


    .... and then you sorted list with list.sort() ... ;-)
    At least you see the problem. Others do not.

    A.
    , Apr 28, 2005
    #13
  14. <> skrev i en meddelelse
    news:...
    > Gregory L. Hansen wrote:
    >>
    >> Uh, I do. But sometimes you have to doubly dereference them, e.g.
    >>
    >> for (ptr = list.begin(); ptr != list.end(); ptr++)
    >> (*ptr)->do_something();

    >
    > ... and then you sorted list with list.sort() ... ;-)
    > At least you see the problem. Others do not.
    >
    > A.
    >

    If you store pointers, the sort will be based on the pointers - not on what
    they dereference. This is as it should be, of course. If you want something
    else, you have to supply your own predicate.

    /Peter
    Peter Koch Larsen, Apr 29, 2005
    #14
    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. Allan Bruce

    To STL or not to STL

    Allan Bruce, Oct 16, 2003, in forum: C++
    Replies:
    41
    Views:
    1,038
    Christopher Benson-Manica
    Oct 17, 2003
  2. Replies:
    4
    Views:
    795
    Daniel T.
    Feb 16, 2006
  3. Replies:
    2
    Views:
    548
    klaus hoffmann
    Feb 22, 2006
  4. Replies:
    5
    Views:
    500
    Markus Schoder
    Apr 16, 2006
  5. Steve
    Replies:
    2
    Views:
    500
    Andre Kostur
    Nov 6, 2007
Loading...

Share This Page