7
\$\begingroup\$

I've implemented a simple vector-like structure. I would appreciate all criticism relevant to code. I have also published code under github. Here is the link to source code + unit test for most functions: https://github.com/Nethius/mystd

const double_t expansion_ratio = 1.5;

namespace mystd {
    template<class T>
    class vector {
        size_t _size;
        size_t _capacity;
        char *_data;
        typedef T *iterator;
        typedef const T *const_iterator;
        typedef T &reference;
        typedef const T &const_reference;

        void reallocate(size_t capacity);

        void move_forward(iterator dest, iterator from, size_t count);

        void move_backward(iterator dest, iterator from, size_t count);

    public:
        vector();

        explicit vector(size_t size);

        vector(size_t size, const T &initial);

        vector(const vector<T> &vector);

        vector(vector<T> &&vector) noexcept;

        vector(std::initializer_list<T> list);

        template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
        vector(input_iterator first, input_iterator last);

        ~vector();

        reference operator[](size_t pos);

        const_reference operator[](size_t pos) const;

        reference at(size_t pos);

        const_reference at(size_t pos) const;

        vector<T> &operator=(const vector<T> &vector);

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

        void assign(size_t count, const_reference value);

        template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
        void assign(input_iterator first, input_iterator last);

        iterator insert(const_iterator pos, const_reference value);

        iterator insert(const_iterator pos, T &&value);

        iterator insert(const_iterator pos, size_t count, const_reference value);

        template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
        iterator insert(const_iterator pos, input_iterator first, input_iterator last);

        iterator insert(const_iterator pos, std::initializer_list<T> list);

        template<typename ... Args>
        iterator emplace(const_iterator pos, Args &&... args);

        iterator erase(const_iterator pos);

        iterator erase(const_iterator first, const_iterator last);

        size_t size() const;

        size_t max_size() const;

        size_t capacity() const;

        bool empty() const;

        iterator begin();

        const_iterator begin() const;

        const_iterator cbegin() const;

        iterator rbegin();

        const_iterator rbegin() const;

        const_iterator rcbegin() const;

        iterator end();

        const_iterator end() const;

        const_iterator cend() const;

        iterator rend();

        const_iterator rend() const;

        const_iterator rcend() const;

        reference front();

        const_reference front() const;

        reference back();

        const_reference back() const;

        iterator data();

        const_iterator data() const;

        void push_back(const_reference value);

        void push_back(T &&value);

        void pop_back();

        template<typename ... Args>
        void emplace_back(Args &&... args);

        void reserve(size_t size);

        void resize(size_t count);

        void resize(size_t count, const_reference value);

        void shrink_to_fit();

        void clear();

        template<class T>
        friend void swap(vector<T> &left, vector<T> &right);

        template<class T>
        friend bool operator==(const vector <T> &left, const vector <T> &right);

        template<class T>
        friend bool operator!=(const vector <T> &left, const vector <T> &right);

        template<class T>
        friend bool operator<(const vector <T> &left, const vector <T> &right);

        template<class T>
        friend bool operator<=(const vector <T> &left, const vector <T> &right);

        template<class T>
        friend bool operator>(const vector <T> &left, const vector <T> &right);

        template<class T>
        friend bool operator>=(const vector <T> &left, const vector <T> &right);
    };

    template<class T>
    vector<T>::vector() : _size(0), _capacity(0), _data(nullptr) {
    }

    template<class T>
    vector<T>::vector(size_t size) : _size(size), _capacity(_size), _data(new char[sizeof(T) * size]()) {
    }

    template<class T>
    vector<T>::vector(size_t size, const T &initial) : vector(size) {
        for (size_t i = 0; i < _size; i++)
            new(_data + sizeof(T) * i) T(initial);
    }

    template<class T>
    vector<T>::vector(const vector <T> &vector) : vector(vector._size) {
        for (size_t i = 0; i < _size; i++)
            new(_data + sizeof(T) * i) T(vector[i]);
    }

    template<class T>
    vector<T>::vector(vector<T> &&vector) noexcept : vector(vector._size) {
        swap(*this, vector);
    }

    template<class T>
    vector<T>::vector(std::initializer_list<T> list) : vector(list.size()) {
        for (size_t i = 0; i < _size; i++)
            new(_data + sizeof(T) * i) T(*(list.begin() + i));
    }

    template<class T>
    template<class input_iterator, typename>
    vector<T>::vector(input_iterator first, input_iterator last) : vector(std::distance(first, last)) {
        auto it = first;
        for (size_t i = 0; i < _size; i++) {
            new(_data + sizeof(T) * i) T(*(it));
            it = std::next(it);
        }
    }

    template<class T>
    vector<T>::~vector() {
        delete[] _data;
    }

    template<class T>
    T &vector<T>::operator[](size_t pos) {
        return *(reinterpret_cast<iterator>(_data + sizeof(T) * pos));
    }

    template<class T>
    const T &vector<T>::operator[](size_t pos) const {
        return *(reinterpret_cast<iterator>(_data + sizeof(T) * pos));
    }

    template<class T>
    vector<T> &vector<T>::operator=(const vector <T> &vector) {
        if (*this != vector) {
            swap(*this, mystd::vector<T>(vector));
        }
        return *this;
    }

    template<class T>
    vector<T> &vector<T>::operator=(vector<T> &&vector) noexcept {
        if (*this != vector) {
            swap(*this, vector);
        }
        return *this;
    }

    template<class T>
    typename vector<T>::iterator vector<T>::begin() {
        return reinterpret_cast<iterator>(_data);
    }

    template<class T>
    typename vector<T>::const_iterator vector<T>::begin() const {
        return reinterpret_cast<iterator>(_data);
    }

    template<class T>
    typename vector<T>::const_iterator vector<T>::cbegin() const {
        return begin();
    }

    template<class T>
    typename vector<T>::iterator vector<T>::end() {
        return reinterpret_cast<iterator>(_data + sizeof(T) * _size);
    }

    template<class T>
    typename vector<T>::const_iterator vector<T>::end() const {
        return reinterpret_cast<iterator>(_data + sizeof(T) * _size);
    }

    template<class T>
    typename vector<T>::const_iterator vector<T>::cend() const {
        return end();
    }

    template<class T>
    size_t vector<T>::size() const {
        return _size;
    }

    template<class T>
    size_t vector<T>::capacity() const {
        return _capacity;
    }

    template<class T>
    bool vector<T>::empty() const {
        return _size == 0;
    }

    template<class T>
    typename vector<T>::reference vector<T>::front() {
        return *begin();
    }

    template<class T>
    typename vector<T>::const_reference vector<T>::front() const {
        return *cbegin();
    }

    template<class T>
    typename vector<T>::reference vector<T>::back() {
        return *(end() - 1);
    }

    template<class T>
    typename vector<T>::const_reference vector<T>::back() const {
        return *(cend() - 1);
    }

    template<class T>
    void swap(vector<T> &left, vector<T> &right) {
        using std::swap; //enable ADL? https://stackoverflow.com/questions/5695548/public-friend-swap-member-function
        swap(left._size, right._size);
        swap(left._capacity, right._capacity);
        swap(left._data, right._data);
    }

    template<class T>
    void vector<T>::push_back(const_reference value) {
        if (_size >= _capacity) {
            reallocate(_size * expansion_ratio);
        }
        new(end()) T(value);
        _size++;
    }

    template<class T>
    void vector<T>::push_back(T &&value) {
        if (_size >= _capacity) {
            reallocate(_size * expansion_ratio);
        }
        *end() = std::move(value);
        _size++;
    }

    template<class T>
    void vector<T>::reallocate(size_t capacity) {
        _capacity = capacity;

        char *new_data = new char[sizeof(T) * _capacity]();
        iterator new_begin = reinterpret_cast<iterator>(new_data);

        for (auto it = begin(); it != end(); it++)
            *new_begin++ = std::move(*it);

        delete[] _data;
        _data = new_data;
    }

    template<class T>
    void vector<T>::move_forward(vector::iterator dest, vector::iterator from, size_t count) {
        if (dest == from)
            return;
        iterator _dest = dest;
        iterator _from = from;
        for (size_t i = 0; i < count; i++)
            *_dest++ = std::move(*_from++);
    }

    template<class T>
    void vector<T>::move_backward(vector::iterator dest, vector::iterator from, size_t count) {
        if (dest == from)
            return;
        iterator _dest = dest + count - 1;
        iterator _from = from + count - 1;
        for (size_t i = count; i > 0; i--)
            *_dest-- = std::move(*_from--);
    }

    template<class T>
    void vector<T>::assign(size_t count, const_reference value) {
        swap(*this, vector<T>(count, value));
    }

    template<class T>
    template<class input_iterator, typename>
    void vector<T>::assign(input_iterator first, input_iterator last) {
        swap(*this, vector<T>(first, last));
    }

    template<class T>
    template<typename... Args>
    typename vector<T>::iterator vector<T>::emplace(vector::const_iterator pos, Args &&... args) {
        size_t index = pos - reinterpret_cast<iterator>(_data);

        if (_size >= _capacity) {
            reallocate(_size * expansion_ratio);
        }

        iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
        move_backward(it + 1, it, _size - index);

        *it = T(std::forward<Args>(args) ...);
        _size++;
        return it;
    }

    template<class T>
    typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, const_reference value) {
        return emplace(pos, value);
    }

    template<class T>
    typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, T &&value) {
        return emplace(pos, std::move(value));
    }

    template<class T>
    typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, size_t count, const_reference value) {
        if (!count)
            return const_cast<iterator>(pos);
        size_t index = pos - reinterpret_cast<iterator>(_data);

        if (_size + count >= _capacity) {
            reallocate((_size + count) * expansion_ratio);
        }

        iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
        move_backward(it + count, it, _size - index);

        for (size_t i = 0; i < count; i++)
            *(it + i) = value;
        _size += count;
        return it;
    }

    template<class T>
    template<class input_iterator, typename>
    typename vector<T>::iterator
    vector<T>::insert(vector::const_iterator pos, input_iterator first, input_iterator last) {
        size_t n = std::distance(first, last);

        if (!n)
            return const_cast<iterator>(pos);
        size_t index = pos - reinterpret_cast<iterator>(_data);

        if (_size + n >= _capacity) {
            reallocate((_size + n) * expansion_ratio);
        }

        iterator dest = reinterpret_cast<iterator>(_data + sizeof(T) * index);
        move_backward(dest + n, dest, _size - index);

        auto from = first;

        for (size_t i = 0; i < n; i++) {
            *(dest + i) = *(from);
            from = std::next(from);
        }
        _size += n;
        return dest;
    }

    template<class T>
    typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, std::initializer_list<T> list) {
        return insert(pos, list.begin(), list.end());
    }

    template<class T>
    void vector<T>::pop_back() {
        erase(end() - 1);
    }

    template<class T>
    typename vector<T>::iterator vector<T>::erase(vector::const_iterator pos) {
        size_t index = pos - reinterpret_cast<iterator>(_data);
        iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
        it->~T();
        if (pos != end() - 1)
            move_forward(it, it + 1, _size - index);
        _size--;
        return it;
    }

    template<class T>
    typename vector<T>::iterator vector<T>::erase(vector::const_iterator first, vector::const_iterator last) {
        size_t n = 0;
        for (auto curr = first; curr <= last; ++curr)
            ++n;

        if (!n)
            return const_cast<iterator>(last);
        size_t index = first - reinterpret_cast<iterator>(_data);

        iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
        for (size_t i = 0; i < n; i++)
            (it + i)->~T();

        move_forward(it, it + n, _size - (index + n));

        _size -= n;
        return it;
    }

    template<class T>
    typename vector<T>::iterator vector<T>::data() {
        return reinterpret_cast<iterator>(_data);
    }

    template<class T>
    typename vector<T>::const_iterator vector<T>::data() const {
        return data();
    }

    template<class T>
    template<typename... Args>
    void vector<T>::emplace_back(Args &&... args) {
        emplace(end(), args ...);
    }

    template<class T>
    void vector<T>::reserve(size_t size) {
        if (size > _capacity)
            reallocate(size);
    }

    template<class T>
    void vector<T>::shrink_to_fit() {
        reallocate(_size);
    }

    template<class T>
    void vector<T>::clear() {
        for (auto it = begin(); it != end(); it++)
            (it)->~T();
        _size = 0;
    }

    template<class T>
    void vector<T>::resize(size_t count) {
        if (count > _capacity)
            reallocate(count * expansion_ratio);
        _size = count;
    }

    template<class T>
    void vector<T>::resize(size_t count, const_reference value) {
        iterator it = reinterpret_cast<iterator>(_data);
        if (count > _size) {
            size_t lastElementIndex = _size;
            resize(count);
            it = begin();
            for (size_t i = lastElementIndex; i < count; i++)
                *(it + i) = value;
        } else {
            for (size_t i = count; i < _size; i++)
                (it + i)->~T();
        }
        _size = count;
    }

    template<class T>
    bool operator==(const vector<T> &left, const vector<T> &right) {
        if (left._size != right._size)
            return false;
        for (size_t i = 0; i < left._size; i++) {
            if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) !=
                *(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
                return false;
        }
        return true;
    }

    template<class T>
    bool operator!=(const vector<T> &left, const vector<T> &right) {
        return !(left == right);
    }

    template<class T>
    bool operator<(const vector<T> &left, const vector<T> &right) {
        size_t size = left.size() < right.size() ? left.size() : right.size();
        for (size_t i = 0; i < size; i++) {
            if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) <
                *(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
                return true;
        }
        return false;
    }

    template<class T>
    bool operator<=(const vector<T> &left, const vector<T> &right) {
        return !(left > right);
    }

    template<class T>
    bool operator>(const vector<T> &left, const vector<T> &right) {
        size_t size = left.size() < right.size() ? left.size() : right.size();
        for (size_t i = 0; i < size; i++) {
            if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) >
                *(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
                return true;
        }
        return false;
    }

    template<class T>
    bool operator>=(const vector<T> &left, const vector<T> &right) {
        return !(left < right);
    }


}
```
\$\endgroup\$
2
\$\begingroup\$

Notes:

There are multiple places where you don't correctly start or end the lifetime of an object. After allocating the raw memory you have allocated capacity space for objects, BUT you have not started the lifetime of any objects in the storage and thus your size is zero.

When adding objects to the storage they MUST be constructed (not assigned to). This means as size is incremented you should always be using placement new (thus calling the constructor) and start the object lifetime. When size decreases you need to manually call the destructor and end the object lifetime. Anything from [size..capacity) is not constructed and thus its lifetime has not started.

There are a couple of places where you assign to objects who's lifetime has not started (assignment assumes the lifetime has started). There are also a couple of places where you don't end the lifetime when you decrease the size (which would mean they could leak or accidentally be constructed onto).

See: Default constructor. Move constructor


You need to understand the strong exception guarantee. This basically says that a mutation works correctly or it fails (probably with an exception) BUT if it fails the state remains unchanged (and thus valid).

To make this work usually this means that mutations happen on temporary objects and state is swapped with the temporary using exception safe operations.

see: resize


The calls to resize if very subtly broken (this happened to me as well when I first tried to write vector).

 reallocate(_size * expansion_ratio);  // does not work if _size is 1.
                                       // if your expansion_ratio is 1.5
                                       // would work for 2 or greater.

Self Plug

I wrote a series of articles on the vector that is worth reading:

https://lokiastari.com/series/

Style

You use a C style when annotating your types for pointers and references by placing the '*' or '&' with the variable rather than with the type.

In C++ we usually place these annotations with the type so that all the type information is placed together. This is because in C++ type information is much more important.

vector& operator=(vector const&  copy); // Notice the '&' with the type.

You store the data in char*. This means you have a lot of reinterpret_cast<>() to convert the pointer back to a T* I would simply change the data member in to a T* member and use the reinterpret_cast<>() once.

Code Review:

Prefer to use using over typedef

        typedef T *iterator;
        typedef const T *const_iterator;
        typedef T &reference;
        typedef const T &const_reference;


        using iterator        =  T*;
        using const_iterator  = const T*;
        using reference       = T&;
        using const_reference = const T&;

Your methods are simply a list of methods with an empty line between them.

        vector();

        explicit vector(size_t size);

        vector(size_t size, const T &initial);

        vector(const vector<T> &vector);

You should make this easier to read. One way to do this is to group together functions that have similar functionality. Constructors/Assignment Op/Insert/Query etc. Something.


I suppose you can check this.

        template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
        vector(input_iterator first, input_iterator last);

I don't see the point. If they don't act like iterators it will fail to compile.


I see why you did this:

        void push_back(const_reference value);    
        void push_back(T &&value);

But I think it is clearer to write like this:

        void push_back(T const& value);    
        void push_back(T&& value);

You don't need the template part here.

        template<class T>
        friend void swap(vector<T> &left, vector<T> &right);

or in the following friend declarations.


The reason to make these operations standalone functions is to allow the left value to auto convert into a vector when comparing something to a vector on the right hand side.

        template<class T>
        friend bool operator==(const vector <T> &left, const vector <T> &right);

Since this conversion can never happen (your only single parameter construcror is explicit). There is not need to make this a friend and it just simpler to make it a member of the class.


This is broken:

Because it is public.

    template<class T>
    vector<T>::vector(size_t size) : _size(size), _capacity(_size), _data(new char[sizeof(T) * size]()) {
    }

You have allocated space for you size elements. BUT you have not constructed the elements of type T this is simply raw uninitialized memory. You need to call the default constructor for each element in the vector.

After reading your other constructors you seem to be using this to allocate the space then the other constructors finish up the initialization. But because this is public it is broken. An alternative is to make it private.

But a couple of the other constructors should not be using this anyway.

Note: You want the capacity to be equal to the size? This means that the next element added is going to force a re-start.


Note: If you fix the above constructor (to initialize the members) you can not use it here:

    template<class T>
    vector<T>::vector(size_t size, const T &initial) : vector(size) {
        for (size_t i = 0; i < _size; i++)
            new(_data + sizeof(T) * i) T(initial);
    }

This is a very expensive move constructor.

    template<class T>
    vector<T>::vector(vector<T> &&vector) noexcept : vector(vector._size) {
        swap(*this, vector);
    }

You allocate the underlying data and then swap the content. Set the current pointer to nullptr and then swap. Not only is this expensive (memory allocation), but the destiantion object is not in a valid state. It has size elements none of which are initialized.

    template<class T>
    vector<T>::vector(vector<T>&& move) noexcept
        : _size{0}
        , _capacity{0}
        , _data{nulptr}
    {
        swap(move);
    }

This is wrong.OK. I see the construction of temporary now.

    template<class T>
    vector<T> &vector<T>::operator=(const vector <T> &vector) {
        if (*this != vector) {
            swap(*this, mystd::vector<T>(vector));
        }
        return *this;
    }

You are attempting to modify the input parameter (which is both const and reference to something else that should not be changed).

It seems to be a corruption of the copy and swap idiom.

The test for self assignment is counter productive. It will actually slow things down (on average). Self assignment is exceedingly rare so the test for self assignment actually slows down the normal case. Now you do need to correctly handle self assignment but because it is so rare it is acceptable for that action to be pesimized so you can optimize the normal situation.

    template<class T>
    vector<T> &vector<T>::operator=(vector <T> const& input)
    {
        vector<T>  copy(input); // Copy.
        swap(copy);             // Swap with the current with copy (see below)

        return *this;
    }

Again the test of self assignment is a pesimization of the normal case while trying to optimize the very rare case. Optimize for the most common situation.

    template<class T>
    vector<T> &vector<T>::operator=(vector<T> &&vector) noexcept {
        if (*this != vector) {
            swap(*this, vector);
        }
        return *this;
    }

I would simplify to:

    template<class T>
    vector<T> &vector<T>::operator=(vector<T>&& move) noexcept
    {
        swap(move);     // swap is safe for self assignment.
        return *this;
    }

These functions are so small and simple.

    template<class T>
    size_t vector<T>::size() const {
        return _size;
    }

    template<class T>
    size_t vector<T>::capacity() const {
        return _capacity;
    }

    template<class T>
    bool vector<T>::empty() const {
        return _size == 0;
    }

I would put them inline in the header file. If a function is simply a line I normally just put it inside the class declaration:

    class vector
    {
         // STUFF
         size_t size()     const {return _size;}
         size_t capacity() const {return _capacity;}
         bool empty()      const {return _size == 0;}
     };

Yes. The enable of ADL is the standard pattern for swap.

Yes you do need a standalone swap. But why not also have a swap member function to simplify things?

    template<class T>
    void swap(vector<T> &left, vector<T> &right) {
        using std::swap; //enable ADL? https://stackoverflow.com/questions/5695548/public-friend-swap-member-function
        swap(left._size, right._size);
        swap(left._capacity, right._capacity);
        swap(left._data, right._data);
    }

I would write like this:

    class vector
    {
         // STUFF
         void swap(vector& other) noexcept     // swap needs to noexcept so
         {                                     // it can be called from noexcept members
             using std::swap; //enable ADL? YES.
             swap(_size,     other._size);
             swap(_capacity, other._capacity);
             swap(_data,     other._data);
          }
          friend void swap(vector& lhs, vector& rhs) {lhs.swap(rhs);}
    };
         

Subtle break: When size is 1.

    template<class T>
    void vector<T>::push_back(const_reference value) {
        if (_size >= _capacity) {
            //
            // size = 1;
            // size * expansion_ratio => (1 * 1.5) => 1.5
            // reallocate accepts (size_t an integer) thus the parameter
            // will be truncated.
            // 
            // So the value passed here is 1
            reallocate(_size * expansion_ratio);
        }
        new(end()) T(value);
        _size++;
    }

This is broken:

template<class T>
void vector<T>::push_back(T &&value) {
    if (_size >= _capacity) {
        reallocate(_size * expansion_ratio);
    }

    // This is wrong.
    // Using the assignment assumes that the destination is properly
    // constructed member. The value at end() has not been constructed.
    // So you must use the constructor (preferably move).
    *end() = std::move(value);

    // To do this correctly you must use the placement new.
    // Like you do everywhere else.
    new(end()) T(std::move(value));
    _size++;
}

Lot of issues here:

    template<class T>
    void vector<T>::reallocate(size_t capacity) {
        _capacity = capacity;

        char *new_data = new char[sizeof(T) * _capacity]();
        iterator new_begin = reinterpret_cast<iterator>(new_data);

        // Not all types support move so this can use copy or move
        // depending on the type. Which is good.
        //
        // But not all copy constructors are `noexcept` so this can potentially
        // throw. If it throws then you need to make sure you do not leak.
        // the pointers.    
        for (auto it = begin(); it != end(); it++)
            // These objects have not been created so you can not use assign.
            // So you need to use placement new (with move) to construct in
            // in place.
            *new_begin++ = std::move(*it);

        // Though normally destructors are noexcept so it should not throw.
        // you can not make that assumption with all random types (which is T).
        // so you have to assume that it can potentially throw. If it throws
        // when you call delete here you leave your object in an invalid state
        // **AND** you leak the value of `new_data`.
        //
        // You can solve both of these by swapping first then calling delete.
        //
        // Another issue is that the destructors of T are not called here.
        delete[] _data;
        _data = new_data;
    }

Use the copy and swap idiom to solve the issue.

    template<class T>
    void vector<T>::reallocate(size_t capacity)
    {
        vector<T>  newVersion(*this, capacity); // construct a new version
                                                // with extra capacity
                                                // you will need a new constructor
                                                // for this.

         // But any exceptions are self contained.
         // and will not affect this object and prevent leaking.

         // Now swap the internal data.
         // the destructor of newVersion will do the cleanup automatically.
         swap(newVersion);
    }

Resizing means you either need to add or remove items.

    template<class T>
    void vector<T>::resize(size_t count) {

        // Why not >=
        if (count > _capacity)
            reallocate(count * expansion_ratio);

        // This changes the size but you may need to construct
        // the objects if you are increasing the size.
        // or if you reduce size you are going to need to destory
        // the items you removed.
        _size = count;
    }

You try and do the resize correctly here:

    template<class T>
    void vector<T>::resize(size_t count, const_reference value) {

         // STUFF
            for (size_t i = lastElementIndex; i < count; i++)

                // Can not use assignment here.
                // You need to use normal construction here.
                *(it + i) = value;
    }

    template<class T>
    bool operator==(const vector<T> &left, const vector<T> &right) {
        if (left._size != right._size)
            return false;
        for (size_t i = 0; i < left._size; i++) {

            // why not use the methods you have already defined.
            if (left[i] != right[i]) {return false;}

            // Very hard to read.
            if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) !=
                *(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
                return false;
        }
        return true;
    }

\$\endgroup\$
3
\$\begingroup\$

Hi and welcome to CodeReview,

There is a lot to unravel here, mostly concerning readability and robust code.

  1. typedef is a relict from C that has been completely superseded by using declarations, so your aliases should read:

     using iterator = T*;
     using const_iterator = const T*;
     using reference = T&;
     using const_reference = const T&;
    

    Note that in this case it was even actively confusing as the * and the & where located directly at the name of the alias.

  2. You have chosen a size based notation rather a pointer based one. That is possible but involves quite a lot of calculations that can be avoided by going with the conventional first, last, end pointers.

  3. Your data members can and should be member initialized, so that there is no possibility to forget to initialize them

     size_t _size{0};
     size_t _capacity{0};
     char *_data{nullptr};
    
  4. Your choice of char* as the underlying buffer is both incorrect and unnecessary. The first observation is that only unsigned char and byte are allowed to represent memory, so the usage of char is wrong. Also alignment might be a huge and hard to debug issue. Why not go with plain T*. That way you can also get rid of all the pesky reinterpret_cast

  5. I see no benefit in separating the member function declarations from their definition. You need them in the header anyway, so why add all this biolerplate?

    Note that this can also introduce correctness issues especially regarding templated friend functions. (There is a talk from Ben Saks about making friends that I would recommend here)

  6. You can default the constructor when you use member intializer.

  7. You vector notably differs from the std implementation in that it does not value initializes the members. This is due to choosing char as the underlying buffer type, which is trivial. This will almost certainly introduce bugs.

  8. You are using placement new in the size, const reference constructor. This would not be necessary if you would use a T* buffer. Also alignment will most certainly bite you.

  9. You should always use braces around for and if. There is literally no reason to not use braces even for single line bodies. It introduces a whole slew of super hard to debug bugs for the incredible gain of a single LoC saved.

  10. Your move constructor is completely wrong. You should move the content of the input to your vector and not swap the elements. Think about the difference in lifetimes this makes.

  11. Use the simples method available. You want to increment an iterator. Which is better ++it or it = std::next(it)?

  12. Your copy assignment is also completely broken. I do not really know why you name your arguments same as the class, given that that will confuse everyone. But this should not even compile, as you cannot swap with a const reference. It is const after all. You need to copy the elements around.

  13. All the reinterpret_cast can go

  14. You are using post-increment, which suggests that you should read up on the difference between ++i and i++. One of the two does a copy.

  15. Currently you are doing no bounds check for your accessors. If you are open that you will crash and burn when someone uses it incorrectly that is fine. Not nice, but technically correct. Maybe an assert here and there would help?

  16. You are open coding a lot of common algorithms. It generally is better to simply use std::copy rather than writing the loop by hand.

  17. Everytime you use swap it is mostly wrong

  18. You are completely neglecting exception safety. If that is intentional you should make it clear.

  19. Please do not check integers against 0 via !

  20. You should reuse internal methods more often. Why is there reinterpret_cast everywhere when you have begin and end and could simply loop over the iterators they give you?

\$\endgroup\$
1
  • \$\begingroup\$ As long as he is using new alignement will never be an issue. \$\endgroup\$ Mar 14 '21 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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