3
\$\begingroup\$

I just started studying data structures and being the std::vector the container that I most use in C++ I decide to try to implement it mimicking its behavior the best I could.

#ifndef VECTOR_H_INCLUDED
#define VECTOR_H_INCLUDED

template<typename T>
class Vector
{
    T* values;
    size_t  v_size;
    size_t  v_capacity;

public:

    using iterator = T*;
    using const_iterator = const T*;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    Vector();
    Vector(size_t sz);
    Vector(size_t sz, const T& v );
    Vector(const std::initializer_list<T>& i_list );
    Vector(const Vector&);
    Vector(const Vector&&);

    ~Vector()
    {
        delete [ ]  values;
    }

    Vector<T>& operator=(Vector<T>);
    Vector<T>& operator=(Vector<T>&&) noexcept;

    // element access
    const T& front() const;
    T& front(); // actually I don't see why would we need this function to be a reference, I think it should be only a const reference, any insight?
    const T& back() const;
    T& back();
    T& operator[ ](size_t i);
    const T& operator[ ](size_t i) const;
    T& at(size_t i);
    const T& at(size_t i) const;
    constexpr T* data() noexcept;
    constexpr const T* data() const noexcept;

    // iterators
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;
    const_iterator cbegin() const noexcept;
    const_iterator  cend() const;
    reverse_iterator rbegin() noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator crend() const noexcept;

    // Modifiers
    template<typename... ARGS>
    void emplace_back(ARGS&&... args); // since C++17 the std::vector::emplace_back() function type is a reference T&, why is that? what does this change brings to the table?
    template<typename... ARGS>
    iterator emplace(const T* pos, ARGS&&... args);
    iterator insert(iterator pos, const T& v );
    iterator insert(const_iterator pos, const T& v );
    iterator insert(const_iterator pos, T&& v );
    void insert(iterator pos, size_t n, const T& v );
    iterator insert(const_iterator pos, size_t n, const T& v );
    void push_back(const T& v);
    void push_back(T&& v);
    void pop_back();
    iterator erase( const_iterator pos );
    iterator erase( iterator first, iterator last );
    void clear() noexcept;
    void resize(size_t n);
    void resize(size_t n, const T& v);


    // capacity
    int size() const noexcept;
    int capacity() const noexcept;
    constexpr bool empty() const noexcept;
    void reserve(size_t n);
    void shrink_to_fit();

    // Non-Member Functions
    template<typename H> friend bool operator==(const Vector<H>& lhs, const Vector<H>& rhs);

    // see https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    friend void swap(Vector& first, Vector& second)
    {
        using std::swap;

        swap(first.v_size, second.v_size);
        swap(first.v_capacity, second.v_capacity);
        swap(first.values, second.values);
    }

private:
    bool ctor_initialized = false;
    void reallocate();
};

template<typename T>
inline Vector<T>::Vector()
{
    v_size = 0;
    v_capacity = 0;
    values = nullptr;
}

template<typename T>
inline Vector<T>::Vector(size_t sz)
{
    ctor_initialized = true;

    v_size = sz;
    v_capacity = sz;

    values = new T[v_capacity];

    for(int i = 0; i < sz; ++i)
        values[ i ] = T();
}

template<typename T>
inline Vector<T>::Vector(size_t sz, const T& v)
{
    ctor_initialized = true;

    v_size = sz;
    v_capacity = sz;

    values = new T[v_capacity];

    for(int i = 0; i < sz; ++i)
        values[ i ] = v;
}

template<typename T>
inline Vector<T>::Vector(const std::initializer_list<T>& i_list)
{
    int sz = i_list.size();

    v_size = sz;
    v_capacity = sz;

    values = new T[v_capacity];

    for(auto iter = i_list.begin(), i = 0; iter != i_list.end(); ++i, ++iter)
        values[ i ] = *iter;
}

template<typename T>
inline Vector<T>::Vector(const Vector<T>& src) : v_size(src.v_size), v_capacity(src.v_capacity),
    values(new T[v_capacity])
{
    for(int i = 0; i < v_size; ++i)
        values[ i ] = src.values[ i ];
}

template<typename T>
inline Vector<T>& Vector<T>::operator=(Vector<T> src)
{
    swap(*this, src);

    return *this;
}

template<typename T>
inline Vector<T>::Vector(const Vector<T>&& mv)
{
    swap(*this, mv);
}

template<typename T>
inline Vector<T>& Vector<T>::operator=(Vector<T>&& mv) noexcept
{
    swap(*this, mv);

    return *this;
}

template<typename T>
inline const T& Vector<T>::back() const
{
    return values[v_size - 1];
}

template<typename T>
inline T& Vector<T>::back()
{
    return values[v_size - 1];
}

template<typename T>
inline const T& Vector<T>::front() const
{
    return values[0];
}

template<typename T>
inline T& Vector<T>::front()
{
    return values[0];
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::begin() noexcept
{
    return values;
}

template<typename T>
inline typename Vector<T>::const_iterator Vector<T>::begin() const noexcept
{
    return values;
}

template<typename T>
inline typename Vector<T>::iterator  Vector<T>::end() noexcept
{
    return values + v_size;
}

template<typename T>
inline typename Vector<T>::const_iterator  Vector<T>::end() const noexcept
{
    return values + v_size;
}

template<typename T>
inline typename Vector<T>::const_iterator Vector<T>::cbegin() const noexcept
{
    return values;
}

template<typename T>
inline typename Vector<T>::const_iterator  Vector<T>::cend() const
{
    return values + v_size;
}

template<typename T>
inline typename Vector<T>::reverse_iterator Vector<T>::rbegin() noexcept
{
    return reverse_iterator(end());
}

template<typename T>
inline typename Vector<T>::reverse_iterator Vector<T>::rend() noexcept
{
    return reverse_iterator(begin());
}

template<typename T>
inline typename Vector<T>::const_reverse_iterator Vector<T>::crbegin() const noexcept
{
    return rbegin();
}

template<typename T>
inline typename Vector<T>::const_reverse_iterator Vector<T>::crend() const noexcept
{
    return rend();
}

template<typename T>
inline T& Vector<T>::operator[ ] (size_t i)
{
    return values[ i ];
}

template<typename T>
inline T& Vector<T>::at (size_t i)
{
    if(i >= v_size)
        throw std::runtime_error("out of range exception");
    else
        return values[ i ];
}

template<typename T>
inline const T& Vector<T>::operator[ ] (size_t i) const
{
    return values[ i ];
}

template<typename T>
inline const T& Vector<T>::at (size_t i) const
{
    if(i >= v_size)
        throw std::runtime_error("out of range exception");
    else
        return values[ i ];
}

template<typename T>
inline constexpr T* Vector<T>::data() noexcept
{
    return values;
}

template<typename T>
inline constexpr const T* Vector<T>::data() const noexcept
{
    return values;
}

template<typename T>
template<typename... ARGS>
void Vector<T>::emplace_back(ARGS&&... args)
{
    if(v_size == v_capacity)
    {
        if(ctor_initialized)
            v_capacity *= 2;
        else
        {
            if (v_size == 0)
                v_capacity = 1;
            else if(v_size < 8)
                v_capacity++;
            else if (v_size >= 8)
                v_capacity *= 2;
        }

        reallocate();
    }

    values[v_size++] = std::move(T(std::forward<ARGS>(args)...));
}

template<typename T>
template<typename... ARGS>
inline typename Vector<T>::iterator Vector<T>::emplace(const T* pos, ARGS&&... args)
{
    // I found a lot of examples implementing this function but they were confusing so I came up with this, is this ok?

    const size_t dist = pos - begin();

    if(dist == v_capacity)
    {
        emplace_back(T(std::forward<T>(args)...));
    }
    else
    {
        if(v_size == v_capacity)
        {
            v_capacity *= 2;

            reallocate();
        }

        std::move_backward(begin() + dist, end(), end() + 1);

        iterator iter = &values[dist];

        *iter = std::move(T(std::forward<ARGS>(args)...));

        ++v_size;

        return iter;
    }
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(iterator pos, const T& v )
{
    emplace(pos, v);
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator pos, const T& v )
{
    emplace(pos, v);
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator pos, T&& v )
{
    emplace(pos, std::forward<T>(v));
}

template<typename T>
void Vector<T>::insert(iterator pos, size_t n, const T& v )
{
    const size_t dist = pos - begin();

    if(v_size + n > v_capacity)
    {
        v_capacity *= 2;

        reallocate();
    }

    std::move_backward(begin() + dist, end(), end() + n);

    for(int i = dist; i < dist + n; ++i)
        values[ i ] = v;

    v_size += n;
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator pos, size_t n, const T& v )
{
    const size_t dist = pos - begin();

    if(v_size + n > v_capacity)
    {
        v_capacity *= 2;

        reallocate();
    }

    T* iter = &values[dist];

    std::move_backward(begin() + dist, end(), end() + n);

    for(int i = dist; i < dist + n; ++i)
        *iter++ = v;

    v_size += n;

    return &values[dist];
}

template<typename T>
inline void Vector<T>::push_back(const T& v)
{
    emplace_back(v);
}

template<typename T>
inline void Vector<T>::push_back(T&& v)
{
    emplace_back(std::forward<T>(v));
}

template<typename T>
inline void Vector<T>::pop_back()
{
    --v_size;

    // what if I use this below, what would be happening and what would be the difference??
    /*   values[--v_size].~T(); */
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::erase( const_iterator pos )
{
    /* I cloud use other implementation of this function that is
      pretty shorter than this but I chose this one that I camne up with, is this ok? */

    /*The reason why I chose this is because when I triy erasing on empty Vector and it doesn't
     crash like the std::vector, instead it just doesn't do anything and neither does it crach
     when you pass an iterator that is out of range. Not sure if this is good or bad. Any insight? */

    const size_t dist = pos - begin();

    if(v_size != 0)
        --v_size;

    int inc;
    for(inc = 2; v_size > pow(2, inc); ++inc);

    if(v_size == 0)
        v_capacity = 0;
    else
        v_capacity = pow(2, inc);

    if(v_capacity != 0)
    {
        T* temp = new T[v_capacity];

        for(int i = 0, j = 0; j <= v_size; ++j)
        {
            if(j != dist)
                temp[ i++ ] = values[ j ];
        }

        delete [ ] values;
        values = temp;
    }

    return &values[ dist ];
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::erase(  iterator first, iterator last )
{
    const size_t n = last - first;

    std::move(last, end(), first);

    v_size -= n;
}

template<typename T>
inline void  Vector<T>::clear() noexcept
{
    v_size = 0;
}

template<typename T>
inline void Vector<T>::shrink_to_fit()
{
    v_capacity = v_size;
    reallocate();
}

template<typename T>
inline void Vector<T>::reserve(size_t n)
{
    if (n > v_capacity)
    {
        v_capacity = n;
        reallocate();
    }
}

template<typename T>
inline void Vector<T>::resize(size_t n)
{
    if(n > v_capacity)
    {
        ctor_initialized = true;

        v_capacity = n;
        reallocate();
    }

    v_size = n;
}

template<typename T>
inline void Vector<T>::resize(size_t n, const T& v)
{
    if(n > v_capacity)
    {
        ctor_initialized = true;

        v_capacity = n;
        reallocate();
    }

    if(n > v_size)
    {
        for(int i = v_size; i < n; ++i)
            values[ i ] = v;
    }

    v_size = n;
}

template<typename T>
inline int  Vector<T>::size() const noexcept
{
    return v_size;
}

template<typename T>
inline int  Vector<T>::capacity() const noexcept
{
    return v_capacity;
}

template<typename T>
inline constexpr bool  Vector<T>:: empty() const noexcept
{
    return begin() == end();
}

template<typename T>
inline void Vector<T>::reallocate()
{
    T* temp = new T[ v_capacity ];

    for(int i = 0; i < v_size; ++i)
        temp[ i ] = values[ i ];

    delete[ ] values;
    values = temp;
}

template<typename H>
inline bool operator==(const Vector<H>& lhs, const Vector<H>& rhs)
{
    if(lhs.v_size != rhs.v_size)
        return false;

    for(int i = 0; i < lhs.v_size; ++i)
        if(lhs.values[ i ] != rhs.values[ i ])
            return false;

    return true;
}

#endif // VECTOR_H_INCLUDED
```
\$\endgroup\$
2
  • \$\begingroup\$ @M.Winter it is supposed to construct those elements even though it is not used, malloc is plain C and new should be used instead unless there is a strong reason not to, in this case I think there isn't. \$\endgroup\$
    – HBatalha
    Apr 14, 2020 at 16:46
  • \$\begingroup\$ @M.Winter Maybe there is strong reason to but as said the idea is to mimic the std::vector,. "static_cast<T*>(new char[sizeof(T) * v_capacity])", I don't understand this code (what is this char), could you please explain? \$\endgroup\$
    – HBatalha
    Apr 14, 2020 at 18:07

4 Answers 4

5
\$\begingroup\$

I'll answer some of the questions in your code comments.


T& front(); // actually I don't see why would we need this function to be
            // a reference, I think it should be only a const reference,
            // any insight?

This is the non-const version of front(), so it should allow the vector to be modified in some way. This method returns a non-const reference so that the item at the front can be modified.

std::vector<int> numbers;
numbers.push_back(2);
numbers.front() += 10;

The last line would not be possible if front() returned a const reference.


template<typename... ARGS>
void emplace_back(ARGS&&... args); // since C++17 the std::vector::emplace_back()
                                   // function type is a reference T&, why is
                                   // that? what does this change brings to the
                                   // table?

This change was for the convenience of the programmer. Emplace methods take arguments to a constructor, but the constructed object was not immediately accessible. So, programmers would have to do the following to get the just-constructed object:

things.emplace_back(arg1, arg2, arg3);
auto& last_thing = things.back(); // or, constantly type things.back()

Now, this can be reduced to a single line.

auto& last_thing = things.emplace_back(arg1, arg2, arg3);

I've seen some people say that returning void was a feature. The reason for this being that references to items contained in a vector are invalidated when the vector is reallocated (e.g., calling push_back() when size() == capacity()), so the returned reference can be fragile if not tracked carefully.


template<typename T>
inline void Vector<T>::pop_back()
{
    --v_size;

    // what if I use this below, what would be happening and what would be the difference??
    /*   values[--v_size].~T(); */
}

If you call the commented version of pop_back() and then the vector goes out of scope, the destructor of the vector element will be called again on the same item, most likely crashing your program. The delete [] values; calls the destructor of each of the items in the vector.


// see https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

The copy-and-swap idiom is great when you want the strong exception guarantee: if assignment fails, no data is changed. It's as if the assignment was never attempted. There is a trade-off. Because of the copy required by this idiom, it is slower and there are optimizations that cannot be done by the compiler. This is just a reminder to think about what your code needs before automatically picking a common practice.

For example:

template<typename T>
inline Vector<T>& Vector<T>::operator=(Vector<T> src)
{
    swap(*this, src);

    return *this;
}

If the vector being assigned to already has enough space, then there's no need to allocate memory (which is being done by the by-value parameter). A const-ref version might look like this:

template<typename T>
inline Vector<T>& Vector<T>::operator=(const Vector<T>& src)
{
    if(src.size() <= capacity())
    {
        std::copy(src.cbegin(), src.cend(), begin());
        v_size = src.size();
    }
    else
    {
        auto src_copy = src;
        swap(*this, src_copy);
    }

    return *this;
}

The first branch reuses already allocated memory, so it can be much faster.

Now, if assignment can throw, then it might be the case that the assignment is left half done if an exception is thrown. If this cannot be allowed to happen, use copy-and-swap and take the performance penalty.


One last thing: check if your for-loops can be replaced by something out of <algorithm>. In your case, look at std::copy() and std::fill().



Answers to follow-up questions:

I have been going over the video you gave me the link (2nd one), in the talk Howard Hinnant said that the solution is default everything, wouldn't that create a shallow copy issue?

Yes, if a class contains pointers and is responsible for deleting them ("owning pointers" in modern C++ parlance), then the default copy constructor and default assignment operator (as well as their move versions) will do the wrong thing. Your vector class has such pointers, so you need to follow the Rule of 5, that if you need to write custom version of any of the following, then you probably need to write a custom version of all of them: destructor, copy constructor, move constructor, copy assignment operator, move assignment operator.

Your other choice is to replace members that cause problems (non-smart pointers that need deletion, a.k.a., "raw pointers") with smart pointers that handle all of this automatically. That way, the default versions of the constructors/destructors/assignment operators all do the correct thing by default with no code that needs to be written by you. Then you would be following the Rule of 0.

In all cases, you need to consider whether the default versions of the special methods do the correct thing. If not, you have two choices: write the correct methods yourself, or change the class members so that the default methods do the correct thing.

Is the code you provided me about the copy constructor the fix for this?

No. The purpose of my version of the copy-assignment operator was to be more efficient and faster than the copy-and-swap idiom version. Your code that uses the copy-and-swap idiom is also a correct fix to the shallow copy problem.

Shouldn't the line be if(src.capacity() <= capacity()) instead of if(src.size() <= capacity())?

In one sense, the capacity of a vector is an implementation detail. Everything with an index larger than size() - 1 and up to capacity() - 1 is garbage data, so there's no need to make room for it in the vector being assigned to. Consider the following stupid code:

vector two_numbers = {1, 2};
vector million_numbers{};
for(auto i = 0; i < 1'000'000; ++i)
    million_numbers.push_back(i);
while(million_numbers.size() > 2)
    million_numbers.pop_back()
two_numbers = million_numbers;

Now, the capacity of million_numbers is at least one million and the capacity of two_numbers is two. Should memory be allocated for a million numbers when only two will be copied?

In fact, my version of the copy assignment operator isn't even optimal. In the branch where the src.size() is greater than the *this capacity, enough memory is allocated to store the capacity of the src vector instead of just the size due to the copying of src.

\$\endgroup\$
12
  • \$\begingroup\$ Thanks for the answers. \$\endgroup\$
    – HBatalha
    Apr 14, 2020 at 13:46
  • \$\begingroup\$ I have been going over the video you gave me the link (2nd one) , in the talk Howard Hinnant said that the solution is default everything, wouldn't that create a shallow copy issue?? Is the code you provided me about the copy constructor the fix for this and in the same code isn't this line this if(src.capacity() <= capacity()) instead of this if(src.size() <= capacity()). \$\endgroup\$
    – HBatalha
    Apr 17, 2020 at 23:32
  • \$\begingroup\$ @HBatalha I've added answers to your questions to the end of my answer. \$\endgroup\$
    – Mark H
    Apr 18, 2020 at 3:13
  • \$\begingroup\$ regarding of your statement that your" version of the copy assignment operator isn't even optimal", I think that a possible fix would be to change the condition line to this: if(src.size() <= capacity() || src.size() < src.capacity() /* + 'a large number' */ ). with the commented part or just without it \$\endgroup\$
    – HBatalha
    Apr 18, 2020 at 19:28
  • \$\begingroup\$ @HBatalha Run the code here and look at the output: cpp.sh/74abg When a std::vector is copied, the capacity of the copy is equal to the size of the original. Allocating more memory than you need for a copy is inefficient (as determined by the std::vector library writers). At the time I wrote my non-optimal example, I didn't want to write a completely optimized version as that would be too complex for this answer and take too much time. \$\endgroup\$
    – Mark H
    Apr 19, 2020 at 4:53
4
\$\begingroup\$

I am no expert at all, but you are missing some optimization which std::vector implements with some certainty.

Note that you can make almost no assumptions about the type T, e.g. you do not know how expensive it is to construct or destruct instances, or how much dynamic memory it consumes. Also, a constructor might have side effect, and a user might expect that for an empty Vector with non-zero capacity, no instances where created and no side effects happened. In short: you should minimize the call of constructors/destructors.

Here is an example: in the constructor Vector<T>::Vector(size_t sz) you write

values = new T[v_capacity];

for(int i = 0; i < sz; ++i)
    values[ i ] = T();

The for-loop is unnecessary. The new T[...] already creates an array of instances, and calls the standard constructor for each of these. In other words: for each element of values you call the constructor T::T(), then the destructor T::~T(), and then the constructor again.

Another example is your resize function, which when called as Vector::resize(n) on an empty Vector calls the constructor T::T() n times, even though the vector still does not contain any actual elements (from the perspective of the user).

The solution

There are ways to allocate memory for T* values without calling the constructors, and only calling them later when actual elements are added.

Instead of values = new T(n) you might write

values = (T*)(new char[sizeof(T) * n]);

to allocate a block of memory, equivalent to the one allocated with new T(n), but without calling any constructors (char is used because it is of size 1 byte, and sizeof(T) gives the size of T in bytes). This is also the same as malloc(sizeof(T) * n) but is actual C++.

If you want to call the constructor of the i-th element of values, you could use placement new, which goes as folllows:

new (values + i) T();

or you write values[i]->T(). Equivalently if you want to destruct an element explicitly use values[i]->~T(). With the latter, in the destructore Vector::~Vector you would call the destructor only for the actually initialized elelemts of values with indices 0, ..., v_size-1.

\$\endgroup\$
5
  • \$\begingroup\$ Hello, first of all, thanks for the whole answer on this. I tried using values = static_cast<T*>(new char[sizeof(T) * n]); but it throws a compile error in its line: invalid static_cast from type 'char*' to type 'int*' \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 17:31
  • \$\begingroup\$ @HBatalha Ok, static_cast seems not to be made for this task. I suppose reintepret_cast will work, but I feel unfomfortable using it. Anyway, I changed the answer to use C-style cast, which at least compiles. \$\endgroup\$
    – M. Winter
    Apr 15, 2020 at 18:03
  • \$\begingroup\$ you haven't actually \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 18:21
  • \$\begingroup\$ @HBatalha It reads values = (T*)(new char[sizeof(T) * n]); now, doesn't it? \$\endgroup\$
    – M. Winter
    Apr 15, 2020 at 19:28
  • \$\begingroup\$ sorry, only paid attention starting from new \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 22:38
3
\$\begingroup\$

You have two functions defined inline in the class definition, with the rest defined later. For consistency these should be defined outside of the class like the others.

The ctor_initialized member variable is defined at the end of the class, while the rest of the members are defined at the top. All the member variables should be grouped together, since it is very easy to miss that one extraneous variable. But you don't need ctor_initialized at all. It is only read in one place - emplace_back - and its use there is nonsensical (other places where you attempt to resize the vector don't look at it).

You could simplify your list of constructors by making use of default parameters and by using the mem-initializer-list with them. For example, by using a default value in Vector(size_t sz, const T& v = T()); you can get rid of Vector(size_t sz);. This constructor should be explicit to avoid accidental conversions of integers to Vectors.

All of the template out-of-class member function definitions do not need the inline keyword, since a template function definition is implicitly an inline function.

The code to do a reallocation should be completely contained in a member function. You have multiple places with code that follows the "double capacity, then reallocate" pattern. Some of them will misbehave if the capacity is 0, or the needed size is more than twice the current capacity (insert(iterator pos, size_t n, const T& v ) is one place if n is sufficiently large). All this should be centralized, so that there is only one place in the code that modifies m_capacity. Tweaks to reallocate should do it. Pass in the new minimum size required, then reallocate can determine what the new capacity should be (which may be more than twice the existing capacity).

Your class will not work with types that are not default constructable. If you set the capacity to 100, you'll construct 100 objects. The real std::vector allocates character arrays and uses placement new to solve these problems.

The move constructor Vector(const Vector<T>&& mv) is broken, because you're swapping with an unconstructed object (*this). This will result in Undefined Behavior.

The emplace looks wrong. pos doesn't seem to be the right type. Should this be an integer or an iterator? In its current form you pass a pointer to a T, which can be anywhere. The calculation of dist will be undefined if pos does not point to an element of the values array.

In erase( const_iterator pos ), the use of pow, which is a floating point function, is a potential source of error. You can simply use the bit shift operator, 1 << inc, to calculate a power of two. Why does this function do any memory allocations? It shouldn't be. The two parameter version does not, resulting in different behavior for erase(p) vs erase(p, p + 1).

empty() can be simplified to just return v_size == 0;.

Your size and capacity members are size_t (assuming this is std::size_t, it is an unsigned type), but many of your uses compare those values with a signed number (often int i). This can result in a compiler warning on some platforms (comparing a signed value with an unsigned one). If size_t is a larger integer than an int (64 vs 32 bits), you'll have problems when i overflows.

The size() and capacity() functions return unsigned quantities as potentially smaller signed values.

\$\endgroup\$
15
  • \$\begingroup\$ Thanks for the partial review, hope you can come back for a full review later \$\endgroup\$
    – HBatalha
    Apr 13, 2020 at 19:44
  • \$\begingroup\$ "(other places where you attempt to resize the vector don't look at it)" - didn't fully understand \$\endgroup\$
    – HBatalha
    Apr 13, 2020 at 19:46
  • \$\begingroup\$ "The code to do a reallocation should be completely contained in a member function." - I had it but I was afraid I was breaking the DRY rule. \$\endgroup\$
    – HBatalha
    Apr 13, 2020 at 19:48
  • \$\begingroup\$ " All this should be centralized." - How? \$\endgroup\$
    – HBatalha
    Apr 13, 2020 at 19:53
  • \$\begingroup\$ "pos is the wrong type." - what type should I be using then? \$\endgroup\$
    – HBatalha
    Apr 13, 2020 at 20:07
2
\$\begingroup\$

Overall

Please put your code in your own namespace.
It is more than likely that other people have created a "Vector" type. But in general you need to keep all your code in your own namespace.

Your main issue is that you construct all the elements in the vector even if you are not using them. This can be expensive if T is expensive or you never use most of the elements in the vector.

Your secondary issue is that you check and allocate extra capacity i nearly all functions that add elements. You need to simplify this and move this code into its own function. Then call this function from each member that adds elements to the vector.

void checkForEnoughSpaceAndAllocateIfRequried(std::size_t totalSpaceRequired);

My full explanation of how to build a vector

Vector - Resource Management Allocation
Vector - Resource Management Copy Swap
Vector - Resize
Vector - Simple Optimizations
Vector - The Other Stuff

Code Review

When using move construction you can't pass by const reference.

    Vector(const Vector&&);

You are going to modify the input value if you remove its content.


If T is non trivial and needs a destructor call then this will call the destructor for all elements in values (assuming it was correctly allocated).

    ~Vector()
    {
        delete [ ]  values;
    }

BUT you have v_capacity member. This means that not all members of values have been constructed (or potentially the elements have been removed and thus destructed). So this is probably wrong.

Or you always construct all the members and keep them constructed. This is an issue if the type T is expensive to construct, there is some special property of T that counts the number of valid entities of T etc.

i.e. you should not construct the members of the vector until they are placed in the vector and they should be destroyed (via destructor) when they are removed erased from the vetctor.


    T& front(); // actually I don't see why would we need this function to be a reference, I think it should be only a const reference, any insight?
    const T& back() const;

You need this so you can modify the front element in the vector (you don't need "need" it but it is very useful).


What about the const version of back() ?

    T& back();

Not sure why you want this to be a friend rather than a member.

    // Non-Member Functions
    template<typename H> friend bool operator==(const Vector<H>& lhs, const Vector<H>& rhs);

Normally the reason to use friend functions is to allow auto conversion of both the right and left hand sides if one side is not a vector. Since you don't really want auto conversion for a comparison I don't see the need.


This is the basics actions needed for swap.

    friend void swap(Vector& first, Vector& second)
    {
        using std::swap;

        swap(first.v_size, second.v_size);
        swap(first.v_capacity, second.v_capacity);
        swap(first.values, second.values);
    }

But probably is not the best way to implement it. Some internal functions also need the ability to swap and calling an external function seems overkill. So I would implement it like this:

    // This is useful to provide as a public function.
    // But provides a member function that allows other members to use swap.
    void swap(Vector& other) noexcept
    {
        using std::swap;

        swap(v_size,     other.v_size);
        swap(v_capacity, other.v_capacity);
        swap(values,     other.values);
    }


// Now the implementation of the swap function (in the same namespace as Vector)
// Becomes really simple.
void swap(Vector& lhs, Vector& rhs)
{
    lhs.swap(rhs);
}

Prefer to use the initializer list rather than construct members the body.

template<typename T>
inline Vector<T>::Vector()
{
    v_size = 0;
    v_capacity = 0;
    values = nullptr;
}

In this case it makes no difference. BUT if the types of the members has non trivial constructor or assignment then you are doing extra work. And one of the things about C++ is that we often come around and simply change the type of a member and expect the type to continue working the same. If you do this type of initialization suddenly your class becomes ineffecient.

So it is better to do it like this:

template<typename T>
Vector<T>::Vector()
    : v_size(0)
    , v_capacity(0)
    , values(nullptr)
{}

The problem here is that you are initializing every member of the array.

    values = new T[v_capacity];

This is not very efficient especially if T is expensive to initialize (or it is not appropriate to initialize members that the user has not created). TO mimik std::vector you should allocate the space but NOT call the constructors on the members.

Members are not constructed until objects are added to the array.

To add an object to memory that is allocated but not initialized you need to use placement new. This is a new where you tell new the memory location to use.

 // Allocate Memory
 values = static_cast<T*>(::operator new(sizeof(T) * v_capacity);


 // Put an element into the memory space.
 // that has not be initialized by calling constructor

 new (&values[i]) T(<constructor parameters>);

Notice the extra parameter to new here (a pointer to a memory location). This means new will not allocate memory but will use the pointer provided.

Conversely when these locations are no longer used you must manually call the destructor.

 values[i].~T();

Lets re-write this version using the guidelines above:

template<typename T>
inline Vector<T>::Vector(size_t sz, const T& v)
    : v_size(sz)
    , v_capacity(sz)
    , values(static_cast<T*>(::operator new(sizeof(T) * v_capacity))
    , ctor_initialized(true)
{    
    for(int i = 0; i < sz; ++i) {
        new (&values[ i ]) T(v);
    }
}

Prefer to use the range based for:

    for(auto iter = i_list.begin(), i = 0; iter != i_list.end(); ++i, ++iter)
        values[ i ] = *iter;

Simpler to write as:

    for(auto const& val: i_list) {
        push_back(val);
    }

This constructor is making a copy of mv before swapping it!

template<typename T>
inline Vector<T>::Vector(const Vector<T>&& mv)
{
    swap(*this, mv);
}

This is correctly written like this:

template<typename T>
inline Vector<T>::Vector(Vector<T>&& mv) noexcept
{
    swap(mv);
}

Notes:

  1. This constructor should be noexcept
  2. Use the internal version of swap()

All these methods are correct and fine. But they are simple one liners.

template<typename T>
inline typename Vector<T>::iterator Vector<T>::begin() noexcept
{
    return values;
}

I would simply declare them in the class and make them one liners.

iterator               begin()   noexcept       {return values;}
const_iterator         begin()   noexcept const {return values;}
const_iterator         cbegin()  noexcept const {return values;}
reverse_iterator       rbegin()  noexcept       {return reverse_iterator(end());}
const_reverse_iterator crbegin() noexcept const {return rbegin();}
iterator               end()     noexcept       {return values + v_size;}
const_iterator         end()     noexcept const {return values + v_size;}
const_iterator         cend()    const          {return values + v_size;}
reverse_iterator       rend()    noexcept       {return reverse_iterator(begin());}
const_reverse_iterator crend()   noexcept const {return rend();}

When I lined them up all nice (and moved const to the right of noexcept). I notices that cend() is different. It is not only one you have not declared noexcept. Why?????


Why do you have the else here?

template<typename T>
inline T& Vector<T>::at (size_t i)
{
    if(i >= v_size)
        throw std::runtime_error("out of range exception");
    else
        return values[ i ];
}

Normally when you check pre-conditions your code looks like this:

    if (precondition-fail) {
        throw excpetion
    }

    Normal Code

You put the precondition check at the top then all your normal code can go at the normal indent level (not be indent an extra level.


Every one of your functions that adds members checks to see if there is room and increases capacity!

You don't think there should be a separate method that does this check and if there is not enough capacity allocates the appropriate amount of memory.

template<typename T>
template<typename... ARGS>
void Vector<T>::emplace_back(ARGS&&... args)
{
    if(v_size == v_capacity)
    {
        if(ctor_initialized)
            v_capacity *= 2;
        else
        {
            if (v_size == 0)
                v_capacity = 1;
            else if(v_size < 8)
                v_capacity++;
            else if (v_size >= 8)
                v_capacity *= 2;
        }

        reallocate();
    }

    values[v_size++] = std::move(T(std::forward<ARGS>(args)...));
}

You don't need std::move here:

    values[v_size++] = std::move(T(std::forward<ARGS>(args)...));

The expression T(std::forward<ARGS>(args)...) is already an r-value reference (its an unamed variable).


You should definately want to use the destructor remove elements when they are removed. Unfortunately you can't because of the way you have created the constructors/destructor.

Currently destroying the element would lead to the destructor re-destroying the element.

template<typename T>
inline void Vector<T>::pop_back()
{
    --v_size;

    // what if I use this below, what would be happening and what would be the difference??
    /*   values[--v_size].~T(); */
}

You do want to do this. But first you must change your code to use inpace new operator everywhere else.


If T is expensive to create you may want to move objects from the original to the destination rather than copying them.

template<typename T>
inline void Vector<T>::reallocate()
{
    T* temp = new T[ v_capacity ];

    for(int i = 0; i < v_size; ++i)
        temp[ i ] = values[ i ];       // This is a copy of T

    delete[ ] values;
    values = temp;
}

You have not considered what would happen if a copy failed! If a copy of T failed during your loop (and throws an exception). Then you leak the memory that was allocated and assigned to temp.

A better technique is to create a new Vector object. If it works then swap the content out of the this new vector object into your own Vector.

template<typename T>
inline void Vector<T>::reallocate()
{
    Vector<T>   temp;
    temp.reserve(v_capacity);

    for(int i = 0; i < v_size; ++i) {
        temp.emplace_back(values[ i ]);
    }

    swap(temp);    
}
\$\endgroup\$
14
  • \$\begingroup\$ Thanks, I have actually fixed some topics you pointed like the member-initializer-list \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 18:14
  • \$\begingroup\$ "Prefer to use the range based for:" - I have actually changed the code to instead of using 'for' to use 'std::copy' and std::fill from <algorithm> library. \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 18:16
  • \$\begingroup\$ Refer to the first answer of this question "The move constructor Vector(const Vector<T>&& mv) is broken, because you're swapping with an unconstructed object (*this). This will result in Undefined Behavior.", I have changed the code to something like this inline Vector<T>::Vector(const Vector<T>&& mv) : Vector(), without noexcept yet though. \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 18:19
  • \$\begingroup\$ " It is not only one you have not declared noexcept. Why?????" - No idea, I have it in my code. Maybe I added it after posting the question. \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 18:22
  • \$\begingroup\$ "What about the const version of back() ?" - it is there, you have actually used in your answer, just above this question. \$\endgroup\$
    – HBatalha
    Apr 15, 2020 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.