Lists, template class List, single & double link, insert sort, merge sort, iters

[David]

Update:  please see this next link:

http://developers-heaven.net/forum/index.php/topic,2636.0.html

FREE homework help NOW available via e-mail ... (or in person if in Toronto Ontario Canada region.)

You can contact me via:
http://sites.google.com/site/securejoules/securetransportservices
http://sites.google.com/site/andeveryeyeshallseehim/home/he-comes

Here is a NEW link (new as of 2013-05-08)  for beginners ... to linked lists (using C++):

http://developers-heaven.net/forum/index.php?topic=2606.0

Here is another (older) link for beginners ... to linked lists (using C++):

http://developers-heaven.net/forum/index.php/topic,106.msg266.html#msg266

For an example of recursive calls to a linked list of char's (to print the list reversed) ... see:
(most recent update is maintained here)
http://developers-heaven.net/forum/index.php/topic,106.msg569.html#msg569

Template class List with insert sort and merge sort (recursive)
(and further below for examples of list classes with iterators) ...

Code: [Select]

// templateClassList2.cpp

// this version: 2018-04-13

// template class List with 'merge sort' and 'insert sort'
// has private class members: 'pFront', 'pRear' and 'size'
// and public copy constructor and overloaded assignment operator

#include <iostream>
#include <fstream>

#define haveFile true

// FILE NAME: int.dat //
/*
1492
1776
1860
-23
1698
1935
1926
1953
1960
1492
1776
1860
-23
1698
2000
1935
1926
1953
1960
-47
*/

using namespace std;

template< typename T >
class List
{
public:
    List();
    ~List();

    List( const List <T> & obj ) // inline copy constructor ...
    {
        pFront = pRear = 0;
        len = 0;
        for( Node* p = obj.pFront; p; p = p->next )
            push_back( p->data );
        is_sorted = obj.is_sorted;
    }

    List& operator = ( const List <T> & obj ) // inline overloaded assignment
    {
        // return if lists are already the same list ...
        if( this == &obj ) return *this;

        // ok ... not same ... so ...
        if( len ) clear(); // sets ...pFront=pRear=0; size=0; is_sorted=true
        else {
            pFront = pRear = 0;
            len = 0;
        }
        // now ...
        for( Node* p = obj.pFront; p; p = p->next )
            push_back( p->data );
        is_sorted = obj.is_sorted;
        return *this;
    }

    void push_front( const T& e );
    void push_back( const T& e );
    void add_at_index( size_t c, const T& e );
    void remove( const T& e );
    void print() const;

    bool exist( const T& e ) const;
    size_t size() const;

    T max() const;
    T min() const;

    // insert new element e in sorted order into a sorted list ...
    void isort_insert( const T& e );
    void isort(); // insert-sort the whole list in place ...
    void update_pRear()
    {
        pRear = pFront;
        while( pRear->next != 0 ) pRear = pRear->next;
    }

    // merge sort the whole list in place (a 'divide and sort' recursive sort)
    void msort()
    {
        Node* p = pFront;
        merge_sort( p, len ); // p is updated in recursion using pass by ref.
        set_pFront_pRear( p );
        is_sorted = true;
    }

    void remove_duplicates()
    {
        if( len <= 1 ) return;

        if( !is_sorted ) msort();

        Node* p = pFront;
        while( p->next != 0 )
        {
            if( p->data == p->next->data )
            {
                Node* tmp = p->next;
                p->next = p->next->next;
                delete tmp;
                -- len;
            }
            else p = p->next; // move up one ...
        }
        update_pRear();
    }

private:
    struct Node
    {
        T data;
        Node* next;
    } *pFront, *pRear;

    size_t len; // number of list nodes
    bool is_sorted;

    void clear()
    {
        if( !len ) return;

        for( Node* q = pFront; q; pFront = q )
        {
            q = pFront->next;
            delete pFront;
        }
        pRear = 0; // Note: pFront is set to 0 above on last for loop
        len = 0;
        is_sorted = true;
    }

    void insert_sorted( Node*& pHead, Node* pNewNode );

    void merge_sort( Node*& pFront, size_t size ); // returns updated pFront by ref.

    // merge two sorted lists with heads 'a' and 'b' ... in sorted order
    Node* merge( Node* a, Node* b )
    {
        if( !a ) return b;
        if( !b ) return a;

        Node* sorted;  // now get appropriate new head for merged list
        if( a->data <= b->data )
        {
            sorted = a;
            a = a->next;
        }
        else
        {
            sorted = b;
            b = b->next;
        }

        Node* new_merged_head = sorted;

        // now merge lists ...
        while( a && b )
        {
            if( a->data <= b->data )
            {
                sorted->next = a;
                sorted = sorted->next;
                a = a->next;
            }
            else
            {
                sorted->next = b;
                sorted = sorted->next;
                b = b->next;
            }
        }

        // now ... append the ONE part that might have been left-over above ...
        if( a )
            sorted->next = a;
        else // b //
            sorted->next = b;

        return new_merged_head;
    }

    void set_pFront_pRear(Node* p) {
        pFront = p;
        update_pRear();
    }
};

// definitions ...

template< typename T >
List<T>::List()
{
    pFront = pRear = 0;
    len = 0;
    is_sorted = true;
}

template< typename T >
List<T>::~List()
{
    clear();
}

template< typename T >
void List<T>::push_front( const T& e ) // inserts e with type T at front of List
{
    Node* n = new Node;
    n->data = e;
    n->next = pFront;
    pFront = n;

    if( !len ) pRear = pFront;
    ++len;
    is_sorted = false;
}

template< typename T >
void List<T>::push_back( const T& e ) // inserts e with type T at end of List
{
    Node* n = new Node;
    n->data = e;
    n->next = 0;

    if( len )
    {
        pRear->next = n;
        pRear = n;
    }
    else
        pRear = pFront = n;

    ++len;
    is_sorted = false;
}

template< typename T >
void List<T>::add_at_index( size_t c, const T& e) // inserts e with type T at index c
{
    if( c < len )
    {
        if( c > 0 )
        {
            // insert at index c  ... BUT after index 0 ... i.e. at 1 to size
            Node* prev = pFront;
            for( size_t i = 1; i < c; ++ i ) prev = prev->next;

            Node* n = new Node;
            n->data = e;

            // now insert n at index c ... A -> B  becomes A->C->B
            n->next = prev->next;  // C -> B
            prev->next = n; // A -> C
            ++ len;
            is_sorted = false;

        } // here c is 0 ... so ...
        else push_front( e ); // resets size, pFront and pRear ... as applicable
    }
    else if( c == len ) push_back( e );
    else
    {
        cout << "\nHighest new index allowed is " << len
             << ". You requested index " << c << " ... push_back y/n ? ";
        string reply;
        getline( cin, reply );
        if( reply == "n" || reply == "N" )
            return;

        // if reach hear ...
        cout << "Ok ... will push_back ...\n";
        push_back( e );  // resets size, pFront and pRear  ... as applicable
    }
}


template< typename T >
void List<T>::remove( const T& e )
{
    if( !len )
    {
        cout << "\nCan not remove '" << e << "' since list is empty.\n";
        return;
    }

    Node* q = pFront;
    if( q->data == e ) // if at front ...
    {
        pFront = q->next;
        delete q;
        --len;
        cout<<"\n'" << e <<"' removed ...";
        if( len <= 1 ) {
            pRear = pFront;
            is_sorted = true;
        }
        return;
    }

    // if reach here ...  'e' is NOT the first
    Node* prev = q;
    q = q->next; // q now points to 2nd node in list ...
    while( q ) // Note: also handles case of just one Node in list
    {
        if( q->data == e )
        {
            prev->next = q->next;
            delete q;
            cout<<"\n'" << e <<"' removed ...";
            --len;
            if( len == 1 ) {
                pRear = prev;
                is_sorted = true;
            }
            return;
        }

        // if reach here ... advance both nodes up the list  ...
        prev = q;
        q = q->next;
    }
    cout<<"\n'" << e <<"' NOT found ...";
}

template< typename T >
void List<T>::print() const
{
    for( Node* q = pFront; q; q = q->next )
        cout << ' ' << q->data;
}

template< typename T >
bool List<T>::exist( const T& e ) const
{
    for( Node* q = pFront; q; q = q->next )
        if( q->data == e )
            return true;
    return false;
}

template< typename T >
size_t List<T>::size() const
{
    return len;
}

template< typename T >
T List<T>::max() const
{
    if( !len )
    {
        cout << "List is empty ... returning 'zero' ... ";
        return T(0);
    }
    T max = pFront->data;
    for( Node* q = pFront; q->next; q = q->next )
        if( q->next->data > max )
            max = q->next->data;
    return max;
}

template< typename T >
T List<T>::min() const
{
    if( !len )
    {
        cout << "List is empty ... returning 'zero' ... ";
        return T(0);
    }
    T min = pFront->data;
    for( Node* q = pFront; q->next; q = q->next )
        if( q->next->data < min )
            min = q->next->data;
    return min;
}


//////////////////////////////// BEGIN MERGE SORT //////////////////////////////

// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'

template< typename T >
void List<T>::merge_sort( Node*& pFront, size_t size )
{
    if( size <= 1 ) return;

    Node* pHead2;
    Node* pEnd1;

    size_t size2 = size/2;
    size_t size1 = size - size2;

    // split the list into two lists ... the first half begins with pHead
    pEnd1 = pFront; // first set pEnd1 to the head address ...
    for( size_t i = 1; i < size1; ++ i )
        pEnd1 = pEnd1->next;

    pHead2 = pEnd1->next; // second half begins with pHead2
    pEnd1->next = 0; // breaking the chain here... so we can have two lists

    // merge the lists after recusively merge_sorting them
    merge_sort( pFront, size1 );
    merge_sort( pHead2, size2 );
    pFront = merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////


/////////////////////////////////// BEGIN ISORT ////////////////////////////////

// does NOT update pRear ... so must call update_pRear() when all inserts done.
template< typename T >
void List<T>::isort_insert( const T& e )
{
    Node* n = new Node;
    n->data = e;
    n->next = 0;
    if( len > 1 && !is_sorted ) msort();
    insert_sorted( pFront, n );
    ++ len;

}

// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template< typename T >
void List<T>::insert_sorted( Node*& pHead, Node* pNewNode )
{
    // First ... handle case where new node should be first element
    if( !pHead || pNewNode->data < pHead->data )
    {
        // It now becomes the first element
        pNewNode->next = pHead; // old pHead becomes 2nd in list
        pHead = pNewNode; // and this new node becomes the head of the list
    }
    else // If here ... search the nexted list for the right location
    {
        Node* q = pHead; // Get a working copy of pHead in q
        // Start comparing with element AFTER 'q' ... i.e. the 'next in'
        while( q->next && q->next->data <= pNewNode->data )
        {
            q = q->next; // Traverse the list ...
        }

        // Ok, insert after 'q' by 're-nexting' the pointers
        // ( Includes inserting at end position ... where q->next == 0 )

        // for A->B to become A->N->B ...
        pNewNode->next = q->next; // first insert/link ... N->B
        q->next = pNewNode; // and now link ... A->N
    }
}

// insert sort a whole list ...
template< typename T >
void List<T>::isort()
{
    // Note: pNewHead MUST be 0 to start ...
    Node *pTmp, *pHead = pFront, *pNewHead = 0;

    while( pHead ) // take each node from old list and insert in new
    {
        pTmp = pHead; // get 'this' node ...
        pHead = pHead->next; // move 'start' up one, to be ready for next node
        insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
    }
    set_pFront_pRear( pNewHead );
    is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////



// used in main ...
void pause()
{
    cout << "\n\nPress 'Enter' to continue ... ";
    string line;
    getline( cin, line );
}


int main() //////////////////// MAIN ///////////////////////////////
{
    List <int> ml; // construct an empty list to hold int's

    ml.remove(1);
    cout<<"Number of elements = "<<ml.size();
    ml.print();

    cout << "\nml.max() = ";
    cout << ml.max();
    cout << "\nml.min() = ";
    cout << ml.max();

    cout << "\n\nAfter push_back(...) 's ...";
    ml.push_back(3);
    ml.push_back(2);
    ml.push_back(1);
    ml.push_back(6);
    ml.push_back(5);
    ml.push_back(4);
    cout<<"\n'6' is in the list = " <<(ml.exist(6) ? "True." : "False.");
    cout<<"\n'22' is in the list = " <<(ml.exist(22) ? "True." : "False.");
    cout << "\nml.max() = ";
    cout << ml.max();
    cout << "\nml.min() = ";
    cout << ml.max();
    ml.print();
    cout<<"\nNumber of elements = "<<ml.size();
    pause();

    ml.add_at_index(0,0);
    ml.push_back(7);
    ml.print();
    cout<<"\nNumber of elements = "<<ml.size();
    pause();

    ml.add_at_index(8,8);
    ml.print();
    cout<<"\nNumber of elements = "<<ml.size();
    pause();

    ml.add_at_index(9,9);
    ml.add_at_index(10,10);
    ml.print();
    cout<<"\nNumber of elements = "<<ml.size();
    pause();

    // before isort ... get a copy ...
    List <int> mlcopy( ml );

    ml.isort();
    ml.print();
    cout<<"\nNumber of (isort sorted) elements = "<<ml.size();
    pause();

    cout << "\nEnlarged mlcopy (before msort) ... ";
    mlcopy.push_front(10);
    mlcopy.push_front(44);
    mlcopy.push_front(10);
    mlcopy.push_front(44);
    mlcopy.print();
    cout<<"\nNumber of elements = "<<mlcopy.size();
    pause();

    mlcopy.msort();
    mlcopy.print();
    cout<<"\nNumber of (msort sorted) elements = "<<mlcopy.size();
    pause();

    mlcopy.remove_duplicates();
    cout << "\nAfter mlcopy.remove_duplicates() ...";
    mlcopy.print();
    cout<<"\nNumber of elements = "<<mlcopy.size();
    pause();

    cout << "\nNow returning to original list ... ml.print() ...";
    ml.print();
    cout<<"\nNumber of elements = "<<ml.size();
    pause();

    ml.remove(4); // now back to ml (original ...)
    ml.remove(3);
    ml.remove(5);
    ml.remove(66);
    ml.remove(0);
    ml.remove(10);
    ml.print();
    cout<<"\nNumber of elements = "<<ml.size();
    pause();

    List < int > asn = ml;
    cout << "\nAfter List < int > asn = ml ...";
    asn.print();
    cout<<"\nAnd ... asn.length() = " << asn.size();
    pause();

# if haveFile
    //=============================================================//


    cout << "\n\nNOW reading file \"int.dat\" ... \n";
    List < int > list; // construct a new empty list 'list' to hold int's ...
    ifstream fin("int.dat");
    int x;
    cout<< "\nA new list of unique elements from file, "
        << "using list.isort_insert(x) \n";
    while( fin >> x )
    {
        if(!list.exist(x))
            list.isort_insert(x);
    }
    list.update_pRear(); // RECALL: *MUST* update pRear when all insertions done

    list.print();
    cout << "\nNumber of elements = "<<list.size();
    pause();

    list.isort_insert(1492);
    list.update_pRear(); // RECALL: *MUST* update pRear when all insertions done

    cout << "\n\nAfter list.isort_insert(1492) \n";
    list.print();
    cout << "\nNumber of elements = "<<list.size();
    pause();

    list.remove(-47);
    list.remove(-23);
    while( list.exist(1492) ) list.remove(1492);
    list.remove(-1);
    if( list.exist(-2) ) list.remove(-2);
    list.remove(1926);
    list.remove(1935);
    cout << "\nList Max = " << list.max();
    cout << "\nList Min = " << list.min();

    cout << "\n\n";
    list.print();
    cout << "\nNumber of elements = "<<list.size();
    pause();
#endif

} ///////////////////////// END MAIN ////////////////////////////
For a demo of template Class List (using a plain linked-list) ... look here for most recent update:

http://developers-heaven.net/forum/index.php/topic,106.msg570.html#msg570


And some links to more 'list' examples ...

Search for a part of a string ... in a STL list of strings ...

http://www.dreamincode.net/forums/index.php?showtopic=152302&view=findpost&p=906829

Compare these next 2 ... that sort a STL vector ... and sort a STL list  ...

1. STL sort function to sort vector container of 'MyContacts' ... (from Chapter 15)
http://developers-heaven.net/forum/index.php/topic,127.msg280.html#msg280

vs ...

2. STL list delete function is added here ... (from Chapter 15)  Note we have switched from a STL vector container to a STL list container ... to allow easy deletes.
http://developers-heaven.net/forum/index.php/topic,127.msg281.html#msg281


Carrying on with C++ lists ...these next 2 may be useful examples for C++ students  ... 1. class Student using the STL list container to hold class Student objects ... vs ... 2. STL vector of class Student objects ...
1. 
http://developers-heaven.net/forum/index.php/topic,106.msg272.html#msg272

vs ...

2. 
http://developers-heaven.net/forum/index.php/topic,106.msg198.html#msg198
C++ Student class ... a very common student problem ...
A very simple example of Student Records to get students started ...
It uses a vector container to hold each 'Student'
   1. takes in info from keyboard into a vector of 'Student' (uses push_back)
   2. shows 'records' in memory on screen
   3. writes to file the 'record's in memory
   4. reads from file and puts records into memory

And ... another class Student ... that uses the STL list ...

http://developers-heaven.net/forum/index.php/topic,127.msg614.html#msg614

[David]

Reserving some space here for a table of contents of links to various C/C++ topics ... and resources ...


A link to a single link list with iterators in the forward direction ...

http://developers-heaven.net/forum/index.php/topic,310.msg821.html#msg821


A link to a double link list with iterators in the forward and reverse directions ...

http://developers-heaven.net/forum/index.php/topic,310.msg820.html#msg820


And a link to a test program that demos using both the above ...

http://developers-heaven.net/forum/index.php/topic,310.msg819.html#msg819


Or backing up some to a simpler example ... (no templates used here) ...
a simple single linked list (of int's) as a base class for a simple set class (of int's) ...

http://developers-heaven.net/forum/index.php/topic,310.msg2932.html#msg2932

[admin]

Good job David

[David]

C examples of linked list (using C) ...


For some basics in linked lists (of integers, using C), both NULL terminated and circular ...

and to see an insertion sort in a linked list, click on the next link:

http://developers-heaven.net/forum/index.php/topic,106.msg580.html#msg580


C an insertion sort method that adds new list elements by inserting them in ABC...abd... sorted order.  (Also, uses typedef char* CString ...  A CString holds a whole line of input ... and using a 'list' of lines ... you can have as many lines as you may wish ... i.e. as much as available memory permits ...  in your 'insertion-sorted list'.  This INSERT SORT in a linked-list *IS* an often seen student problem.)

http://developers-heaven.net/forum/index.php/topic,106.msg257.html#msg257


Merge two files into one new file, in sorted order, via insert_sort and a linked list ...

http://developers-heaven.net/forum/index.php/topic,106.msg571.html#msg571


Student GRADES MANAGEMENT SYSTEM ... C version uses a linked-list of struct Student ... C way to approximate class Student ... with an insert-sorted list and simple password protection. Note: will only permit unique id's

http://developers-heaven.net/forum/index.php/topic,106.msg273.html#msg273


C Student Registration program ... using a linked-list of struct Student ...  (with 9 data items)

http://developers-heaven.net/forum/index.php/topic,106.msg275.html#msg275

[David]

Cvec: Here is the beginning of an emulation, in C, of the C++ push_back of a vector ... (Note: uses qsort)

http://developers-heaven.net/forum/index.php/topic,106.msg563.html#msg563

And following this Cvec, (at the link above), is an emulation, Clist, that uses a stable mergesort for that linked-list of struct's ... instead of the qsort used for this 'Cvec' dynamic array of struct's.


Here is a demo of qsort (of arrays) in C ... of ... int's, C string's, struct's ...
(and also demo's sorts that ignore case - click on following link to jump there now)

http://developers-heaven.net/forum/index.php/topic,106.msg277.html#msg277

[David]

Here is a step on the way to a mail merge program ... in C ...


Take a look at this split_demo.c that shows how to split a line ( a CString ) ...

and return a Clist of words/tokens ...

Note:

You will need all three files that follow, in the same folder, to compile/run this split_demo.c ...

(First the demo file ... then the three helper files ...)

http://developers-heaven.net/forum/index.php/topic,106.msg591.html#msg591

[David]

Here is a list with iterators, both a single link list and a double link list ... each with both merge sort and insert sort:

First the test program ...

Code: [Select]

// List2IterNode_h_test.cpp // this version 2010-10-15 //

#include <fstream>
//#include <string>
#include <ctime> // re. clock ...

// defaults to testing file "List1IterNode.h"
#define link2 false // change 'false' to 'true' to test file "List2IterNode.h"
#define do_part1 true // change 'true' to 'false' to skip file test in 'part1'

#if link2
    #define links "double-link linked list"
    #include "List2IterNode.h"
    // includes <iostream>, <string>, <cstdlib>, using namespace std; and myAssert
#else
    #define links "single-link linked list"
    #define insert_before insert
    #include "List1IterNode.h"
    // includes <iostream>, <string>, <cstdlib>, using namespace std; and myAssert
#endif

// above ListxIterNode.h includes ...
/*
#include <iostream>
#include <string>
#include <cstdlib> // re. exit ...
using namespace std;
*/

const char DATAFILE[] = "randInt3M.txt";

bool fillFromFile( List< int >& il )
{
    ifstream fin( DATAFILE );
    if( !fin ) return false;
    int tmp;
    while( fin >> tmp ) il.push_back( tmp );
    fin.close();
    return true;
}

#if link2
bool writeFile( const List< int >& il )
{
    ofstream fout( "randInt3M_rev_sorted.txt" );
    if( !fout ) return false;
    for( Iter< int > pos = il.end(); pos != il.begin(); )
        fout << *--pos << "\n";
    return true;
}
#else
bool writeFile( const List< int >& il )
{
    ofstream fout( "randInt3M_sorted.txt" );
    if( !fout ) return false;
    for( Iter< int > pos = il.begin(), end = il.end(); pos != end; ++pos )
        fout << *pos << "\n";
    return true;
}
#endif

bool createFile( List< int >& il )
{
    ofstream fout( DATAFILE );
    if( !fout ) return false;

    srand( (unsigned) time(0) );
    for( int i = 0; i < 3000000; ++i )
    {
        int tmp = rand();
        il.push_back( tmp );
        fout << tmp << " ";
        if( i % 10 == 0 ) fout << endl;
    }
    fout.close();
    return true;
}



int main()
{
    cout << "For " << links << " ...\n\n";
   
    cout << "sizeof(List<int>) = " << sizeof(List<int>)
         << ", sizeof(Iter<int>) = " << sizeof(Iter<int>)
         << ", sizeof(Node<int>) = " << sizeof(Node<int>) << " ...\n\n";

#if do_part1

    List< int > ml; // construct an empty list to hold int's ...(here 3 Million)
    cout << "time in sec's to execute fillFromFile( ml ) = " << flush;
    double ti = clock();
    if( !fillFromFile( ml ))
    {
        if( createFile( ml )) cout << "\n(created) ";
        else
        {
            cerr << "\nError in creating data file!"
                 << "\nPress 'Enter' to continue/exit ... " << flush;
            cin.get();
            return 1;
        }
    }
   
    double tp = clock() - ti;
    cout << tp/CLOCKS_PER_SEC << " and ml.get_size() = " << ml.get_size();
   
    cout << "\ntime in sec's to execute ml.msort() = " << flush;
    ti = clock();
    ml.msort();
    tp = clock() - ti;
    cout << tp/CLOCKS_PER_SEC << " and ml.isSorted() = "<< ml.isSorted() << endl;
   
    cout << "time in sec's (pre-sorted) to execute ml.msort() = " << flush;
    ti = clock();
    ml.msort();
    tp = clock() - ti;
    cout << tp/CLOCKS_PER_SEC << " and ml.isSorted() = "<< ml.isSorted() << endl;

    List< int > mlRev;
    for( Iter< int > it = ml.begin(), end = ml.end(); it != end; ++it )
        mlRev.push_front( *it );
   
    cout << "time in sec's (rev-sorted) to execute ml.msort() = "
         << flush;
    ti = clock();
    mlRev.msort();
    tp = clock() - ti;
    cout << tp/CLOCKS_PER_SEC << " and ml.isSorted() = "<< mlRev.isSorted() << endl;

    int count = 0;
#if link2
    // for double-link linked list ...
    for( Iter< int > it = ml.begin(), end = ml.end(); it != end; )
    {
        if( *it == 32767 ) // try also removing all 0's ...
        {
            ++count;
            it = ml.erase( it );
        }
        else ++it;
    }
#else
    // for single-link linked list ...
    for( Iter< int > it = ml.begin(), end = ml.end(), prev = end ; it != end  ; )
    {
        if( *it == 32767 ) // try also removing all 0's ...
        {
            ++count;
            it = ml.erase( it, prev ); // for single linked-list ...
        }
        else
        {
            prev = it;
            ++it;
        }
    }
#endif // link2

    cout << "\nThe count of 32767's = " << count << endl;
    cout << "\nThe new size is ml.get_size() = " << ml.get_size() << endl;
   
    ml.remove_duplicates();
    cout << "\nThe new size is ml.get_size() = " << ml.get_size() << endl;
   
    count = 0;
    Iter< int > it = ml.begin(), end = ml.end();
    while( it != end )
    {
        if( *it == 32767 ) ++count;
        ++it;
    }
    cout << "\nThe count NOW of 32767's = " << count << endl;


    cout << "time in sec's, for REDUCED list, to execute writeFile( ml ) = "
         << flush;
    ti = clock();
    writeFile( ml ); // test of reverse iter & previous links after msort was ok
    tp = clock() - ti;
    cout << tp/CLOCKS_PER_SEC << "\nand ml.get_size() = "<< ml.get_size() << endl;

    cout << "\nWait briefly ... freeing large list now ..." << flush;
    ml.free();
   
    cout << "\nPress 'Enter' to continue ... " << flush;
    cin.get();

#endif // do_part1

    List< string > students; // construct an empty List (of strings) ...
    cout << "\nstudents.get_size() = " << students.get_size() << "\n";
   
    students.push_back( "Cane, Sugar" );
    students.push_back( "Dame, Lady" );
    students.push_back( "Fame, Fanny" );
    students.push_back( "Game, Pretty" );
    cout << "students.get_size() = " << students.get_size() << "\n";

    // add a value in 5th position ...
    Iter< string > pos, poscpy;
    pos = students.begin();
    ++pos;
    ++pos;
    ++pos;
    ++pos;

    students.insert( pos, "Tame, Very" );
    cout << "students.get_size() = " << students.get_size() << "\n";

    students.insert( pos, "Tame, Very Very" );

    //print the list ...
    for( pos = students.begin(); pos != students.end(); ++pos )
        cout << *pos << "\n";
    cout << "students.get_size() = " << students.get_size() << "\n";
#if link2
    // remove the 3rd last value ...
    pos = students.end();
    --pos;
    --pos;
    --pos;
#else
    // remove the 4th value ...
    pos = students.begin();
    ++pos;
    ++pos;
    ++pos;
#endif

    poscpy = students.erase(pos);
    //print the list ...
    cout << "\nAter removing 3rd last value ...\n";
    for( pos = students.begin(); pos != students.end(); ++pos )
        cout << *pos << "\n";
    cout << "students.get_size() = " << students.get_size() << "\n";

    // insert a student at 'poscpy' returned above ...
    students.insert( poscpy, "Anthony, Timothy Horton" );
    //print the list ...
    cout << "\nAfter insertion ...\n";
    for( pos = students.begin(); pos != students.end(); ++pos )
        cout << *pos << "\n";
    cout << "students.get_size() = " << students.get_size() << "\n";
#if link2
    //print the list in reverse order ...
    cout << "\nPrinting list in reverse order ...\n";
    for( pos = students.end(); pos != students.begin();  )
        cout << *--pos << "\n";
    cout << "students.get_size() = " << students.get_size() << "\n";
#else
    //print the list
    cout << "\nPrinting list ...\n";
    for( pos = students.begin(); pos != students.end(); ++pos )
        cout << *pos << "\n";
    cout << "students.get_size() = " << students.get_size() << "\n";
#endif

    List < string > s_copy( students );
    students.free();
    cout << "\nAfter students.free() ... ";
    cout << "students.get_size() = " << students.get_size() << "\n";

    cout << "\nPrinting s_copy ...\n";
    for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
        cout << *pos << "\n";
    cout << "s_copy.get_size() = " << s_copy.get_size() << "\n";

    s_copy.push_front( "Saucer, Lucy" );

    if( !s_copy.isSorted() ) { cout << "\nsorting ..."; s_copy.isort(); }
#if link2
    cout << "\nPrinting s_copy rev...\n";
    for( pos = s_copy.end(); pos != s_copy.begin(); )
        cout << *--pos << "\n";
#else
    cout << "\nPrinting s_copy ...\n";
    for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
        cout << *pos << "\n";
#endif
    cout << "s_copy.get_size() = " << s_copy.get_size() << "\n";

    s_copy.isort_insert( "Georgette, Baby" );
    s_copy.update_pRear(); // update links ...

#if link2
    cout << "\nAfter isort_insert(...) ... printing s_copy now rev...\n";
    for( pos = s_copy.end(); pos != s_copy.begin(); )
        cout << *--pos << "\n";
#else
    cout << "\nAfter isort_insert(...) ... printing s_copy now ...\n";
    for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
        cout << *pos << "\n";

    List< string > rev;
    for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
        rev.push_front( *pos );
    cout << "\nAfter making a rev copy ... printing rev now ...\n";
    for( pos = rev.begin(); pos != rev.end(); ++pos )
        cout << *pos << "\n";
    cout << "rev.get_size() = " << rev.get_size() << "\n";
#endif
    cout << "s_copy.get_size() = " << s_copy.get_size() << "\n";


   
    pos = s_copy.find( "Anthony, Timothy Horto" ); // test can't find ...

    s_copy.insert( pos, "Lace, Fanny" );
    cout << "\nAfter insert ... printing s_copy ...\n";
    for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
        cout << *pos << endl;
       
    if( (pos = s_copy.find( "Anthony, Timothy Horton" )) != s_copy.end() )
        s_copy.erase( pos );

    cout << "\nAfter erase ... printing s_copy ...\n";
    for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
        cout << *pos << endl;


   
    cout << "\nPress 'Enter' to continue ... " << flush;
    cin.get();
}

// example output ...
/*
For single-link linked list ...

sizeof(List<int>) = 16, sizeof(Iter<int>) = 4, sizeof(Node<int>) = 8 ...

time in sec's to execute fillFromFile( ml ) = 3.828 and ml.get_size() = 3000000
time in sec's to execute ml.msort() = 6.875 and ml.isSorted() = 1
time in sec's (pre-sorted) to execute ml.msort() = 8.688 and ml.isSorted() = 1
time in sec's (rev-sorted) to execute ml.msort() = 0.875 and ml.isSorted() = 1

The count of 32767's = 92

The new size is ml.get_size() = 2999908

The new size is ml.get_size() = 32767

The count NOW of 32767's = 0
time in sec's, for REDUCED list, to execute writeFile( ml ) = 0.078
and ml.get_size() = 32767

Wait briefly ... freeing large list now ...
Press 'Enter' to continue ...

students.get_size() = 0
students.get_size() = 4
students.get_size() = 5
Cane, Sugar
Dame, Lady
Fame, Fanny
Game, Pretty
Tame, Very
Tame, Very Very
students.get_size() = 6

Ater removing 3rd last value ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Tame, Very
Tame, Very Very
students.get_size() = 5

After insertion ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
students.get_size() = 6

Printing list ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
students.get_size() = 6

After students.free() ... students.get_size() = 0

Printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
s_copy.get_size() = 6

sorting ...
Printing s_copy ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Saucer, Lucy
Tame, Very
Tame, Very Very
s_copy.get_size() = 7

After isort_insert(...) ... printing s_copy now ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very

After making a rev copy ... printing rev now ...
Tame, Very Very
Tame, Very
Saucer, Lucy
Georgette, Baby
Fame, Fanny
Dame, Lady
Cane, Sugar
Anthony, Timothy Horton
rev.get_size() = 8
s_copy.get_size() = 8

After insert ... printing s_copy ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny

After erase ... printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny

Press 'Enter' to continue ...

////////////////////////////////////////////////////////////////////////////////

For double-link linked list ...

sizeof(List<int>) = 16, sizeof(Iter<int>) = 8, sizeof(Node<int>) = 12 ...

time in sec's to execute fillFromFile( ml ) = 5.343 and ml.get_size() = 3000000
time in sec's to execute ml.msort() = 7.282 and ml.isSorted() = 1
time in sec's (pre-sorted) to execute ml.msort() = 9.125 and ml.isSorted() = 1
time in sec's (rev-sorted) to execute ml.msort() = 1.172 and ml.isSorted() = 1

The count of 32767's = 92

The new size is ml.get_size() = 2999908

The new size is ml.get_size() = 32767

The count NOW of 32767's = 0
time in sec's, for REDUCED list, to execute writeFile( ml ) = 0.063
and ml.get_size() = 32767

Wait briefly ... freeing large list now ...
Press 'Enter' to continue ...

students.get_size() = 0
students.get_size() = 4
students.get_size() = 5
Cane, Sugar
Dame, Lady
Fame, Fanny
Game, Pretty
Tame, Very
Tame, Very Very
students.get_size() = 6

Ater removing 3rd last value ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Tame, Very
Tame, Very Very
students.get_size() = 5

After insertion ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
students.get_size() = 6

Printing list in reverse order ...
Tame, Very Very
Tame, Very
Anthony, Timothy Horton
Fame, Fanny
Dame, Lady
Cane, Sugar
students.get_size() = 6

After students.free() ... students.get_size() = 0

Printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
s_copy.get_size() = 6

sorting ...
Printing s_copy rev...
Tame, Very Very
Tame, Very
Saucer, Lucy
Fame, Fanny
Dame, Lady
Cane, Sugar
Anthony, Timothy Horton
s_copy.get_size() = 7

After isort_insert(...) ... printing s_copy now rev...
Tame, Very Very
Tame, Very
Saucer, Lucy
Georgette, Baby
Fame, Fanny
Dame, Lady
Cane, Sugar
Anthony, Timothy Horton
s_copy.get_size() = 8

After insert ... printing s_copy ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny

After erase ... printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny

Press 'Enter' to continue ...
*/


[David]

Now the 2 files used by the above program ...

Code: [Select]

// List2IterNode.h // this version 2011-11-30 //

// a 'double-link' linked-list ...

// template class List with 'merge sort' and 'insert sort'
// has private class members: 'head', 'tail', 'size', 'is_sorted' ...

// now includes template class Node and template class Iter

#ifndef LIST2_ITER_NODE_H
#define LIST2_ITER_NODE_H

#include <iostream>
#include <string>
#include <cstdlib> // re. exit ...
using namespace std;

void myAssert( int a, const string& msg )
{
    if( !a )
    {
        cerr << msg << " ... Press 'Enter' to exit ... " << flush;
        cin.clear(); cin.sync(); cin.get(); exit(1);
    }
}

// forward declarations ...
template < typename T > class Iter;
template < typename T > class List;

template < typename T >
class Node
{
public:
    Node( T n ) : data( n ), prev( NULL ), next( NULL ) {}
private:
    T data;
    Node< T >* prev;
    Node< T >* next;
    friend class Iter< T >;
    friend class List< T >;
};


// an Iter 'points' to a Node's position in a list ... or a 'NULL' i.e. end()
// (i.e. ... past the end of the list)
template< typename T >
class Iter
{
public:
    // construct an Iter (not attached to any particular list) ...
    Iter() : cur( NULL ), tail( NULL ) {}

    // return T value at Node of this Iter  ...
    T operator * () const
    {
        myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
        return cur->data;
    }
    T& operator * ()
    {
        myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
        return cur->data;
    }
    Iter operator ++ ()
    {
        myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (2)" );
        cur = cur->next;
        return *this;
    }
    Iter operator ++ ( int anIntDummyHereToIndicatePostPP )
    {
        myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (3)" );
        cur = cur->next;
        return *this;
    }
    Iter operator -- ()
    {
        if( cur == NULL ) cur = tail;
        else cur = cur->prev;
        myAssert( (cur != NULL), "Iter operator -- cannot return NULL (4)" );
        return *this;
    }
    Iter operator -- ( int anIntDummyHereToIndicatePostPP )
    {
        if( cur == NULL ) cur = tail;
        else cur = cur->prev;
        myAssert( (cur != NULL), "Iter operator -- cannot return NULL (5)" );
        return *this;
    }

    bool operator == ( Iter< T > it ) const { return cur == it.cur; }
    bool operator != ( Iter< T > it ) const { return cur != it.cur; }

private:
    Node< T >* cur;
    Node< T >* tail;
    friend class List< T >;
};


template< typename T >
class List
{
public:
    // default ctor ...
    List() : head( NULL ), tail( NULL ), size(0), is_sorted(true) {} // default ctor ...
    // dtor ...
    ~List() { free(); }

    void free() // free all ...
    {
        for( Node< T >* q = head; q != NULL; head = q )
        {
            q = head->next;
            delete head;
        }
        tail = NULL; // Note: head is set to NULL above on last for loop
        size = 0;
        is_sorted = true;
    }

    // copy ctor ...
    List( const List< T >& obj ) : head( NULL ), tail( NULL ), size( 0 ),
                                   is_sorted( obj.is_sorted ) //{ copy( obj ); }
    {
        for( Node< T >* p = obj.head; p != NULL; p = p->next )
            push_back( p->data );
    }

    // overloaded assignment ...
    List< T >& operator = ( const List< T >& obj )
    {
        if( this != &obj )
        {
            free();
            is_sorted = obj.is_sorted;
            for( Node< T >* p = obj.head; p != NULL; p = p->next )
                push_back( p->data );
        }
        return *this;
    }
   
    //Node< T >* get_head() const { return head; }

    void push_front( T e )
    {
        Node< T >* newnode = new Node< T > ( e );
        if( head != NULL ) // NOT empty ...
        {
            head->prev = newnode;
            newnode->next = head;
            head = newnode;
        }
        else head = tail = newnode;
        ++size;
        is_sorted = false;
    }
    void push_back( T e )
    {
        Node< T >* newnode = new Node< T > ( e );
        if( tail != NULL ) // NOT empty ...
        {
            newnode->prev = tail;
            tail->next = newnode;
            tail = newnode;
        }
        else head = tail = newnode;
        ++size;
        is_sorted = false;
    }

    void insert( Iter< T > it, T e )
    {
        if( it.cur != NULL )
        {
            Node< T >* after = it.cur;
            Node< T >* before = after->prev;
            Node< T >* newnode = new Node< T > ( e );
            newnode->prev = before;
            newnode->next = after;
            after->prev = newnode;
           
            if( before != NULL )
                before->next = newnode;
            else // insert at beginning ...
                head = newnode;
            ++size;
            is_sorted = false;
        }
        else push_back( e );
    }

    int get_size() const { return size; }
    int length() const { return size; }

    Iter< T > erase( Iter< T > it )
    {
        myAssert( (it.cur != NULL), "List canNOT erase itr.cur = NULL (5)" );
        Node< T >* remove = it.cur;
        Node< T >* before = remove->prev;
        Node< T >* after = remove->next;

        if( remove == head ) head = after;
        else before->next = after;

        if( remove == tail ) tail = before;
        else after->prev = before;

        it.cur = after;
        delete remove;
        --size;
        return it;
    }
   
    Iter< T > find( T e ) const
    {
        Iter< T > pos;
        for( pos = begin(); pos != end(); pos++ )
            if( *pos == e ) return pos;
        return pos; // i.e. return end();
    }

    Iter< T > begin() const
    {
        Iter< T > itr;
        itr.cur = head;
        itr.tail = tail;
        return itr;
    }
    Iter< T > end() const
    {
        Iter< T > itr;
        itr.cur = NULL;
        itr.tail = tail;
        return itr;
    }
   
    // insert new element e in sorted order into a sorted list ...
    void isort_insert( T e );
    void isort(); // insert-sort the whole list in place ...
   
    void update_pRear() // and update all 'prev' links also ... (after sorts)
    {
        if( head == NULL ) { tail = NULL; return; }
        Node< T >* prev = tail = head; // initial tail and prev to head ...
        head->prev = NULL; // set head prev value ...
        while( tail->next != NULL ) // traversing in 'front-to-back' direction
        {
            tail = tail->next;
            tail->prev = prev;
            prev = prev->next;
        }
    }

    // merge sort the whole list in place (a 'divide and sort' recursive sort)
    void msort()
    {
        Node< T >* p = head;
        merge_sort( p, size ); // p is updated in recursion using pass by ref.
        set_pFront_pRear( p ); // update all 'prev' links also ...
        is_sorted = true;
    }
   
    bool get_is_sorted() const { return is_sorted; }
    void set_issorted( bool is ) {is_sorted = is; }
   
    bool isSorted( bool a = true ) const
    {
        if( size < 2 ) return true;
        if( a )
        {
            for( Node< T >* q = head; q->next != NULL; q = q->next )
                if( q->next->data < q->data ) return false;
        }
        if( !a ) // i.e ... if descending
        {
            for( Node< T >* q = head; q->next != NULL; q = q->next )
                if( q->data < q->next->data ) return false;
        }
        //
        return true;
    }
   
    void remove_duplicates()
    {
        if( size < 2 ) return;

        if( !is_sorted ) msort();

        Node< T >* p = head;
        while( p->next != NULL )
        {
            if( p->data == p->next->data )
            {
                Node< T >* tmp = p->next;
                p->next = p->next->next;
                delete tmp;
                --size;
            }
            else p = p->next; // move up one ...
        }
        update_pRear(); // updates all prev links also ...
    }


private:
    void insert_sorted( Node < T >*& pHead, Node< T >* pNewNode );
   
    // returns updated pFront by ref...
    void merge_sort( Node< T >*& pFront, int size );

    // merge two sorted lists with heads 'a' and 'b' ... in sorted order
    Node< T >* merge( Node< T >* a, Node< T >* b )
    {
        if( a == NULL ) return b;
        if( b == NULL ) return a;

        Node< T >* sorted;  // now get appropriate new head for merged list
        if( a->data <= b->data )
        {
            sorted = a;
            a = a->next;
        }
        else
        {
            sorted = b;
            b = b->next;
        }

        Node< T >* new_merged_head = sorted;

        // now merge lists ...
        while( a != NULL && b != NULL )
        {
            if( a->data <= b->data )
            {
                sorted->next = a;
                sorted = sorted->next;
                a = a->next;
            }
            else
            {
                sorted->next = b;
                sorted = sorted->next;
                b = b->next;
            }
        }

        // now ... append the ONE part that might have been left-over above ...
        if( a != NULL )
            sorted->next = a;
        else if( b != NULL )
            sorted->next = b;

        return new_merged_head;
    }

    void set_pFront_pRear(Node< T >* p) { head = p; update_pRear(); }
   
    Node< T >* head;
    Node< T >* tail;
    int size;
    bool is_sorted;
};

//////////////////////////////// BEGIN MERGE SORT //////////////////////////////

// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'

template< typename T >
void List< T >::merge_sort( Node< T >*& pFront, int size )
{
    if( size < 2 ) return;

    Node< T >* pHead2;
    Node< T >* pEnd1;

    int size2 = size/2;
    int size1 = size - size2;

    // split the list into two lists ... the first half begins with pHead
    pEnd1 = pFront; // first set pEnd1 to the head address ...
    for( int i=1; i<size1; ++i )
        pEnd1 = pEnd1->next;

    pHead2 = pEnd1->next; // second half begins with pHead2
    pEnd1->next = NULL; // breaking the chain here... so we can have two lists

    // merge the lists after recusively merge_sorting them
    merge_sort( pFront, size1 );
    merge_sort( pHead2, size2 );
    pFront=merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////


/////////////////////////////////// BEGIN ISORT ////////////////////////////////

// does NOT update pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::isort_insert( T e )
{
    Node< T >* n = new Node< T > ( e );

    if( size > 0 && !is_sorted ) msort();
    insert_sorted( head, n );
    ++size;

}

// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::insert_sorted( Node< T >*& pHead, Node< T >* pNewNode )
{
    // First handle most likely cases where new node is NOT first element ...
    if( pHead != NULL && pNewNode->data >= pHead->data )
    {
        // If here ... search the list for the right location
        Node< T >* q = pHead; // Get a working copy of pHead in q
        // Start comparing with element AFTER 'q' ... i.e. the 'next in'
        while( q->next != NULL && q->next->data <= pNewNode->data )
            q = q->next; // Traverse the list ...

        // Ok, insert after 'q' by 're-nexting' the pointers ...
        // ( Includes inserting at end position ... where q->next is NULL )
       
        // for A->B to become A->N->B ...
        pNewNode->next = q->next; // first insert/link ... N->B
        q->next = pNewNode; // and now link ... A->N
    }
    else // becomes the first element ...
    {
        pNewNode->next = pHead; // old pHead becomes 2nd in list
        pHead = pNewNode; // and this new node becomes the head of the list
    }
}

// insert sort a whole list ...
template < typename T >
void List< T >::isort()
{
     // Note: pNewHead MUST be NULL to start ...
    Node< T > *pTmp, *pHead = head, *pNewHead = NULL;

    while( pHead != NULL ) // take each node from old list and insert in new
    {
        pTmp = pHead; // get 'this' node ...
        pHead = pHead->next; // move 'start' up one, to be ready for next node
        insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
    }
    set_pFront_pRear( pNewHead );
    is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////

#endif


[David]

And for the single link list ...

Code: [Select]

// List1IterNode.h // this version 2011-11-30 //

// a 'single-link' linked-list //

// template class List with 'merge sort' and 'insert sort'
// has private class members: 'pFront', 'pRear', 'size', 'is_sorted' ...

// now includes template class Node and template class Iter

#ifndef LIST1_ITER_NODE_H
#define LIST1_ITER_NODE_H

#include <iostream>
#include <string>
#include <cstdlib> // re. exit ...
using namespace std;

void myAssert( int a, const string& msg )
{
    if( !a )
    {
        cerr << msg << " ... Press 'Enter' to exit ... " << flush;
        cin.clear(); cin.sync(); cin.get(); exit(1);
    }
}

// forward declarations ...
template < typename T > class Iter;
template < typename T > class List;

template < typename T >
class Node
{
public:
    Node( T n ) : data( n ), next( NULL ) {}
private:
    T data;
    Node* next;
    friend class Iter< T >;
    friend class List< T >;
};

// an Iter 'points' to a Node's position in a list ... or a 'NULL' i.e. end()
// (i.e. ... past the end of the list)
template< typename T >
class Iter
{
public:
    // construct an Iter (not attached to any particular list) ...
    Iter() : cur( NULL ) {}

    // return T value at Node of this Iter  ...
    T operator * () const
    {
        myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
        return cur->data;
    }
    T& operator * ()
    {
        myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
        return cur->data;
    }
    // pre ++ ...
    Iter& operator ++ ()
    {
        myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (2)" );
        cur = cur->next;
        return *this;
    }
    // post ++ ...
    Iter& operator ++ ( int anIntDummyHereToIndicatePostPP )
    {
        myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (3)" );
        cur = cur->next;
        return *this;
    }
   
    bool operator == ( Iter< T > it ) const { return cur == it.cur; }
    bool operator != ( Iter< T > it ) const { return cur != it.cur; }

private:
    Node< T >* cur;
    friend class List< T >;
};



template< typename T >
class List
{
public:
    // default ctor ...
    List() : pFront( NULL ), pRear( NULL ), size( 0 ), is_sorted( true ) {}
    // dtor ...
    ~List() { free(); }
    void free() // free all ...
    {
        for( Node< T >* q = pFront; q != NULL; pFront = q )
        {
            q = pFront->next;
            delete pFront;
        }
        pRear = NULL; // Note: pFront is set to NULL above on last for loop
        size = 0;
        is_sorted = true;
    }

    List( const List < T > & obj ) // inline copy constructor ...
    {
        pFront = pRear = NULL;
        size = 0;
        for( Node< T >* p = obj.pFront; p != NULL; p = p->next )
            push_back( p->data );
        is_sorted = obj.is_sorted;
    }

    List& operator = ( const List < T > & obj ) // inline overloaded assignment
    {
        if( this != &obj )
        {
            free();
            for( Node< T >* p = obj.pFront; p != NULL; p = p->next )
                push_back( p->data );
            is_sorted = obj.is_sorted;
        }
        return *this;
    }

    void push_front( T e );
    void push_back( T e );
    void add_at_index( int c, T e );
    void remove( T e );
    void show_all() const;

    bool exist( T e ) const;
    int length() const { return size; }
    int get_size() const { return size; }

    bool get_is_sorted() const { return is_sorted; }
    void set_issorted( bool is ) {is_sorted = is; }

    bool isSorted( bool a = true ) const
    {
        if( size < 2 ) return true;
        if( a )
        {
            for( Node< T >* q = pFront; q->next != NULL; q = q->next )
                if( q->next->data < q->data ) return false;
        }
        if( !a ) // i.e ... if descending
        {
            for( Node< T >* q = pFront; q->next != NULL; q = q->next )
                if( q->data < q->next->data ) return false;
        }
        //
        return true;
    }


    T max() const;
    T min() const;

    // insert new element e in sorted order into a sorted list ...
    void isort_insert( T e );
    void isort(); // insert-sort the whole list in place ...
    void update_pRear()
    {
        pRear = pFront;
        if( pRear == NULL ) return;
        while( pRear->next != NULL ) pRear = pRear->next;
    }

    // merge sort the whole list in place (a 'divide and sort' recursive sort)
    void msort()
    {
        Node< T >* p = pFront;
        merge_sort( p, size ); // p is updated in recursion using pass by ref.
        set_pFront_pRear( p );
        is_sorted = true;
    }

    void remove_duplicates()
    {
        if( size <= 1 ) return;

        if( !is_sorted ) msort();

        Node< T >* p = pFront;
        while( p->next != NULL )
        {
            if( p->data == p->next->data )
            {
                Node< T >* tmp = p->next;
                p->next = p->next->next;
                delete tmp;
                --size;
            }
            else p = p->next; // move up one ...
        }
        update_pRear();
    }

    //Node< T >* get_pFront() const { return pFront; }

    void insert_after( Iter< T > it, T e ) // insert after 'it' ....
    {
        if( it.cur != NULL  )
        {
            Node< T >* newnode = new Node< T >( e );

            // for A->B to become A->N->B ...
            newnode->next  = it.cur->next; // ....... set N->B
            it.cur->next = newnode; // now can set ... A->N
            ++size;
            is_sorted = false;
        }
        else push_back( e );
    }

    void insert_before( Iter< T > it, T e ) // insert before 'it' ....
    {
        if( it.cur == pFront ) push_front( e );
        //else if( it.cur == NULL ) push_back( e);
        else
        {
            Node< T >* newnode = new Node< T >( e );
            Node< T >* before = pFront;
            while( before->next != it.cur )
                before = before->next;

            // for A->B to become A->N->B ...
            before->next = newnode; // ... set A->N
            newnode->next  = it.cur; // and N->B
            ++size;
            is_sorted = false;
        }
    }

    Iter< T > erase( Iter< T > it )
    {
        myAssert( (it.cur != NULL), "List canNOT erase it.cur = NULL (4)" );
        Node< T >* remove = it.cur;
        Node< T >* before = NULL;
        Node< T >* after = remove->next;

        if( remove == pFront ) pFront = after;
        else
        {
            before = pFront;
            while( before->next != remove )
                before = before->next;
            before->next = after; // skip over this 'remove node' address ...
        }
        if( remove == pRear ) pRear = before;
        it.cur = after;
        delete remove;
        --size;
        return it;
    }
    Iter< T > erase( Iter< T > it, Iter< T > prev )
    {
        myAssert( (it.cur != NULL), "List canNOT erase it.cur = NULL (5)" );
        Node< T >* remove = it.cur;
        Node< T >* before = prev.cur;
        Node< T >* after = remove->next;

        if( remove == pFront )
            pFront = after;
        else
            before->next = after; // skip over this 'remove node' address ...
        if( remove == pRear )
            pRear = before;
        it.cur = after;
        delete remove;
        --size;
        return it;
    }

    Iter< T > find( T e ) const
    {
        Iter< T > pos;
        for( pos = begin(); pos != end(); ++pos )
            if( *pos == e ) return pos;
        return pos; // i.e. return end();
    }
    Iter< T > begin() const
    {
        Iter< T > itr;
        itr.cur = pFront;
        return itr;
    }
    Iter< T > end() const
    {
        Iter< T > itr;
        itr.cur = NULL;
        return itr;
    }

private:
    Node < T > *pFront, *pRear;
    int size; // number of list nodes
    bool is_sorted;

    void insert_sorted( Node < T >*& pHead, Node< T >* pNewNode );

    void merge_sort( Node< T >*& pFront, int size ); // returns updated pFront by ref.

    // merge two sorted lists with heads 'a' and 'b' ... in sorted order
    Node< T >* merge( Node< T >* a, Node< T >* b )
    {
        if( a == NULL ) return b;
        if( b == NULL ) return a;

        Node< T >* sorted;  // now get appropriate new head for merged list
        if( a->data <= b->data )
        {
            sorted = a;
            a = a->next;
        }
        else
        {
            sorted = b;
            b = b->next;
        }

        Node< T >* new_merged_head = sorted;

        // now merge lists ...
        while( a != NULL && b != NULL )
        {
            if( a->data <= b->data )
            {
                sorted->next = a;
                sorted = sorted->next;
                a = a->next;
            }
            else
            {
                sorted->next = b;
                sorted = sorted->next;
                b = b->next;
            }
        }

        // now ... append the ONE part that might have been left-over above ...
        if( a != NULL )
            sorted->next = a;
        else if( b != NULL )
            sorted->next = b;

        return new_merged_head;
    }

    void set_pFront_pRear(Node< T >* p) { pFront = p; update_pRear(); }
};

// definitions ...

template< typename T >
void List< T >::push_front( T e ) // inserts e with type T at front of List
{
   Node< T >* n = new Node< T > ( e );
   
   n->next = pFront;
   pFront = n;

   if( pRear == NULL ) pRear = pFront;
   ++size;
   is_sorted = false;
}

template< typename T >
void List< T >::push_back( T e ) // inserts e with type T at end of List
{
    Node< T >* n = new Node< T > ( e );

    if( pFront != NULL )
    {
        pRear->next = n;
        pRear = n;
    }
    else
        pRear = pFront = n;

    ++size;
    is_sorted = false;
}

template< typename T >
void List< T >::add_at_index( int c, T e ) // inserts e with type T at index c
{
    if( c >= 0 && c < size )
    {
        if( c > 0 )
        {
            // insert at index c  ... BUT after index 0 ... i.e. at 1 to size
            Node< T >* prev = pFront;
            for( int i = 1; i < c; ++i ) prev = prev->next;

            Node< T >* n = new Node< T > ( e );
            n->data = e;

            // now insert n at index c ... A -> B  becomes A->C->B
            n->next = prev->next;  // C -> B
            prev->next = n; // A -> C
            ++ size;
            is_sorted = false;

        } // here c is 0 ... so ...
        else push_front( e ); // resets size, pFront and pRear ... as applicable
    }
    else if( c == size ) push_back( e );
    else
    {
        cout << "\nHighest new index allowed is " << size
             << ". You requested index " << c << " ... push_back y/n ? ";
        int reply = cin.get();
        cin.sync();
        if( reply == 'n' || reply =='N' )
            return;

        // if reach hear ...
        cout <<"Ok ... will push_back ...\n";
        push_back( e );  // resets size, pFront and pRear  ... as applicable
    }
}


template< typename T >
void List< T >::remove( T e )
{
    if( !size )
    {
        cout << "\nCan not remove '" << e << "' since list is empty.\n";
        return;
    }

    Node< T >* q = pFront;
    if( q->data == e ) // if at front ...
    {
        pFront = q->next;
        delete q;
        --size;
        cout<<"\n'" << e <<"' removed ...";
        if( size <= 1 ) { pRear = pFront; is_sorted = true; }
        return;
    }

    // if reach here ...  'e' is NOT the first
    Node< T >* prev = q;
    q = q->next; // q now points to 2nd node in list ...
    while( q != NULL ) // Note: also handles case of just one Node in list
    {
        if( q->data == e )
        {
            prev->next = q->next;
            delete q;
            cout<<"\n'" << e <<"' removed ...";
            --size;
            if( prev->next == NULL ) pRear = prev; // update 'rear' ...
            if( size == 1 ) is_sorted = true;
            return;
        }

        // if reach here ... advance both nodes up the list  ...
        prev = q;
        q = q->next;
    }
    cout<<"\n'" << e <<"' NOT found ...";
}

template< typename T >
void List< T >::show_all() const
{
    for( Node< T >* q = pFront; q != NULL; q = q->next )
        cout << endl << q->data;
}

template < typename T >
bool List< T >::exist( T e ) const
{
    for( Node< T >* q = pFront; q != NULL; q = q->next )
        if( q->data == e )
            return true;
    return false;
}

template < typename T >
T List< T >::max() const
{
    if( !size )
    {
        cout << "List is empty ... returning 'zero' ... ";
        return T(0);
    }
    T max = pFront->data;
    for( Node< T >* q = pFront; q->next != NULL; q = q->next )
        if( q->next->data > max )
            max = q->next->data;
    return max;
}
template < typename T >
T List< T >::min() const
{
    if( !size )
    {
        cout << "List is empty ... returning 'zero' ... ";
        return T(0);
    }
    T min = pFront->data;
    for( Node< T >* q = pFront; q->next != NULL; q = q->next )
        if( q->next->data < min )
            min = q->next->data;
    return min;
}

       

//////////////////////////////// BEGIN MERGE SORT //////////////////////////////

// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'

template < typename T >
void List< T >::merge_sort( Node< T >*& pFront, int size )
{
    if( size < 2 ) return;

    Node< T >* pHead2;
    Node< T >* pEnd1;

    int size2 = size/2;
    int size1 = size - size2;

    // split the list into two lists ... the first half begins with pHead
    pEnd1 = pFront; // first set pEnd1 to the head address ...
    for( int i=1; i<size1; ++i )
        pEnd1 = pEnd1->next;

    pHead2 = pEnd1->next; // second half begins with pHead2
    pEnd1->next = NULL; // breaking the chain here... so we can have two lists

    // merge the lists after recusively merge_sorting them
    merge_sort( pFront, size1 );
    merge_sort( pHead2, size2 );
    pFront=merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////


/////////////////////////////////// BEGIN ISORT ////////////////////////////////

// does NOT update pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::isort_insert( T e )
{
    Node< T >* n = new Node< T > ( e );
    if( size > 0 && !is_sorted ) msort();
    insert_sorted( pFront, n );
    ++size;

}

// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::insert_sorted( Node< T >*& pHead, Node< T >* pNewNode )
{
    // First handle most likely cases where new node is NOT first element ...
    if( pHead != NULL && pNewNode->data >= pHead->data )
    {
        // If here ... search the list for the right location
        Node< T >* q = pHead; // Get a working copy of pHead in q
        // Start comparing with element AFTER 'q' ... i.e. the 'next in'
        while( q->next != NULL && q->next->data <= pNewNode->data )
            q = q->next; // Traverse the list ...

        // Ok, insert after 'q' by 're-nexting' the pointers ...
        // ( Includes inserting at end position ... where q->next is NULL )

        // for A->B to become A->N->B ...
        pNewNode->next = q->next; // first insert/link ... N->B
        q->next = pNewNode; // and now link ... A->N
    }
    else // becomes the first element ...
    {
        pNewNode->next = pHead; // old pHead becomes 2nd in list
        pHead = pNewNode; // and this new node becomes the head of the list
    }
}

// insert sort a whole list ...
template < typename T >
void List< T >::isort()
{
     // Note: pNewHead MUST be NULL to start ...
    Node< T > *pTmp, *pHead = pFront, *pNewHead = NULL;

    while( pHead != NULL ) // take each node from old list and insert in new
    {
        pTmp = pHead; // get 'this' node ...
        pHead = pHead->next; // move 'start' up one, to be ready for next node
        insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
    }
    set_pFront_pRear( pNewHead );
    is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////

#endif


[David]

Backing up some ... this simple single linked list class ... a base class for a primitive set class (that works ok/fast-enough for small sets) ...

Code: [Select]

// simpleSLL_Set.cpp // 2012-01-04 //

#include <iostream>
#include <fstream>

using namespace std;


class LinkedList
{
protected:
    struct Node
    {
        int data;
        Node* link;
        Node( int d = 0 ) : data(d), link(0) {} // default ctor
    } *front, *back ;
    int len;
    friend ostream& operator << ( ostream&, const LinkedList& );
public:
    LinkedList() : front(0), back(0), len(0) {} // default ctor
    ~LinkedList() { clear(); }
    LinkedList( const LinkedList& ); // copy ctor
    LinkedList& operator = ( const LinkedList& ); // overloaded assignment
    void push_front( int e );
    void push_back( int e );
    int pop_front();
    int pop_back();
    int size() const { return len; }
    bool exists( const int& e ) const;
    void clear();
} ;

ostream& operator << ( ostream& os, const LinkedList& obj )
{
    for( LinkedList::Node* cur = obj.front; cur != 0; cur = cur->link )
        os << cur->data << " ";
    return os;
}

LinkedList::LinkedList( const LinkedList& old )
{
    for( Node* cur = old.front; cur != 0; cur = cur->link )
        push_back( cur->data );
}

LinkedList& LinkedList::operator = ( const LinkedList& old )
{
    if( this != &old )
    {
        for( Node* cur = old.front; cur != 0; cur = cur->link )
            push_back( cur->data );
    }
    return *this;
}
   
void LinkedList::push_front( int e )
{
    Node* newNode = new Node(e);
    newNode->link = front;
    front = newNode;
    if( !back ) back = front;
    ++len;
}

void LinkedList::push_back( int e )
{
    Node* newNode = new Node(e);
    if( back )
    {
        back->link = newNode;
        back = newNode;
    }
    else back = front = newNode;
    ++len;
}

int LinkedList::pop_front()
{
    int tmp = 0;
    if( front )
    {
        Node* cur = front;
        tmp = front->data;
        front = front->link;
        delete cur;
        --len;
        if( !front ) back = 0;
    }
    else cout << "\nList was empty ... so returning data value '0'\n";
    return tmp;
}

int LinkedList::pop_back()
{
    int tmp = 0;
    if( len > 1 )
    {
        Node* prev = front;
        Node* cur = front->link;
        while( cur != back )
        {
            prev = cur;
            cur = cur->link;
        }
       
        tmp = back->data; // cur->data
        prev->link = 0;
        back = prev;
        delete cur;
        --len;
    }
    else if( len == 1 )
    {
        tmp = front->data;
        delete front;
        --len;
        back = front = 0;
    }
    else cout << "\nList was empty ... so returning data value '0'\n";
    return tmp;
}

bool LinkedList::exists( const int& e ) const
{
    for( Node* cur = front; cur != 0; cur = cur->link )
        if( e == cur->data ) return true;
    // else ...
    return false;
}

void LinkedList::clear()
{
    for( Node* cur = front; cur != 0; cur = front )
    {
        front = front->link;
        delete cur;
    }
    back = 0;
    len = 0;
}


////////////////////////////////////////////////////////////////////////////////
class Set : public LinkedList
{
public:
    void insert( int e );
    Set create_union( const Set& b ) const ;
    Set create_intersection( const Set& b ) const ;
} ;

void Set::insert( int e )
{
    if( !exists( e ) ) push_back( e );
}

Set Set::create_union( const Set& b ) const
{
    Set tmp; // to hold copy of first set ...
    for( Node* cur = front; cur != 0; cur = cur->link )
        tmp.push_back( cur->data );
   
    for( Node* cur = b.front; cur != 0; cur = cur->link )
        tmp.insert( cur->data );
       
    return tmp;
}

Set Set::create_intersection( const Set& b ) const
{
    Set tmp; // to hold intersection set ...
    for( Node* cur = front; cur != 0; cur = cur->link )
        if( b.exists( cur->data ) ) tmp.push_back( cur->data );
       
    return tmp;
}
////////////////////////////////////////////////////////////////////////////////


int main()
{

    cout << "Testing the class LinkedList ...\n\n";
    LinkedList myLst;
    myLst.push_front( 5 );
    myLst.push_front( 6 );
    myLst.push_front( 7 );
   
    cout << "The list now is: " << myLst << endl;
   
    myLst.push_back( 1 );
    myLst.push_back( 2 );
    myLst.push_back( 3 );

    cout << "The list now is: " << myLst << endl;
   
    cout << "\npopping front the first 3 values: ";
    while( myLst.size() > 3 ) cout << myLst.pop_front() << " ";
   
    cout << "\npopping back the last 3 values: ";
    while( myLst.size() ) cout << myLst.pop_back() << " ";



    cout << "\n\n\nTesting the class Set ...\n\n";

    int ary[] = { 0, 1, 6, 0, 6, 1, 5, 7, 5, 1 };
    const int ary_size = sizeof ary / sizeof ary[0];
    cout << "ary is: ";
    for( int i = 0; i < ary_size; ++i ) cout<< ary[i] << " ";

    Set mySet;
    for( int i = 0; i < ary_size; ++i ) mySet.insert( ary[i] );
    cout << "\nmySet is: " << mySet;
   

    int ary2[] = { 9, 8, 7, 6, 9, 1, 7 };
    const int ary2_size = sizeof ary2 / sizeof ary2[0];
    cout << "\n\nary2 is: ";
    for( int i = 0; i < ary2_size; ++i ) cout<< ary2[i] << " ";
   
    Set mySet2;
    for( int i = 0; i < ary2_size; ++i ) mySet2.insert( ary2[i] );
    cout << "\nmySet2 is: " << mySet2;
   
   
    cout << "\n\nUnion is: " << mySet.create_union( mySet2 );
    cout << "\nIntersection is: " << mySet.create_intersection( mySet2 );
   
    cout << "\n\nPress 'Enter' to continue ... " << flush;
    cin.get();
}


Now ... as a template class ...

Code: [Select]

// template_simpleSLL_Set.cpp // 2012-01-04 //

#include <iostream>
#include <string>

using namespace std;

template< typename T >
class LinkedList
{
protected:
    struct Node
    {
        T data;
        Node* link;
        Node( T d = 0 ) : data(d), link(0) {} // default ctor
    } *front, *back ;
    int len;
public:
    LinkedList() : front(0), back(0), len(0) {} // default ctor
    ~LinkedList() { clear(); }
    LinkedList( const LinkedList< T >& ); // copy ctor
    LinkedList< T >& operator = ( const LinkedList< T >& ); // overloaded assignment
    void push_front( T e );
    void push_back( T e );
    T pop_front();
    T pop_back();
    int size() const { return len; }
    bool exists( const T& ) const;
    void clear();
    void print() const;
} ;


template< typename T >
void LinkedList< T >::print() const
{
    for( Node* cur = front; cur != 0; cur = cur->link )
        cout << cur->data << " ";
}


template< typename T >
LinkedList< T >::LinkedList( const LinkedList< T >& old )
{
    for( Node* cur = old.front; cur != 0; cur = cur->link )
        push_back( cur->data );
}

template< typename T >
LinkedList< T >& LinkedList< T >::operator = ( const LinkedList< T >& old )
{
    if( this != &old )
    {
        for( Node* cur = old.front; cur != 0; cur = cur->link )
            push_back( cur->data );
    }
    return *this;
}

template< typename T >
void LinkedList< T >::push_front( T e )
{
    Node* newNode = new Node(e);
    newNode->link = front;
    front = newNode;
    if( !back ) back = front;
    ++len;
}

template< typename T >
void LinkedList< T >::push_back( T e )
{
    Node* newNode = new Node(e);
    if( back )
    {
        back->link = newNode;
        back = newNode;
    }
    else back = front = newNode;
    ++len;
}

template< typename T >
T LinkedList< T >::pop_front()
{
    int tmp = 0;
    if( front )
    {
        Node* cur = front;
        tmp = front->data;
        front = front->link;
        delete cur;
        --len;
        if( !front ) back = front;
    }
    else cout << "\nList was empty ... so returning data value '0'\n";
    return tmp;
}

template< typename T >
T LinkedList< T >::pop_back()
{
    int tmp = 0;
    if( len > 1 )
    {
        Node* prev = front;
        Node* cur = front->link;
        while( cur != back )
        {
            prev = cur;
            cur = cur->link;
        }
       
        tmp = back->data; // cur->data
        prev->link = 0;
        back = prev;
        delete cur;
        --len;
    }
    else if( len == 1 )
    {
        tmp = front->data;
        delete front;
        --len;
        back = front = 0;
    }
    else cout << "\nList was empty ... so returning data value '0'\n";
    return tmp;
}

template< typename T >
bool LinkedList< T >::exists( const T& e ) const
{
    for( Node* cur = front; cur != 0; cur = cur->link )
        if( e == cur->data ) return true;
    // else ...
    return false;
}

template< typename T >
void LinkedList< T >::clear()
{
    for( Node* cur = front; cur != 0; cur = front )
    {
        front = front->link;
        delete cur;
    }
    back = 0;
    len = 0;
}
////////////////////////////////////////////////////////////////////////////////


template< typename T >
class Set : public LinkedList< T >
{
public:
    void insert( T e );
    Set create_union( const Set< T >& b ) const ;
    Set create_intersection( const Set< T >& b ) const ;
} ;

template< typename T >
void Set< T >::insert( T e )
{
    if( !exists( e ) ) push_back( e );
}

template< typename T >
Set< T > Set< T >::create_union( const Set< T >& b ) const
{
    Set< T > tmp; // to hold copy of first set ...
    for( typename LinkedList< T >::Node* cur = LinkedList< T >::front;
            cur != 0; cur = cur->link )
        tmp.push_back( cur->data );
   
    for( typename LinkedList< T >::Node* cur = b.front;
            cur != 0; cur = cur->link )
        tmp.insert( cur->data );
       
    return tmp;
}

template< typename T >
Set< T > Set< T >::create_intersection( const Set< T >& b ) const
{
    Set< T > tmp; // to hold intersection set ...
    for( typename LinkedList< T >::Node* cur = LinkedList< T >::front;
            cur != 0; cur = cur->link )
        if( b.exists( cur->data ) ) tmp.push_back( cur->data );
       
    return tmp;
}
////////////////////////////////////////////////////////////////////////////////


int main()
{
    cout << "Testing the template class LinkedList ...\n\n";
    LinkedList< int > myLst;
    myLst.push_front( 5 );
    myLst.push_front( 6 );
    myLst.push_front( 7 );
   
    cout << "The list now is: ";
    myLst.print();
   
    myLst.push_back( 1 );
    myLst.push_back( 2 );
    myLst.push_back( 3 );

    cout << "\nThe list now is: ";
    myLst.print();
   
    cout << "\n\npopping front the first 3 values: ";
    while( myLst.size() > 3 ) cout << myLst.pop_front() << " ";

    cout << "\npopping back the last 3 values: ";
    while( myLst.size() ) cout << myLst.pop_back() << " ";



    cout << "\n\nTesting the template class Set ...\n\n";

    string ary[] = { "0", "1", "6", "0", "6", "1", "5", "7", "5", "1" };
    const int ary_size = sizeof ary / sizeof ary[0];
    cout << "ary is: ";
    for( int i = 0; i < ary_size; ++i ) cout<< ary[i] << " ";

    Set< string > mySet;
    for( int i = 0; i < ary_size; ++i ) mySet.insert( ary[i] );
    cout << "\nmySet is: ";
    mySet.print();
   

    string ary2[] = { "9", "8", "7", "6", "9", "1", "7" };
    const int ary2_size = sizeof ary2 / sizeof ary2[0];
    cout << "\n\nary2 is: ";
    for( int i = 0; i < ary2_size; ++i ) cout<< ary2[i] << " ";
   
    Set< string > mySet2;
    for( int i = 0; i < ary2_size; ++i ) mySet2.insert( ary2[i] );
    cout << "\nmySet2 is: ";
    mySet2.print();
   
   
    cout << "\n\nUnion is: ";
    mySet.create_union( mySet2 ).print();
   
    cout << "\nIntersection is: ";
    mySet.create_intersection( mySet2 ).print();
   
    cout << "\n\nPress 'Enter' to continue ... " << flush;
    cin.get();
}


[David]

More examples of template class List ... these use nested classes of class iterator ...

1. A single linked list ... with nested class iterator ...
   (has an interesting quick-sort of a linked list, that is NOT really so quick,
    and it is only useful for NOT too long a list,
    as the stack will overflow with all the recursion,
    and the program will crash/or it will become way too slow.)

Code: [Select]

// classList1.h // 2011-12-18 //

// a template class for a single-link linked list ...

// with template functions for bsort (an array like bubble sort, swaps values)
// and a template function quicksort (a list type quick sort that moves nodes)

#ifndef CLASSLIST1_H
#define CLASSLIST1_H

#include <string> // should include this ...


////////////////////////////////////////////////////////////////////////////////
template < typename T >
class List1
{
private:
    class Node
    {
    public:
        T  value;
        Node *next;
    };
   
    Node *head, *tail;
    int len;
public:
    List1();
    ~List1();
    List1( const List1< T >& );
    List1< T >& operator = ( const List1< T >& );
    void clear();
    int size() const;

    class iterator
    {
        friend class List1< T >; // to give class List access to private ptr
    public:
        iterator& operator ++ (); // { ptr = ptr->next; return *this; }
        iterator& operator ++ ( int dummy ) { ptr = ptr->next; return *this; }
        bool operator != (const iterator & it2) const;
        T operator * () const;
        T& operator * ();
    private:
        Node* ptr;
    };

    iterator begin();
    iterator end();

    void push_front( const T& );
    void push_back( const T& );
   
    void pop_front_push_other_front( List1< T >& );
    void append_clear_other( List1< T >& );
};


////////////////////////////////////////////////////////////////////////////////
// Begin definitions of List member functions ...
////////////////////////////////////////////////////////////////////////////////

template < typename T >
List1< T >::List1() : head(0), tail(0), len(0) {} // default constructor ...

template < typename T >
List1< T >::~List1() { clear(); } // destructor ...

template < typename T > // copy constructor ...
List1< T >::List1( const List1< T >& old_list )
{
    head = tail = 0;
    len = 0;
    for( Node* n = old_list.head; n != 0; n = n->next )
        push_back( n->value );
}

template < typename T > // overloaded operator = ...
List1< T >& List1< T>::operator = ( const List1< T >& old_list )
{
    if( this != &old_list )
    {
        clear();
        for( Node* n = old_list.head; n != 0; n = n->next )
            push_back( n->value );
    }
    return *this;
}

template < typename T >
int List1< T >::size() const { return len; }

template < typename T >
void List1< T >::clear()
{
    for( Node* tmp = head; head != 0; tmp = head )
    {
        head = head->next;
        delete tmp;
    }
    tail = 0;
    len = 0;
}

// Assigns the iterator to the next Node and returns that iterator.
template < typename T >
typename List1< T >::iterator& List1 < T >::iterator::operator ++ ()
{
ptr = ptr->next;
return *this;
}

// Compares two iterators and returns true or false depending on whether
// or not ...  they are referencing the same Node.
template < typename T >
bool List1< T >::iterator::operator != (
    const typename List1< T >::iterator& it2 ) const
{
return  ptr != it2.ptr;
}

// Returns the value of the Node that the iterator is referencing.
template < typename T >
T List1< T >::iterator::operator * () const
{
    return ptr->value;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List1< T >::iterator::operator * ()
{
    return ptr->value;
}

template < typename T >
typename List1< T >::iterator List1< T >::begin()
{
    typename List1< T >::iterator it;
    it.ptr = head;
    return it;
}

template < typename T >
typename List1< T >::iterator List1< T >::end()
{
    typename List1< T >::iterator it;
    it.ptr = 0;;
    return it;
}

template < typename T >
void List1< T >::push_front( const T& val )
{
Node* n = new Node;
n->value = val;
if( head == 0 ) tail = n;
n->next = head;
head = n;

++len;
}

template < typename T >
void List1< T >::push_back( const T& val )
{
Node* n = new Node;
n->value = val;
n->next = 0;
if( head != 0 )
    {
        tail->next = n;
        tail = n;
    }
else head = tail = n;

++len;
}

/****************************************************************
*   This function removes the Node pointed to by the head pointer
*   and pushs that Node onto the front of the list that is passed
*   in as a parameter.
****************************************************************/
template < typename T >
void List1< T >::pop_front_push_other_front( List1< T >& y )
{
    if( head )
   {
      Node* tmp = head;
      head = head->next;
      y.push_front( tmp->value);
      delete tmp;
     
      --len;
      if( !len ) tail = 0;
    }
}

/****************************************************************
*   This function takes a singly linked list in as a parameter,
*   appends it to the end of the current singly linked list, sets
*   the appropriate private members, and clears the other list.
****************************************************************/
template < typename T >
void List1< T >::append_clear_other( List1< T >& y )
{
    if( head )
    {
        tail->next = y.head;
        tail = y.tail;
        len += y.len;

    }
    else
    {
        head = y.head;
        tail = y.tail;
        len = y.len;
    }
    y.head = y.tail = 0;
    y.len = 0;
}

////////////////////////////////////////////////////////////////////////////////
// End ... definitions of List member functions
////////////////////////////////////////////////////////////////////////////////



// Utility function to quick sort a List1< T > ... (uses function pointers)
// 1. needs a 'compare' function passed in ... here see ...
//    bool ( *before )( const T&, const T& ) )
// 2. also needs TWO List1 < T > member functions defined above ...
//    see example below: A.pop_front_push_other_front( pivot );
//    see example below: A.append_clear_other( pivot );
// 3. also needs List1< T > copy constructor and overloaded assignment ...
//    see example below: A = Abefore;

template < typename T >
void quicksort( List1 < T > & A, bool ( *before )( const T&, const T& ) )
{
    List1 < T > Abefore, Aafter, pivot;
    typename List1 < T >::iterator toSort, toPivot;

    // sufficent recursion end condition ... since  ...
    // prev pass took pivot and then was sorted or split into two one (or zero) node lists
    if( A.size() < 2 )  return;

    // firstly, get (and remove/save) pivot for this (recursive) pass ...
    A.pop_front_push_other_front( pivot );

    // then get pointer to pivot value
    toPivot = pivot.begin();

    // now traverse the list 'A 'from begin to end and create  ...
    // two lists ... 'Abefore' ... and ... 'Aafter' ...
    for( toSort = A.begin(); toSort != A.end(); toSort = A.begin() )
    {
        if( before( *toSort, *toPivot ) )
            A.pop_front_push_other_front( Abefore );
        else
            A.pop_front_push_other_front( Aafter );
    }

    // now recutsively quick sort these two lists ...
    quicksort( Abefore, before );
    quicksort( Aafter, before );
   
    // now reconstruct A from recursively sorted 2 pieces ...
    A = Abefore; // get 'first section' ... ( needs copy ctor and overloaded = )
    A.append_clear_other( pivot ); // add pivot back to its 'mid' place ...
    A.append_clear_other( Aafter ); // append 'last section'
}

// Utility functions to bubble sort a List1< T > ...

// Simple bubble sort ... uses a similar method as used to bubble sort an array
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort( List1<T>& a, bool ( *yourCmp )( const T&, const T& ) )
{
    // traverse list,  n-1 compares ...
    int j, new_size = a.size();
    typename List1< T >::iterator it, it2;
    T tmp;
    bool swap;
    do
    {
        swap = false;
        for(  j = 1, it2 = a.begin(); j < new_size; ++j )
        {
            it = it2;
            ++it2; // advance to next element in to compare it ...
            if( yourCmp( *it2, *it ) ) // then ... swap values at nodes
            {
                tmp = *it;
                *it = *it2;
                *it2 = tmp;
                swap = true;
            }
        }
        -- new_size;
    }
    while( swap );
}

// Simple bubble sort using a similar method as used to bubble sort an array
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort
(
    List1< T >& s,
    typename List1< T >::iterator a, typename List1< T >::iterator b,
    bool ( *yourCmp )( const T&, const T& )
)
{
    // traverse list ... n-1 compares each pass, with --n before next pass
// done if no swap ...

// first .. count the len of this sub-list to be sorted
    int j, new_size = 0;
    typename List1< T >::iterator it, it2;
    T tmp;
for( it = a; it != s.end(); ++it )
{
++new_size; // count the len of this sub-list to be sorted ...
        if( it == b ) break;
}

// now can do bubble sort ... in simple similar manner as per an array
    bool swap;
    do
    {
        swap = false; // if swap not set to true on this pass ... then done
        for(  j = 1, it2 = a; j < new_size; ++j )
        {
            it = it2;
            ++it2; // advance to next element in ... to compare it
            if( yourCmp( *it2, *it ) ) // then ... swap values at nodes
            {
                tmp = *it;
                *it = *it2;
                *it2 = tmp;
                swap = true;
            }
        }
// decrement before next pass since top element(s) already in sorted order
        -- new_size; 
    }
    while( swap );
}

#endif

A little test program for the above ...

Code: [Select]

// classList1_test.cpp // 2011-12-19 //

#include <iostream>


// a template class for a single-link linked ...
// with template functions for bsort ... (a bubble sort)
// ... call like this: bsort( yourList, ascendingCmp );
// and a template function quicksort ... (a quick sort)
// ... call like this: quicksort( yourList, ascendingCmp );
#include "classList1.h" // has include <string>


// Compare function 'ascendingCmp' handed to bsort ...
template < typename T >
bool ascendingCmp( const T& a, const T& b )
{
    return a < b;
}
template < typename T >
bool descendingCmp( const T& a, const T& b )
{
    return a > b;
}

int main( int argc, char *argv[] )
{
    using std::string;
    using std::cout;
    using std::endl;
    using std::flush;
    using std::cin;
   
    List1< string > s1;
    s1.push_back( "Hi" );
    s1.push_back( "there" );
    s1.push_back( "my" );
    s1.push_back( "friend" );
    s1.push_back( "Bob" );
    s1.push_back( "Attfield" );
    List1< string >::iterator it;
   
    cout << "After " << s1.size()
         << " calls to s1.push_back( \"cppStr\" ) ... s1 =\n";
    for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";
   
    List1< string > s2 = s1;
    cout << "\n\nAfter List< string > s2 = s1 ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); it++ ) cout << *it << " ";

    bsort( s2, ascendingCmp );
    cout << "\n\nAfter bsort( s2, ascendingCmp ) ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";

    s1 = s2;
    cout << "\n\nAfter s1 = s2 ... s1 = \n";
    for( it = s1.begin(); it != s2.end(); it++ ) cout << *it << " ";

    quicksort( s1, ascendingCmp );
    cout << "\n\nquicksort( s1, ascendingCmp ), s1 = \n";
    for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";

    quicksort( s2, descendingCmp );
    cout << "\n\nquicksort( s2, descendingCmp ), s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";

    cout << "\nPress 'Enter' to continue ... " << flush;
    cin.get();
}


[David]

2. A double linked list ... with nested class iterator ...

Code: [Select]

// classList2.h // 2012-01-04 //

// a template class for a double-link linked list...

// with template functions for bsort (an array like bubble sort, swaps values)
// and a template function qSort2 (an array like quick sort, swaps values)
// and a member function for isort (insert sort) and isort_insert

#ifndef CLASSLIST2_H
#define CLASSLIST2_H

#include <string> // should include this ...


////////////////////////////////////////////////////////////////////////////////
template < typename T >
class List
{
    struct Node; // forward declaration ...
public:
    List() : head(0), tail(0), len(0) {}
~List() { clear(); }
    List( const List< T >& ); // copy ctor ...
    List< T >& operator = ( const List< T >& ); // overloaded operator =
   
int size() const { return len; }
void clear();

    class iterator
    {
        friend class List< T >; // to give class List access to private ptr
    public:
        iterator( Node* p = 0, Node* t = 0 ) : ptr(p), ptl(t) {}
        iterator& operator ++ () { ptr = ptr->next; return *this; }
        iterator& operator ++ ( int dummy ) { ptr = ptr->next; return *this; }
        iterator& operator -- () { if( ptr == 0 ) ptr = ptl;
                                    else ptr = ptr->prev; return *this; }
        iterator& operator -- ( int dummy ) { if( ptr == 0 ) ptr = ptl;
                                    else ptr = ptr->prev; return *this; }
        bool operator != (const iterator & it2) const { return  ptr != it2.ptr; }
        bool operator == (const iterator & it2) const { return  ptr == it2.ptr; }
        T operator * () const { return ptr->value; }
        T& operator * () { return ptr->value; }
    private:
        Node* ptr; // cur
        Node* ptl; // tail
    };

    iterator begin() { iterator it( head, tail ); return it; }
    iterator end()   { iterator it( 0, tail ); return it; }

    void push_front( const T& );
    void push_back( const T& );
   
    void isort_insert( const T& e, bool ( *yourCmp )( const T&, const T& ) );
    void isort( bool ( *yourCmp )( const T&, const T& ) );
   
    bool isSorted( bool ( *yourCmp )( const T&, const T& ) );
   
private:
    void insert_sorted( typename List< T >::Node*& pHead,
                        typename List< T >::Node*& pTail,
                        typename List < T >::Node* pNewNode,
                        bool ( *yourCmp )( const T&, const T& ) );
    struct Node
    {
        T  value;
        Node* next;
        Node* prev;
    } *head, *tail ;
   
    int len;
} ;

////////////////////////////////////////////////////////////////////////////////
// begin class member definitions ...

// copy ctor
template < typename T >
List< T >::List( const List< T >& old_list )
{
    head = tail = 0;
    len = 0;
    for( Node* n = old_list.head; n != 0; n = n->next )
        push_back( n->value );
}

 // overloaded operator =
template < typename T >
List< T >& List< T>::operator = ( const List< T >& old_list )
{
    if( this != &old_list )
    {
        clear();
        for( Node* n = old_list.head; n != 0; n = n->next )
            push_back( n->value );
    }
    return *this;
}

template < typename T >
void List< T >::clear()
{
    for( Node* tmp = head; head != 0; tmp = head )
    {
        head = head->next;
        delete tmp;
    }
    tail = 0;
    len = 0;
}

template < typename T >
void List< T >::push_front( const T& val )
{
    Node* n = new Node;
    n->value = val;
    n->prev = 0;
    n->next = head;
    if( head ) head->prev = n;
    else tail = n;
    head = n;
    ++len;
}
template < typename T >
void List< T >::push_back( const T& val )
{
    Node* n = new Node;
    n->value = val;
    n->next = 0;
    n->prev = tail;
    if( head ) tail->next = n;
    else head = n;
    tail = n;
    ++len;
}

template < typename T >
bool List< T >::isSorted( bool ( *yourCmp )( const T&, const T& ) )
{
    typename List< T >::Node* i;
    typename List< T >::Node* j;
    for( j = i = head ; i != 0; i = j )
    {
        j = j->next;
        if( j && yourCmp( j->value, i->value ) ) return false;
    }
    // else ...
    return true;
}

//////////////////////////////// BEGIN ISORT's /////////////////////////////////

// call this function only if pre-sorted in appropriate order ...
template < typename T >
void List< T >::isort_insert( const T& e, bool ( *yourCmp )( const T&, const T& ) )
{
    typename List< T >::Node* n = new Node;
    n->value = e;
    insert_sorted( head, tail, n, yourCmp );
    ++len;

}

// insert a new node in a list with its node data in proper order ...
template < typename T >
void List< T >::insert_sorted( typename List < T >::Node*& pHead,
                               typename List < T >::Node*& pTail,
                               typename List < T >::Node* pNewNode,
                               bool ( *yourCmp )( const T&, const T& ) )
{
    // First handle most likely cases where new node is NOT first element ...
    if( pHead != 0 && yourCmp(pNewNode->value, pHead->value) ) // pNewNode->value >= pHead->value
    {
        // If here ... search the list for the right location
        typename List< T >::Node* q = pHead; // Get a working copy of pHead in q
        // Start comparing with element AFTER 'q' ... i.e. the 'next in'
        while( q->next != 0 &&  yourCmp(pNewNode->value, q->next->value) ) // pNewNode->value >= q->next->value
            q = q->next; // Traverse the list ...

        // Ok, insert after 'q' by 're-nexting' the pointers ...
        // ( Includes inserting at end position ... where q->next is NULL )

        // for A->B and A<-B to become A->N->B ... and ... A<-N<-B
        pNewNode->next = q->next; // first insert/link ... N->B
        pNewNode->prev = q; // then link ... A<-N
        if( q->next ) q->next->prev = pNewNode; // then link ... N<-B
        else pTail = pNewNode;
        q->next = pNewNode; // and now link ... A->N
    }
    else // becomes the first element ...
    {
        pNewNode->prev = 0;
        pNewNode->next = pHead; // old pHead becomes 2nd in list
        if( pHead ) pHead->prev = pNewNode;
        else pTail = pNewNode;
        pHead = pNewNode; // and this new node becomes the head of the list
    }
}

// insert sort a whole list ...
template < typename T >
void List< T >::isort( bool ( *yourCmp )( const T&, const T& ) )
{
     // Note: pNewHead MUST be 0 to start ...
    typename List< T >::Node *pTmp, *pHead = head, *pNewHead = 0, *pNewTail = 0;

    while( pHead != 0 ) // take each node from old list and insert in new
    {
        pTmp = pHead; // get 'this' node ...
        pHead = pHead->next; // move 'start' up one, to be ready for next node
        insert_sorted( pNewHead, pNewTail, pTmp, yourCmp ); // insert 'this' pTmp node
    }
    head = pNewHead;
    tail = pNewTail;
} ////////////////////////////// END ISORT 's //////////////////////////////////

// end of class member definitions
////////////////////////////////////////////////////////////////////////////////


// Utility function to bubble sort a List< T > ...

// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort( List<T>& a, bool ( *yourCmp )( const T&, const T& ) )
{
    // traverse list,  n-1 compares ...
    int j, new_size = a.size();
    typename List< T >::iterator it, it2;
    T tmp;
    bool swap;
    do
    {
        swap = false;
        for(  j = 1, it2 = a.begin(); j < new_size; ++j )
        {
            it = it2;
            ++it2; // advance to next element in to compare it ...
            if( yourCmp( *it2, *it ) ) // then ... swap values at nodes ...
            {
                tmp = *it;
                *it = *it2;
                *it2 = tmp;
                swap = true;
            }
        }
        -- new_size;
    }
    while( swap );
}

// simple bubble sort ... uses a similar method as used to bubble sort an array
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort( List< T >& s,
            typename List< T >::iterator a,
            typename List< T >::iterator b,
            bool ( *yourCmp )( const T&, const T& ) )
{
    // traverse list ... n-1 compares each pass, with --n before next pass
// done if no swap ...

// first .. count the len of this sub-list to be sorted
    int j, new_size = 0;
    typename List< T >::iterator it, it2 = s.end();
    T tmp;
    if( b == it2 ) --b;
for( it = a; it != it2; ++it )
{
++new_size; // count the len of this sub-list to be sorted ...
        if( it == b ) break;
}

// now can do bubble sort ... in simple similar manner as per an array ...
    bool swap;
    do
    {
        swap = false; // if swap not set to true on this pass ... then done
        for(  j = 1, it2 = a; j < new_size; ++j )
        {
            it = it2;
            ++it2; // advance to next element in ... to compare it
            if( yourCmp( *it2, *it ) ) // then ... swap values at nodes
            {
                tmp = *it;
                *it = *it2;
                *it2 = tmp;
                swap = true;
            }
        }
// decrement before next pass since top element(s) already sorted ...
        -- new_size; 
    }
    while( swap );
}


////////////////////////////////////////////////////////////////////////////////
// a simple recursive quick sort of a list ...
// patterned after ...
// a fairly efficent recursive quick sort of an array

// Note: this quick sort needs to be able to traverse the list ----> and <----
//       which implies it will only work with a double-link linked-list

template< typename T >
void qSort2It
(
    typename List< T >::iterator old_lft,
    typename List< T >::iterator old_rht,
    bool ( *myCmp )( const T&, const T& )
)
{
    typename List< T >::iterator lft = old_lft, rht = old_rht;

    int len = 1;
    while( lft != rht ) // find mid element ...
    {
        --rht;
        ++len;
        if( lft != rht ) ++lft, ++len;
    }
    T tmp, comp = *rht; // get this comp element ...
    lft = old_lft, rht = old_rht; // reset now that found above

    bool c1 = true, c2 = true;

    do
    {
        while( myCmp(*lft, comp) )  ++lft, --len; if( lft == old_rht ) c1 = false;
        while( myCmp(comp, *rht) )  --rht, --len; if( old_lft == rht ) c2 = false;
        if( len > 0 ) // if(lft <= rht) // swap ...
        {
            tmp = *lft;
            *lft = *rht;
            *rht = tmp;

            ++lft, --len;
            if( lft == old_rht ) c1 = false;

            --rht, --len;
            if( old_lft == rht ) c2 = false;
        }
    }while( len > 0 ); // while( lft <= rht );

    //if( old_lft < rht   )
    if( c2 ) qSort2It( old_lft, rht, myCmp );
    //if( lft  < old_rht )
    if( c1 ) qSort2It( lft, old_rht, myCmp );
}

// must pass in two valid iterators in correct left to right order ...
template< typename T >
void qSort2
(
    List< T >& a,
    typename List< T >::iterator old_lft,
    typename List< T >::iterator old_rht,
    bool ( *myCmp )( const T&, const T& )
)
{
    if( a.size() < 2 ) return;

    if ( old_rht == a.end() ) --old_rht;
    qSort2It( old_lft, old_rht, myCmp );
}

#endif

A little test program for the above ...

Code: [Select]

// classList2_test.cpp // 2011-12-22 // a test of classList2.h //

#include <iostream>

// a template class for a single-link linked ...
// with a template function for bsort ... (a bubble sort) ... call like this:
//      bsort( yourList, ascendingCmp );
// and a template function for bsort ... (a bubble sort) ... call like this:
//      bsort( yourList, yourList.begin(), yourList.end(),  ascendingCmp );
// and a template function qSort2 ... (a quick sort) ... call like this:
//      qSort2( yourList, yourList.begin(), yourList.end(), ascendingCmp );
// and a member function for isort ... (an insert sort) ... and isort_inserted
//      yourList.isort( isortCmp ) ... or ... yourList.isort_insert( new_obj );
#include "classList2.h" // has include <string>

#define push_x push_back
#define x "back"

// Compare function 'ascendingCmp' handed to bsort ...
template < typename T >
bool ascendingCmp( const T& a, const T& b )
{
    return a < b;
}
template < typename T >
bool descendingCmp( const T& a, const T& b )
{
    return a > b;
}
template < typename T >
bool isortCmp( const T& a, const T& b )
{
    return a >= b;
}
template < typename T >
bool isortCmpDwn( const T& a, const T& b )
{
    return a <= b;
}



int main( int argc, char *argv[] )
{
    using std::string;
    using std::cout;
    using std::endl;
    using std::flush;
    using std::cin;
   
    string test[] = { "Hi", "there", "my", "friend", "Bob", "Attfield" };
    List< string > s1;
    const int size = sizeof test / sizeof test[0];
    for( int i = 0; i < size; ++i ) s1.push_x( test[i] );
       
    List< string >::iterator it;
    cout << "After " << size
         << " calls to s1.push_" << x << "( test[i] ) ... s1 =\n";
    for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";
   
    List< string > s2 = s1;
    cout << "\n\nAfter List< string > s2 = s1 ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); it++ ) cout << *it << " ";

    s2.isort( isortCmp );
    cout << "\n\nAfter s2.isort( isortCmp ) ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
   
    s2.isort_insert( "old", isortCmp );
    cout << "\n\nAfter s2.isort_insert( \"old\", isortCmp ) ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
   
    s2.isort( isortCmpDwn );
    cout << "\n\nAfter s2.isort( isortCmpDwn ) ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
   
    s2.isort_insert( "fine", isortCmpDwn );
    cout << "\n\nAfter s2.isort_insert( \"fine\", isortCmpDwn ) ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";


    s1 = s2;
    cout << "\n\nAfter s1 = s2 ... s1 = \n";
    for( it = s1.begin(); it != s2.end(); it++ ) cout << *it << " ";

    qSort2( s1, s1.begin(), s1.end(), ascendingCmp );
    cout << "\n\nqSort2( s1, s1.begin(), s1.end(), ascendingCmp ), s1 = \n";
    for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";

    qSort2( s2, s2.begin(), s2.end(), descendingCmp );
    cout << "\n\nqSort2( s2, s2.begin(), s2.end(), descendingCmp ), s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
   
    bsort( s2, s2.begin(), s2.end(), ascendingCmp );
    cout << "\n\nAfter bsort( s2, s2.begin(), s2.end(), ascendingCmp ) ... s2 = \n";
    for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";

    cout << "\n\nPress 'Enter' to continue ... " << flush;
    cin.get();
}