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

        //
        // do what-not with xlist 
        //

	// 
	// now replace the 1st element with something else.
	//
	X x2;
	xlist.front() = x2;             //   <-------- (4)

	//
        // remove the element with value x3
	//
	X x3;
	xlist.remove(x3);               //   <-------- (5)

	//
        // now sort the list
	//
	xlist.sort();                   //   <-------- (6)


	//
        // do stuff with xlist and then return from f()
	//

        return;
    }                                   //   <-------- (7)

</pre>

Now let's see what happens at steps (1) through (7).

<ol>
<li> Enter a new scope, function <tt>f</tt>. Automatic objects will
    be destructed when we leave this scope in Step (7).
    <p>

<li> Create a concrete <tt>list&lt;X&gt;</tt> from parameterized type,
    <tt>list&lt;T&gt;</tt>. At this point, the constructor for <tt>list</tt>
    creates a <tt>list_node</tt> that has a member data holding 
    a copy of <tt>X</tt>. The <tt>list_node</tt> looks like the
    following:
    <pre>
    template &lt;class T&gt;
    struct list_node {
	void_pointer next;
	void_pointer prev;
	T data;
    };
    </pre>

    To create <tt>list_node</tt>, the data member, <tt>T</tt>, 
    <em>must</em> have a <b>default constructor</b> (or equivalent,
    such as a constructor with all default arguments) defined.

    <p>
    <b>Step (2) requires a default constructor</b>.
    <p>

<li> Here we add an object, <tt>x</tt>, of type <tt>X</tt>, to the end
    of the <tt>list</tt>. The method <tt>push_back</tt> would typically
    invoke the following:
    <pre>
    insert(begin(), x);
    </pre>

    And here's the code for a typical <tt>insert</tt> method:

    <pre>

    iterator insert(iterator position, const T&amp; x) {
        link_type tmp = get_node();                         &lt; ---- (3a)
        construct(value_allocator.address((*tmp).data), x); &lt; ---- (3b)
        (*tmp).next = position.node;
        (*tmp).prev = (*position.node).prev;
        (*(link_type((*position.node).prev))).next = tmp;
        (*position.node).prev = tmp;
        ++length;
        return tmp;
    }
    
    </pre>

    <p>
    Step 3a requires the construction of a data member of type <tt>X</tt>
    as in the Step 1, and hence requires a default constructor. Step 2b
    uses the STL allocator interface to construct the object from
    argument <tt>x</tt> using <tt>placement new</tt> and hence requires
    a copy constructor. The typical <tt>construct</tt> looks like the
    following:

    <pre>

    template &lt;class T1, class T2&gt;
    inline void construct(T1* p, const T2& value) {
	new (p) T1(value);
    }

    </pre>

    <p>
    <b>Step (3) requires a copy constructor (3b) in addition to a 
    default constructor (3a)</b>.
    <p>

<li> Here we are replacing the first element of the <tt>list</tt> with
    a new object, <tt>x2</tt>. Here the <tt>front</tt> method returns
    a reference (lvalue) to the data member of the first element in the 
    list and it is assigned a new value <tt>x2</tt>. This operation
    hence requires the assignement operator (ie., operator=).

    <p>
    <b>Step (4) requires an assignment operator, ie., 
    operator=(const X& x)</b>.
    <p>

<li> Here we want to remove the element, if any, in the list that equals
    the value <tt>x3</tt>. The code looks like the following:

    <pre>

    template &lt;class T&gt;
    void list&lt;T&gt;::remove(const T&amp; value) {
	iterator first = begin();
	iterator last = end();
	while (first != last) {
	    iterator next = first;
	    ++next;
	    if (*first == value)        //   &lt;-------- (5a)
		erase(first);
	    first = next;
	}
    }

    </pre>

    The <tt>remove</tt> member starts in the beginning of the list and
    searches till either the end is reached or a value equalling 
    <tt>value</tt> argument is found; if found, <tt>remove</tt> removes
    the element from the list and calls the destructor. Note in Step (6a), 
    we need the equality operator (operator==) defined for this to work.

    <p>
    <b>Step (5) requires an equality operator, ie., 
    bool operator==(const X& x)</b>.
    <p>

<li> Now we sort the list. The <tt>sort</tt> member use an in-place <em>
    merge sort</em> algorithm that requires the <em>less-than</em>
    relation defined for the object (Step 6a below).
   
    <pre>

    template &lt;class T&gt;
    void list&lt;T&gt;::merge(list&lt;T&gt;&amp; x) {
	iterator first1 = begin();
	iterator last1 = end();
	iterator first2 = x.begin();
	iterator last2 = x.end();
	while (first1 != last1 &amp;&amp; first2 != last2)
	    if (*first2 &lt; *first1) {            //   &lt;-------- (6a)
		iterator next = first2;
		transfer(first1, first2, ++next);
		first2 = next;
	    } else
		first1++;
	if (first2 != last2) transfer(last1, first2, last2);
	length += x.length;
	x.length= 0;
    }

    template &lt;class T&gt;
    void list&lt;T&gt;::sort() {
	if (size() &lt; 2) return;
	list&lt;T&gt; carry;
	list&lt;T&gt; counter[64];
	int fill = 0;
	while (!empty()) {
	    carry.splice(carry.begin(), *this, begin());
	    int i = 0;
	    while(i &lt; fill &amp;&amp; !counter[i].empty()) {
		counter[i].merge(carry);
		carry.swap(counter[i++]);
	    }
	    carry.swap(counter[i]);         
	    if (i == fill) ++fill;
	} 
	while(fill--) merge(counter[fill]);
    }

    </pre>

    <p>
    <b>Step (6) requires a less-than operator, ie., 
    bool operator&lt;(const X& x)</b>.
    <p>


<li> Here the <tt>list</tt> object goes out of scope and is automatically
    destructed by the C++ runtime system. The destructor for <tt>list</tt>
    in turns calls the destructor for all the elements that are in the
    list. Hence the object requires a destructor.

    <p>
    <b>Step (7) requires a destructor</b>
    <p>

</ol>

<p>
The following are automatically supplied by the compiler if not defined by
the user:
<ul>
<li> <tt>X()</tt> -- default constructor, but <em>only when</em> no other 
   constructor is defined
<li> <tt>X(X const&amp;)</tt> -- copy constructor
<li> <tt>operator=(X const&amp;)</tt> -- assignment operator
<li> <tt>~X()</tt> -- destructor
</ul>

<p>
If <tt>X</tt> in this example contains pointers, please be sure to define
all of these instead of leaving it to the compiler.

<p>
The following <em>must</em> be defined explicitly by the user:
<ul>
<li> <tt>bool operator==(X const&amp;)</tt> --  equality operator
<li> <tt>bool operator&lt;(X const&amp;)</tt> -- less-than operator
</ul>

Note that if we had not used the <tt>remove</tt> and <tt>sort</tt>
members, most smart compilers would not require <tt>X</tt> to define
these two operators.