template class Vector ... with merge sort, insert sort, find, erase ...

[David]

Here is a C++ template class Vector example ... similar to the Cvec example in C at this next link:
http://developers-heaven.net/forum/index.php/topic,2473.msg2740.html#msg2740

It demos push_back, enlarge, reserve, merge sort, insertion sort, find, erase ... since these are fairly common student requests.  It also demonstrates friend functions that overload operators << and >> ... so you can use these to output and input Vector objects.

First the template class Vector file ... followed then by a test program.

Code: [Select]

// vector.h // // this version 2011-03-27 //

// with merge sort and insertion sort ...

                           
#ifndef dwVECTOR_H
#define dwVECTOR_H


/* can re-set this to minimize copying and getting new memory using push_back */
#ifndef VEC_CHUNK_SIZE
#define VEC_CHUNK_SIZE 8
#endif


template < typename T >
class Vector
{
public:
    Vector();
    ~Vector() { clear(); }
    void push_back( T );
    void reserve( int );
    void shrink( int );
    void clear();
    T& operator [] (int i) { return ary[i]; }
    const T& operator [] (int i) const { return ary[i]; }
    int get_size() const { return size; }
    int get_cap() const { return cap; }
    bool get_isSorted() const { return isSorted; }
    bool isSortedUp() const;
    int find( T ) const; // returns index if T value present ... else -1
    void erase( int ); // if int index valid, erases element there
    void msort();
    void isort();
private:
    int cap; // capacity
    int size;
    bool isSorted;
    T* ary;
   
    void enlarge(); // used by push_back
   
    void merge( int, int, int, Vector< T >& ); // used by msort ...
    void my_msort( int, int, Vector< T >& );
};

template < typename T >
Vector<T>::Vector() : cap(0), size(0), isSorted(true), ary(0) {}

template < typename T >
void Vector<T>::push_back( T e )
{
    if( size == cap ) enlarge();
    /* now add in new Rec ... */
    ary[size] = e;
   
    ++ size;
    isSorted = false;
}

// new array to hold 2x's records ... copies old to new
template < typename T >
void Vector<T>::enlarge()
{
    if( cap ) cap += cap; // double capacity ...
    else cap = VEC_CHUNK_SIZE; // set initial capacity
    T* tmp = new T[ cap ];
    for( int i = size-1; i >= 0; --i ) tmp[i] = ary[i];
    //for( int i = cap-1; i >= size; --i ) tmp[i] = 0;
    delete [] ary;
    ary = tmp; // update the base address of ary
}

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

template < typename T >
void Vector<T>::shrink( int newSize )
{
    if( newSize < size && newSize >= 0 ) size = newSize; // leave cap unchanged
    if( size < 2 ) isSorted = true;
}

template < typename T >
void Vector<T>::clear()
{
    if( ary != 0 )
    {
        delete [] ary;
        cap = size = 0;
        ary = 0;
        isSorted = true;
    }
}

template < typename T >
int Vector<T>::find( T value ) const // returns index if present ... else -1
{
    for( int i = 0; i < size; ++i )
        if( ary[i] == value ) return i;
    // else if reach here ...
    return -1;
}

template < typename T >
void Vector<T>::erase( int index ) // if index valid, erases element there
{
    if( index < 0 || index >= size )
    {
        std::cout << "\nERROR! Index " << index
                  << " out of range 0.." << size-1 << std::endl;
        return;
    }
    for( int i = index; i < size-1; ++i )
        ary[i] = ary[i+1]; // copy each element above, down one index, so erased
    // now update size and return (by reference, since address passed in)
    -- size;
}

template < typename T >
bool Vector<T>::isSortedUp() const
{
    int size_ = size;
    while( --size_ )
        if( ary[size_] < ary[size_-1] ) return 0;
    return 1;
}

/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector<T>::merge( int bot, int mid, int top, Vector<T>& tmp )
{
    int sz = top - bot + 1;   // size of the range to be merged
    int j = 0;                // next open index in tmp
    int h1 = bot;             // next index to consider in the 1st half
    int h2 = mid + 1;         // next index to consider in the 2nd half

    // while indexes h1 and h2 are not past their ends ...
    while( h1 <= mid && h2 <= top )
    {   // move the smaller element into the tmp vec...
        if( ary[h1] < ary[h2] ) tmp[j++] = ary[h1++];
        else tmp[j++] = ary[h2++];
    }

    // Note: only one of the two while loops below is executed ...
    while( h1 <= mid ) tmp[j++] = ary[h1++]; // copy any remaining entries (1st half)
    while( h2 <= top ) tmp[j++] = ary[h2++]; // copy any remaining entries (2nd half)

    for( j = 0; j < sz; ++j ) ary[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void Vector<T>::my_msort( int bot, int top, Vector& tmp )
{
    if( bot == top ) return;
    else
    {
        int mid = ( bot + top ) / 2;
        my_msort( bot, mid, tmp );      // sort the first ...
        my_msort( mid + 1, top, tmp );  // and the second half ...
        merge( bot, mid, top, tmp );    // now merge these 2 sorted chunks
    }
}
template < typename T >
void Vector<T>::msort()
{
    if( isSorted ) return;
   
    Vector<T> tmp;
    tmp.reserve( size );
    my_msort( 0, size-1, tmp );
    isSorted = true;
}

template < typename T >
void Vector<T>::isort()
{
    if( isSorted ) return;
   
    // start with an array of just the first 2 elements (if exists)
    for( int i = 1; i < size; ++i )
    {
        T cmp = ary[i]; // get copy of this new cmp element on each outer loop
        int j = i-1; // get index of element just to the left of the above 'cmp'
                    // to start comparisons
        while( j >= 0 && cmp < ary[j] )
        {
            ary[j+1] = ary[j]; // copy element 'up' ...
            --j; // decrement j in preparation for next inner loop
        }
        ary[j+1] = cmp; // insert element at index j+1 (since j was decremented above)
    }
    isSorted = true;
}

#endif


[David]

And now the test program for the above file ...

Code: [Select]

// Vector_test1.cpp // // 2011-03-27 //

// enter data, find sum, average, msort, isort, find value, erase, show vector

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

#include <iostream>

#include "Vector.h"

template < typename T >
T takeIn( const char prompt[] )
{
    for( ; ; ) // an example of a C/C++ forever loop ... until 'return'
    {
        std::cout << prompt << std::flush;
        T tmp;
        if( std::cin >> tmp )
        {
            std::cin.sync();
            return tmp;
        }
        // else ...
        std::cin.clear();
        std::cin.sync();
        std::cout << "Invalid input ...\n";
    }
}

bool more() // defaults to 'true'/'yes' ... unless 'n' or 'N' entered
{
    std::cout << "More (y/n) ? " << std::flush;
    int reply = std::cin.get();
    std::cin.sync();
    if( reply == 'n' || reply == 'N' ) return false;
    // else ...
    return true;
}

template< typename T >
void show(const Vector< T >& v )
{
    for( int i = 0; i < v.get_size(); ++i ) std::cout << v[i] << " ";
    std::cout << std::endl;
}

template< typename T >
T sum(const Vector< T >& v )
{
    T sum = 0;
    for( int i = 0; i < v.get_size(); ++i ) sum += v[i];
    return sum;
}



int main()
{
    Vector< int > v;
    do
    {
        int val = takeIn< int >( "Enter next integer to sum: " );
        v.push_back( val );
    }
    while( more() );
   
    int sum_v = sum( v );
   
    std::cout << "\nFor " << v.get_size()
              << " numbers entered, sum_v was "
              << sum_v << "  and average was "
              << (float)sum_v/v.get_size() << std::endl;
         
    std::cout << "\nshow( v ) : "; show( v );
   
    int last = v[ v.get_size()-1 ];
   
    v.msort();
    std::cout << "\nAfter v.msort() ... "
              << "v.isSortedUp() = " << v.isSortedUp()
              << " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
              << "show( v ) : "; show( v );
         
    int index = v.find( last );
    if( index >= 0 )
    {
        v.erase( index );
        std::cout << "\nAfter erasing " << last << " ...";
        std::cout << "\nshow( v ) : "; show( v );
    }
    else std::cout << "\n" << last << " NOT found in Vectot.\n";


    int val = takeIn< int >( "\n\nEnter a new integer before isort: " );
    v.push_back( val );
    v.isort();
    std::cout << "After v.isort()... "
              << "v.isSortedUp()= " << v.isSortedUp()
              << " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
              << "show( v ) : "; show( v );
             
    v.shrink( 2 );
    std::cout << "After v.shrink( 2 )... "
              << "v.get_cap()= " << v.get_cap()
              << " ... v.get_size() = " << v.get_size() << std::endl
              << "show( v ) : "; show( v );

   
    v.clear();
    std::cout << "\nAfter v.clear() ... "
              << "v.get_cap()= " << v.get_cap()
              << " ... v.get_size() = " << v.get_size()

              << "\n\nPress 'Enter' to continue/exit ... " << std::flush;
    std::cin.get(); // keep 'Window' open until 'Enter' key is pressed ...
}


[David]

A little upgrade ... with insert and pack added ... and more standard function names like size() and capacity() ...

AND NOW Iterators ...

Code: [Select]

// Vector_test2.cpp // // 2013-06-15 //

// enter data, find sum, average, msort, isort, find value, erase, show vector

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

#include <iostream>
#include <string>

#include "Vector2.h"

template < typename T >
T takeIn( const char prompt[] )
{
    for( ; ; ) // an example of a C/C++ forever loop ... until 'return'
    {
        std::cout << prompt << std::flush;
        T tmp;
        if( std::cin >> tmp )
        {
            std::cin.sync();
            return tmp;
        }
        // else ...
        std::cin.clear();
        std::cin.sync();
        std::cout << "Invalid input ...\n";
    }
}

bool more() // defaults to 'true'/'yes' ... unless 'n' or 'N' entered
{
    std::cout << "More (y/n) ? " << std::flush;
    int reply = std::cin.get();
    std::cin.sync();
    if( reply == 'n' || reply == 'N' ) return false;
    // else ...
    return true;
}

template< typename T >
void show(const Vector< T >& v )
{
    for( int i = 0; i < v.size(); ++i ) std::cout << v[i] << " ";
    std::cout << std::endl;
}

template< typename T >
T sum(const Vector< T >& v )
{
    T sum = 0;
    for( int i = 0; i < v.size(); ++i ) sum += v[i];
    return sum;
}



int main()
{
    Vector< int > v;
    do
    {
        int val = takeIn< int >( "Enter next integer to sum: " );
        v.push_back( val );
    }
    while( more() );
   
    int sum_v = sum( v );
   
    std::cout << "\nFor " << v.size()
              << " numbers entered, sum_v was "
              << sum_v << "  and average was "


              << (float)sum_v/v.size() << std::endl;
     

Vector< int >::iterator it;   

std::cout << "showing v with for( it = v.begin(); it != v.end() ; ++it ) ...\n";
for( it = v.begin(); it != v.end() ; ++it )
std::cout << *it << " ";
std::cout << std::endl;

Vector< int >::reverse_iterator rit;
std::cout << "showing v with for( rit = v.rbegin(); rit != v.rend() ; ++rit ) ...\n";
for( rit = v.rbegin(); rit != v.rend() ; ++rit  )
std::cout << *rit << " ";
std::cout << std::endl;



    int last = v[ v.size()-1 ];
   
    v.msort();
    std::cout << "After v.msort() ... "
              << "v.isSortedUp() = " << v.isSortedUp()
              << " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
              << "show( v ) : "; show( v );
         
    int index = v.find( last );
    if( index >= 0 )
    {
        v.erase( index );
        std::cout << "After erasing " << last << " ...";
        std::cout << "\nshow( v ) : "; show( v );
    }
    else std::cout << "\n" << last << " NOT found in Vectot.\n";


    int val = takeIn< int >( "\n\npush_back a new integer and then call isort: " );
    v.push_back( val );
    v.isort();
    std::cout << "After v.isort()... "
              << "v.isSortedUp()= " << v.isSortedUp()
              << " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
              << "show( v ) : "; show( v );
             
    v.resize( 20 );
    std::cout << "After v.resize( 20 )... "
              << "v.capacity()= " << v.capacity()
              << " ... v.size() = " << v.size() << std::endl
              << "show( v ) : "; show( v );

    v.resize( 2 );
    std::cout << "After v.resize( 2 )... "
              << "v.capacity()= " << v.capacity()
              << " ... v.size() = " << v.size() << std::endl
              << "show( v ) : "; show( v );
             
    Vector < int > v2 = v;
    std::cout << "After Vector v2 = v ... "
              << "v2.capacity()= " << v2.capacity()
              << " ... v2.size() = " << v2.size() << std::endl
              << "show( v2 ) : "; show( v2 );

    v.clear();
    std::cout << "\nAfter v.clear() ... "
              << "v.capacity()= " << v.capacity()
              << " ... v.size() = " << v.size() << std::endl;
             
    v2 = v;
    std::cout << "After v2 = v ... "
              << "v2.capacity()= " << v2.capacity()
              << " ... v2.size() = " << v2.size() << std::endl;

    using std::string;
    Vector <string> v3;
    string iAry[] = { "the", "fat", "cat", "was", "wearing", "a", "tiny", "hat" };
    v3 = Vector <string> ( iAry, iAry + sizeof(iAry)/sizeof(string) );
    std::cout << "\nAfter "
              << "v3 = Vector <string> ( iAry, iAry + sizeof(iAry)/sizeof(string) )...\n"
              << "v3.capacity()= " << v3.capacity()
              << " ... v3.size() = " << v3.size() << std::endl
              << "show( v3 ) : "; show( v3 );

    v3.msort();
    std::cout << "\nAfter calling v3.msort ... "
              << "v3.capacity()= " << v3.capacity()
              << " ... v3.size() = " << v3.size() << std::endl
              << "show( v3 ) : "; show( v3 );

             
    std::cout << "\nPress 'Enter' to continue/exit ... " << std::flush;
    std::cin.get(); // keep 'Window' open until 'Enter' key is pressed ...
}


Code: [Select]

// classVector2_demo.cpp // // this version 2012-05-24 //

// with merge sort and insertion sort ... and added ...

// resize, pack ... and ...
// size constructor,

// copy constuctor, array constructor and overloaded operator=
                           
#include "Vector2.h" // includes <iostream>

#include <fstream>
using namespace std;

template < typename T >
ostream& operator << ( ostream& os, const Vector< T >& v )
{
    int size = v.size();
    for( int i = 0; i < size; ++ i ) os << ' ' << v[i];
    os << "  ::  size = " << v.size() << "  ::  capacity = " << v.capacity();
    return os;
   
}

bool reverseCmp( const int& a, const int& b )
{
    return a > b;
}


int main()
{
    int ary[] = { 9, 8, 6, 0, 1, 4, 7, 3, 2, 5 }; // get some test data ...

    // select Vector constructor for an (int) array passed in
    Vector < int > v( ary, ary+sizeof(ary)/sizeof(ary[0]) );
    cout << "Showing vector v ... \n" << v << endl;
   
    v.msort();
    cout << "After msort ... \n" << v << endl;
   
    v.insert( 1, 3, -1 ); // insert at index 1, 3 copies of -1
    cout << "After v.insert( 1, 3, -1 ) ... \n" << v << endl;
   
    v.erase( 10, 3 ); // erase, beegin at index 1, 3 elemements ...
    cout << "After v.erase( 10, 3 ) ... \n" << v << endl;
   
    v.unique();
    cout << "After v.unique() ... \n" << v << endl;

    v.erase( 0 ); // erase at index 0, 1 elemement ...
    cout << "After v.erase( 0 ) ... \n" << v << endl;
   
   
    msort( v, reverseCmp ); // erase at index 0, 1 elemement ...
    cout << "After msort( v, reverseCmp ) ... \n" << v << endl;

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

// example output ...
/*
Showing vector v ...
 9 8 6 0 1 4 7 3 2 5  ::  size = 10  ::  capacity = 10
After msort ...
 0 1 2 3 4 5 6 7 8 9  ::  size = 10  ::  capacity = 10
After v.insert( 1, 3, -1 ) ...
 0 -1 -1 -1 1 2 3 4 5 6 7 8 9  ::  size = 13  ::  capacity = 13
After v.erase( 10, 3 ) ...
 0 -1 -1 -1 1 2 3 4 5 6  ::  size = 10  ::  capacity = 13
After v.unique() ...
 -1 0 1 2 3 4 5 6  ::  size = 8  ::  capacity = 13
After v.erase( 0 ) ...
 0 1 2 3 4 5 6  ::  size = 7  ::  capacity = 13

Press 'Enter' to continue/exit ...
*/


[David]

This file is used by the above test programs ...

UPDATE:  Now with forward and reverse iterators

Code: [Select]

// Vector2.h // // this version 2013-06-15 //

// with merge sort and insertion sort ... and added ...

// resize, pack ... and ...
// size constructor,

// copy constuctor, array constructor and overloaded operator=
                           
#ifndef dwVECTOR_H
#define dwVECTOR_H

#include <iostream>


/* can re-set this to minimize copying and getting new memory using push_back */
#ifndef VEC_CHUNK_SIZE
#define VEC_CHUNK_SIZE 8
#endif


template < typename T >
class Vector
{
public:
    Vector();
    Vector( int n );
    Vector( const Vector< T >& ); // copy constructor ...
    Vector( const T*, const T* ); // array constructor ...
    Vector<T>& operator= ( const Vector< T >& v ); // overloaded operator=
    ~Vector() { clear(); }
   
    void push_back( const T& );
    void reserve( int );
    void resize( int );
    void shrink( int );
    void pack();
    void clear();
   
    T& operator [] (int i) { return ary[i]; }
    const T& operator [] (int i) const { return ary[i]; }
 
 
   
class iterator
{
public:
    iterator( T* p = 0 ) : ptr(p) {}
    iterator& operator ++ () { ++ptr; return *this; }
    iterator& operator ++ ( int ) { ++ptr; return *this; }
    iterator& operator -- () { --ptr; return *this; }
    iterator& operator -- ( int ) { --ptr; return *this; }
    bool operator != (const iterator & it2) const { return  ptr != it2.ptr; }
    bool operator == (const iterator & it2) const { return  ptr == it2.ptr; }
    const T& operator * () const { return *ptr; }
    T& operator * () { return *ptr; }
private:
    T* ptr; // cur
} ;

iterator begin() { iterator it( ary ); return it; }
iterator end() { iterator it( ary + len ); return it; }


class reverse_iterator
{
public:
    reverse_iterator( T* p = 0 ) : ptr(p) {}
    reverse_iterator& operator ++ () { --ptr; return *this; }
    reverse_iterator& operator ++ ( int ) { --ptr; return *this; }
    reverse_iterator& operator -- () { ++ptr; return *this; }
    reverse_iterator& operator -- ( int ) { ++ptr; return *this; }
    bool operator != (const reverse_iterator & it2) const { return  ptr != it2.ptr; }
    bool operator == (const reverse_iterator & it2) const { return  ptr == it2.ptr; }
    const T& operator * () const { return *ptr; }
    T& operator * () { return *ptr; }
private:
    T* ptr; // cur
} ;

reverse_iterator rbegin() { reverse_iterator it( ary + len-1 ); return it; }
reverse_iterator rend() { reverse_iterator it( ary-1 ); return it; }
   

   
    int size() const { return len; }
    int capacity() const { return cap; }
    bool get_isSorted() const { return isSorted; }
    void set_isSorted() { isSorted = true; }
    bool isSortedUp() const;
   
    int find( T ) const; // returns index if T value present ... else -1
    void erase( int ); // if int index valid, erases element there
    void erase( int, int ); // if int index valid, erases n elements there
    void insert( int, int, const T& );
    void msort();
    void isort();
   
    void unique();
    bool isUnique() const ;
private:
    int cap; // capacity
    int len;
    bool isSorted;
    T* ary;
   
    void enlarge(); // used by push_back
   
    void merge( int, int, int, Vector< T >& ); // used by msort ...
    void my_msort( int, int, Vector< T >& );
};


// definitions ...

template < typename T >
Vector< T >::Vector() : cap(0), len(0), isSorted(true), ary(0) {}

template < typename T >
Vector< T >::Vector( int n ) : cap(0), len(0), isSorted(true), ary(0)
{
    if( n > 0 )
    {
        cap = len = n;
        if( len > 1 ) isSorted = false;
        ary = new T[size];
        for( int i = 0; i < len; ++i ) ary[i] = T(0);
    }
}

template < typename T >
Vector< T >::Vector( const Vector< T > & v ) // copy constructor ...
{
    cap = v.cap;
    len = v.len;
    isSorted = v.isSorted;
    ary = new T[cap];
    for( int i = 0; i < len; ++i ) ary[i] = v.ary[i];
}

template < typename T >
Vector< T >::Vector( const T* a, const T* b ) // array constructor ... NOTE! b is one past last element
{
    len = cap = b-a;
    isSorted = false;
    ary = new T[cap];
    for( int i = 0; i < len; ++i ) ary[i] = a[i];
}

template < typename T >
Vector< T >& Vector< T >::operator= ( const Vector< T >& v ) // overloaded operator=
{
    if( this != &v )
    {
        delete [] ary;
        cap = v.cap;
        len = v.len;
        isSorted = v.isSorted;
        ary = new T[cap];
        for( int i = 0; i < len; ++i ) ary[i] = v.ary[i];
    }
    return *this;
}

template < typename T >
void Vector< T >::push_back( const T& e )
{
    if( len == cap ) enlarge();
    /* now add in new Rec ... */
    ary[len] = e;
   
    ++ len;
    isSorted = false;
}

// new array to hold 2x's records ... copies old to new
template < typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // double capacity ...
    else cap = VEC_CHUNK_SIZE; // set initial capacity
    T* tmp = new T[ cap ];
    for( int i = len-1; i >= 0; --i ) tmp[i] = ary[i];
    //for( int i = cap-1; i >= len; --i ) tmp[i] = 0;
    delete [] ary;
    ary = tmp; // update the base address of ary
}

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

template < typename T >
void Vector< T >::resize( int newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( int i = cap-1; i >= len; --i ) ary[i] = T(0);
        len = newSize;
        isSorted = false;
    }
    else if( newSize < len )
    {
        shrink( newSize );
        //pack(); // ? //
    }
}

template < typename T >
void Vector< T >::shrink( int newSize )
{
    if( newSize < len && newSize >= 0 ) len = newSize; // leave cap unchanged
    if( len < 2 ) isSorted = true;
}

template < typename T >
void Vector< T >::pack()
{
    if( len < cap )
    {
        cap = len;
        T* tmp = new T[cap];
        for( int i = len-1; i >= 0; --i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update address ...
    }
}

template < typename T >
void Vector< T >::clear()
{
    if( ary != 0 )
    {
        delete [] ary;
        cap = len = 0;
        ary = 0;
        isSorted = true;
    }
}

template < typename T >
int Vector< T >::find( T value ) const // returns index if present ... else -1
{
    for( int i = 0; i < len; ++i )
        if( ary[i] == value ) return i;
    // else if reach here ...
    return -1;
}

template < typename T >
void Vector< T >::erase( int index ) // if index valid, erases element there
{
if( ! len )
{
std::cout << "\nERROR! Vector empty." << std::endl;
return;
}
//else ...
    if( index < 0 || index >= len )
    {
        std::cout << "\nERROR! Index " << index
                  << " out of range 0.." << len-1 << std::endl;
        return;
    }
// else ...
    for( int i = index; i < len-1; ++i )
        ary[i] = ary[i+1]; // copy each element above, down one index, so erased
    // now update len for 'this' vector object ...
    -- len;
}

template < typename T >
void Vector< T >::erase( int index, int num ) // if index valid, erases n elements there
{
if( ! len )
{
std::cout << "\nERROR! Vector empty." << std::endl;
return;
}
//else ...
    if( index < 0 || index >= len )
    {
        std::cout << "\nERROR! Index " << index
                  << " out of range 0.." << len-1 << std::endl;
        return;
    }
//else ...
    if( num > len - index )
    {
        num = len - index;
        std::cout << "\nERROR! num to erase " << num
                  << " out of range 0.." << len-index << std::endl;
        return;
    }
// else ...
    for( int i = index; i < len-num; ++i )
        ary[i] = ary[i+num]; // copy nth element above, down n places, so erased
    // now update len for 'this' vector object ...
     len -= num;
}

// default is push_front one '0' value element
template < typename T > // assumes pos >= 0, num > 0
void Vector< T >::insert( int pos = 0, int num = 1, const T& val = T(0) )
{
    if( pos < 0 || num < 1 )
    {
        std::cout << "\nERROR! Index must be >= 0 and num must be  > 1  \n";
        return;
    }
       
    if( cap < len + num ) reserve( len + num ); // updates cap
    if( pos > cap-num ) pos = len; // just add in ... at end ...
    else if( pos < len ) // shift last 'len-pos' elements up num places ....
    {
        int top = len + num - 1;
        for( int i = 0; i < len-pos; ++i ) { ary[top] = ary[top-num]; --top; }
    }
    for( int i = 0; i < num; ++ i ) ary[pos+i] = val; // insert val's
    len += num; // update len
    isSorted = false;
}

template < typename T >
bool Vector< T >::isSortedUp() const
{
    int sizeTmp = len;
    while( --sizeTmp )
        if( ary[sizeTmp] < ary[sizeTmp-1] ) return false;
    return true;
}

/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector< T >::merge( int bot, int mid, int top, Vector< T >& tmp )
{
    int sz = top - bot + 1;   // len of the range to be merged
    int j = 0;                // next open index in tmp
    int h1 = bot;             // next index to consider in the 1st half
    int h2 = mid + 1;         // next index to consider in the 2nd half

    // while indexes h1 and h2 are not past their ends ...
    while( h1 <= mid && h2 <= top )
    {   // move the smaller element into the tmp vec...
        if( ary[h1] < ary[h2] ) tmp[j++] = ary[h1++];
        else tmp[j++] = ary[h2++];
    }

    // Note: only one of the two while loops below is executed ...
    while( h1 <= mid ) tmp[j++] = ary[h1++]; // copy any remaining entries (1st half)
    while( h2 <= top ) tmp[j++] = ary[h2++]; // copy any remaining entries (2nd half)

    for( j = 0; j < sz; ++j ) ary[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void Vector< T >::my_msort( int bot, int top, Vector< T >& tmp )
{
    if( bot == top ) return;
    else
    {
        int mid = ( bot + top ) / 2;
        my_msort( bot, mid, tmp );      // sort the first ...
        my_msort( mid + 1, top, tmp );  // and the second half ...
        merge( bot, mid, top, tmp );    // now merge these 2 sorted chunks
    }
}
template < typename T >
void Vector< T >::msort()
{
    if( isSorted ) return;

    if( len > 1 )
    {
        Vector< T > tmp;
        tmp.reserve( len );
        my_msort( 0, len-1, tmp );
        isSorted = true;
    }
}

template < typename T >
void Vector< T >::isort()
{
    if( isSorted ) return;
   
    // start with an array of just the first 2 elements (if exists)
    for( int i = 1; i < len; ++i )
    {
        T cmp = ary[i]; // get copy of this new cmp element on each outer loop
        int j = i-1; // get index of element just to the left of the above 'cmp'
                    // to start comparisons
        while( j >= 0 && cmp < ary[j] )
        {
            ary[j+1] = ary[j]; // copy element 'up' ...
            --j; // decrement j in preparation for next inner loop
        }
        ary[j+1] = cmp; // insert element at index j+1 (since j was decremented above)
    }
    isSorted = true;
}
/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */

template < typename T >
void Vector< T >::unique()
{
    if( !isSorted ) msort();

int i = 0;
    for( int j = 1; j < len ; ++j )
    {
        if( ary[i] != ary[j] )
        {
            ++i;
            if( i != j ) ary[i] = ary[j];
        }
    }

    len = ++i;
}

template < typename T >
bool Vector< T >::isUnique() const
{
    if( !isSorted ) msort();
    for( int i = len-1; i > 0; --i )
        if( ary[i] == ary[i-1] ) return false;
    // else ...
    return true;
}



template < typename T >
void merge( Vector< T >& v, int bot, int mid, int top, Vector< T >& tmp, bool (*cmp) (const T& a, const T& b ) )
{
    int sz = top - bot + 1;   // size of the range to be merged
    int j = 0;                // next open index in tmp
    int h1 = bot;             // next index to consider in the 1st half
    int h2 = mid + 1;         // next index to consider in the 2nd half

    // while indexes h1 and h2 are not past their ends ...
    while( h1 <= mid && h2 <= top )
    {   // move the 'true' element into the tmp vec...
        if( cmp(v[h1], v[h2]) ) tmp[j++] = v[h1++];
        else tmp[j++] = v[h2++];
    }

    // Note: only one of the two while loops below is executed ...
    while( h1 <= mid ) tmp[j++] = v[h1++]; // copy any remaining entries (1st half)
    while( h2 <= top ) tmp[j++] = v[h2++]; // copy any remaining entries (2nd half)

    for( j = 0; j < sz; ++j ) v[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void my_msort( Vector< T >& v, int bot, int top, Vector < T >& tmp, bool (*cmp) (const T& a, const T& b ) )
{
    if( bot == top ) return;
    else
    {
        int mid = ( bot + top ) / 2;
        my_msort( v, bot, mid, tmp, cmp );      // sort the first ...
        my_msort( v, mid + 1, top, tmp, cmp );  // and the second half ...
        merge( v, bot, mid, top, tmp, cmp );    // now merge these 2 sorted chunks
    }
}
template < typename T >
void msort( Vector< T >& v, bool (*cmp) (const T& a, const T& b ) )
{
    if( v.size() > 1 )
    {
        Vector< T > tmp;
        int size = v.size();
        tmp.reserve( size );
        my_msort( v, 0, size-1, tmp, cmp );
        v.set_isSorted();
    }
}

#endif