Vectors are sequence contianers representing arrays that can change in size. The example usage is as follow.
#include <vector> std::vector<int> v; for (int i = 0; i < 5; i++) v.push_back(i); for (int i = 1; i < 5; i++) v[i] += v[i - 1];
Vector is a commonly used STL, it's important to be familiar with the usage of vector. You're recommend to know what is a vector in advance. For more information of vector, you can google it or refer to the link.
In this problem, you are asked to implement a vector.
class Vector { private: value_type **arr_; size_type size_, cap_; public: ~Vector(); Vector(); Vector(const Vector &rhs); Vector &operator=(const Vector &rhs); reference front(); reference back(); reference operator[](size_type pos); const_reference operator[](size_type pos) const; size_type capacity() const; size_type size() const; void clear(); bool empty() const; void erase(size_type pos); void insert(size_type pos, size_type cnt, const_reference val); void pop_back(); void pop_front(); void push_back(const_reference val); void push_front(const_reference val); void reserve(size_type new_capacity); void shrink_to_fit(); };
The main idea that vector can change its size dynamically is because of the preallocation of extra memory spaces to accommodate for growth without the need to reallocate on each insertion.
value_type **arr_; size_type size_, cap_;
So size_ is the size of vector, and cap_ is the capacity of vector which is the size of the storage space currently allocated for the vector. arr_ is a double pointer, it points to the array that stores the pointer that points to the elements in the vector.
~Vector(); Vector(); Vector(const Vector &rhs); Vector &operator=(const Vector &rhs);
The constructor, destructor, copy constructor, assignment operator overload of vector.
reference front(); reference back();
Return the reference to front/back element of the vector.
reference operator[](size_type pos); const_reference operator[](size_type pos) const;
overload the [] operator to access the [pos] elements in vector.
size_type capacity() const; size_type size() const;
Return the size and capacity of the vector.
void clear(); bool empty() const;
clear() removes all elements from the vector and empty return true if the size of vector is 0.
void erase(size_type pos); void insert(size_type pos, size_type cnt, const_reference val);
erase(pos): remove the element at pos.
insert(pos, cnt, val): insert cnt elements which is val at pos. If the pos is equal to size of vector, it represents inserting the elemnt at the end of vector.
For example:
current vector is [7, 1, 2, 3] and insert(2, 3, 4) will cause the vector to becomes [7, 1, 2, 4, 4, 4, 3].
You can assume that the pos in the above two functions are all valid.
void pop_back(); void pop_front(); void push_back(const_reference val); void push_front(const_reference val);
Remove the last/first element from vector and insert val at the begin/end of the vector. You can assume that the program won't pop the element when the vector is empty.
void reserve(size_type new_capacity); void shrink_to_fit();
reserve(new_capacity): If new_capacity is greater than the current capacity, adjust the capacity to new_capacity.
shrink_to_fit(): Reduce the capacity to fits its size.
While inserting elements to the vector, if the capacity of vector is not enought, we often double the size of the capacity. It can let push_back becomes an O(1) amortized operation.
In order to verify the correctness of the implementation, main function will compare your vector with std::vector, if anything goes wrong, it should assert(false) and cause Runtime Error on online judge.
Note:
You're not allowed to modify the code other than the implementation of class Vector.
Please use new/delete, new[]/delete[] to dynamic allcoate the memory, and use at least C++11 to compile the code.
You're encouraged to trace the code to in-depth understand what you have to do.
The random seed of main.cpp.
Output the hash value and "AC" if the program excecutes successfully.