http:^^www.xraylith.wisc.edu^~khan^software^stl^stl.newbie.html

This data set contains WWW-pages collected from computer science departments of various universities

<hr>
<!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><a href=#class_howto>What's so special about writing container objects</a>
<br>
<!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><a href=#index>Back to index</a>
<hr>

<a name=pointers><h1>Pointers and STL</h1></a>
As you might've noticed, STL containers manage the storage for objects,
not pointers, and this has caused some trepidation about using STL for
projects which need to store pointers in various STL containers. I
strongly suggest people revisit their designs and <em>not</em> store 
pointers, but if you have no choice, here's what I have found so far 
regarding STL containers and pointers to defined types.

<a name=class_pointer><h2>Gotcha's with storing pointers to objects</h2></a>
Contrary to what some believe, STL does not care if you're storing pointers 
to objects instead of objects in its containers. However, more often than 
not, containers of pointers may be a design flaw that leads to memory 
leaks and such lovely things. There are a few obvious exceptions:
<ul>
<li> Large objects that are too expensive to duplicate and are
    already constructed on the heap.
<li> Single object stored in multiple containers. This is quite common
    and I believe the right way to do is to wrap the pointers into a class
    the manages the objects, perhaps via a reference count. 
<li> When you need to store objects derived from a (or a set of) base
    objects in a container. This is quite common in CAD systems where
    most manipulable objects are derived from a common base with a set of
    common semantics. See <!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><a href=#pointer_deriv> here</a> for an example.
    Remember that <em> C++ != Smalltalk</em>, and true heterogeneous 
    containers are simply too messy to do in C++.
</ul>

There are few notable gotcha's:
<ul>
<li> No pointers to local variables please. See the function 
    <tt><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><a href=#map_charptr>change_phno</a></tt> for an example of this.
<li> Who manages the destruction? See <!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><a href=#class_ptr_destruction> here
   </a> for an example of templatized sequence destructor.
<li> Most STL containers use <tt>&lt</tt> for comparison which may be 
    meaningless in some contexts. This is where <em>Smart pointers</em> 
    shine.
<li> Be careful when supplying a <em>Comparator</em> to STL containers need
    one, such as SET, MAP, etc. See <!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><a href=#comparators> here
    </a> for a rather involved example. Also see <!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><a href=#map_charptr>
    here</a> for another example.
    <p>
    A better solution is to wrap the pointers in a simple class that you
    store in STL containers. For a trivial example, see 
    <!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><a href=#pointer_wrap>here</a>.
<li> Some compilers and STL implementations seem to have inordinate
    amount of trouble when you store pointers to objects instead of
    objects, and it stems from <tt>construct</tt> and <tt>destroy</tt>
    functions in STL allocator design; eg., HP reference implementation
    comes with <tt>destroy</tt> specialized for pointers to all built-in
    types, so it works fine if you store <tt>int*</tt> in a container, but
    not when you store <tt>X*</tt>, where <tt>X</tt> is some user-defined
    data type. See <!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><a href=#pointer_storage> here</a> for Benjamin 
    Scherrey's note on how to manage this.
</ul>

<ul>
<li> <!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><a href=#seq_pointer>Storing pointers in STL containers: Example code</a>
<li> <!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><a href=#class_ptr_destruction>Deallocating pointers stored in STL 
containers</a>
<li> <!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><a href=#class_ptr_owner>Who owns the storage?</a>
<li> <!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><a href=#class_ptr_char>More gotchas in storing char*</a>
</ul>

<a name=seq_pointer>
    <h3>Storing pointers in STL containers: Example code</h3>
</a>
The following example is an excerpt from my <em>c.l.c++</em> posting on
the subject of storing the same object in multiple container.
<hr>

<! 									>
<!		CODE EXAMPLE BEGIN					>
<! 									>

<pre>

<STRONG>#include</STRONG> &lt;<!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><A HREF="#stl.h">stl.h</A>&gt;                <EM><STRONG>//</STRONG> or individual includes if you like</EM>
                                <EM><STRONG>//</STRONG> need list.h, set.h and algo.h</EM>
<STRONG>#include</STRONG> &lt;iostream.h&gt;

<EM><STRONG>//</STRONG></EM>
<EM><STRONG>//</STRONG> THIS IS VERY IMPORTANT (see note above). You have to tell the set</EM>
<EM><STRONG>//</STRONG> or multiset or map to compare the objects pointed to rather than </EM>
<EM><STRONG>//</STRONG> the pointers these containers are storing.</EM>
<EM><STRONG>//</STRONG></EM>
<STRONG>struct</STRONG> compare <STRONG>{</STRONG>
    bool <STRONG>operator</STRONG><STRONG>(</STRONG><STRONG>)</STRONG> <STRONG>(</STRONG><STRONG>const</STRONG> <STRONG>int</STRONG><STRONG>*</STRONG> i1<STRONG>,</STRONG> <STRONG>const</STRONG> <STRONG>int</STRONG><STRONG>*</STRONG> i2<STRONG>)</STRONG> <STRONG>const</STRONG> <STRONG>{</STRONG>
        <STRONG>return</STRONG> <STRONG>*</STRONG>i1 <STRONG>&lt;</STRONG> <STRONG>*</STRONG>i2<STRONG>;</STRONG>
    <STRONG>}</STRONG>
<STRONG>}</STRONG><STRONG>;</STRONG>

<STRONG>void</STRONG> print<STRONG>(</STRONG><STRONG>int</STRONG><STRONG>*</STRONG> i<STRONG>)</STRONG> <STRONG>{</STRONG>
    cout <STRONG>&lt;&lt;</STRONG> &quot;<EM> </EM>&quot; <STRONG>&lt;&lt;</STRONG> <STRONG>*</STRONG>i<STRONG>;</STRONG>
<STRONG>}</STRONG>

<STRONG>int</STRONG> main<STRONG>(</STRONG><STRONG>int</STRONG><STRONG>,</STRONG> <STRONG>char</STRONG><STRONG>*</STRONG><STRONG>[</STRONG><STRONG>]</STRONG><STRONG>)</STRONG> <STRONG>{</STRONG>
    list<STRONG>&lt;</STRONG><STRONG>int</STRONG><STRONG>*</STRONG><STRONG>&gt;</STRONG> list1<STRONG>;</STRONG>

    <EM><STRONG>//</STRONG></EM>
    <EM><STRONG>//</STRONG> create a list of new'd integers.</EM>
    <EM><STRONG>//</STRONG></EM>
    <STRONG>for</STRONG><STRONG>(</STRONG><STRONG>int</STRONG> i <STRONG>=</STRONG> 0<STRONG>;</STRONG> i <STRONG>&lt;</STRONG> 5<STRONG>;</STRONG> <STRONG>++</STRONG>i<STRONG>)</STRONG> <STRONG>{</STRONG>
        list1<STRONG>.</STRONG>push_back<STRONG>(</STRONG><STRONG>new</STRONG> <STRONG>int</STRONG><STRONG>(</STRONG>i <STRONG>*</STRONG> i<STRONG>)</STRONG><STRONG>)</STRONG><STRONG>;</STRONG>
    <STRONG>}</STRONG>

    cout <STRONG>&lt;&lt;</STRONG> &quot;<EM>List of int*: (</EM>&quot;<STRONG>;</STRONG>
    for_each<STRONG>(</STRONG>list1<STRONG>.</STRONG>begin<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>,</STRONG> list1<STRONG>.</STRONG>end<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>,</STRONG> print<STRONG>)</STRONG><STRONG>;</STRONG>
    cout <STRONG>&lt;&lt;</STRONG> &quot;<EM>)</EM>&quot; <STRONG>&lt;&lt;</STRONG> endl<STRONG>;</STRONG>

    <EM><STRONG>//</STRONG></EM>
    <EM><STRONG>//</STRONG> now put these integers into a set. Note that I'm using a</EM>
    <EM><STRONG>//</STRONG> custom comparator to compare the integers, not the pointers.</EM>
    <EM><STRONG>//</STRONG></EM>
    set<STRONG>&lt;</STRONG><STRONG>int</STRONG><STRONG>*</STRONG><STRONG>,</STRONG> compare<STRONG>&gt;</STRONG> set1<STRONG>;</STRONG>
    copy<STRONG>(</STRONG>list1<STRONG>.</STRONG>begin<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>,</STRONG> list1<STRONG>.</STRONG>end<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>,</STRONG> 
        insert_iterator<STRONG>&lt;</STRONG>set<STRONG>&lt;</STRONG><STRONG>int</STRONG><STRONG>*</STRONG><STRONG>,</STRONG> compare<STRONG>&gt;</STRONG> <STRONG>&gt;</STRONG> <STRONG>(</STRONG>set1<STRONG>,</STRONG> set1<STRONG>.</STRONG>begin<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>)</STRONG>
    <STRONG>)</STRONG><STRONG>;</STRONG>

    cout <STRONG>&lt;&lt;</STRONG> &quot;<EM>Set of int* : [</EM>&quot;<STRONG>;</STRONG>
    for_each<STRONG>(</STRONG>set1<STRONG>.</STRONG>begin<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>,</STRONG> set1<STRONG>.</STRONG>end<STRONG>(</STRONG><STRONG>)</STRONG><STRONG>,</STRONG> print<STRONG>)</STRONG><STRONG>;</STRONG>
    cout <STRONG>&lt;&lt;</STRONG> &quot;<EM>]</EM>&quot; <STRONG>&lt;&lt;</STRONG> endl<STRONG>;</STRONG>

    <STRONG>return</STRONG> 0<STRONG>;</STRONG>
<STRONG>}</STRONG>

</pre>

<hr>

<pre>

When you run the program, it should produce the following output.

% ./testc++
List of int*: ( 0 1 4 9 16)
Set of int* : [ 0 1 4 9 16]

</pre>

<! 									>
<!		CODE EXAMPLE END					>
<! 									>
<hr>

<p>

<a name=pointer_storage>Special Note for Borland C++ users:</a>
However, Ben Scherrey (<tt>[e-mail]</tt>) points out that 
the OS/2 Borland C++ compiler cannot handle this, and I believe this is due 
the compiler's lack of support for explicitly calling template destructor.
Ben says that the if you overload <tt>destroy</tt> and <tt>construct</tt> 
yourself, it works out. Thanks Ben.

<p>

<hr>
<pre>

void destroy(X** pointer ) {
    (*pointer)->~X();
}

inline void construct(X** p, const X* value ) {
    new (p) (const X*)(value);
}

</pre>
<hr>

<hr>
<!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><a href=#pointers>Pointers and STL</a> 
<br>
<!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><a href=#index>Back to index</a>
<hr>

<a name=class_ptr_destruction>
    <h3>Deallocating pointers stored in STL containers</h3>
</a>

If you create containers of pointers, make sure you deallocate the
storage explicitly in the code, especially if the container is on the
stack and goes out of scope creating a memory leak. STL containers only 
copy and delete the storage required to hold the <strong>pointer</strong>,
not the <strong>object</strong> it's pointing to.
You can create templated deleters like the following:

<pre>
   template &lt;class ForwardIterator, class ForwardIterator&gt;
   void sequence_delete(ForwardIterator first, ForwardIterator last) {
       while (first != last)
	   delete *first++;
   }

   template &lt;class ForwardIterator, class ForwardIterator&gt;
   void map_delete(ForwardIterator first, ForwardIterator last) {
       while (first != last)
	   delete (*first++).second;
   }

   Map&lt;int, SomeType*, less&lt;int&gt &gt; mymap_;
   //
   // populate my map with new'd SomeType's.
   //
   map_delete(mymap_.begin(), mymap_.end());

</pre>

ObjectSpace uses a non-standard <tt>release()</tt> member to achieve the 
above.

<hr>
<!WA67><!WA67><!WA67><!WA67><!WA67><!WA67><a href=#pointers>Pointers and STL</a> 
<br>
<!WA68><!WA68><!WA68><!WA68><!WA68><!WA68><a href=#index>Back to index</a>
<hr>

<a name=class_ptr_owner><h3>Who owns the storage?</h3></a>

The following example shows another nasty side effect of storing pointers
to things in STL containers.

<p>

<tt>list&lt;char*&gt;</tt> means a list character pointers, <em>NOT</em> 
strings they point to. less&lt;char*&gt; will compare the pointers,
<em>NOT</em> the strings (ie., <em>NOT</em> use <tt>strcmp</tt> and friends).

<p>

<pre>