Author Topic: class Vector ... and Stacks and Queues ...  (Read 27375 times)

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
class Vector ... and Stacks and Queues ...
« on: November 30, 2015, 08:48:26 PM »


An often asked student request is regarding coding a dynamic array ...

So ... .

UPDATE: start here now to see the new 3 fast steps ..

http://developers-heaven.net/forum/index.php/topic,2622.msg3177.html#msg3177

Or here, to see even more recent Six Fast Steps ....

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


Return here to see a more 'complete' class Vector ... (in file Vector3.h below.)

template < typename T >
class Vector
{
 ///
} ;

to get you started.


Firstly the .h file ...

Code: [Select]
// Vector3.h //  // 2016-02-12 //

#ifndef VECTOR3_H
#define VECTOR3_H

#include <iostream>

const unsigned CHUNK_SIZE = 8;

template < typename T >
class Vector
{
public:
    typedef T* iterator;
    typedef const T* const_iterator;

    Vector();
    Vector( size_t n );
    Vector( const Vector& ); // copy ctor ...
    Vector( const T*, const T* ); // array ctor ...
    Vector< T >& operator = ( const Vector< T >& ); // overloaded =
    ~Vector() { clear(); }

    void push_back( const T& );
    void reserve( size_t );
    void resize( size_t );
    void shrink( size_t );
    void pack();
    void clear();

    // overloaded [], done below ...
    T& operator [] ( size_t ) ; // allow element to be updated
    const T& operator [] ( size_t ) const; // 'read only'

    // overloaded << is done outside class below ...

    // += is different for numbers and strings ...
    // NOTE: def'n of >> is often best done outside of class

    iterator begin() ; // { return ary; }
    iterator end() ; // { return ary+len; }
    const_iterator begin() const ; // { return ary; }
    const_iterator end() const ; // { return ary+len; }

    T at( size_t pos ) const ;

    size_t capacity() const;
    size_t size() const;

    bool empty() const { return len == 0 ; }

    T back() const;
    void pop_back();

    void erase( Vector< T >::iterator it );
    void erase( Vector< T >::iterator it, size_t num );
    void insert( size_t pos, const T& val, size_t num = 1 );


    void output( std::ostream& , char end = '\n' ) const;

protected:
    size_t cap;
    size_t len;
    T* ary;
    void enlarge(); // used by push_back
} ;




template < typename T >
void Vector< T >::output( std::ostream & outs, char end ) const
{
    for( size_t i = 0; i < len; ++i )
    {
        outs << ary[i] << end;
    }
}

template < typename T >
std::ostream& operator << ( std::ostream& os, const Vector< T >& v )
{
    v.output( os );
    return os;
}

// note syntax here ..................................... //
template < typename T >
typename Vector< T >::iterator Vector< T >::begin()
{
    return ary;
}

template < typename T >
typename Vector< T >::iterator Vector< T >::end()
{
    return ary+len;
}

template < typename T >
typename Vector< T >::const_iterator Vector< T >::begin() const
{
    return ary;
}

template < typename T >
typename Vector< T >::const_iterator Vector< T >::end() const
{
    return ary+len;
}
// ...................................................... //


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

template < typename T >
Vector< T >::Vector( size_t n ) : cap(n), len(n), ary( new T[cap] )
{
    for( size_t i = 0; i < len; ++i ) ary[i] = T();
}

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

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

// overloaded operator=
template < typename T >
Vector< T >& Vector< T >::operator = ( const Vector< T >& v )
{
    if( this != &v )
    {
        delete [] ary;
        cap = v.cap;
        len = v.len;
        ary = new T[cap];
        for( size_t 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 element ... */
    ary[len] = e;

    ++ len;
}

// 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 = CHUNK_SIZE; // set initial capacity
    T* tmp = new T[ cap ];
    for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
    //for( int i = cap-1; i >= len; --i ) tmp[i] = T();
    delete [] ary;
    ary = tmp; // update the base address of ary
}

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 = cap-1; i >= len; --i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
    {
        len = newSize;
        pack();
    }
}

template < typename T >
void Vector< T >::shrink( size_t newSize )
{
    if( newSize < len ) len = newSize; // leave cap unchanged
}

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

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


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

// NO bounds checking here ... //
template < typename T >
T& Vector< T >::operator [] (size_t i)
{
    return ary[i];
}
template < typename T >
const T& Vector< T >::operator [] (size_t i) const
{
    return ary[i];
}

template < typename T >
T Vector< T >::at( size_t pos ) const
{
    if( pos < len ) return ary[pos];

    // else ... if reach here ...
    std::cerr << "\nINDEX '" << pos
              << "' IS OUT OF BOUNDS"
              << ", THUS, RETURNED VALUE '" << T()
              << "' IS NOT VALID!\n";
    return T();
}


template < typename T >
T Vector< T >::back() const
{
    if( len ) return ary[len-1];

    // else ... if reach here ...
    std::cerr << "\nEmpty ... THUS, RETURNED VALUE '" << T()
              << "' IS NOT VALID!\n";
    return T();
}

template < typename T >
void Vector< T >::pop_back()
{
    if( len ) -- len;
    else //if reach here ...
        std::cerr << "\nEmpty ... THUS ... can NOT pop_back() anything!\n";
}


template < typename T >
void Vector< T >::erase( Vector< T >::iterator it )
{
    if( ! len )
    {
        std::cerr << "\nERROR! Vector empty.\n";
        return;
    }
    //else ...
    if( it < begin() || it >= end() )
    {
        std::cerr << "\nERROR! NOT in vector ...\n";
        return;
    }
    // else ...
    for( size_t i = it - begin() ; 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( Vector< T >::iterator it, size_t num ) // begin at it, num to erase //
{
    if( ! len )
    {
        std::cerr << "\nERROR! Vector empty.\n";
        return;
    }
    //else ...
    if( it < begin() || it >= end() )
    {
        std::cerr << "\nERROR! NOT in vector ...\n";
        return;
    }

    const size_t index = it - begin();
    if( num > len - index ) num = len - index;

    // else ...
    if( num > 0 )
        for( size_t 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;

    pack();
}

// default is INSERT ONE element, i.e. num = 1 //
template < typename T > // assumes pos >= 0, num > 0
void Vector< T >::insert( size_t pos,  const T& val, size_t num )
{
    if( num == 0 )
    {
        std::cerr << "\nERROR! Can NOT insert 0 elements ...\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( size_t i = 0; i < len-pos; ++i ) {
            ary[top] = ary[top-num];
            --top;
        }
    }
    for( size_t i = 0; i < num; ++ i ) ary[pos+i] = val; // insert val's
    len += num; // update len
}


#endif
« Last Edit: March 11, 2017, 07:32:51 AM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector
« Reply #1 on: November 30, 2015, 08:50:03 PM »
And now, a little demo / test program for class Vector ...

Code: [Select]
// test_Vector3.h.cpp //  // 2016-02-12  //


// Note: this class Vector, with iterator, and const_iterator,
// uses the C++ <algorithm> library 'sort' and 'find' functions OK. //


#include "Vector3.h" // note: also includes <iostream>

#include <string>
#include <iomanip> // re. setw
#include <algorithm> // re. testing here, with this Vector, C++ library sort & find //

const int W = 50;


// re. library sort (reversed order) //
bool reverseCmp( const int& a, const int& b )
{
    return b < a;
}

// re. printing out Vector in reversed order  //
template< typename T >
void output_rev( const Vector< T >& v, std::ostream& os = std::cout, char end = ' ' )
{
    typename Vector< T >::const_iterator it = v.end(), stop = v.begin() ;
    --it, --stop;
    for( ; it != stop ; -- it )
        os << *it << end;
}




int main()
{
    using namespace std;

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

    const int ary_size = sizeof ary / sizeof *ary;

    // select Vector constructor for an (int) array passed in
    Vector < int > v( ary, ary + ary_size );

    cout << left << setw(W) << "Showing Vector v: ";
    v.output( cout, ' ' );


    sort( v.begin(), v.end(), reverseCmp ); // erase at index 0, 1 elemement ...
    cout << '\n' << setw(W) << "After sort(v.begin(), v.end(), reverseCmp ): ";
    v.output( cout, ' ' );

    cout << '\n' << setw(W) << "Showing Vector v (back to front): ";
    output_rev( v );


    sort( v.begin(), v.end() );
    cout << '\n' << setw(W) << "After sort(v.begin(), v.end() ): ";
    v.output( cout, ' ' );

    cout << '\n' << setw(W) << "Showing Vector v (back to front): ";
    output_rev( v );


    cout << "\n\n";
    int val = -1;
    Vector< int >::iterator it = find( v.begin(), v.end(), val );
    if( it == v.end() )
    {
        cout << val << " was NOT found in: ";
        v.output( cout, ' ' );
        cout << '\n';
    }

    val = 5;
    it = find( v.begin(), v.end(), val );
    if( it != v.end() )
    {
        cout << val << ", i.e. *it = " << *it << " was found at " << it;
        v.erase( it );
        cout << "\nAfter erasing " << val << ", v is now: ";
        v.output( cout, ' ' );
        cout << ", v.capacity() = " << v.capacity()
             << ", v.size() = " << v.size() << "\n";
    }

    val = 2;
    it = find( v.begin(), v.end(), val );
    if( it != v.end() )
    {
        cout << val << ", i.e. *it = " << *it << " was found at " << it << endl;
        v.erase( it, 6 );
        cout << "After erasing " << val << " and 5 more, v is now: ";
        v.output( cout, ' ' );
        cout << ", v.capacity() = " << v.capacity() << ", v.size() = " << v.size() << '\n';
    }

    v.insert( 2, -1, 3 );
    cout << '\n' << setw(W) << "After v.insert( 2, -1, 3 ): ";
    v.output( cout, ' ' );
    cout << "\nv.capacity() = " << v.capacity() << ", v.size() = " << v.size();


    v.reserve(13);
    cout << '\n' << setw(W) << "After v.reserve(13): ";
    v.output( cout, ' ' );
    cout << "\nv.capacity() = " << v.capacity() << ", v.size() = " << v.size();

    v.resize(2);
    cout << '\n' << setw(W) << "After v.resize(2): ";
    v.output( cout, ' ' );
    cout << "\nv.capacity() = " << v.capacity() << ", v.size() = " << v.size();

    v.clear();
    cout << "\nAfter calling v.clear() ... v.empty() = "
         << (v.empty() ? "true" : "false") << '\n';

    const string names[] = { "Andy", "Bill", "Jill", "Lucy", "Marie", "Sam", "Sharon", "Zoe" };
    const int num_names = sizeof names / sizeof *names;

    Vector< string > vNames( names, names + num_names );

    cout << "\nTesting pop_back: ";
    while( !vNames.empty() )
    {
        cout << vNames.back() << ' ';
        vNames.pop_back();
    }

    cout << "\n\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}
« Last Edit: February 12, 2016, 07:23:51 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector
« Reply #2 on: February 28, 2016, 12:25:30 AM »
A little demo re. ...

the use of objects (and copies of those objects)

vs.

the use of (new) pointers to each object (and copies of those pointers) ...


See demo program and comments there ...

Code: [Select]
// pointerToObjDemo.cpp // // see comments below to fix crash of this runnung program //

// Also see comments at end about one 'limited special' use of pointers //

// NOTE: USE the objects them selves,  where ever possible,
// and AVOID the use of pointers as much as possible in C++,
// Note: C++ 11 adds 'smart pointers' usage ...
// to help auto-mate memory management in situations where pointers ARE actually needed. //


#include <iostream>
#include <string>
#include <vector>



class Student
{
public:
    //ctor...
    Student( const std::string& name="", int id=0 ) : name(name), id(id) {}
    // mutator/settor ...
    void set_name( const std::string& new_name ) {
        name = new_name;
    }
    // def'n of overloaded operator << for Student objects //
    friend std::ostream& operator << ( std::ostream& os, const Student& st )
    {
        return os  << st.id << ", " << st.name;
    }
private:
    std::string name;
    int id;
} ;




int main()
{
    using namespace std;
    vector< Student > studs;

    // get some test data ...
    studs.push_back( Student("Sam", 1) );
    studs.push_back( Student("Ann", 2) );
    studs.push_back( Student("Zak", 3) );

    // edit name at index 1 ...
    studs[1] = Student("Sam", 2);  // new *object constructed and then copied over* ... //

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

    // NOTE ... above ... the STL vector class handles ALL memory
    // allocation and deletion for you //



    cout << "Press 'Enter' to continue (to see program crash/but see comments re. 'fix')... ";
    string dummy;
    getline( cin, dummy );




    // BUT below ... the above is only NOW 'partly true' ... since here ...
    // you NEED to allocate ALSO EACH new pointer to each new object and then ...
    // clean-up/free-up the reserved heap memory re. these pointers when done with each //
    vector< Student* > p_studs;

    // get some test data ...
    p_studs.push_back( new Student("Sam2", 1) );
    p_studs.push_back( new Student("Ann2", 2) );
    p_studs.push_back( new Student("Zak2", 3) );


    // BUT NOTE !!!
    // BIG PROBLEM below ...
    // since now former pointer over-written, (former pointer to dynamic memory IS LOST),
    // so can NOT delete it ... and --> MEMORY LEAK! //

    p_studs[1] = p_studs[0]; // *pointer ONLY* copied //

    // fix is this:
    //p_studs[1]->set_name( "Sam2" ); // need to have/use a 'set' method to 'mutate' the private data member of the class //

    // or this
    //delete p_studs[1];
    //p_studs[1] = new Student( "Sam2", 2);


    for( size_t i = 0; i < p_studs.size(); ++ i )
        cout << *p_studs[i] << '\n';

    // clean up all dynamically allocated memory //
    for( int i = p_studs.size()-1; i >= 0; -- i )
    {
        delete p_studs[i];  // AMD running program crashes here when trying to delete twice //
    }



    cout << "Press 'Enter' to continue/exit ... ";
    getline( cin, dummy );

}


/*
So why would one ever want to create and use pointers to objects ?

One reason might be ...
If moving around (copying) a lot of BIG onjects ... copying (instead) only pointers to those objects is faster ...
and can offset the extra work/time needed to create, dereference and delete all those added pointers to each object,
IF ...
there is room to handle added memory usage to track all these pointers ... in addition to the memory of each object itself !!!

*/

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector
« Reply #3 on: February 29, 2016, 06:52:27 AM »
OK ... the 3 fast steps to a simple expandable array class ...

Step 1 ... just a simple struct to hold our resizable dynamic array ...

Firstly, the file "MyIntArray.h" ...

Code: [Select]
// MyIntArray.h //  // 2016-02 28 //


#ifndef MYARRAY_H
#define MYARRAY_H

#include <iostream>
using std::cerr;


// firstly as a struct
struct MyIntArray
{
   size_t len;
   size_t cap;
   int* ary;
   // the rest ...
   
    // ctors...
   
    // default ctor ...
    MyIntArray() : len(0), cap(0), ary(0) {}
    //with size passed in
    MyIntArray( size_t size ) : len(size), cap(size), ary( new int [len] )
    {
        for( size_t i = 0; i < len; ++i ) ary[i] = 0;
    }
    // with ary (beg, end) passed in ...
    MyIntArray( const int* beg, const int* end )
    {
        len = cap = end - beg;
        ary = new int[len];
        for( size_t i =  0; i < len; ++i ) ary[i] = beg[i];
    }
    // copy ctor...
    MyIntArray ( const MyIntArray& v ) // copy constructor ...
    {
        cap = v.cap;
        len = v.len;
        ary = new int[cap];
        for( size_t i = 0; i < len; ++i ) ary[i] = v.ary[i];
    }
    // overloaded operateo = ...
    MyIntArray& operator = ( const MyIntArray& v ) // copy constructor ...
    {
        if( this != &v )
        {
            delete [] ary;
           
            cap = v.cap;
            len = v.len;
            ary = new int[cap];
            for( size_t i = 0; i < len; ++i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // clear ...
    void clear()
    {
        if( ary )
        {
            delete [] ary;
            cap = 0;
            len = 0;
            ary = 0;
        }
    }
    // destructor ..
    ~MyIntArray() { clear(); }
   

    // enlarge
    void enlarge()
    {
        if( cap ) cap += cap; // double capacity ...
        else cap = 2; // set initial capacity
        int* tmp = new int[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        //for( int i = cap-1; i >= len; --i ) tmp[i] = T();
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
    // reserve ...
    void reserve( size_t newCap )
    {
        if( newCap > cap )
        {
            cap = newCap;
            int* tmp = new int[ cap ];
            for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
            delete [] ary;
            ary = tmp; // update the base address of ary
        }
    }
    // resize ...
    void resize( size_t newSize )
    {
        if( newSize > len )
        {
            reserve( newSize );
            for( size_t i = cap-1; i >= len; --i ) ary[i] = 0;
            len = newSize;
        }
        else if( newSize < len )
        {
            for( size_t i = len-1; i >= newSize; --i ) ary[i] = 0;
            len = newSize;
        }
    }
   
   
    // push_back ...
    void push_back( int val )
    {
        if( len == cap ) enlarge();
        /* now add in new element ... */
        ary[len] = val;
        ++ len;
    }
   
    // overloaded operator [] ...
    int& operator [] ( size_t i ) { return ary[i]; } // allow element to be updated
    const int& operator [] ( size_t i ) const { return ary[i]; } // 'read only'
   
    size_t size() const { return len; }
    size_t capacity() const { return cap; }
   
    int back() const
    {
        if( len ) return ary[len-1];
        // else ...
        cerr << "\nERROR! MyIntArray is empty ... return value of 0 is NOT valid.\n";
        return 0;
       
    }
    void pop_back() { if( len ) --len;  }

    bool empty() const { return len == 0; }

} ;

#endif


Then ... a little program to test it out ...

Code: [Select]
// test_MyIntArray.h.cpp //  // 2016-02-28 //


#include "MyIntArray.h"


int main()
{
    using namespace std;

    const int nums[]= { 5, 4, 3, 2, 1 };
    const int size = sizeof nums / sizeof(int);

    MyIntArray v( nums, nums+size );
    MyIntArray cpy( v ), a;
    a = cpy;
   
    for( size_t i = 0; i < v.size(); ++ i ) cout << v[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < cpy.size(); ++ i ) cout << cpy[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < a.size(); ++ i ) cout << a[i] << ' ';
    cout << "\n\n";
   
    while( !a.empty() )
    {
        cout << a.back() << ' ';
        a.pop_back();
    }
   
    cout << "\nPrees 'Enter' to exit/continue ... ";
    cin.get();
}
« Last Edit: February 29, 2016, 08:09:50 AM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector
« Reply #4 on: February 29, 2016, 07:01:10 AM »
Then see the very few changes to re-code as a class ...

Firstly the .h file ...

Code: [Select]
// MyIntArray2.h //  // 2016-02-28 //


#ifndef MYARRAY_H
#define MYARRAY_H

#include <iostream>
using std::cerr;


// 2ndly as a class ...
class MyIntArray
{
public:
    // ctors...
   
    // default ctor ...
    MyIntArray() : len(0), cap(0), ary(0) {}
    //with size passed in
    MyIntArray( size_t size ) : len(size), cap(size), ary( new int [len] )
    {
        for( size_t i = 0; i < len; ++i ) ary[i] = 0;
    }
    // with ary (beg, end) passed in ...
    MyIntArray( const int* beg, const int* end )
    {
        len = cap = end - beg;
        ary = new int[len];
        for( size_t i =  0; i < len; ++i ) ary[i] = beg[i];
    }
    // copy ctor...
    MyIntArray ( const MyIntArray& v ) // copy constructor ...
    {
        cap = v.cap;
        len = v.len;
        ary = new int[cap];
        for( size_t i = 0; i < len; ++i ) ary[i] = v.ary[i];
    }
    // overloaded operateo = ...
    MyIntArray& operator = ( const MyIntArray& v ) // copy constructor ...
    {
        if( this != &v )
        {
            delete [] ary;
           
            cap = v.cap;
            len = v.len;
            ary = new int[cap];
            for( size_t i = 0; i < len; ++i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // clear ...
    void clear()
    {
        if( ary )
        {
            delete [] ary;
            cap = 0;
            len = 0;
            ary = 0;
        }
    }
    // destructor ..
    ~MyIntArray() { clear(); }
   
   
    // reserve ...
    void reserve( size_t newCap )
    {
        if( newCap > cap )
        {
            cap = newCap;
            int* tmp = new int[ cap ];
            for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
            delete [] ary;
            ary = tmp; // update the base address of ary
        }
    }
    // resize ...
    void resize( size_t newSize )
    {
        if( newSize > len )
        {
            reserve( newSize );
            for( size_t i = cap-1; i >= len; --i ) ary[i] = 0;
            len = newSize;
        }
        else if( newSize < len )
        {
            for( size_t i = len-1; i >= newSize; --i ) ary[i] = 0;
            len = newSize;
        }
    }
   
   
    // push_back ...
    void push_back( int val )
    {
        if( len == cap ) enlarge();
        /* now add in new element ... */
        ary[len] = val;
        ++ len;
    }
   
    // overloaded operator [] ...
    int& operator [] ( size_t i ) { return ary[i]; } // allow element to be updated
    const int& operator [] ( size_t i ) const { return ary[i]; } // 'read only'
   
    size_t size() const { return len; }
    size_t capacity() const { return cap; }
   
    int back() const
    {
        if( len ) return ary[len-1];
        // else ...
        cerr << "\nERROR! MyIntArray is empty ... return value of 0 is NOT valid.\n";
        return 0;
       
    }
    void pop_back() { if( len ) --len;  }

    bool empty() const { return len == 0; }
   
private:
   size_t len;
   size_t cap;
   int* ary;
   
    // enlarge
    void enlarge()
    {
        if( cap ) cap += cap; // double capacity ...
        else cap = 2; // set initial capacity
        int* tmp = new int[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        //for( int i = cap-1; i >= len; --i ) tmp[i] = T();
        delete [] ary;
        ary = tmp; // update the base address of ary
    }

} ;

#endif


Then a little test program ...

Code: [Select]
// test_MyIntArray2.h.cpp //  // 2016-02-28 //


#include "MyIntArray2.h"



int main()
{
    using namespace std;

    const int nums[]= { 5, 4, 3, 2, 1 };
    const int size = sizeof nums / sizeof(int);

    MyIntArray v( nums, nums+size );
    MyIntArray cpy( v ), a;
    a = cpy;

    for( size_t i = 0; i < v.size(); ++ i ) cout << v[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < cpy.size(); ++ i ) cout << cpy[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < a.size(); ++ i ) cout << a[i] << ' ';
    cout << "\n\n";

    while( !a.empty() )
    {
        cout << a.back() << ' ';
        a.pop_back();
    }

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

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector
« Reply #5 on: February 29, 2016, 07:09:34 AM »
Finally ... as a template ...

Code: [Select]
// MyArray3.h //


#ifndef MYARRAY_H
#define MYARRAY_H

#include <iostream>
using std::cerr;


// 3rdly as a template ...
template < typename T >
class MyArray
{
public:
    // ctors...
   
    // default ctor ...
    MyArray() : len(0), cap(0), ary(0) {}
    //with size passed in
    MyArray( size_t size ) : len(size), cap(size), ary( new T [len] )
    {
        for( size_t i = 0; i < len; ++i ) ary[i] = T();
    }
    // with ary (beg, end) passed in ...
    MyArray( const T* beg, const T* end )
    {
        len = cap = end - beg;
        ary = new T[len];
        for( size_t i =  0; i < len; ++i ) ary[i] = beg[i];
    }
    // copy ctor...
    MyArray ( const MyArray< T >& v ) // copy constructor ...
    {
        cap = v.cap;
        len = v.len;
        ary = new T[cap];
        for( size_t i = 0; i < len; ++i ) ary[i] = v.ary[i];
    }
    // overloaded operateo = ...
    MyArray< T >& operator = ( const MyArray< T >& v ) // copy constructor ...
    {
        if( this != &v )
        {
            delete [] ary;
           
            cap = v.cap;
            len = v.len;
            ary = new T[cap];
            for( size_t i = 0; i < len; ++i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // clear ...
    void clear()
    {
        if( ary )
        {
            delete [] ary;
            cap = 0;
            len = 0;
            ary = 0;
        }
    }
    // destructor ..
    ~MyArray() { clear(); }
   
   
    // reserve ...
    void 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
        }
    }
    // resize ...
    void resize( size_t newSize )
    {
        if( newSize > len )
        {
            reserve( newSize );
            for( size_t i = cap-1; i >= len; --i ) ary[i] = T();
            len = newSize;
        }
        else if( newSize < len )
        {
            for( size_t i = len-1; i >= newSize; --i ) ary[i] = T();
            len = newSize;
        }
    }
   
   
    // push_back ...
    void push_back( const T& val )
    {
        if( len == cap ) enlarge();
        /* now add in new element ... */
        ary[len] = val;
        ++ len;
    }
   
    // overloaded operator [] ...
    T& operator [] ( size_t i ) { return ary[i]; } // allow element to be updated
    const T& operator [] ( size_t i ) const { return ary[i]; } // 'read only'
   
    size_t size() const { return len; }
    size_t capacity() const { return cap; }
   
    const T& back() const
    {
        if( len ) return ary[len-1];
        // else ...
        cerr << "\nERROR! MyArray is empty ... return value of 0 is NOT valid.\n";
        return errVal;;
    }
    T& back()
    {
        if( len ) return ary[len-1];
        // else ...
        cerr << "\nERROR! MyArray is empty ... return value of 0 is NOT valid.\n";
        return errVal;;
    }
    void pop_back() { if( len ) --len;  }

    bool empty() const { return len == 0; }
   
private:
   size_t len;
   size_t cap;
   T* ary;
   
   static T errVal;
   
    // enlarge
    void enlarge()
    {
        if( cap ) cap += cap; // double capacity ...
        else cap = 2; // set initial capacity
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        //for( int i = cap-1; i >= len; --i ) tmp[i] = T();
        delete [] ary;
        ary = tmp; // update the base address of ary
    }

} ;


// initail here ... //
template< typename T >
T MyArray< T >::errVal = T();

#endif


And a cheap little test file ...

Code: [Select]
// test_MyIntArray3.h.cpp //  // 2016-02-28 //


#include "MyIntArray3.h"

#include <string>



int main()
{
    using namespace std;

    const int nums[]= { 5, 4, 3, 2, 1 };
    const int size = sizeof nums / sizeof(int);

    MyArray < int > v( nums, nums+size );
    MyArray < int > cpy( v ), a;
    a = cpy;
   
    for( size_t i = 0; i < v.size(); ++ i ) cout << v[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < cpy.size(); ++ i ) cout << cpy[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < a.size(); ++ i ) cout << a[i] << ' ';
    cout << "\n\n";
   
    while( !a.empty() )
    {
        cout << a.back() << ' ';
        a.pop_back();
    }
   
   
    cout << "\n\n";
   
    const string strs[] = { "5", "4", "3", "2", "1" };
    const int sizeStrs = sizeof strs / sizeof(string);

    MyArray < string > vStr( strs, strs+sizeStrs );
    MyArray < string > cpyStr( vStr ), aStr;
    aStr = cpyStr;

    for( size_t i = 0; i < vStr.size(); ++ i ) cout << vStr[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < cpyStr.size(); ++ i ) cout << cpyStr[i] << ' ';
    cout << '\n';
    for( size_t i = 0; i < aStr.size(); ++ i ) cout << aStr[i] << ' ';
    cout << "\n\n";

    while( !aStr.empty() )
    {
        cout << aStr.back() << ' ';
        aStr.pop_back();
    }
   
    cout << "\nPrees 'Enter' to exit/continue ... ";
    cin.get();
}
« Last Edit: February 29, 2016, 07:30:19 AM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector ... and Stacks and Queues ...
« Reply #6 on: February 29, 2016, 07:56:36 AM »
Now to some simple stacks demo'd ...


Code: [Select]
// Stack.h //  // 2016-02-29 //

#ifndef dwSTACK_H
#define dwSTACK_H

#include <iostream>
#include <vector>

// default container for *THIS CUSTOM* stack here is std:: vector< T > //
template < typename T, class Container = std::vector < T > >
class Stack
{
public:
    void push( const T& val ) { stk.push_back( val ); }
   
    /////////  NOTE! *NO* bounds checking is done here /////
    const T& top() const { return stk.back(); }
    T& top() { return stk.back(); }
    void pop() { stk.pop_back(); }
    ////////////////////////////////////////////////////////
   
    size_t size() const { return stk.size(); }
    bool empty() const { return stk.empty(); }

private:
    Container stk;
} ;

#endif


And a little test progrom ...


Code: [Select]
// test_Stack.h.cpp //  // 2016-02-29  //


#include "Stack.h"

#include <iostream> // included above //
#include <string>
#include <list>
#include <deque> // a double ended queue //



int main()
{
    using namespace std;

    const string names[] = { "Andy", "Bill", "Jill", "Lucy", "Marie", "Sam", "Sharon", "Zoe" };
    const int num_names = sizeof names / sizeof *names;

    Stack < string > vNames; // by default, container inside *THIS CUSTOM* Stack wrapper class is a vector //
   
    for( int i = 0; i < num_names; ++ i ) vNames.push( names[i] );

    cout << "Testing pop vNames: \n";
    while( !vNames.empty() )
    {
        cout << vNames.top() << ' ';
        vNames.pop();
    }
   
    // Note C++ list is a double_link linked list ...
    // so has push_back and pop_back and back methods all implemented ok //
    Stack < string, list< string > > lstNames; // here, using a list container inside the class Stack //

    for( int i = 0; i < num_names; ++ i ) lstNames.push( names[i] );

    cout << "\n\nTesting pop lstNames: \n";
    while( !lstNames.empty() )
    {
        cout << lstNames.top() << ' ';
        lstNames.pop();
    }
   
   
    Stack < string, deque< string > > deqNames; // here, using a deque container inside the class Stack //

    for( int i = 0; i < num_names; ++ i ) deqNames.push( names[i] );

    cout << "\n\nTesting pop deqNames: \n";
    while( !deqNames.empty() )
    {
        cout << deqNames.top() << ' ';
        deqNames.pop();
    }
   
    cout << "\n\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: class Vector ... and Stacks and Queues ...
« Reply #7 on: February 29, 2016, 08:01:21 AM »
Now to Queues ...


Code: [Select]
// Queue.h //  // 2016-02-29 //

#ifndef dwQUEUE_H
#define dwQUEUE  _H

#include <iostream>
#include <list>

// default container for stack here is std::list < T > //
template < typename T, typename Container = std::list < T > >
class Queue
{
public:
    void push_back( const T& obj ) { que.push_back( obj ); }
   
    /////////  NOTE! *NO* bounds checking is done here /////
    const T& back() const { return que.back(); }
    T& back() { return que.back(); }
   
    const T& front() const { return que.front(); }
    T& front() { return que.front(); }
   
    void pop_front() { que.pop_front(); }
    ////////////////////////////////////////////////////////
   
    size_t size() const { return que.size(); }
    bool empty() const { return que.empty(); }

private:
    Container que;
} ;

#endif


And a little test program ...


Code: [Select]
// test_Queue.h.cpp //  // 2016-02-13  //


#include "Queue.h"

#include <iostream> // included above //
#include <string>
#include <deque> // a double ended queue //



int main()
{
    using namespace std;

    const string names[] = { "Andy", "Bill", "Jill", "Lucy", "Marie", "Sam", "Sharon", "Zoe" };
    const int num_names = sizeof names / sizeof *names;

   
    // Note C++ list is a double_link linked list ...
    // so has push_back and pop_back and back methods all implemented ok //
    Queue < string > lstNames; // here, using default list container inside the class Queue //

    for( int i = 0; i < num_names; ++ i ) lstNames.push_back( names[i] );

    cout << "\n\nTesting pop_front lstNames: \n";
    while( !lstNames.empty() )
    {
        cout << lstNames.front() << ' ';
        lstNames.pop_front();
    }
   
   
    // here, using a deque container inside the class Queue //
   
    Queue < string, deque< string > > deqNames;

    for( int i = 0; i < num_names; ++ i ) deqNames.push_back( names[i] );

    cout << "\n\nTesting pop_front deqNames: \n";
    while( !deqNames.empty() )
    {
        cout << deqNames.front() << ' ';
        deqNames.pop_front();
    }
   
    cout << "\n\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}


« Last Edit: February 29, 2016, 08:04:11 AM by David »