Desktop Programming > C/C++ & Visual C++
class Vector ... and Stacks and Queues ...
David:
Update: FREE homework help NOW available ...
You can contact me via:
http://sites.google.com/site/andeveryeyeshallseehim/home/he-comes
http://developers-heaven.net/forum/index.php/topic,2587.0.html
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: ---// 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
--- End code ---
David:
And now, a little demo / test program for class Vector ...
--- Code: ---// 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();
}
--- End code ---
David:
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: ---// 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 !!!
*/
--- End code ---
David:
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: ---// 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
--- End code ---
Then ... a little program to test it out ...
--- Code: ---// 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();
}
--- End code ---
David:
Then see the very few changes to re-code as a class ...
Firstly the .h file ...
--- Code: ---// 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
--- End code ---
Then a little test program ...
--- Code: ---// 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();
}
--- End code ---
Navigation
[0] Message Index
[#] Next page
Go to full version