Since we would like to store any type of object in the our vector container we use a parametric type. Also we must distinguish between the size and capacity of the vector. The first denotes the number of elements and the second denotes the total capacity. Internally the vector uses a dynamic array to store the objects.
template<typename T>
class vector {
int _size, _capacity;
T* _data;
Most STL algorithms assume that a container has value_type otherwise we have no need for it
public:
using value_type= T;
vector iterator inner class.
class iterator {
T* p;
public:
iterator() :p(nullptr) {}
iterator(T* q) :p(q) {}
bool operator!=(iterator rhs) {
return p != rhs.p;
}
iterator operator++() {
p++;
return *this;
}
iterator operator++(int d) {
p++;
return *this;
}
iterator operator--() {
p--;
return *this;
}
iterator operator--(int d) {
p--;
return *this;
}
iterator operator+(size_t off) {
return iterator(p + off);
}
iterator operator-(size_t off) {
return iterator(p - off);
}
T& operator*() {
return *p;
}
T* operator->() {
return p;
}
friend vector<T>;
};
Constructors.
vector() :_size(0), _capacity(0),_data(nullptr) {}
vector(int c) :_size(c), _capacity(c),_data(nullptr) {
//create space for and initialize c elements
_data = (value_type*)operator new (_size*sizeof(value_type));
for (int i = 0; i < _size; ++i)
new (_data + i) value_type{};
}
Copy constructor
vector(const vector& rhs) {
_size = rhs._size;
_capacity = rhs._capacity;
_data = (value_type*)operator new (_capacity * sizeof(value_type));
for (int i = 0; i < _size; i++)
new (_data+i) value_type( rhs._data[i]);
}
Preallocate enough memory. Note that we are using the operator new operator which is not the same as new.
void resize() {
value_type* old = _data;
_capacity *= 2;
_data = (value_type*) operator new (sizeof(value_type) * _capacity);
for (int i = 0; i < _size; ++i) {
new (_data + i) value_type(std::move(old[i]));
}
for(int i=0;i<_size;++i)
old[i].~value_type();
operator delete (old);
}
Assignment operator.
vector& operator=(const vector& rhs) {
for (int i = 0; i < _size; ++i)
_data[i].~value_type();
operator delete (_data);
_size = rhs._size;
_capacity = rhs._capacity;
_data = (value_type *) operator new (sizeof(value_type) *_capacity);
for (int i = 0; i < _size; ++i) {
new (_data + i) value_type(rhs[i]);
}
return *this;
}
void push_back(T val) {
if (_capacity == 0) {
_data = (value_type *)operator new (sizeof(value_type));
_capacity = 1;
}
else if (_size == _capacity) {
resize();
}
new (_data+_size) value_type( std::move(val));
_size++;
}
template<typename ...Ts>
value_type& emplace_back(Ts&& ...args) {
if (_capacity == 0) {
_data =(value_type *) operator new (sizeof(value_type));
_capacity = 1;
}
else if (_size == _capacity) {
resize();
}
new (_data + _size) value_type(args...);
_size++;
return _data[_size - 1];
}
~vector() {
for (int i = 0; i < _size; ++i) {
_data[i].~value_type();
}
operator delete (_data);
}
int size() {
return _size;
}
int capacity() {
return _capacity;
}
iterator begin() noexcept {
return iterator(_data);
}
iterator end() noexcept {
return iterator(_data + _size);
}
insert at arbitrary position because it invalidates the input itr p we should be careful when we resize. This is why we save the offset from the beginning of the data @param p (iterator) position to in @param val value to insert @return an iterator to the inserted elt
iterator insert(iterator p,T val) {
auto offset = p.p - _data;
if (_size == _capacity) {
resize();
}
iterator q(_data + offset);
for (iterator itr =begin()+_size; itr != q; --itr) {
*itr = *(itr - 1);
}
*q = val;
_size++;
return q;
}
T& operator[](int idx) const noexcept {
return _data[idx];
}
};