Recent Posts

Pages: [1] 2 3 ... 10
1
And now back to a demo of coding and using an iterator for a binary search tree ...

Firstly the .txt data file (Name it Persons.txt), then the test .cpp file ... and then the .h file ...

Enjoy :)

Code: [Select]
19570810 101440980 Bob Lamprey NY
19270624 103980155 Pinky Fellowes OR
19470314 106100903 Oliver Kringle ND
19480105 108690448 Louie Brown KS
19641028 111180924 Alan Davies UT
19710227 112200747 Bella Napster OK
19730716 112550407 Roger Stone OR
19750716 111111111 Mary Stone OR
19570504 113070570 James Mitchell TX
19401023 113220519 Jilly Aston WY
19670607 114680858 Matt Vincent MI


Now the . cpp file ...

Code: [Select]
// test_bsTreeIterator.h.cpp //  // 2017-04-16 //


#include "bsTreeIterator.h"

#include <fstream>
#include <iomanip>
#include <sstream>
#include <string>


const char* MENU =
    "Find .............. Enter :  F lastname \n"
    "Print (tree) ...... Enter :  P lastname \n"
    "eXit .............. Enter :  X";

const char* FNAME = "Persons.txt";
/*
19570810 101440980 Bob Lamprey NY
19270624 103980155 Pinky Fellowes OR
19470314 106100903 Oliver Kringle ND
19480105 108690448 Louie Brown KS
19641028 111180924 Alan Davies UT
19710227 112200747 Bella Napster OK
19730716 112550407 Roger Stone OR
19750716 111111111 Mary Stone OR
19570504 113070570 James Mitchell TX
19401023 113220519 Jilly Aston WY
19670607 114680858 Matt Vincent MI
*/


class Person
{
public:
    // ctor... (also default ctor with default values) //
    Person( int dob=0, int ssn=0, std::string fn="", std::string ln="", std::string st="" )
        : dob(dob), ssn(ssn), fname(fn), lname(ln), state(st) {}

    // re. 'ordering rule' for 'Person' objects ...
    bool operator < ( const Person& other ) const
    {
        if( lname != other.lname )
            return lname < other.lname;
        // else are the same ... so ...
        return fname < other.fname;
    }
    // re. search on names ...
    bool operator == ( const Person& other ) const
    {
        return lname == other.lname;
    }
private:
    int dob;
    int ssn;
    std::string fname;
    std::string lname;
    std::string state;
   
    // def'n of overloaded operator << for Person objects ...
    friend std::ostream& operator << ( std::ostream& os, const Person& per )
    {
        return os << std::left << std::setw(25) << per.lname + ", " + per.fname
                  << std::right << ' ' << per.state
                  << ' ' << per.dob << ' ' << per.ssn;
    }
    // to facilitate file input //
    friend std::istream& operator >> ( std::istream& is, Person& per )
    {
        is >> per.dob >> per.ssn >> per.fname >> per.lname >> per.state;
        return is;
    }
} ;


// load into (an empty) BSTree object, all records from file with name: fname
// BUT only load up to MAX elements //
bool load( const char* fname, BSTree< Person >& bst )
{
    std::ifstream fin( fname );
    if( fin )
    {
        Person tmp;
        while( fin >> tmp )
            bst.insert( tmp );
        fin.close();
        return true;
    }

    std::cout << "\nThere was a problem opening file "
              << fname << '\n';
    return false;
}

Person extractSearchInfo( const std::string& ans )
{
    std::string dummy, lname;
    std::istringstream iss( ans );
    iss >> dummy >> lname;
    return Person( 0, 0, "", lname );
}

std::string showMenuGetChoice()
{
    std::cout << MENU << "\nEnter your choice of line :  ";
    std::string line;
    getline( std::cin, line );
    return line;
}




int main()
{
    using std::cout; using std::string;
   
    BSTree< Person > tree;
    if( load( FNAME, tree ) )
    {
        cout << "There were " << tree.size() << " people in file '"
             << FNAME << "'\n";
             
        BSTree< Person >::Iterator it;
        for( it = tree.begin(); it != tree.end(); ++ it )
        {
            cout << *it << '\n';
        }
       
        for( ; ; )
        {
            char ch = 0;
            string ans = showMenuGetChoice();
            if( ans.size() ) ch = ans[0];
            Person tmp;
            switch( ch )
            {
                case 'f' : case 'F' : /* take in search info and search and report */
                    tmp = extractSearchInfo( ans );
                    if( tree.isItem( tmp, true ) ) // 'true' to show num checks //
                        cout << "Found and data on file is: "
                             << *tree.find( tmp ) << '\n';
                    else cout << "Not found.\n";
                break;
                case 'p' : case 'P' : /* talke in top of tree info and report (from there) */
                    tmp = extractSearchInfo( ans );
                    if( tree.isItem( tmp ) )
                    {
                        cout << "Found and tree (printed in order) from there is:\n";
                        tree.print_r( tree.findNode(tmp), cout, '\n' );

                    }
                    else cout << "Not found.\n";
                break;
                case 'x' : case 'X' :
                    return 0;
                break;
                default  : cout << "'" << ch << "' is NOT a valid entry here ...\n";
            }
        }
    }
}


And finally, the .h file ...

Code: [Select]
// BSTreeIterator.h //  // revised 2017-04-16 //

// this revision was on 2017-04-15 ...
// and was to make (most all) recursive methods PRIVATE
// since these meyhods are NOT to Be called by the user. //


// Using the C++ library stack in the following (nested) class iterator  ...

#ifndef BSTREEITERATOR_H
#define BSTREEITERATOR_H

#include <iostream>
#include <stack>


////////////////////////////////////////////////////////////
//
// // USAGE example:
//
// // constuct begin ('it') and end ('end') iterators:
// BSTree< objTYPE >::Iterator it = bst.begin(), end = bst.end();
//
// // print tree via *it and ++ it  ... till reach end:
// for( ; it != end ;  ++ it ) std::cout << *it << '\n';
//
////////////////////////////////////////////////////////////


template< typename T >
class BSTree
{
    // forward declaration ...
    class TreeNode;
public:
    // default ctor...
    BSTree() : root(0), len(0) {}

    // dtor...
    ~BSTree() { clean(); }
   
    void clean()
    {
std::cout << "Please wait a bit while the tree memory is freed up ... ";
        clean_r( root );

        root = 0;
        len = 0;
    }
   
    // copy ctor ... calls the recursive private method given below...
    BSTree( const BSTree& bst )
    {
        root = 0;
        len = 0;
        BSTree_r( root, bst.root );
    }

    // overloaded asignment ... calls the same recursive private method ...
    BSTree& operator = ( const BSTree& bst )
    {
        if( this != &bst )
        {
            clean(); // Note: sets root to 0 and len to 0 //
            BSTree_r( root, bst.root );
        }
        return *this;
    }

    void insert( const T& data )
    {
        insert_r( root, data ); // calls the private resursive method below ... //
        ++ len;
    }

    // A NON recursive search method ... //
    bool isItem( const T& data, bool show_count_steps = false ) const
    {
        // Return true if data is one of the items in the binary
        // sort tree to which root points.   Return false if not.
        TreeNode* cur = root;  // For "running" down the tree ...
                                    // start at the root node
        int count = 0; // so can count 'steps' ... and report if needed. //
        for( ; ; )
        {
            if( cur == 0 ) // We've fallen off the tree without finding data.
            {
                if( show_count_steps)
                    std::cout << "Number of tests was: " << ++count << '\n';
                return false;
            }
            else if( data == cur->data ) // We've found the data.
            {
                if( show_count_steps)
                    std::cout << "Number of tests was: " << ++count << '\n';
                return true;
            }
            else if( data < cur->data )
            {
                ++ count;
                // If the data occurs, it must be in the left subtree,
                // So, advance the runner down one level to the left.
                cur = cur->left;
            }
            else
            {
                ++ count;
                // If the data occurs, it must be in the right subtree.
                // So, advance the runner down one level to the right.
                cur = cur->right;
            }
        }  // end 'loop for ever' ... until return is reached //
    }
   
    TreeNode* findNode( const T& data )
    {
        return findNode( root, data ); // calls private method //
    }
   
   
    class Iterator
    {
    private:
        TreeNode* curNode;
        std::stack< TreeNode* > stkNodes;
    public:
        Iterator() : curNode(0) {}
       
        void set_curNode( TreeNode* tn ) { curNode = tn; }
       
        Iterator( TreeNode* binTree )
        {
            TreeNode* root = binTree;

            while( root )
            {
                stkNodes.push( root );
                root = root->left;
            }

            if( stkNodes.size() > 0 )
            {
                curNode = stkNodes.top();
                stkNodes.pop();
            }
            else
                curNode = 0;
        }

        T& operator * ()             { return curNode->data; }
        const T& operator * () const { return curNode->data; }


        bool operator == (const Iterator& other) const
        {
            return curNode == other.curNode;
        }

        bool operator != (const Iterator& other) const
        {
            return curNode != other.curNode;
        }

        Iterator& operator ++ ()
        {
            if( curNode->right )
            {
                stkNodes.push( curNode->right );

                if( curNode->right->left )
                    stkNodes.push( curNode->right->left );
            }

            if( stkNodes.empty() )
            {
                curNode = 0;
                return *this;
            }

            curNode = stkNodes.top();
            stkNodes.pop();

            return *this;
        }

        // Note that since, here, we are returning ONLY a copy,
        // this version does NOT permit records to be updated. //
        Iterator operator ++ ( int )
        {
            // NOTE this cpy here, i..e the correct way to implement POST ++ //
            Iterator cpy = *this;

            if( curNode->right )
            {
                stkNodes.push( curNode->right );

                if( curNode->right->left )
                    stkNodes.push( curNode->right->left );
            }

            if( stkNodes.empty() )
            {
                curNode = 0;
                return *this;
            }

            curNode = stkNodes.top();
            stkNodes.pop();
           
            return cpy;
        }
       
    } ; // END class Iterator //
   
    Iterator begin() { return Iterator( root ); }
    Iterator end() { return Iterator( 0 ); }
   
    Iterator find( const T& data )
    {
        Iterator tmp;
        tmp.set_curNode( findNode( root, data ) ); // calls the private method def'd below ... //
        return tmp;
    }
   
   
    //TreeNode* get_root() { return root; }

    size_t size() const { return len; }

/*
    size_t countNodes_r( const TreeNode< T >* cur ) const // recursive //
    {
        if( cur == 0 ) return 0;  // The tree is empty.  It contains no nodes.
        // else

        size_t count = 1;  // Start by counting the root.
        count += countNodes_r( cur->left) ;  // Add the number of nodes in the left subtree.
        count += countNodes_r( cur->right ); // Add the number of nodes in the right subtree.
        return count;  // Return the total.
    }
    size_t countNodes() const { return countNodes_r( root ); }
*/
    int maxDepth_r( const TreeNode* cur ) const
    {
        if( cur == 0 ) return 0;
        // else
       
        /* get depth of each subtree */
        int ld = maxDepth_r( cur->left );
        int rd = maxDepth_r( cur->right );

        /* return greater of two values + 1 */
        return ( ld > rd ? ld +1 : rd +1 );
    }
    int maxDepth() const // calls above method //
    {
        return maxDepth_r( root );
    }
   
    // print in order  ... used in main here so left here in public section ... //
    void print_r( const TreeNode* root, std::ostream& os = std::cout, char end = ' ' ) const
    {
        // The items in the left subtree are printed first, followed
        // by the data in the root node, followed by the items in
        // the right subtree.
        if( root == 0 )  return;         // there's nothing to print //

        print_r( root->left, os, end );  // Print items in left subtree.
        os << root->data << end;         // Print the root data.
        print_r( root->right, os, end ); // Print items in right subtree.
    }

    // print in order //
    void print( std::ostream& os = std::cout, char end = ' ' ) const
    {
        print_r( root, os, end );
    }
    void preorderPrint( std::ostream& os = std::cout, char end = ' ' ) const
    {
        preorderPrint_r( root, os, end );
    }
    void postorderPrint( std::ostream& os = std::cout, char end = ' ' ) const
    {
        postorderPrint_r( root, os, end );
    }

private:
    struct TreeNode
    {
        T data;           // The data in this node.
        TreeNode* left;   // Pointer to the left subtree.
        TreeNode* right;  // Pointer to the right subtree.
       
        // ctor...
        TreeNode( T data ) : data(data), left(0), right(0) {}
/*
        friend std::ostream& operator << ( std::ostream& os, const TreeNode& tn )
        {
            return os << tn.data;
        }
*/
    } ;

    TreeNode* root;
    size_t len;
   
    void clean_r( TreeNode* root )
    {
        if( root == 0 ) return;

        clean_r( root->left  );
        clean_r( root->right );
        delete root;
    }
   
    // Note ...traversing the passed in const bst in pre-order

    // Note that this recusive method is also called by
    // the overloaded assignment nelow //
    void BSTree_r( TreeNode*& nroot, const TreeNode* bstroot  )
    {
        if( ! bstroot ) return; // there's nothing to insert //

        insert( bstroot->data );           // insert the root data
        BSTree_r( nroot, bstroot->left );  // ...items in left subtree
        BSTree_r( nroot, bstroot->right ); // ... items in right subtree
    }
   
    // recursive method //
    void insert_r( TreeNode*& root, const T& data )
    {
        // Note that root is passed by reference since its value
        // can change in the case where the tree is empty.
        if( ! root )
        {
            // The tree is empty. Set root to point to a new node containing
            // the new data. This becomes the only node in the tree.

            root = new TreeNode( data );

            // NOTE: The left and right subtrees of root
            // are automatically set to 0 by the constructor.
            // This is important! !!! //

            return;
        }
        if( data < root->data )
            insert_r( root->left, data );
        else
            insert_r( root->right, data );
    }

    // A NON-recursive find ...
    // BUT!!! do NOT CHANGE, via this pointer,
    // the 'key' field(s) in the Mode !!! //
    TreeNode* findNode( TreeNode* cur, const T& data )
{
while( cur )
{
            if( data == cur->data )
                return cur;
if( data < cur->data )
cur = cur->left;
else
cur = cur->right;
}
return 0; // NOT found ... //
     }
     
    void preorderPrint_r( const TreeNode* root, std::ostream& os, char end ) const
    {
        if( root == 0 ) return;

        os << root->data << end; // Print the root data.
        preorderPrint_r( root->left, os, end );  // Print items in left subtree.
        preorderPrint_r( root->right ); // Print items in right subtree.
    }
    void postorderPrint_r( const TreeNode* root, std::ostream& os, char end ) const
    {
        if( root == 0 ) return;

        postorderPrint_r( root->left );  // Print items in left subtree.
        postorderPrint_r( root->right ); // Print items in right subtree.
        os << root->data << end;  // Print the root data.
    }
   
} ;

 #endif
2
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 11, 2017, 06:59:04 AM »
Here in step 6, we add iterators ... and separate out our Vector class into its own .h file with suitable guards ...


So, firstly, a little test program ...

Code: [Select]
// Vector_6_iterators.cpp //  // 2017-03-10 //


// Here, in step 6, we add iterators ...
// Also, we separate out our class Vector into its own .h file
// with suitable guards //


#include "Vector.h" // includes <iostream>



// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;
    typename Vector< T >::const_iterator it;
    for( it = v.begin(); it != v.end(); ++ it )
        cout << *it << ' ';
       
    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}



int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.reserve(10);
    print( v );
   
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    v.shrink();
    cout << "After v.reserve(10) and 3 push_backs and calling v.shrink() ...\n";
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.resize(10);
    w.push_back( 9 );
    cout << "After calling w.resize(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
   
    w.swap(v);
    cout << "After calling w.swap(v) ... print( w ) is ...\n";
    print( w );
    cout << "And print( v ) is ...\n";
    print( v );
}


And now, the file Vector.h needed above ...

Code: [Select]
// Vector.h //  // 2017-03-10 //

#ifndef VECTOR_2017_03_10_H
#define VECTOR_2017_03_10_H


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );

    void swap( Vector& );
    void shrink();


    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }

    size_t size() const { return len; }
    size_t capacity() const { return cap; }
   
    typedef T* iterator;
    iterator begin() { return ary; }
    iterator end() { return ary+len; }

    typedef const T* const_iterator;
    const_iterator begin() const { return ary; }
    const_iterator end() const { return ary+len; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}

template < typename T >
void Vector< T >::swap( Vector& vec )
{
    T* aryTmp  = vec.ary; // save start address
    size_t lenTmp = vec.len;
    size_t capTmp = vec.cap;

    vec.ary = ary;
    vec.len = len;
    vec.cap = cap;

    ary = aryTmp;
    len = lenTmp;
    cap = capTmp;
}

template < typename T >
void Vector< T >::shrink()
{
    if( len < cap )
    {
        T* tmp = new T[ len ]; // get 'right-sized' memory //
        for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i];
        delete [] ary; // now can delete old memory //
        ary = tmp; // update with the address of the new memory //
        cap = len;
    }
}

#endif


Also ... to get hints about how to add these methods

push
pop
back
empty

You can look here ...

class Vector ... and Stacks and Queues ...

http://developers-heaven.net/forum/index.php/topic,2622.0.html
3
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 11, 2017, 06:43:54 AM »
Step 5 ... (again, please see comments in program ... and at the top ...)


Code: [Select]
// Vector_5_shrink_swap.cpp //  // 2017-03-10 //


// Here, in step 5, we add methods shrink and swap //


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );
   
    void swap( Vector& vec );
    void shrink();

    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }


    size_t size() const { return len; }
    size_t capacity() const { return cap; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}

template< typename T >
void Vector< T >::swap( Vector& vec )
{
    T* aryTmp  = vec.ary; // save start address
    size_t lenTmp = vec.len;
    size_t capTmp = vec.cap;

    vec.ary = ary;
    vec.len = len;
    vec.cap = cap;

    ary = aryTmp;
    len = lenTmp;
    cap = capTmp;
}

template< typename T >
void Vector< T >::shrink()
{
    if( len < cap )
    {
        T* tmp = new T[ len ]; // get 'right-sized' memory //
        for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i];
        delete [] ary; // now can delete old memory //
        ary = tmp; // update with the address of the new memory //
        cap = len;
    }
}


// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;
   
    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';

    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}




int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.reserve(10);
    print( v );
   
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    v.shrink();
    cout << "After v.reserve(10) and 3 push_backs and calling v.shrink() ...\n";
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.resize(10);
    w.push_back( 9 );
    cout << "After calling w.resize(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
   
    w.swap(v);
    cout << "After calling w.swap(v) ... print( w ) is ...\n";
    print( w );
    cout << "And print( v ) is ...\n";
    print( v );
}
4
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:12:34 AM »
In step 4 ... (again please see comments at top of program)


Code: [Select]
// Vector_step4.cpp //  // 2017-03-10 //


// Here, in step 4, we add methods reserve and resize


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );

    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }


    size_t size() const { return len; }
    size_t capacity() const { return cap; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}




// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;
   
    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}



int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.reserve(10);
    w.push_back( 9 );
    cout << "After calling w.reserve(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
}


A test to check-out a specific case of resize method ...


Code: [Select]
// Vector_4_test_resize.cpp //  // 2017-03-10 //


// Here, in step 4, we add specific test of resize //


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );

    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }


    size_t size() const { return len; }
    size_t capacity() const { return cap; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}




// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;

    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';

    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}




int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.resize(10);
    print( v );
   
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.reserve(10);
    w.push_back( 9 );
    cout << "After calling w.reserve(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
}
5
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:10:04 AM »
In step 3 ... (again, please see comments at top of program)


Code: [Select]
// Vector_step3.cpp //  // 2017-03-10  //


// Here, in step 3, we do simple and fairly straight-foward
// update to a template class //



#include <iostream>

using namespace std;

const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
    size_t len;
    size_t cap;
    T* ary;
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}
   
    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }
   
    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }
   
    // destructor //
    ~Vector() { clear(); }
   
    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }
   
    void push_back( const T& val );
    void enlarge();
   
    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //
   
    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }
   
    size_t size() const { return len; }
    size_t capacity() const { return cap; }
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}
template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;
   
    T* tmp = new int[cap]; // get enlarged memory //
   
    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //
   
    delete [] ary; // delete OLD array memory //
   
    ary = tmp; // update ary pointer to point to new memory //
}


// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}



int main()
{
    Vector< int > v, w;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
}
6
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:07:43 AM »
In step 2 we ... (please see comments in program at top)


Code: [Select]
// Vector_step2.cpp //  // 2017-03-09 //


// Here, in step 2,
// we add "BIG THREE" needed when you use new memory
// 1) destructor ... (that calls a clear method)
// and 2) copy ctor
// and 3) overloaded assignment //


#include <iostream>

using namespace std;

const unsigned INIT_CAP = 2;

struct Vector
{
    size_t len;
    size_t cap;
    int* ary;
   
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}
   
    // copy ctor ...
    Vector( const Vector& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }
   
    // overloaded assignment ...
    Vector& operator = ( const Vector& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }
   
    // destructor //
    ~Vector() { clear(); }
   
    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }
   
    void push_back( int val );
    void enlarge();
   
    int operator [] ( size_t i ) const { return ary[i]; }
   
    // so can set new values in vector //
    int& operator [] ( size_t i ) { return ary[i]; }
} ;


// definitions //

void Vector::push_back( int val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

void Vector::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;
   
    int* tmp = new int[cap]; // get enlarged memory //
   
    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //
   
    delete [] ary; // delete OLD array memory //
   
    ary = tmp; // update ary pointer to point to new memory //
}




// a little test ... //
void print( const Vector& v )
{
    for( size_t i = 0; i < v.len; ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe len = " << v.len
         << ", the cap = " << v.cap << '\n';
}


int main()
{
    Vector v, w;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
   
   
}
7
C/C++ & Visual C++ / Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:05:50 AM »
Here is one more attempt, to demystify for beginning C++ students,  the steps to coding a simple Vector class ...



The first step will be just a Vector of int ...using a struct ... so all members are public by default.

Code: [Select]
// Vector_step1.cpp //  // 2017-03-09 //


#include <iostream>

using namespace std;

const unsigned INIT_CAP = 2;

struct Vector
{
    size_t len;
    size_t cap;
    int* ary;
   
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}
   
    void push_back( int val );
    void enlarge();
   
    int operator [] ( size_t i ) const { return ary[i]; }
   
    // so can set new values in the vector //
    int& operator [] ( size_t i ) { return ary[i]; }
} ;


// definitions //

void Vector::push_back( int val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

void Vector::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;
   
    int* tmp = new int[cap]; // get enlarged memory //
   
    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //
   
    delete [] ary; // delete OLD aray memory //
   
    ary = tmp; // update ary pointer to point to new memory //
}




// a little test ... //
void print( const Vector& v )
{
    for( size_t i = 0; i < v.len; ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe len = " << v.len
         << ", the cap = " << v.cap << '\n';
}


int main()
{
    Vector v;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
}
8
An observation to NOTE about sorting a container that already is mostly sorted ... note the following very quick ways to sort it then ...


Code: [Select]
// DDLsorts.h //  // 2017-02-13 //

#ifndef DDLSORTS_H
#define DDLSORTS_H

#include <iostream>

template < typename T >
class List
{
    struct Node
    {
        T data;
        Node* prev;
        Node* next;

        Node( const T& data = T() ) : data(data), prev(0), next(0) {}
    } ;

    Node* head;
    Node* tail;
    size_t len;

public:
    // ctor...
    List() : head(0), tail(0), len(0) {}
   
    //dtor...
    ~List() { clear(); }
   
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        len = 0;
    }

    // copy ctor...
    List ( const List& other )
    {
        head = tail = 0;
        len = 0;
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }

    // for ... def'n of overloaded (assignment) operator =
    // see def'n below //
    List& operator = ( const List& other ) ;
    /*
    {
        if( this != &other )
        {
            clear();
            for( Node* cur = other.head; cur != 0; cur = cur->next )
                push_back( cur->data );
        }
        return *this;
    }
    */
   
    size_t size() const { return len; }

    void push_front( const T& data )
    {
        Node* nNode = new Node( data );

        if( len )
        {
            nNode->next = head; // N->A
            head->prev = nNode; // N<-A
            head = nNode;
        }
        else tail = head = nNode;
        ++len;
    }


    void push_back( const T& data )
    {
        Node* nNode = new Node( data );

        if( len )
        {
            tail->next = nNode; // B->N
            nNode->prev = tail; // B<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++len;
    }

    void insert_sorted( const T& data )
    {
        Node* nNode = new Node( data );

        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }

        ++ len;
    }

    // a re-link method ... might be faster? for LARGE data records ? //
    void insert_sorted( Node* nNode )
    {
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= nNode->data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= nNode->data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                nNode->next = 0;
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            nNode->prev = 0;
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else { nNode->next= 0 ; tail = head = nNode; }
        }

        ++ len;
    }
   
    // Note! This method, (moving and re-linking Nodes),
    // is MUCH slower than that below, for small (int) data records tested //
    void relink_insert_sort()
    {
        if( len > 1 ) // then head and cur != 0 //
        {
            Node* cur = head;
            Node* next = cur->next;
            head = tail = 0;
            len = 0;
            for( ; ; next = cur->next )
            {
                insert_sorted( cur );
                cur = next;
                if( !cur ) break;
            }
        }
    }
   
    void insert_sort()
    {
        if( len > 1 )
        {
            Node* cur = head->next;

            for( ; cur != 0; cur = cur->next ) /* start with set of just the first 2 elements (if exists) */
            {
                T cmp = cur->data; /* get copy of this new cmp element on each outer loop ... */
                Node* prev = cur->prev; /* get Node of element just to the left of the above 'cmp' to start comparisons */
                while( prev != 0 && cmp < prev->data )
                {
                    prev->next->data = prev->data; /* copy element 'up' ... */
                    prev = prev->prev; /* decrement j in preparation for next inner loop ... */
                }
                /* insert element at prev->next (since prev was 'decremented' above) */
                if( prev ) prev->next->data = cmp;
                else head->data = cmp;
            }
        }
    }
   
    void select_sort()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }
           
            if( cur != min ) // swap min and cur //
            {
                T tmp = cur->data;
                cur->data = min->data;
                min->data = tmp;
            }
           
            cur = cur->next;
        }
    }
   
    void select_sort_simpler()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }

            T tmp = cur->data;
            cur->data = min->data;
            min->data = tmp;

            cur = cur->next;
        }
    }
   
    void bubble_sort()
    {
        if( len > 1 )
        {
            Node* end = 0;
            Node* cur = head->next; // start 1 element in //
            bool swap;
            bool pass = false;
            do
            {
                swap = false;
                while( cur != end )
                {
                    if( cur->data < cur->prev->data ) // swap //
                    {
                        T tmp = cur->data;
                        cur->data = cur->prev->data;
                        cur->prev->data = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
               
                if( pass ) end = end->prev;
                else end = tail;
               
                pass = true;
               
                if( !end ) break;
               
                cur = head->next; // get ready ready for next outer (do) loop //
            }
            while( swap );
        }
    }
   
   
   
    void print( std::ostream& os = std::cout ) const
    {
        Node* cur = head;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->next;
        }
    }

    void printReversed( std::ostream& os = std::cout ) const
    {
        Node* cur = tail;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->prev;
        }
    }
   
    bool isSorted() const
    {
        if( len > 1 )
        {
            Node* cur = head;
            while( cur->next )
            {
                if( cur->next->data < cur->data ) return false;
                cur = cur->next;
            }
        }
        return true;
    }
   
} ;



// def'n of overloaded (assignment) operator =
template< typename T >
List< T >& List< T >::operator = ( const List& other )
{
    if( this != &other )
    {
        clear();
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }
    return *this;
}
   

#endif


Now the test program for the above DLLsorts.h code ...

Code: [Select]
// test_DLLSorts.h.cpp //  // 2017-02-13 //
 

#include "DLLsorts.h"

// include <iostream> // included above //
#include <string>




int main()
{
    using std::string;
    using std::cout;
    using std::cin;
   
    List < string > myLst;

    cout << "Now testing push_front: ";
    myLst.push_front( "Sam" );
    myLst.push_front( "Anne" );
    myLst.push_front( "Joe" );
    myLst.push_front( "Zak" );
   
    List< string > myLstCpy( myLst ); // construct a (backup) copy //
   
    myLst.print();
   
    cout << "\nPrinting after relink_insert_sort: ";
    myLst.relink_insert_sort();
    myLst.print();
   
    cout << "\nPrinting reversed: ";
    myLst.printReversed();
   
    myLst.clear();
   
   
    cout << "\n\nNow testing push_back: ";

    myLst.push_back( "Sam" );
    myLst.push_back( "Anne" );
    myLst.push_back( "Joe" );
    myLst.push_back( "Zak" );

    myLst.print();

    cout << "\nPrinting after insert_sort: ";
    myLst.insert_sort();
    myLst.print();

    cout << "\nPrinting reversed: ";
    myLst.printReversed();

    myLst.clear();
   

    cout << "\n\nNow testing insert_sorted: ";
    myLst.insert_sorted( "Billy" );
    myLst.insert_sorted( "Sam" );
    myLst.insert_sorted( "Joe" );
    myLst.insert_sorted( "Anne" );
    myLst.insert_sorted( "Jill" );
    myLst.insert_sorted( "Zak" );
   

    myLst.print();

    cout << "\nPrinting reversed: ";
    myLst.printReversed();
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before select_sort: ";
    myLst.print();

    cout << "\nPrinting after select_sort: ";
    myLst.select_sort();
    myLst.print();
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before select_sort_simpler: ";
    myLst.print();

    cout << "\nPrinting after select_sort_simpler: ";
    myLst.select_sort_simpler();
    myLst.print();
   
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before bubble_sort: ";
    myLst.print();

    cout << "\nPrinting after bubble_sort: ";
    myLst.bubble_sort();
    myLst.print();
   
   
   
    cout << "\n\nPress 'Enter' to continue/exit ...";
    cin.get();
}


And the timed sorts version ...

Code: [Select]
// timed_DLLsorts.cpp //  // 2017-02-13 //
 

#include "DLLsorts.h"

// include <iostream> // included above //

#include <string>
#include <sstream> // re. stringstream
#include <cstdlib> // re, rand, srand
#include <ctime> // re, time clock


const int MAX_SIZE = 30000;


template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg << std::flush;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flasgs
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}

char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}

bool more( const std::string& text = "" )
{
    char reply = takeInChr( "More " + text + "(y/n) ? " );
    if( reply == 'n' || reply == 'N' )
return false;
    // else ...
    return true;
}


void fillUpList( List< int >& lst, int num )
{
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}




int main()
{
    using std::cout; using std::cin;
    using std::string; using std::stringstream;
   
    srand( time(0) ); // seed the random generator //
   
    do
    {
        int num = 0;
        for( ; ; )
        {
            stringstream ss;
            ss << MAX_SIZE;
            num = takeIn< int >( "How many numbers to sort (10000.." + ss.str() + "): " );
            if( num >= 10000 && num <= MAX_SIZE ) break;
            //else ///
            cout << "\nTry again with a value in range 10000.." << MAX_SIZE << " ...\n\n";
        }
       
        List< int > lst;
        fillUpList( lst, num );
       
        List< int > lstCpy( lst ); // save a (backup) copy //
       
       
        double t1 = clock();
        lst.insert_sort();
        double t2 = clock();
        cout << "\nTime to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.insert_sort();
        t2 = clock();
        cout << "Time to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             


        lst = lstCpy;
        t1 = clock();
        lst.relink_insert_sort();
        t2 = clock();
        cout << "\n\nTime to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.relink_insert_sort();
        t2 = clock();
        cout << "Time to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
             
        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.select_sort();
        t2 = clock();
        cout << "\n\nTime to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.select_sort();
        t2 = clock();
        cout << "Time to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             

        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.select_sort_simpler();
        t2 = clock();
        cout << "\n\nTime to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.select_sort_simpler();
        t2 = clock();
        cout << "Time to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
             
        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.bubble_sort();
        t2 = clock();
        cout << "\n\nTime to bubble_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.bubble_sort();
        t2 = clock();
        cout << "Time to bubble sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );


        cout << "\n\n";
    }
    while( more() );


}
9
This next test program is similar to the above, but it is menu driven ...

(Note that it uses the same DLL .h file as was used/provided above.)


Code: [Select]
// 6sorts_timed_all_menu_version.cpp //  // revised: 2016-05-05 //
 

#include "DLLinsertSorted.h"

// include <iostream> // included above //

#include <string>
#include <sstream> // re. istringstream
#include <cstdlib> // re, rand, srand
#include <ctime>   // re, time clock
#include <climits> // re. RAND_MAX
#include <cctype>  // re. tolower
#include <cmath>   // re. log

#include <list>    // to compare c++ library 'list sort' times with 'list sort' times //


const int MAX_PRINT = 5;
const int MAX_NxN = 20000;
const int MAX = 2000000;

const std::string MENU =
    "1) Insert sort\n"
    "2) Insert sorted\n"
    "3) Select sort\n"
    "4) Bubble sort\n"
    "5) Merge sort\n"
    "6) C++ list sort\n"
    "0) Exit program\n"
    "Your choice 0..6 ";


// 2 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flags
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}
char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}



// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
    std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}

template < typename T >
std::ostream& operator << ( std::ostream& os, const List< T >& lst )
{
    typename List< T >::const_iterator it;
    for( it = lst.begin(); it != lst.end(); ++ it ) os << *it << ' ';
    return os;
}


char showMenuGetChoice()
{
    return takeInChr( MENU );
}


int main()
{
    using std::cout; using std::cin;
    using std::string; using std::istringstream;
   
    srand( time(0) ); // seed the random generator //
   
    for( ; ; )
    {
        int num = 0;

        List< int > lst, lstCpy;
        List< int >::const_iterator cit;
       
        std::list< int > cppLst; // to compare times //
       
        double dt, t1, k;
       
        char choice = showMenuGetChoice();
        if( choice == '0' )
            break;
           
        int max_size = MAX;
        if( '1' <= choice && choice <= '4' )
            max_size = MAX_NxN;
           
        if( '1' <= choice && choice <= '6' )
        {
            // form prompt ...
            std::ostringstream oss;
            oss << "How many numbers to sort (3.." << max_size << ") : ";

            for( ; ; )
            {
                cout << "To see numbers printed, choose a number <= " << MAX_PRINT << '\n';
                num = takeIn< int >( oss.str() );
                if( num >= 3 && num <= max_size )
                    break;
                // else ...
                cout << "\nTry again with a value in range 3.." << max_size << " ...\n\n";
            }

            fillUpList( lstCpy, num );
        }
       
        switch( choice )
        {
            case '1':
                lst = lstCpy; // get from a copy //
                t1 = clock();
                lst.insert_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                // t = k*n*n;
                // k = t/n/n
                k = dt/num/num;

                lst = lstCpy;
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //

                t1 = clock();
                lst.insert_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '2':
                lst.clear();
                t1 = clock();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.insert_sorted( *cit );
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sorted was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.insert_sorted( *cit );
                for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
                    lst.insert_sorted( *cit );
                // Now size is doubled //

                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to insert_sorted was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '3':
                lst = lstCpy; // restore from copy //
                t1 = clock();
                lst.select_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to select_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.select_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to select_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '4':
                lst = lstCpy; // restore from copy //
                t1 = clock();
                lst.bubble_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to bubble_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.bubble_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to bubble_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '5':
                lst = lstCpy; // restore from copy //
                if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
                t1 = clock();
                lst.merge_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to merge_sort was " << dt<< " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                // t = k*n*log(n)
                // k = t/n/og(n)

                k = dt/num/log(num);

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.merge_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to merge_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << k*2*num*log(2*num) << '\n';
            break;
               
            case '6':
                // compare with C++ library list ...
                cppLst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                t1 = clock();
                cppLst.sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nC++ library list sort was " << dt << " seconds.";


                k = dt/num/log(num);

                cppLst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                cppLst.sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nC++ library list sort was " << dt << " seconds.";
                cout << " Expected: " << k*2*num*log(2*num) << '\n';
            break;
           
            default: cout << "choice '" << choice << "' is NOT implemented here ...\n";
           
        } // end switch //
       
        if( num <= MAX_PRINT )
        {
            if( '1' <= choice && choice <= '5' )
            {
                cout << "\nSorted  : " << lst << "\nReversed: ";
                lst.printReversed();
            }
            else if( choice == '6' )
            {
                cout << "\nSorted  : ";
                std::list< int >::const_iterator ccit;
                for( ccit = cppLst.begin(); ccit != cppLst.end(); ++ ccit  )
                    cout << *ccit << ' ';

                cout << "\nReversed: ";
                std::list< int >::const_reverse_iterator rit;
                for( rit = cppLst.rbegin(); rit != cppLst.rend(); ++ rit  )
                    cout << *rit << ' ';
            }
        }
       
        cout << '\n';
       
    } // end while //
}

10
Now a timed test program so that you can easily compare sorting times ...


Code: [Select]
// 6sorts_timed_all_auto_version.cpp //  // revised: 2017-02-13 //
 

#include "DLLinsertSorted.h"

// include <iostream> // included above //

#include <string>
#include <cstdlib>  // re, rand, srand
#include <ctime>    // re, time clock
#include <climits>  // re. RAND_MAX
#include <cctype>   // re. tolower
#include <cmath>    // re. log

#include <list>     // to compare c++ library 'list sort' times with 'list sort' times //


const int MAX_PRINT = 11;
const int MAX_NxN = 30000;


// 3 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flasgs
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}
char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}
bool more( const std::string& text = "" )
{
    char reply = takeInChr( "More " + text + "(y/n) ? " );
    if( reply == 'n' || reply == 'N' )
return false;
    // else ...
    return true;
}


// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
    std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}

template < typename T >
std::ostream& operator << ( std::ostream& os, const List< T >& lst )
{
    typename List< T >::const_iterator it;
    for( it = lst.begin(); it != lst.end(); ++ it ) os << *it << ' ';
    return os;
}




int main()
{
    using std::cout; using std::cin;
    using std::string;
   
    srand( time(0) ); // seed the random generator //
   
    do
    {
        int num = 0;
        for( ; ; )
        {
            num = takeIn< int >( "How many numbers to sort (10..2000000): " );
            if( num >= 10 && num <= 2000000 ) break;
            //else ///
            cout << "\nTry again with a value in range 10..2000000 ...\n\n";
        }
       
        List< int > lstCpy;
        fillUpList( lstCpy, num );
       
        List< int > lst;
        List< int >::const_iterator cit;
        double dt, t1, k;

        if( num <= MAX_NxN )
        {
            lst = lstCpy; // get from a copy //
            t1 = clock();
            lst.insert_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to insert_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
           
            // t = k*n*n;
            // k = t/n/n
            k = dt/num/num;
           
            lst = lstCpy;
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.push_back( *cit );
            // Now size is doubled //
           
            t1 = clock();
            lst.insert_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to insert_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';
                 

             

            lst.clear();
            t1 = clock();
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.insert_sorted( *cit );
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to insert_sorted was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                 
            k = dt/num/num;

            lst.clear();
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.insert_sorted( *cit );
            for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
                lst.insert_sorted( *cit );
            // Now size is doubled //
     
            dt = (clock() - t1)/CLOCKS_PER_SEC;
           
            cout << "\nTime to insert_sorted was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';

                 
                 
                 
                 
            lst = lstCpy; // restore from copy //
            t1 = clock();
            lst.select_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to select_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                 
            k = dt/num/num;

            lst = lstCpy; // restore from copy //
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.push_back( *cit );
            // Now size is doubled //
            t1 = clock();
            lst.select_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
           
            cout << "\nTime to select_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';



            lst = lstCpy; // restore from copy //
            t1 = clock();
            lst.bubble_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to bubble_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                 
            k = dt/num/num;

            lst = lstCpy; // restore from copy //
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.push_back( *cit );
            // Now size is doubled //
            t1 = clock();
            lst.bubble_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;

            cout << "\nTime to bubble_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';
         }
             



        lst = lstCpy; // restore from copy //
        if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
        t1 = clock();
        lst.merge_sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;
        cout << "\nTime to merge_sort was " << dt<< " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        if( num <= MAX_PRINT )
        {
            cout << "\nSorted  : " << lst << "\nReversed: ";
            lst.printReversed();
            cout << '\n';
        }
       
        // t = k*n*log(n)
        // k = t/n*/log(n)
       
        k = dt/num/log(num);

        lst = lstCpy; // restore from copy //
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            lst.push_back( *cit );
        // Now size is doubled //
        t1 = clock();
        lst.merge_sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;

        cout << "\nTime to merge_sort was " << dt << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
        cout << " Expected: " << k*2*num*log(2*num) << '\n';



             
        // compare with C++ library list ...
        std::list< int > cppLst;
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            cppLst.push_back( *cit );
        t1 = clock();
        cppLst.sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;
        cout << "\nC++ library list sort was " << dt << " seconds.";
       
       
        k = dt/num/log(num);

        cppLst.clear();
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            cppLst.push_back( *cit );
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            cppLst.push_back( *cit );
        // Now size is doubled //
        t1 = clock();
        cppLst.sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;

        cout << "\nC++ library list sort was " << dt << " seconds.";
        cout << " Expected: " << k*2*num*log(2*num) << '\n';
       

        cout << '\n';
    }
    while( more() );
}
Pages: [1] 2 3 ... 10