STL implmementation

[Alvin]

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.

 

[Victor Bazarov]

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

 

[abecedarian]

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

 

[Thomas Matthews]

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

 

[Alvin]

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

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.

 

[Marcin Kalicinski]

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.

 

[abecedarian]

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

 

[Jaap Versteegh]

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

 

[Gregory L. Hansen]

Alvin wrote on Apr 28, 10:56 am:


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.

 

[Peter Koch Larsen]

Alvin wrote on Apr 28, 10:56 am:


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

 

[abecedarian]

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.

 

[Peter Koch Larsen]

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