I am relearning data structures while trying to implement them on my own while also trying to get better at C++ as although I have knowledge of C, OOP is still non-inituitive to me.
In this simple Vector implementation, I double the array size if it becomes equal to the capacity and half it when it becomes less than a quarter of the capacity. I have also added the main() function that I used to test. Please let me know how I can improve it and what other functionalities to add to get better at C++.
#include <iostream>
#include <cassert>
const int MIN_CAPACITY = 16;
const int GROWTH_FACTOR = 2;
const int SHRINK_FACTOR = 4;
template <class T>
class Vector {
private:
int _size;
int _capacity;
T * _data;
// Check if resize needed. If yes, do accordingly.
bool resize() {
bool resized = false;
if (_size >= _capacity) {
_capacity *= GROWTH_FACTOR;
resized = true;
} else if (_capacity > MIN_CAPACITY &&
_size <= _capacity / SHRINK_FACTOR) {
_capacity /= GROWTH_FACTOR;
resized = true;
}
if (resized) {
T *tmp = _data;
_data = new T[_capacity];
std::copy(tmp, tmp+_size, _data);
delete [] tmp;
}
return resized;
}
public:
Vector() : _size(0), _capacity(MIN_CAPACITY), _data(new T[MIN_CAPACITY]) {}
// create vector with given initial size and default value.
Vector(int n, T default_val) {
assert (n > 0);
_size = 0;
int capacity = MIN_CAPACITY;
while (capacity < n)
capacity *= GROWTH_FACTOR;
_capacity = capacity;
_data = new T[_capacity];
while (_size < n)
_data[++_size] = default_val;
}
Vector(const Vector& src) : _size(src._size), _capacity(src._capacity) {
_data = new T[_capacity];
std::copy(src._data, src._data + _size, _data);
}
~Vector() {
delete [] _data;
}
int size() const {
return _size;
}
int capacity() const {
return _capacity;
}
void insert(const int index, const T obj) {
assert(index >= 0 && index <= _size);
resize();
for (int i = _size; i > index; --i)
_data[i] = _data[i-1];
_data[index] = obj;
++_size;
}
void push_back(const T obj) {
insert(_size, obj);
}
T erase(const int index) {
assert(index >= 0 && index < _size);
resize();
T tmp = _data[index];
for (int i = index; i < _size-1; ++i)
_data[i] = _data[i+1];
--_size;
return tmp;
}
T pop_back() {
return erase(_size-1);
}
T get(const int index) const {
assert(index >= 0 && index < _size);
return _data[index];
}
void set(const int index, const T obj) {
assert(index >= 0 && index < _size);
_data[index] = obj;
}
void print() {
std::cout << "Size: " << size() << ", Capacity: " <<
capacity() << std::endl;
for (int i = 0; i < size(); ++i)
std::cout << _data[i] << ", ";
std::cout << std::endl;
}
};
int main() {
Vector<int> v;
v.push_back(1000);
v.print();
v.pop_back();
v.print();
for (int i = 0; i < 25; ++i)
v.push_back(i);
v.print();
for (int i = 0; i < 10; ++i)
v.insert(i, i+25);
v.print();
Vector<int> v1 = v;
for (int i = 0; i < 10; ++i)
std::cout << "Popped " << v.pop_back() << std::endl;
v.print();
for (int i = 0; i < 12; ++i)
std::cout << "Erased " << v.erase(i) << " from index " << i << std::endl;
v.print();
std::cout << "Starting element: " << v.get(0) << std::endl;
std::cout << "Ending element: " << v.get(v.size() - 1) << std::endl;
v1.print();
std::cout << "Starting element: " << v1.get(0) << std::endl;
std::cout << "Ending element: " << v1.get(v1.size() - 1) << std::endl;
Vector<char> v2(20, 'a');
v2.print();
for (int i=0; i < 12; ++i)
v2.set(i, 'a'+1+i);
v2.print();
std::cout << "Starting element: " << v2.get(0) << std::endl;
std::cout << "Ending element: " << v2.get(v2.size() - 1) << std::endl;
return 0;
}
std::vector
should still be the default choice, as mentioned at the end of this answer. The cppreference example forerase
, of course, is just a demonstration of its usage; actually removing elements of a vector calls for the erase-remove idiom. \$\endgroup\$if (_size >= _capacity) { _capacity *= GROWTH_FACTOR;
.. it assumes that GROWTH_FACTOR will be sufficient to make capacity bigger than size .. Your ctor does the right thing, but resize doesn't \$\endgroup\$