🚀 go-pugleaf

C++ STL FAQ
   This FAQ deals with the containers, iterators,
and algorithms sections of the C++ Standard, 
Clauses 23, 24 and 25.

If you have any questions you had while working with the
STL and answers you received or worked out, please
submit them to me for inclusion. I will give you credit
for it if you include your name. 

Thanks,
Marian Corcoran
mcorcora@ix.netcom.com
Copyright (c) 1995, Marian Corcoran
This may be freely distributed, but not sold. 
No guarantees.

update 1/16/96

Article:
1.  Glass, Graham. "Extending STL." C++ Report, Jan, 1996.

2.  New e-mail list for STL discussion started
  To post to the list, send email to

  genstl@atext.com

To ask to be added or removed from the list, send email to

  genstl-request@atext.com

with the word "subscribe" or "unsubscribe" in the Subject line.

This mailing list is devoted to STL (the C++ Standard Template Library)
and the style of generic programming it exemplifies.  Appropriate 
topics
for discussion include the following:

- The effective use of STL.
- The design of STL.
- Possible extensions to STL.
- STL programming questions.
- Language-related issues, e.g., language extensions to C++ or other 
languages
  that would make generic programming easier.
- Traps and pitfalls in using STL.
- Design principles, strategies, and techniques for producing libraries 
of
  generic software components.
- Specifying and reasoning about generic algorithms (e.g.,
  required properties of iterators).
- Application areas to target for the development of their own 
libraries
  of generic software components.
- Announcements of papers and other publications.

The following are NOT appropriate for this list:

- Flames
- Questions that can be answered by reading Marian Corcoran's STL FAQ,
  which is posted regularly to comp.lang.c++ and can also be obtained
  at ftp://butler.hpl.hp.com/stl/stl.faq.

3.  Whitepaper on using STL with VC++ 4
  http://www.microsoft.com/devonly/visualc
  
update 12/1/95

1. New Books and Articles:
   Glass, Graham.  STL Primer.  Prentice-Hall, 1995.
     Based on ObjectSpace Manual.
   Musser, David.  STL Tutor and Reference.  Addison-Wesley, 1995.
   Nelson, Mark.  C++ Programmer Guide to STandard Template
      Library Programming. IDG Books, 1995.
     Good introduction.  
   Plauger, P.J.  Has an article on STL in C/C++ Users
      Journal, Dec 1995.
2. Added questions 6 and onward in Q & A part.

3. RogueWave STL to be included in Borland C++ Compiler.

4. The following comes from one of my students in my STL course:
   After managing to install the ObjectSpace STL<Toolkit> with the    
   Watcom   
   C++/C 10.5 compiler, I wrote notes on the subject in FAQ format.  
   The experience was positive - the two work well together. 
   I humbly hope that this may be of others who need to install this   
   version of the STL under a compiler which is not Borland, MS, or 
gnu,   
   or on a platform other than DOS/Win or unix (I used Warp). 
   I placed the ASCII text version of the faq in: 
   ftp.netcom.com/pub/me/medina/C++/objectspace_and_watcom_faq.txt 
   (with a web browser, place the string, "ftp://" ahead of that 
address.) 
   -- Sean Medina
update 9/2/75
   Two excellent articles have appeared on the STL

Dawes, Beman.  "You Can Count On It."  C/C++ Users 
    Journal, July, 1995.  Excellent intro material.
Zigmond, Dan. "Generic Programming and the C++ STL."
    Dr. Dobb's Journal, August, 1995.  Another good
    sample program.

Rogue-Wave will be providing the STL to the following
vendors: HP, SGI, SunSoft, Siemens-Nixdorf

update 7/3/95
   Started adding new sections on questions 

Of special note:  A major complaint about libraries that
programmers have is that you don't get the source.  Well, 
with STL, you get the source.  STL source is 
also excellent code to study.  It is very well written code. 

CONTENTS

I have put together four articles for the STL FAQ:
  I.    Sources 
  II.   Questions
  III.  References of STL (M. Corcoran).  
  IV.   Report from Lockheed on their first experiences 
        with STL.  
  V.    On using MODENA by Edgar Crisostomo (along with some 
		needs in education that he sees for STL)
  VI.   Comparison of Modena and ObjectSpace by Mike Lindner. 

REQUEST FOR OTHER MATERIAL  If someone has other material 
or experiences to include you may e-mail them to me and 
I will add them.  Especially of interest would be 
examples of STL that you may have developed as you 
learn STL or industrial applications or porting 
instructions for different platforms.  Please state 
whether I may use your article in the FAQ and whether 
I may use your name.

Marian
===============================================================
PART I  SOURCES

1.  Where does one get the STL?

    A. anonymous ftp via butler.hpl.hp.com 
		works with Borland 4.5 and IBM
		also includes something on hash tables 
		not in STL by Bob Fraley bfhash.zip
            and David Musser dmhash.zip
   		no support included
		to use the public domain version 
            of STL with BC4.5
		Projects|Defines  and type __MINMAX_DEFINED
		or use #define __MINMAX_DEFINED before
		#include <iostream.h>

    B. STL++: Modena Software at 1-800-MODENA-1
		works with Borland, IBM C Set++, Apogee, 
            Visual C++ 2.0 (this last has some limitations.)
		comes with tutorial, you can get the tutorial 
			   
            separately (read this tutorial after A. Stevens 
            and after playing with ObjectSpace examples.)

    C. STL<ToolKit>:ObjectSpace at 1-800-OBJECT-1
		most C++ compilers
		code is well documented
	      comes with tutorial with over 200 elementary 
			examples that have just been placed in the 
      public domain available
      via anonymous ftp via butler.hpl.hp.com at 
				/STL/examples.Z or .zip for PC
		These examples are a good place to start. 


     D. libstdc++ (part of libg++):	Free Software Foundation
		anonymous ftp via prep.ai.mit.edu and many other 
		machines only some containers exist, but works with GNU 
C++, 
      and probably many other C++ compilers

     E.  RogueWave to include STL, coming out in first quarter, 1996

===============================================================
PART II  QUESTIONS

1.  What are the iterators, containers, and algorithms 
sections of the  STL (Standard Library)?
A.  The STL has a is a data structures or container class 
library that has been adopted into the language.  It 
consists of three major components:
	Containers or data structures
        Iterators
	Algorithms

2.  What are containers?
Containers include such things as vectors, lists, queues, 
priority queues, stacks, maps, and sets.  In STL, 
containers (data structures) are templatized.  For 
example, the stack class may be used with integers, 
doubles, and user defined types.

3.  What are iterators?
Iterators may be thought of as the key to STL, acting 
as an intermediary between the algorithms and the 
containers.  You are already familiar with the concept 
of an iterator when you think of the pointer used to 
traverse an array.  Iterators are objects in STL.  
One may think of them as a finger moving across the 
elements of a container.  The five categories of 
iterators are:

   Random Access -> Bidirectional-> Forward -> Input
				            -> Output
4.  How are iterators related to containers and
algorithms?
One may think of each container and each algorithm as 
being associated with a certain iterator.  A vector has 
a random access iterator, therefore it may use a random 
access algorithms such as a sort.  A container may use 
any algorithm associated with its iterator or any 
algorithm associated with an iterator to the right of 
it in the above diagram. Therefore a vector (random 
access iterator) may use algorithms associated with 
bidirectional, forward, input or output iterators.  
Can a vector be used with the binary_search algorithm 
(takes a forward iterator) ?  If we look at the diagram 
above, forward is to the right of random access, 
therefore we may use binary_search with a vector 
container.  Can a vector be used with copy (takes an 
input and an output iterator)?  Since input and output 
are to the right of random access, vector may used 
with copy.

There are quite a number of algorithms in STL, 
including count(), copy(), replace( ), reverse( ), ...
Just as each container is associated with a certain 
iterator, each algorithm is also associated with a 
certain iterator(s).
 
count( ) - input iterator
copy ( ) - input and output iterator
replace( ) - forward iterator
reverse( ) - bidirectional iterator

6.  I got the ObjectSpace examples and they don't work 
with the HP STL.  I get an error message that there 
is no Stl.h file.

A.  ObjectSpace compiled all the different files of the 
STL together.  This is helpful when first learning 
it.  However, later you will probably want to include 
just the files you need.  
     A rule of thumb here is to always include the algo.h 
or algorith.h (latter for ObjectSpace) file and then 
nclude the file with the container you are using:

list - list.h
stack, queue, priority_queue - stack.h
deque - deque.h
vector - vector.h
map - map.h
multimap - multimap.h
set - set.h
multiset - multiset.h

7.  When I try to use HP STL with Borland 4.5, 
I get an error function min and max already 
defined.  Why?

The functions min( ) and max( ) are already defined 
in the stdlib.h file.  However, there is #ifdef to 
compile them only if they are already not defined.  
Therefore, you may place a __MINMAX_DEFINED  line in 
your Project|Defines window of put the line 
#define __MINMAX_DEFINE before the 
#include <iostream.h>

8.  Where is the code for the STL?  When I downloaded
STL from the HP site, I only got header files.

The code for the STL is in the .h files

9.  I hear the STL is extensible.  What does that mean?
How will different vendors extend the STL?

Extensible means that one will be able to add algorithms,
containers, and iterators to the STL.
Joe Buck (jbuck@synopsis.com) writes:
Rogue Wave is now giving a January 1996 date for STL
inclusion.  See

http://www.roguewave.com/rwpav/products/stdlibwp.htm

for discussion of their plans for including STL support
in their Tools.h++ class library.

Reading that paper, and looking at what ObjectSpace has
done (see http://www.objectspace.com/products/stl/), it
seems that vendors are making their own enhancements to
the libraries, generally in the same direction: to make
the library somewhat less low-level, to provide cleaner
interfaces for the very common

	algorithm(container.begin(), container.end())

so that one can write something like algorithm(container)
(in ObjectSpace's case) or container.algorithm() (in
Rogue Wave's case).

Perhaps the committee should consider doing a little bit in
this area, before every library vendor does it differently?
It seems that there are fairly natural interfaces that could
be provided to cover the common cases where a range that
is the entire container is to be specified, where the user
is thinking "sort the container" or "copy container A to
container B".  If the committee doesn't provide them, they
will still be there, based on what vendors are already
doing, but they will be non-portable.




==============================================================
PART III  REFERENCES

A. PERIODICALS
    D. Jordan. ODMG Update: Collections in ODMG-93
   	Discusses ODMG and STD LIB.  C++ Report, June 1995
    A. Koenig. File iterators. Journal of Object-oriented
 	Programming  (JOOPS), Nov/Dec 1994
    A. Koenig. Generic iterators. JOOPS, Sept. 1994
    A. Koenig. Templates and generic iterators.  
	JOOPS, June 1994
    A. Koenig. ? . January , 1995
    D.R. Musser and A.A. Stepanov. Algorithm-oriented 
       generic libraries.  Software-Practice and Experience, 
       July 1994
    N. Meyers. A New and Useful Template Technique: 
       "Traits" C++ Report, June 1995
    A.A. Stepanov and M.Lee.  The Standard Template 
      Library. ISO Programming Language C++ Project. 
      Doc. No. X3J16/94-0095, WG21/N0482, May 1994.  
      (Look in HP's ftp for stl.doc, I believe). 
       Although it is the 
	"definitive" STL, it is not intro material. 
    A. Stevens. He has an interview with Stepanov in
      Dr. Dobb's Journal, March 1995.  This is an 
      excellent conceptual introduction to the STL, 
      also a good place to start.
    A. Stevens.  The Standard Template Library 
       (with some code) in his column, Dr. Dobb's Journal, 
       April 1995.  Also good intro material.
    B. Stroustrup. Making a vector fit for a standard. 
        C++ Report, Oct. 1994. intermediate level 
        material. Stroustrup made some important 
        contributions to the design of STL, discussed 
        here.
    M.J. Vilot. An introduction to the standard template
 	library.  C++ Report, Oct 1994. You might want to read 
	Stevens and Dawes first.
    Also see 
	http://www.cs.rpi.edu/~musser/STL.html
	This material is also available via anonymous ftp
       ftp.cs.rpi.edu in directory pub/STL the file 
	STL-info.ps.Z
 	includes STD LIB Online Algorithm Reference 
      by R. Cook, 
	D. Musser, and K Zalewski with examples.
	See ObjectSpace examples first.

  B.  STL Web Pages - "Newbie" guide
	http://weber.u.washington.edu/~bytewave/STL.html
   1.  Intro material including Stepanov Speaks on 
       STD LIB in C++ 	(M. Corcoran),
   2.  Dr. Dobbs article (A. Stevens), STD LIB newbie 
       notes (M. Khan),
   3. STD LIB by Stepanov & Lee, STD LIB files, and 
      ANSI C++ Draft (HTML version)


==============================================================
PART IV. EXPERIENCES FROM LOCKHEED

We've just obtained STL<ToolKit> for use with our HP 
cfront compiler and the Softbench development 
environment. Here are the first impressions & observations:

Apparently ObjectSpace doesn't routinely deliver 4mm DAT 
tapes and added $25 to do it. The tape we recieved was 
DOA (unreadable) but the ObjectSpace support folks quickly 
e-mailed the TAR-file and we were in bussiness. We did 
not experience the problems reported by Mike Linder 
contacting the ObjectSpace people. The above problem w
as solved within two hours.

Our experience with installing and building the 
libraries supports Mike Linder's observations. 
Good job here by the vendor.

Compiling with the debug option (-g) resulted in many 
warnings similar **to the following:

CC: "release1.C", line 28: warning: 
debug.emit_type_entry:typedef node has no 
symid_ptr: vector <X*> ::size_type (187)
CC: "release1.C", line 28: warning: 
debug.emit_type_entry:typedef node 
**has no symid_ptr: vector <X*> ::const_reference (187)

The executable does run and the debugger still works, 
however.

Note that the person evaluating STL<ToolKit> is 
not an experienced C++ programmer and is proceding 
on the strength of a C++ class. His first impressions 
of the ObjectSpace documentation are favorable and 
he was able to write a simple program from a 
standing-start in a few hours. We also have the 
documentation from HPs public-domain STD LIB. 
I'll keep you posted.

===============================================================
PART V. ON USING MODENA at SIEMENS-ROLM

   We use Modena STL++ v2.0 - they respond fairly 
quickly to our needs, they add bug fixes or compiler 
support for our Unixware 2.0 SDK C++ compiler, and 
they answer our many technical questions.

The STD LIB++ Manual has a "Files" Heading at the top 
of each component description, and that is all that 
should be explicitly #included to use that component 
(mutual independence).

When I #include <vector.h>, it pulls in all the other 
dependent includes.  It is not explicitly stated, but 
for C-like arrays, you #include <algobase.h>.

There are minor problems, I will report to Modena 
(example: hashfun.h has non-template function 
_definitions_, so you get multiply defined, when 
used over several translation units.   To improve 
the ability (for us) to specify manual template 
instantiation, it would be nice if they factor out 
the non-inline template definitions into another file.

EDUCATIONAL HINTS
A discussion of build issues would be useful.  Especially 
since STL template code can have really obscure 
compiler messages with todays compiler technology.  
There are also issues with debugging template code.

A discussion of when to pass container by reference, 
versus passing iterators would be useful.

Edgar Crisostomo    408-492-6528, 
edgar@clipper.robadome.com
Systems Software, 
Siemens Rolm Communications, Inc. FAX 408-492-3305  

=============================================================
PART VI
COMPARISON OF MODENA AND OBJECTSPACE 

I just bought STL++ from Modena and 
STL<toolkit> from ObjectSpace, for purposes of 
comparison.  So far I have not had a chance to use 
either extensively, but I have the following observations:

Modena was very helpful on the phone, and responded 
quickly to whatever I called about.  The initial 
floppy they sent me was bad, and they replaced it 
overnight.  In every case but one technical question, 
the person who answered the phone was able to do 
everything I needed.  In the remaining case, I 
received a call back within hours of my question.  
I like their service.

 ObjectSpace had an operator, who directed me to the 
one salesperson, who was always "out of the office" 
when I called, and who was the only one who could 
sell me the product (it took 5 days just to order 
the product, because I couldn't get in touch with her).

Both products come as source, and you must build the 
libraries yourself.  The documentation for doing this 
from Modena was sketchy, and it wasn't until I called 
tech support that I discovered I had to change some 
files by hand to make them compile with my compiler 
(which is one of the one's they advertise as working with).

ObjectSpace, on the other hand, has a neat little 
config package that tests what your compiler can do, 
and writes a header file which configures the code 
to be correct for your compiler (lots of preprocessor 
magic in them there header files).  It was a joy to use.

So far, the test programs I have compiled are much 
smaller when I use the ObjectSpace libraries than 
with the Modena libraries.  As I said, I have not 
stressed either product, so these numbers may not 
reflect use in an actual application.

As for conformance, ObjecSpace doesn't necessarily support 
everything in STL, but only as much as they can 
squeeze out of the compiler you give them to work 
with.  Is that good or bad?

The ObjectSpace library claims to be "thread safe", 
although I haven't tried that our yet.  Apparently 
they have a wrapper class that behaves like a smart 
pointer, but can be locked for reading or writing.  
They also have some other platform independent thread 
and mutex code.

  The Modena folks said their library is not 
"thread safe", but only in one place, and they would 
gladly show me how to modify the source to add that 
feature.  One of my compiler vendors says they'll be 
shipping Modena with their compiler soon, and their 
version will be thread safe.

Modena includes some extra goodies, like hash tables 
and an ANSI string class.
ObjectSpace has added some features recently as well.

Mike Lindner
mikel@attmail.com
mpl@cmprime.attpls.com
mpl@pegasus.att.com
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]