Due 10/06/2023
Educational Objectives: Understanding generic programming and information hiding by developing generic containers; getting familiar with the concept of class template and its usage; using iterators, namespace, and operator overloading; analyzing algorithm complexity.
Statement of Work: Implement a vector class template Vector and its associated iterator. Analyze the complexity of member functions of the developed Vector.
Requirements:
A header file Vector.h is provided, which contains the interface of the vector class template Vector. In addition to data members and member functions of Vector, both iterator and const_iterator are also defined for Vector. The header file also contains a number of global non-class function templates (overloaded operators). You cannot change anything in the Vector.h file.
A driver program test_vector.cpp is also provided. It is used to test your implementation of the vector class template for different data types (it tests Vector<int> and Vector<string>). Similarly, you cannot change anything in the test_vector.cpp file. Note that additional tests will be performed to check your implementation of the Vector class template.
You need to implement the member functions of the vector class template Vector in a file named Vector.hpp. Note that, Vector.hpp has been included in the header file Vector.h (towards the end of the file). As we have discussed in class, you should not try to compile Vector.hpp (or Vector.h). Instead, you should compile the driver program test_driver.cpp to obtain the executable program. You need to implement all the member functions of Vector class template and non-class global overloaded functions operator==(), operator!=(), and operator<<() included in Vector.h. Vector has three member variables, theSize, theCapacity, and array. Member variable theSize records the number of elements currently stored in the vector; theCapacity indicates the maximum number of elements the vector can hold without requesting new memory allocation; and array is a pointer of type T (the memory should be dynamically allocated). The member variable array is used to store elements of the vector. The design of the Vector container closely follows the vector container included in C++/STL, which is also similar to the one presented in the textbook. It is OK for you to adapt the code provided in the textbook. However, you need to note that there are minor differences between the design of the Vector class in this project and the one given given in the textbook. In particular, whenever you need to insert a new element into the vector and the vector is full, you need to double the capacity. If the current capacity is zero, change the new capacity to 1. We describe the requirements of each function in the following.
Member functions of Vector class template:
Vector(): Default zero-parameter constructor. This will create an empty vector with both size and capacity to be zero. You need to initialize the member variables. In particular, you need to assign array to NULL (nullptr for c++11).
Vector(const Vector &rhs): Copy constructor. Create the new vector using elements in existing vector rhs.
Vector(Vector &&rhs): Move constructor.
Vector(int num, const T & val = T()): Construct a Vector with num elements, all initialized with value val. Note that the capacity should also be num.
Vector(const_iterator start, const_iterator end): Construct a Vector with elements from another Vector between start and end. Including the element referred to by the start iterator, but not by the end iterator, that is, the new vector should contain the elements in the range [start, end).
~Vector(): Destructor. You should properly reclaim memory.
operator[](index): Index operator. Return reference to the element at the specified location. No error checking on value of index. Note that there are two versions of the index operator.
operator=(const Vector &rhs): Copy assignment operator
operator=(Vector &&rhs): Move assignment operator
at(index): Return reference to the element at the specified location. Throw "out_of_range" exception if index is not in the valid range [0, theSize). There are two versions of this member function.
front() and back(): Return reference to the first and last element in the vector, respectively. There are two versions of both member functions.
size(): Return the number of elements currently stored in the vector.
capacity(): Return the number of elements that can be stored in the vector without any new memory allocation.
empty(): Return true if no element is in the vector; otherwise, return false.
clear(): Delete all elements in the vector. Memory associated with the vector does not need to be reclaimed.
push_back(): Insert a new object as the last element into the vector.
pop_back(): Delete the last element in the vector.
resize(newSize, newValue): Change the size of the vector to newSize. If newSize is greater than the current size theSize, the new positions in the vector should hold the value newValue. Note that capacity may also be changed accordingly.
reserve(newCapacity): Change the capacity of the vector to newCapacity, if newCapacity is greater than the current capacity of the vector. Otherwise, this function does not change the capacity of the vector.
print(ostream &os, char ofc = ' '): Print all elements in the Vector, using character ofc as the deliminator between elements of the vector.
begin(): Return iterator to the first element in the vector. No error checking is required. There are two versions of this member function.
end(): Return iterator to the end marker of the vector (the position after the last element in the vector). No error checking is required. There are two versions of this member function.
insert(iterator itr, const T & val): Insert value val ahead of the element referred by the iterator itr. All current elements in the vector starting at itr should be pushed back by one position. The return value is the iterator referring to the newly inserted element.
erase(iterator itr): Delete element referred to by itr. The return value is the iterator referring to the element following the deleted element.
erase(iterator start, iterator end): Delete all elements between start and end (including start but not end), that is, all elements in the range [start, end). The return value is the iterator referring to the element following the last element being deleted.
doubleCapacity(): Double the capacity of the vector. If the current capacity is 0, set the new capacity to 1. This is a private member function, which can be used by other member functions such as push_back(). Note that this function can call reserve() member function to do the real work, after calculating the proper capacity value.
Non-class global functions
operator==(const Vector<T> & lhs, const Vector<T> & rhs): Check if two vectors contain the same sequence of elements. Two vectors are equal if they have the same number of elements and the elements at the corresponding position are equal.
operator!=(const Vector<T> & lhs, const Vector<T> & rhs): Opposite of operator==().
operator<<(ostream & os, const Vector<T> & v): Print out all elements in Vector v by calling Vector<T>::print() function.
Write a makefile for your project and name your executable as proj2.x. Your program must be able to compile and run on the linprog machines.
Analyze the worst-case run-time complexity of the member functions empty(), erase(iterator itr), and pop_back() of the Vector. Give the complexity in the form of Big-O. Your analysis must be clearly understandable by others. Name the file containing the complexity analysis as "analysis.txt".
Downloads
Click here to download the tar file, which contains the following files: Vector.h, test_vector.cpp, and proj2.x. The sample executable program proj2.x was compiled on a linprog machine from test_vector.cpp.
Note: The first person to find a programming error in our program will get a bonus point! (There is no known error in the program.)
Deliverables
Turn in files makefile, Vector.hpp, and analysis.txt in a single tar file via the Canvas. If you cannot finish all functions, you must also submit a modified test_vector.cpp (this file must be the original provided test_vector.cpp with some lines commented out) that would allow the executable to be produced to avoid your program being treated as having compiling errors.
Grading
Hints