Question

C++ You are going to implement your own vector class. Actually, we are using the following small and simplified subset of the interface from std::vector to keep things manageable:

template class DiyVector{
    public:
        DiyVector();
        ~DiyVector();

        T& at(unsigned int index) const;
        // item at index
        // throws OutOfRange

        unsigned int size() const;
        // number of items in the vector

        void pushBack(const T& item);
        // append item at the end of vector

        void popBack();
        // remove item at the end of vector
        // throws OutOfRange

        void erase(unsigned int index);
        // remove element at index
        // throws OutOfRange

        void insert(unsigned int index, const T& item);
        // insert item before element at index, with:
        // 0 <= index <= size()
        // throws OutOfRange

        class OutOfRange{};

    private:

        // your implementation goes here!
};
Your DiyVector will store items of type T in an array that is dynamically allocated on the heap, using new[].

We only expand this array, but never shrink it:

when adding an item (using pushBack or insert), if there is no currently unused element in the array, create a new array, able to hold one more element, and copy over the old items. Of course, you delete[] the old, too-short array afterwards.

when deleting an item (using popBack or erase), you simply "pack" the array by copying all items behind the erased one to close the gap (and adjust the bookkeeping of used elements). Later, when a new item is to be added (using pushBack or insert), you re-use an old space at the end of the array, instead of creating a whole new array.

Your program must not use any item storage but arrays that are created by new[]. (No statically created arrays, no vectors, no other container classes from std::)

You deliver your DiyVector as a header file called diyvector.h.

It will be automatically tested by the following program( create a seperate file named vector-tester.cpp using code below) :

#include

#include "diyvector.h"

class TestFailed{

public:

TestFailed(int seq){

sequenceNumber = seq;

}

int sequenceNumber;

};

int testNumber = 0;

#define check(CALL) { testNumber++; if ( !(CALL) ) throw TestFailed(testNumber); }

#define checkException(CALL){ \

testNumber++; \

bool exceptionRaised = false; \

try{ \

CALL; \

}catch(DiyVector::OutOfRange& o){ \

exceptionRaised = true; \

} \

if ( !exceptionRaised ) throw TestFailed(testNumber); \

}

int main(){

try{

DiyVector v;

check(v.size() == 0); // test 1

checkException(v.at(0));

v.pushBack(42);

check(v.size() == 1);

check(v.at(0) == 42);

checkException(v.at(1)); // test 5

v.pushBack(43);

check(v.size() == 2);

check(v.at(1) == 43);

check(v.at(0) == 42);

v.popBack();

v.popBack();

check(v.size()==0);

checkException(v.popBack()); // test 10

v.pushBack(142);

v.pushBack(143);

v.pushBack(144);

check(v.size()==3);

check(v.at(0)==142);

check(v.at(1)==143);

check(v.at(2)==144);

checkException(v.at(3)); // test 15

v.at(0) = 17;

check(v.at(0)==17);

checkException(v.erase(3));

checkException(v.erase(42));

v.erase(1);

check(v.size()==2);

check(v.at(0)==17); // test 20

check(v.at(1)==144);

v.pushBack('A');

v.pushBack('B');

check(v.size()==4);

check(v.at(2)==65);

check(v.at(3)==66);

v.insert(2, 22);

check(v.at(0)==17); // test 25

check(v.at(1)==144);

check(v.at(2)==22);

check(v.at(3)==65);

check(v.at(4)==66);

check(v.size()==5); // test 30

DiyVector v2;

v2.insert(0,42);

v2.pushBack(11);

v2.insert(0,44);

check(v2.size()==3);

check(v2.at(0)==44);

check(v2.at(1)==42);

check(v2.at(2)==11);

v2.popBack();

v2.insert(0,99);

check(v2.size()==3); // test 35

check(v2.at(0)==99);

check(v2.at(1)==44);

check(v2.at(2)==42);

DiyVector v3;

v3.pushBack(1);

v3.erase(0);

checkException(v3.at(0));

check(v3.size()==0); // test 40

checkException(v3.insert(1,-5));

check(v3.size()==0); // test 42

std::cout << "All tests passed!\n";

}

catch(TestFailed& tf){

std::cerr << "Test number " << tf.sequenceNumber << " failed.\n";

return 1;

}

catch(...){

std::cerr << "an unexpected exception occured\n";

std::cerr << "Tests passed so far: " << testNumber << std::endl;

return 2;

}

return 0;

}

Answer 1

// diyvector.h

#ifndef DIYVECTOR_H_
#define DIYVECTOR_H_

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

T& at(unsigned int index) const;
// item at index
// throws OutOfRange

unsigned int size() const;
// number of items in the vector

void pushBack(const T& item);
// append item at the end of vector

void popBack();
// remove item at the end of vector
// throws OutOfRange

void erase(unsigned int index);
// remove element at index
// throws OutOfRange

void insert(unsigned int index, const T& item);
// insert item before element at index, with:
// 0 <= index <= size()
// throws OutOfRange

class OutOfRange{};

private:
unsigned int numElements;
unsigned int maxSize;
T *arr;
};

/// default constructor to create an empty vector
template <class T>
DiyVector<T>::DiyVector()
{
   arr = nullptr; // set arr to nullptr
   numElements = 0; // set current number of elements to 0
   maxSize = 0; // set maximum size of arr to 0
}

// destructor to delete the release the memory of the vector
template <class T>
DiyVector<T>::~DiyVector()
{
   // if arr is not null, delete the pointer
   if(arr != nullptr)
       delete arr;
}

// item at index
// throws OutOfRange
template <class T>
T& DiyVector<T>::at(unsigned int index) const
{
   // if valid index, return the element at index
   if(index >=0 && index < numElements)
       return arr[index];
   else // else throw OutOfRange exception
       throw OutOfRange();
}

// number of items in the vector
template <class T>
unsigned int DiyVector<T>:: size() const
{
   return numElements;
}

// append item at the end of vector
template <class T>
void DiyVector<T>::pushBack(const T& item)
{
   // if arr is null or vector is full
   if(arr == nullptr || numElements == maxSize)
   {
       // expand the array
       maxSize = maxSize + 1;
       T *temp = new T[maxSize];
       for(int i=0;i<numElements;i++)
           temp[i] = arr[i];
       if(arr != nullptr)
           delete arr;
       arr = temp;
   }

   // add the item at the end
   arr[numElements] = item;
   numElements++; // increment the size of vector
}

// remove item at the end of vector
// throws OutOfRange
template <class T>
void DiyVector<T>:: popBack()
{
   // if empty vector, throw OutOfRange exception
   if(numElements == 0)
       throw OutOfRange();
   numElements--; //else decrement the number of items
}

// remove element at index
// throws OutOfRange
template <class T>
void DiyVector<T>:: erase(unsigned int index)
{
   // if valid index, then remove the element at index
   if(index >=0 && index < numElements)
   {
       // shift the elements to the left
       for(int i=index;i<numElements-1;i++)
       {
           arr[i] = arr[i+1];
       }
       numElements--; // decrement the number of elements
   }else // else throw OutOfRange exception
       throw OutOfRange();
}

// insert item before element at index, with:
// 0 <= index <= size()
// throws OutOfRange
template <class T>
void DiyVector<T>:: insert(unsigned int index, const T& item)
{
   // if valid index
   if(index >=0 && index <= numElements)
   {
       // if arr is null or vector is full, expand the vector
       if(arr == nullptr || numElements == maxSize)
       {
           maxSize = maxSize + 1;
           T *temp = new T[maxSize];
           for(int i=0;i<numElements;i++)
               temp[i] = arr[i];
           if(arr != nullptr)
               delete arr;
           arr = temp;
       }

       // loop to shift the elements to the right
       for(int i=numElements;i>index;i--)
       {
           arr[i] = arr[i-1];
       }
       // insert the element at the index
       arr[index] = item;
       numElements++;
    }else // else throw OutOfRange exception
       throw OutOfRange();
}

#endif
//end of diyvector.h

// vector-tester.cpp

#include <iostream>
#include "diyvector.h"
class TestFailed{
public:
TestFailed(int seq){
sequenceNumber = seq;
}
int sequenceNumber;
};
int testNumber = 0;
#define check(CALL) { testNumber++; if ( !(CALL) ) throw TestFailed(testNumber); }
#define checkException(CALL){ \
testNumber++; \
bool exceptionRaised = false; \
try{ \
CALL; \
}catch(DiyVector::OutOfRange& o){ \
exceptionRaised = true; \
} \
if ( !exceptionRaised ) throw TestFailed(testNumber); \
}
int main(){
try{
DiyVector v;
check(v.size() == 0); // test 1
checkException(v.at(0));
v.pushBack(42);
check(v.size() == 1);
check(v.at(0) == 42);
checkException(v.at(1)); // test 5
v.pushBack(43);
check(v.size() == 2);
check(v.at(1) == 43);
check(v.at(0) == 42);
v.popBack();
v.popBack();
check(v.size()==0);
checkException(v.popBack()); // test 10
v.pushBack(142);
v.pushBack(143);
v.pushBack(144);
check(v.size()==3);
check(v.at(0)==142);
check(v.at(1)==143);
check(v.at(2)==144);
checkException(v.at(3)); // test 15
v.at(0) = 17;
check(v.at(0)==17);
checkException(v.erase(3));
checkException(v.erase(42));
v.erase(1);
check(v.size()==2);
check(v.at(0)==17); // test 20
check(v.at(1)==144);
v.pushBack('A');
v.pushBack('B');
check(v.size()==4);
check(v.at(2)==65);
check(v.at(3)==66);
v.insert(2, 22);
check(v.at(0)==17); // test 25
check(v.at(1)==144);
check(v.at(2)==22);
check(v.at(3)==65);
check(v.at(4)==66);
check(v.size()==5); // test 30
DiyVector v2;
v2.insert(0,42);
v2.pushBack(11);
v2.insert(0,44);
check(v2.size()==3);
check(v2.at(0)==44);
check(v2.at(1)==42);
check(v2.at(2)==11);
v2.popBack();
v2.insert(0,99);
check(v2.size()==3); // test 35
check(v2.at(0)==99);
check(v2.at(1)==44);
check(v2.at(2)==42);
DiyVector v3;
v3.pushBack(1);
v3.erase(0);
checkException(v3.at(0));
check(v3.size()==0); // test 40
checkException(v3.insert(1,-5));
check(v3.size()==0); // test 42
std::cout << "All tests passed!\n";
}
catch(TestFailed& tf){
std::cerr << "Test number " << tf.sequenceNumber << " failed.\n";
return 1;
}
catch(...){
std::cerr << "an unexpected exception occured\n";
std::cerr << "Tests passed so far: " << testNumber << std::endl;
return 2;
}
return 0;
}
//end of vector-tester.cpp

Output: