Custom STL Vector in C++

Question

This is my first time I tried to implement a custom STL vector with iterator. I have some questions:

• What are better ways to write an iterator?
• I know that there is a const iterator so in my case I need to create a second class for iterator? Is there any approachable way to not repeat yourself with second (and others) iterators?
• Why in vector there are a lot of functions which can cause undefined behaviour?

For example : method back and I quote : "Calling back on an empty container is undefined" but why? Why in STL there is no place for exceptions? I read some explanations but it was mainly "c++ it's all about speed", throwing exceptions and making code probably safer is such a big deal (in reference to time?)

Vector.h

#ifndef VECTOR_TEMPLATE_VECTOR_H
#define VECTOR_TEMPLATE_VECTOR_H

#include "Iterator.h"

template<typename DT>
class Vector {
private:
    DT *tab;
    int sizeVector;
    int capacityVector;
public:
    Vector() : tab(nullptr), sizeVector(), capacityVector() {}
    explicit Vector(int size);
    Vector(int size, int value);
    Vector(const std::initializer_list<DT> & v);
    Vector(const Vector<DT> & v);
    Vector(Vector<DT> && v);

    Vector & operator=(const Vector<DT> &v);
    Vector & operator=(Vector<DT> &&v);

    ~Vector();

    bool operator==(const Vector<DT> & v);
    bool operator!=(const Vector<DT> & v);

    int capacity();
    int size();

    void push_back(DT & v);

    void pop_back();

    void swap(Vector & other);

    DT & front();
    const DT & front() const;

    const DT & back() const;
    DT & back();

    DT &operator[](int size);
    const DT &operator[](int size) const;

    void assign(int count, const DT &value);

    void resize(int count);

    friend class Iterator<DT>;
    typedef class Iterator<DT> iterator;

     Iterator<DT> erase(Iterator<DT> pos);
     Iterator<DT> erase(Iterator<DT> first, Iterator<DT> last);
     Iterator<DT> insert(Iterator<DT> pos, const DT & value);
     void insert(iterator pos, int count, const DT & value);

     Iterator<DT> end();
     Iterator<DT> begin();    
};

template<typename DT>
Vector<DT>::Vector(int size) : sizeVector(size), capacityVector(size) {
    tab = new DT[sizeVector];
}

template<typename DT>
Vector<DT>::Vector(int size, int value) : sizeVector(size), capacityVector(size){
    tab = new DT[sizeVector];

    for (int i = 0; i < sizeVector; i++)
        tab[i] = value;
}

template<typename DT>
Vector<DT>::Vector(const std::initializer_list<DT> &v) : sizeVector(v.size()), capacityVector(v.size()) {
    tab = new DT[v.size()];

    for (int i = 0; i < v.size(); i++)
        tab[i] = *(v.begin() + i);
}

template<typename DT>
Vector<DT>::Vector(const Vector<DT> &v) : sizeVector(v.sizeVector), capacityVector(v.capacityVector) {
    tab = new DT[capacityVector];

    for (int i = 0; i < sizeVector; i++)
        tab[i] = v.tab[i];
}

template<typename DT>
Vector<DT>::Vector(Vector<DT> &&v) : sizeVector(v.sizeVector), capacityVector(v.capacityVector) {
    tab = v.tab;
    v.tab = nullptr;
    v.sizeVector = 0;
    v.capacityVector = 0;
}

template<typename DT>
Vector<DT> &Vector<DT>::operator=(const Vector<DT> &v) {
    if (this == &v)
        return *this;

    delete[] tab;
    sizeVector = v.sizeVector;
    capacityVector = v.capacityVector;
    tab = new DT[capacityVector];

    for (int i = 0; i < capacityVector; i++)
        tab[i] = v.tab[i];
}

template<typename DT>
Vector<DT> &Vector<DT>::operator=(Vector<DT> &&v) {
    if (this == &v)
        return *this;

    delete[] tab;
    sizeVector = v.sizeVector;
    capacityVector = v.capacityVector;
    tab = v.tab;
    v.sizeVector = 0;
    v.capacity = 0;
    v.tab = nullptr;

    return *this;
}

template<typename DT>
Vector<DT>::~Vector() {
    delete[] tab;
}

template<typename DT>
bool Vector<DT>::operator==(const Vector<DT> &v) {
    if (sizeVector == v.sizeVector && capacityVector == v.capacityVector) {
        for (int i = 0; i < sizeVector; i++)
            if (tab[i] != v.tab[i])
                return false;
        return true;
    }
    return false;

}

template<typename DT>
bool Vector<DT>::operator!=(const Vector<DT> &v) {
    return !operator==(v);
}

template<typename DT>
int Vector<DT>::capacity() {
    return capacityVector;
}

template<typename DT>
int Vector<DT>::size() {
    return sizeVector;
}

template<typename DT>
void Vector<DT>::push_back(DT &v) {
    if (sizeVector == capacityVector) {
        capacityVector += 5;
        DT *temp = new DT[capacityVector];
        for (int i = 0; i < sizeVector; i++)
            temp[i] = tab[i];

        temp[sizeVector] = v;
        delete[] tab;
        tab = temp;
        size++;
    } else {
        tab[sizeVector] = v;
        size++;
    }
}

template<typename DT>
void Vector<DT>::pop_back() {
    if (sizeVector > 0)
        sizeVector--;
}

template<typename DT>
void Vector<DT>::swap(Vector &other) {
    int tempSize, tempCapacity;
    DT *tempTab;

    tempTab = other.tab;
    tempSize = other.sizeVector;
    tempCapacity = other.capacityVector;

    other.tab = tab;
    other.sizeVector = sizeVector;
    other.capacity = capacityVector;

    sizeVector = tempSize;
    capacityVector = tempCapacity;
    tab = tempTab;
}

template<typename DT>
DT &Vector<DT>::front() {
    if (sizeVector > 0)
        return tab[0];
    else
        throw std::logic_error("Empty container");
}

template<typename DT>
const DT &Vector<DT>::front() const {
    if (sizeVector > 0)
        return tab[0];
    else
        throw std::logic_error("Empty container");
}

template<typename DT>
void Vector<DT>::resize(int count) {
    if (count < 0)
        throw std::length_error();
    else if (count < sizeVector)
        size = count;
    else if (count > capacityVector) {
        DT *tempTab = new DT[count];
        for (int i = 0; i < sizeVector; i++)
            tempTab[i] = tab[i];
        delete[] tab;
        tab = tempTab;
    }
}

template<typename DT>
const DT &Vector<DT>::back() const {
    if (sizeVector == 0)
        throw std::logic_error("Empty");

    return tab[sizeVector - 1];
}

template<typename DT>
DT &Vector<DT>::back() {
    if (sizeVector == 0)
        throw std::logic_error("Empty");

    return tab[sizeVector - 1];
}

template<typename DT>
DT &Vector<DT>::operator[](int size) {
    if (size > sizeVector - 1 || size < 0)
        throw std::out_of_range("Out of scope");
    else
        return tab[size];
}

template<typename DT>
const DT &Vector<DT>::operator[](int size) const {
    if (size > sizeVector - 1 || size < 0)
        throw std::out_of_range("Out of scope");
    else
        return tab[size];
}

template<typename DT>
void Vector<DT>::assign(int count, const DT &value) {
    if (count < 0)
        throw std::out_of_range("Out of scope");

    if (count < capacityVector)
        for (int i = 0; i < count; i++)
            tab[i] = value;
    else if (count >= capacityVector) {
        delete[] tab;
        tab = new DT[count + 5];
        capacityVector = count + 5;
        sizeVector = count;
        for (int i = 0; i < count; i++)
            tab[i] = value;
    }
}

template<typename DT>
Iterator<DT> Vector<DT>::end(){
     Iterator<DT> temp(tab + sizeVector);
    return temp;
}

template<typename DT>
Iterator<DT> Vector<DT>::begin(){
    Iterator<DT> temp(tab);
    return temp;
}

template<typename DT>
Iterator<DT> Vector<DT>::erase(Iterator<DT> pos) {
    int i = 0;
    auto it = (*this).begin();

    for (it; it != pos; it++, i++);

    for (auto it = pos + 1; it != (*this).end(); it++, i++)
        tab[i] = tab[i + 1];

    sizeVector--;
    return pos;
}

template<typename DT>
Iterator<DT> Vector<DT>::erase(Iterator<DT> first, Iterator<DT> last){
    int i = 0;
    int temp = 0;
    auto it = (*this).begin();

    for (it; it != first; it++, i++);
    for (it = first; it != last; it++, temp++, i++);

    for (auto it = last; it != (*this).end(); it++, i++)
        tab[i - temp] = tab[i];

    sizeVector -=  temp;
    return last;
}

template<typename DT>
Iterator<DT> Vector<DT>::insert(Iterator<DT> pos, const DT & value){
    int i = 0;

    if (capacityVector > sizeVector){
        for(Iterator<DT> it = tab + sizeVector; it != pos; it--, i++)
            tab[sizeVector - i] = tab[sizeVector - i - 1];
        *pos = value;
        sizeVector++;
    } else{
        DT * temp = new DT[sizeVector + 1];
            for (Iterator<DT> it = tab; it != pos; it++, i++)
             temp[i] = tab[i];
        temp[i] = value;
        i++;
            for (Iterator<DT> it = tab + i + 1; it != tab + sizeVector + 2; it++, i++)
            temp[i] = tab[i-1];
        delete [] tab;
        tab = temp;
        sizeVector++;
        capacityVector = sizeVector;
    }
}

template<typename DT>
void Vector<DT>::insert(Iterator<DT> pos, int count, const DT & value){
    DT * temp = new DT[sizeVector + count];
    int i = 0, j = 0;

    for (Iterator<DT> it = tab; it != pos; it++, i++)
        temp[i] = tab[i];

    for (j; j < count; j++)
        temp[i+j] = value;

    for (Iterator<DT> it = tab + i; it != tab + sizeVector; it++, i++)
        temp[i+j] = tab[i];

    sizeVector += count;
    capacityVector = sizeVector;
    delete [] tab;
    tab = temp;
}

#endif //VECTOR_TEMPLATE_VECTOR_H

Iterator.h

#ifndef VECTOR_TEMPLATE_ITERATOR_H
#define VECTOR_TEMPLATE_ITERATOR_H

template<typename DT>
class Iterator {
private:
    DT * pointer;
public:
    Iterator(): pointer(nullptr){};
    Iterator(DT * item) : pointer(item){}

    Iterator<DT> & operator=(const Iterator<DT> & iter) = default;
    ~Iterator() = default;

    Iterator operator+(int add);
    Iterator operator-(int sub);

    bool operator!=(const Iterator<DT> & iter) const;
    bool operator==(const Iterator<DT> & iter) const;
    bool operator<(const Iterator<DT> & iter) const;
    bool operator<=(const Iterator<DT> & iter) const;
    bool operator>(const Iterator<DT> & iter) const;
    bool operator>=(const Iterator<DT> & iter) const;

    Iterator & operator++();
    Iterator operator++(int);
    Iterator & operator--();
    Iterator operator--(int);

    DT & operator[](int n);
    DT & operator*();
};

template<typename DT>
bool Iterator<DT>::operator==(const Iterator<DT> & iter) const {
    return pointer == iter.pointer;
}

template<typename DT>
bool Iterator<DT>::operator!=(const Iterator<DT> & iter) const {
    return pointer != iter.pointer;
}

template<typename DT>
bool Iterator<DT>::operator<(const Iterator<DT> & iter) const{
    return pointer < iter.pointer;
}

template<typename DT>
bool Iterator<DT>::operator<=(const Iterator<DT> & iter) const{
    return pointer <= iter.pointer;
}

template<typename DT>
bool Iterator<DT>::operator>(const Iterator<DT> &iter) const {
    return pointer > iter.pointer;
}

template<typename DT>
bool Iterator<DT>::operator>=(const Iterator<DT> &iter) const {
    return pointer >= iter.pointer;
}

template<typename DT>
DT & Iterator<DT>::operator[](int n) {
    return *(pointer + n);
}

template<typename DT>
Iterator<DT> Iterator<DT>::operator+(int add) {
    Iterator<DT> temp(pointer + add);
    return temp;
}

template<typename DT>
Iterator<DT> Iterator<DT>::operator-(int sub){
    Iterator<DT> temp(pointer - sub);
    return temp;
}

template<typename DT>
Iterator<DT> operator+(int add, const Iterator<DT> & iter){
    return iter + add;
}

template<typename DT>
Iterator<DT> & Iterator<DT>::operator++(){
    pointer++;
    return *this;
}

template<typename DT>
Iterator<DT> Iterator<DT>::operator++(int){
    Iterator<DT> temp = *this;
    pointer++;
    return temp;
}

template<typename DT>
Iterator<DT> & Iterator<DT>::operator--(){
    pointer--;
    return *this;
}

template<typename DT>
Iterator<DT> Iterator<DT>::operator--(int){
    Iterator<DT> temp = *this;
    pointer--;
    return temp;
}

template<typename DT>
DT & Iterator<DT>::operator*(){
    return *pointer;
}
#endif //VECTOR_TEMPLATE_ITERATOR_H

Answer 1

Good first try.

Rule of 5 done. Excellent.
The one thing to note is that you should probably mark the move operators as noexcept this will provide extra optimization opportunities to the compiler when your class is used with standard containers (or within classes that are optimized for movable objects). Note: The swap operator is also usually noexcept.

You missed a couple of const functions, though in general you did rather well.

// These should all be const members.
bool operator==(const Vector<DT> & v);
bool operator!=(const Vector<DT> & v);
int capacity();
int size();

Missed moving and emplacing elements into vector:

void push_back(ST&& move);
template<typename... A>
void emplace_back(A&&... args);

Design:

The problem with your vector is that you initialize all the elements in the vector. This has two nasty side effects:

• This means that your template class DT must be default constructible.
• If DT is expensive to construct you are doing wasted work.

The point of capacity. Is that it tracks the number of uninitialized members of the vector. You only construct these members as you use them (thus they can be constructed with parameters) and you don't pay for their construction if you don't need them.

// Allocate memory
char* data = new char[sizof(DT) * capacityVector];

// Add a new element to the end.
DT* location = &(reinterpret_cast<DT*>(data)[sizeVector]);
new (location) DT(copy);
++sizeVector;

// Remove an element from the end.
DT* location = &(reinterpret_cast<DT*>(data)[sizeVector-1]);
location->~DT();
--sizeVector;

Code Review

Issues:

Your copy assignment is not exception safe. The general rule is that you should not release your resources until you have the replacement ready. Then you should swap the resources.

template<typename DT>
Vector<DT> &Vector<DT>::operator=(const Vector<DT> &v) {
    if (this == &v)
        return *this;

    delete[] tab;

    // What happens if there is an exception after this point?
    // If the following `new` throws a Bad Alloc this object is
    // left in a bad state with (the tab pointer is currently bad).

    sizeVector = v.sizeVector;
    capacityVector = v.capacityVector;
    tab = new DT[capacityVector];

    for (int i = 0; i < capacityVector; i++)
        tab[i] = v.tab[i];

    // you forgot the return
    return *this;
}

You should write it like this:

template<typename DT>
Vector<DT> &Vector<DT>::operator=(const Vector<DT> &v) {
    if (this == &v)
        return *this;

    int newSizeVector     = v.sizeVector;
    int newCapacityVector = v.capacityVector;
    DT* newTab            = new DT[capacityVector];

    for (int i = 0; i < newCapacityVector; i++)
        newTab[i] = v.tab[i];

    // You have now done all the dangerious work.
    // so swap the state in an excetion safe way.

    swap(newSizeVector,     sizeVector);
    swap(newCapacityVector, capacityVector);
    swap(newTab,            tab);

    // Now you can release the resources safely.
    delete[] newTab;

    return *this;
}

But this is all done much tidier when you use the copy and swap Idiom. The constructor/destructor of the temp object handles or the resource management for you.

template<typename DT>
Vector<DT> &Vector<DT>::operator=(const Vector<DT> &v) {

    Vector<DT> copy(v);
    copy.swap(*this);
    return *this;
}

Simplify

The move operators are usually just implemented as swap operations. This delays destruction until the moved object is destroyed which is a potentiall optimization if it is not destroyed but re-used.

template<typename DT>
Vector<DT>::Vector(Vector<DT> &&v)
    : sizeVector(v.sizeVector)
    , capacityVector(v.capacityVector)
{
    tab = v.tab;       // Not sure why you did this in the body 
                       // and the other two in the initializer list.
    v.tab = nullptr;
    v.sizeVector = 0;
    v.capacityVector = 0;
}
// Simpler to write as:
template<typename DT>
Vector<DT>::Vector(Vector<DT> &&v)
    : sizeVector(0)
    , capacityVector(0)
    , tab(nullptr)
{
    v.swap(*this);
}


template<typename DT>
Vector<DT> &Vector<DT>::operator=(Vector<DT> &&v) {
    v.swap(*this);    
    return *this;
}

Swap

There is already a standard swap function. You should use it (like any standard algorithm when you can). It will simplify your code and express intent much more clearly.

template<typename DT>
void Vector<DT>::swap(Vector &other) {
    int tempSize, tempCapacity;
    DT *tempTab;

    tempTab = other.tab;
    tempSize = other.sizeVector;
    tempCapacity = other.capacityVector;

    other.tab = tab;
    other.sizeVector = sizeVector;
    other.capacity = capacityVector;

    sizeVector = tempSize;
    capacityVector = tempCapacity;
    tab = tempTab;
}

// Simpler as:
template<typename DT>
void Vector<DT>::swap(Vector &other) noexcept {
    using std::swap;
    swap(tab,           other.tab);
    swap(sizeVector,    other.sizeVector);
    swap(capacityVector,other.capacityVector);
}

Question

What are better ways to write an iterator?

I think your iterator is basically fine. Though to make them work correctly with the iterator traits you should define the following type members:

difference_type
value_type
pointer
reference
iterator_category

I know that there is a const iterator so in my case I need to create a second class for iterator? Is there any approachable way to not repeat yourself with second (and others) iterators?

Yes you can either do some work with templatizing the iterator and then defining a const and a non const version from that. Or you can define the base class that knows all the iterator movements and then have two derived types that provide the accesses interface (one class is for const the other non cost interface).

Why in vector there are a lot of functions which can cause undefined behaviour?

Because in C++ they don't want the library to do extra work.

So the call to back() could do extra work and test if the object is empty and throw an exception if it is. Let assume that is the way it works for a second.

In my code I have designed the code well and know that the back() method is never called if the object is empty. So the test to check for empty inside back() is slowing my code down. So I am having to pay for an extra check just because you as a beginner need.

The C++ community thought that this was a high price. So they said it is the responsibility of the user of the object to test and pay the price. So that people that know what they are doing don't have to pay the price all the time but only when they need to.

So the API is: If you call this when it is not in the correct state your code is broken and the result is unspecified.

For example : method back and I quote : "Calling back on an empty container is undefined" but why?

That's a perfectly good design decision. It is just not the same decision that was made for the standard library.

Why in STL there is no place for exceptions?

They did not want to pay the price. So they provided the code that allows you to test the state before use so you can make sure you use it in the correct state.

I read some explanations but it was mainly "c++ it's all about speed", throwing exceptions and making code probably safer is such a big deal (in reference to time?)

• It is about speed.
• But it is also why should I pay a price that and use training wheels. I know how to use the interface correctly and don't get it wrong. So I should not be forced to pay a price to accommodate the amateur.

Self Promo

I wrote a couple of articles about doing this.

• Resource Management
• Copy and Swap
• Resize
• Simple Optimizations
• Other Stuff

Answer 2

I agree with what @LokiAstari wrote. However, some other points I found:

Variable names

DT *tab;
int sizeVector;
int capacityVector;

These variable names are not very clear. What is tab? Is it a tab character, or a table? I guess it is a pointer to the actual memory that you reserve for the vector. Maybe storage is clearer.

Then you have sizeVector and capacityVector. The suffix Vector is not very clear. These variables are not vectors themselves. I understand that you could not name them size or capacity, because those are already functions. In this case, it's best to follow some convention to mark these variables as private ones, like prefixing them with an underscore: _size and _capacity.

Try to minimize nesting of if-statements

There are some opportunities to reduce the level of nesting in your code. For example:

template<typename DT>
bool Vector<DT>::operator==(const Vector<DT> &v) {
    if (sizeVector == v.sizeVector && capacityVector == v.capacityVector) {
        for (int i = 0; i < sizeVector; i++)
            if (tab[i] != v.tab[i])
               return false;
        return true;
    }
    return false;
}

This can be rewritten as:

template<typename DT>
bool Vector<DT>::operator==(const Vector<DT> &v) {
    if (sizeVector != v.sizeVector || capacityVector != v.capacityVector)
        return false;

   for (int i = 0; i < sizeVector; i++)
        if (tab[i] != v.tab[i])
            return false;

    return true;
}