By Einiemand


2019-01-10 07:19:22 8 Comments

Here is a simple reimplementation of most of std::vector. I want to check if I implement it correctly but the standard libraries source code is not very readable for me.

namespace nonstd {

    template<typename Ty>
    class vector
    {
    public:
        using iterator = Ty * ;
        using const_iterator = const Ty*;

        vector();
        explicit vector(const size_t count);
        vector(const size_t count, const Ty& val);
        vector(const vector& other);
        vector(vector&& other);
        ~vector();

        vector& operator=(const vector& other);
        vector& operator=(vector&& other);

        size_t size() const;
        size_t capacity() const;

        void push_back(const Ty& val);
        void push_back(Ty&& val);
        void pop_back();

        Ty& front();
        const Ty& front() const;
        Ty& back();
        const Ty& back() const;
        Ty& operator[](const size_t pos);
        const Ty& operator[](const size_t pos) const;

        iterator begin();
        const_iterator begin() const;
        iterator end();
        const_iterator end() const;
    private:
        Ty * buffer;
        iterator m_first;
        iterator m_last;
        iterator m_end;

        void realloc(const size_t factor, const size_t carry);
        void alloc(const size_t cap);
    };

    template<typename Ty>
    vector<Ty>::vector() : buffer(new Ty[10]), m_first(buffer), m_last(buffer), m_end(buffer + 10) {

    }

    template<typename Ty>
    vector<Ty>::vector(const size_t count) : buffer(new Ty[count]), m_first(buffer), m_last(buffer + count), m_end(buffer + count) {

    }

    template<typename Ty>
    vector<Ty>::vector(const size_t count, const Ty& val) : buffer(new Ty[count]), m_first(buffer), m_last(buffer + count), m_end(buffer + count) {
        while (count--) {
            buffer[count] = val;
        }
    }

    template<typename Ty>
    vector<Ty>::vector(const vector& other) : buffer(new Ty[other.capacity()]), m_first(buffer), m_last(buffer + other.size()), m_end(buffer + other.capacity()) {
        for (size_t i = 0; i < size(); ++i) {
            buffer[i] = other[i];
        }
    }

    template<typename Ty>
    vector<Ty>::vector(vector&& other) : buffer(other.buffer), m_first(other.m_first), m_last(other.m_last), m_end(other.m_end) {
        other.buffer = nullptr;
        other.m_first = other.m_last = other.m_end = nullptr;
    }

    template<typename Ty>
    vector<Ty>::~vector() {
        if (buffer != nullptr) {
            m_first = m_last = m_end = nullptr;
            delete[] buffer;
        }
    }

    template<typename Ty>
    vector<Ty>& vector<Ty>::operator=(const vector<Ty>& other) {
        if (this == &other) {
            return *this;
        }
        this->~vector();
        buffer = new Ty[other.capacity()];
        m_first = buffer;
        m_last = buffer + other.size();
        m_end = buffer + other.capacity();
        for (size_t i = 0; i < size(); ++i) {
            buffer[i] = other[i];
        }
        return *this;
    }

    template<typename Ty>
    vector<Ty>& vector<Ty>::operator=(vector<Ty>&& other) {
        if (this == &other) {
            return *this;
        }
        this->~vector();

        buffer = other.buffer;
        m_first = other.m_first;
        m_last = other.m_last;
        m_end = other.m_end;

        other.buffer = nullptr;
        other.m_first = other.m_last = other.m_end = nullptr;
        return *this;
    }

    template<typename Ty>
    size_t vector<Ty>::size() const {
        return static_cast<size_t>(m_last - m_first);
    }

    template<typename Ty>
    size_t vector<Ty>::capacity() const {
        return static_cast<size_t>(m_end - m_first);
    }

    template<typename Ty>
    void vector<Ty>::push_back(const Ty& val) {
        if (size() < capacity()) {
            *(m_last++) = val;
            return;
        }
        realloc(2, 2);
        *(m_last++) = val;
    }

    template<typename Ty>
    void vector<Ty>::push_back(Ty&& val) {
        if (size() < capacity()) {
            *(m_last++) = std::move(val);
            return;
        }
        realloc(2, 2);
        *(m_last++) = std::move(val);
    }

    template<typename Ty>
    void vector<Ty>::pop_back() {
        if (size() == 0) {
            throw std::exception("vector is empty");
        }
        (--m_last)->~Ty();
    }

    template<typename Ty>
    Ty& vector<Ty>::front() {
        if (size() == 0) {
            throw std::exception("front(): vector is empty");
        }
        return *begin();
    }

    template<typename Ty>
    const Ty& vector<Ty>::front() const {
        if (size() == 0) {
            throw std::exception("front(): vector is empty");
        }
        return *begin();
    }

    template<typename Ty>
    Ty& vector<Ty>::back() {
        if (size() == 0) {
            throw std::exception("back(): vector is empty");
        }
        return *(end() - 1);
    }

    template<typename Ty>
    const Ty& vector<Ty>::back() const {
        if (size() == 0) {
            throw std::exception("back(): vector is empty");
        }
        return *(end() - 1);
    }

    template<typename Ty>
    Ty& vector<Ty>::operator[](const size_t pos) {
        if (pos >= size()) {
            throw std::exception("index out of range");
        }
        return buffer[pos];
    }

    template<typename Ty>
    const Ty& vector<Ty>::operator[](const size_t pos) const {
        if (pos >= size()) {
            throw std::exception("index out of range");
        }
        return buffer[pos];
    }

    template<typename Ty>
    typename vector<Ty>::iterator vector<Ty>::begin() {
        return m_first;
    }

    template<typename Ty>
    typename vector<Ty>::iterator vector<Ty>::end() {
        return m_last;
    }

    template<typename Ty>
    typename vector<Ty>::const_iterator vector<Ty>::begin() const {
        return m_first;
    }

    template<typename Ty>
    typename vector<Ty>::const_iterator vector<Ty>::end() const {
        return m_last;
    }

    template<typename Ty>
    void vector<Ty>::realloc(const size_t factor, const size_t carry) {
        alloc(capacity() * factor + carry);
    }

    template<typename Ty>
    void vector<Ty>::alloc(const size_t cap) {
        Ty* new_buffer = new Ty[cap];
        size_t sz = size();
        for (size_t i = 0; i < sz; ++i) {
            new_buffer[i] = buffer[i];
        }
        this->~vector();
        buffer = new_buffer;
        m_first = buffer;
        m_last = buffer + sz;
        m_end = buffer + cap;
    }
}

3 comments

@Deduplicator 2019-01-10 15:23:59

  1. Missing includes:
    • You need an include for std::size_t (though you could just use size_type everywhere, and declare that as using size_type = decltype(sizeof 0);.
    • You use std::move, and thus need <utility>.
namespace nonstd {

    template<typename Ty>
    class vector
  1. If (nearly) everything is in the same namespace, it is conventional not to indent it.

  2. Obviously, you forego allocator-support (for now?).

  3. Using Ty instead of T is very unconventional. Following convention reduces cognitive load, allowing you to expend it elsewhere more profitably. I'll pretend you followed convention for the rest of the review.

    using iterator = Ty * ;
    using const_iterator = const Ty*;
  1. The whitespace around the first * is misplaced. Consider auto-formatting, or just be a bit more careful to stay consistent.

  2. Those aliases are good. You are missing myriad other useful (and necessary) ones though, namely value_type, size_type, difference_type, reference, const_reference, pointer, and const_pointer.
    And when you add reverse-iterator-support, reverse_iterator and const_reverse_iterator.

    vector();
    explicit vector(const size_t count);
    vector(const size_t count, const Ty& val);
    vector(const vector& other);
    vector(vector&& other);
    ~vector();

    vector& operator=(const vector& other);
    vector& operator=(vector&& other);
  1. There is no reason not to make the default-ctor noexcept and constexpr, even if that means not allocating any memory. Especially as passing a zero count to a ctor or invoking the move-ctor can already result in a 0-capacity vector.
    Also, the magic constant you chose is pretty arbitrary, and should be a (private) named constant if you decide to keep it.

  2. Having const parameters in an API is at best irritating to the reader: It doesn't actually do anything.

  3. You are missing constructors from std::initializer_list<T> and iterator-pair. At least copy-ctor and creating from initializer-list should then delegate to iterator-pair for code-reuse.

  4. The move-ctor cannot throw by design, and should thus be marked noexcept.

  5. Dito for move-assignment.

    size_t size() const;
    size_t capacity() const;
  1. Both observers above could be constexpr if you have at least one constexpr ctor...

  2. You are missing empty(), and max_size().

    void push_back(const Ty& val);
    void push_back(Ty&& val);
    void pop_back();
  1. You are missing emplace_back(), which the first two should delegate to.

  2. Also missing are clear(), insert(), emplace(), erase(), and swap(). The last one is crucial for a simple, efficient and exception-safe implementation of much of the class.

    Ty& front();
    const Ty& front() const;
    Ty& back();
    const Ty& back() const;
    Ty& operator[](const size_t pos);
    const Ty& operator[](const size_t pos) const;
  1. All the mutable versions can be implemented by delegating to the const variant and applying a judicious const_cast to the result.
    Especially as you decided that "undefined behavior" means "throws exception" in your case.

  2. Even though you gave the above observers the behavior of at(), you shouldn't leave it out.

  3. You are missing data() completely. Yes, it behaves the same as begin() for you, but there you have it.

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
  1. You are missing the reverse_iterator equivalents.
    Ty * buffer;
    iterator m_first;
    iterator m_last;
    iterator m_end;
  1. Either buffer or m_first is redundant.
    void realloc(const size_t factor, const size_t carry);
    void alloc(const size_t cap);
  1. Centralizing allocation to enforce policy and reduce repetition is a good idea. You aren't quite there though, and implementing the wrong signature. You need one private member for automatic growth void grow(size_type n = 1) and the rest should be public, so a consumer who knows can use it:

    void reserve(size_type n);
    void resize(size_type n);
    void shrink_to_fit();
    
  2. Your current allocation-policy is "double plus constant" on reallocation. That's actually the worst one you could choose, as it makes it impossible to reuse any memory over multiple consecutive reallocations (all the returned memory from earlier together is never enough). For that, it should be below two, maybe m_new = max(needed, m_old * 7 / 4) for automatic reallocation.

  3. You are missing assignment from std::initializer_list<T>, the more versatile assign(),

Now only implementation-details:

vector<Ty>::vector() : buffer(new Ty[10]), m_first(buffer), m_last(buffer), m_end(buffer + 10) {
// and many more
  1. You are aware that new T[n] doesn't only reserve space for n Ts, but also constructs them? That extra-work might be quite involved, and is most emphatically not expected. You should only allocate raw memory (by calling e. g. void* operator new(std::size_t)) and construct the members on demand as needed.
template<typename Ty>
vector<Ty>::~vector() {
    if (buffer != nullptr) {
        m_first = m_last = m_end = nullptr;
        delete[] buffer;
    }
}
  1. Why do you guard against deleting a nullpointer? Also, why repaint the house when demolishing it?
template<typename Ty>
vector<Ty>& vector<Ty>::operator=(const vector<Ty>& other) {
    if (this == &other) {
        return *this;
    }
    this->~vector();
    buffer = new Ty[other.capacity()];
    m_first = buffer;
    m_last = buffer + other.size();
    m_end = buffer + other.capacity();
    for (size_t i = 0; i < size(); ++i) {
        buffer[i] = other[i];
    }
    return *this;
}

template<typename Ty>
vector<Ty>& vector<Ty>::operator=(vector<Ty>&& other) {
    if (this == &other) {
        return *this;
    }
    this->~vector();

    buffer = other.buffer;
    m_first = other.m_first;
    m_last = other.m_last;
    m_end = other.m_end;

    other.buffer = nullptr;
    other.m_first = other.m_last = other.m_end = nullptr;
    return *this;
}
  1. Don't pessimise the common case, by optimising self-assignment.

  2. Calling the dtor means the lifetime ended. Pretending it didn't causes Undefined Behavior.

  3. Assignment should be transactional: Either succeed, or have no effect. Look into the copy-and-swap idiom.

  4. Move-assignment should be simple and efficient: Just swap().

template<typename Ty>
void vector<Ty>::pop_back() {
    if (size() == 0) {
        throw std::exception("vector is empty");
    }
    (--m_last)->~Ty();
}
  1. pop_back() seems to be the only part of vector assuming you construct and destruct elements on demand. That mismatch can be explosive.

@user673679 2019-01-10 13:50:11

Code:

  • I realise you're not implementing the complete functionality, but you probably want add and use at least the value_type, size_type, reference and const_reference typedefs.

  • operator== and operator!= are simple to implement and quite useful.

  • Use std::size_t, not size_t (the latter is the C version).

  • Prefer named constants to magic numbers (e.g. declare a static const std::size_t m_initial_size = 10u;).


  • m_first is the same as buffer, so we don't need it.

  • It's simpler to store the size and capacity, and calculate last and end when needed (we seem to need the size and capacity quite often).


  • Good job with const-correctness. Note that function arguments passed by value may be better left non-const because:
    • const is very important for reference / pointer types since with these the function can affect a variable outside its scope. It's easier to read a function definition where these "important" consts stand out. e.g. (int foo, T const* bar) vs (const int foo, T const* const bar).
    • C++ will actually match a function declaration that includes / omits a const for a pass-by-value argument with a function definition that omits / includes it respectively.

  • Note that the standard version of the single argument constructor explicit vector(const size_t count); does initialize elements (as if it were calling vector(const size_t count, const Ty& val); with a default constructed Ty). In fact, we can use a delegating constructor to do this:

    template<typename Ty>
    vector<Ty>::vector(const size_t count) : vector(count, Ty()) { }
    

  • Don't call the class destructor in the copy / move operators. The destructor should be called only once (usually automatically) when a class is destroyed. Calling it multiple times may be undefined behaviour. The memory cleanup should be moved into a separate function (e.g. deallocate()), which should be called wherever necessary.

Design:

The difference between memory allocation and object construction is an important feature of std::vector that isn't mirrored completely in this nonstd version. With std::vector, a memory buffer of the appropriate size is allocated without any constructor calls. Then objects are constructed in place inside this buffer using "placement new".

As such, it might be cleaner to abstract the memory buffer into a separate class that only allocates / deallocates memory. This is separate from the construction, copying, and destruction of the elements contained within this buffer, which can be handled by the vector class.

Various standard algorithms also exist to help with placement new, e.g. std::uninitialized_copy_n and std::uninitialized_fill_n.

As a (largely untested) example:

#include <cassert>
#include <cstddef>
#include <algorithm>

namespace nonstd {

    template<class Ty>
    class memory_block
    {
    public:

        using size_type = std::size_t;
        using value_type = Ty;
        using pointer = Ty*;
        using const_pointer = Ty const*;

        memory_block():
            m_size(size_type{ 0 }),
            m_buffer(nullptr) { }

        explicit memory_block(size_type count):
            m_size(count),
            m_buffer(allocate(m_size)) { }

        memory_block(memory_block const& other):
            m_size(other.m_size),
            m_buffer(allcoate(m_size)) { }

        memory_block(memory_block&& other):
            m_size(std::move(other.m_size)),
            m_buffer(std::move(other.m_buffer))
        {
            other.m_size = size_type{ 0 };
            other.m_buffer = nullptr;
        }

        ~memory_block()
        {
            deallocate(m_buffer);
        }

        void swap(memory_block& other)
        {
            using std::swap;
            swap(m_size, other.m_size);
            swap(m_buffer, other.m_buffer);
        }

        memory_block& operator=(memory_block const& other)
        {
            auto temp = memory_block(other);
            swap(temp);
            return *this;
        }

        memory_block& operator=(memory_block&& other)
        {
            auto temp = memory_block(std::move(other));
            swap(temp);
            return *this;
        }

        size_type size() const
        {
            return m_size;
        }

        pointer data()
        {
            return m_buffer;
        }

        const_pointer data() const
        {
            return m_buffer;
        }

        pointer at(size_type index)
        {
            assert(index < m_size); // maybe throw instead
            return m_buffer + index;
        }

        const_pointer at(size_type index) const
        {
            assert(index < m_size);  // maybe throw instead
            return m_buffer + index;
        }

    private:

        static pointer allocate(std::size_t size)
        {
            return static_cast<pointer>(::operator new (sizeof(value_type) * size));
        }

        static void deallocate(pointer buffer)
        {
            delete static_cast<void*>(buffer);
        }

        std::size_t m_size;
        Ty* m_buffer;
    };

    template<class Ty>
    inline void swap(memory_block<Ty>& a, memory_block<Ty>& b)
    {
        a.swap(b);
    }

    template<class Ty>
    class vector
    {
    public:

        using size_type = std::size_t;
        using value_type = Ty;

        vector();
        explicit vector(size_type count);
        vector(size_type count, const value_type& val);

        vector(const vector& other);
        vector(vector&& other);

        ~vector();

        void swap(vector& other);

        vector& operator=(const vector& other);
        vector& operator=(vector&& other);

        size_t size() const;
        size_t capacity() const;

        void push_back(const value_type& val);
        void pop_back();

    private:

        static const size_type M_INITIAL_SIZE = size_type{ 10 };

        size_type m_size;
        memory_block<Ty> m_buffer;

        void grow(size_type amount);
        void reallocate(size_type min_size);

        void construct(size_type index, const value_type& value);
        void destruct(size_type index);
        void destruct_all();
    };

    template<class Ty>
    inline void swap(vector<Ty>& a, vector<Ty>& b)
    {
        a.swap(b);
    }

    template<class Ty>
    vector<Ty>::vector(): 
        m_size(0u), 
        m_buffer(M_INITIAL_SIZE)
    {

    }

    template<class Ty>
    vector<Ty>::vector(size_type count):
        m_size(count),
        m_buffer(m_size)
    {
        std::uninitialized_value_construct_n(m_buffer.data(), m_size); // value construct each element w/ placement new (C++17)
    }

    template<class Ty>
    vector<Ty>::vector(size_type count, const value_type& value) : 
        m_size(count),
        m_buffer(m_size)
    {
        std::uninitialized_fill_n(m_buffer.data(), m_size, value); // copy construct each element w/ placement new
    }

    template<class Ty>
    vector<Ty>::vector(const vector& other):
        m_size(other.m_size),
        m_buffer(m_size) // note: allocates only what we need to contain the existing elements, not the same as the capacity of the other buffer
    {
        std::uninitialized_copy_n(other.m_buffer.data(), other.m_size, m_buffer.data()); // copy construct each element from old buffer to new buffer w/ placement new
    }

    template<class Ty>
    vector<Ty>::vector(vector&& other):
        m_size(std::move(other.m_size)),
        m_buffer(std::move(other.m_buffer)) // take ownership of the buffer
    {
        other.m_size = size_type{ 0 }; // other vector is now empty (nothing needs to be constructed / destructed)
    }

    template<class Ty>
    vector<Ty>::~vector()
    {
        destruct_all();
    }

    template<class Ty>
    void vector<Ty>::swap(vector& other)
    {
        using std::swap;
        swap(m_size, other.m_size);
        swap(m_buffer, other.m_buffer);
    }

    template<class Ty>
    vector<Ty>& vector<Ty>::operator=(const vector& other)
    {
        auto temp = vector(other);
        swap(temp);
        return *this;
    }

    template<class Ty>
    vector<Ty>& vector<Ty>::operator=(vector&& other)
    {
        auto temp = vector(std::move(other));
        swap(temp);
        return *this;
    }

    template<class Ty>
    size_t vector<Ty>::size() const
    {
        return m_size;
    }

    template<class Ty>
    size_t vector<Ty>::capacity() const
    {
        return m_buffer.size();
    }

    template<class Ty>
    void vector<Ty>::push_back(const value_type& value)
    {
        grow(size_type{ 1 });
        construct(m_size, value);
        ++m_size;
    }

    template<class Ty>
    void vector<Ty>::pop_back()
    {
        assert(m_size > 0); // maybe throw instead

        destruct(m_size - 1);
        --m_size;
    }

    template<class Ty>
    void vector<Ty>::grow(size_type amount)
    {
        if (m_buffer.size() - m_size < amount)
            reallocate(m_size + amount);
    }

    template<class Ty>
    void vector<Ty>::reallocate(size_type min_size)
    {
        assert(min_size > m_size);

        auto capacity = std::max(min_size, m_buffer.size() + std::max(m_buffer.size() / size_type{ 2 }, size_type{ 1 })); // growth factor of 1.5ish

        auto buffer = memory_block<value_type>(capacity);
        std::uninitialized_copy_n(m_buffer.data(), m_size, buffer.data()); // copy each element from old buffer to new buffer w/ placement new

        destruct_all(); // clean up the old buffer (call destructors on each of the old elements)

        m_buffer = std::move(buffer); // take ownership of the new buffer
    }

    template<class Ty>
    void vector<Ty>::construct(size_type index, const value_type& value)
    {
        new (m_buffer.at(index)) value_type(value); // placement new w/ copy constructor
    }

    template<class Ty>
    void vector<Ty>::destruct(size_type index)
    {
        assert(index < m_size);

        m_buffer.at(index)->~value_type(); // explictly call destructor (because we used placement new)
    }

    template<class Ty>
    void vector<Ty>::destruct_all()
    {
        for (auto index = size_type{ 0 }; index != m_size; ++index)
            destruct(index);
    }

} // nonstd

int main()
{
    {
        nonstd::vector<int> v;
        v.push_back(10);
    }
    {
        nonstd::vector<int> v(5);
        v.pop_back();
    }
    {
        nonstd::vector<int> v(5, 1);
    }
    {
        nonstd::vector<int> v1(2, 2);
        nonstd::vector<int> v2(v1);
    }
    {
        nonstd::vector<int> v1(2, 2);
        nonstd::vector<int> v2(std::move(v1));
    }
}

Note the use of the "copy and swap" idiom in the copy and move assignment operators, which makes implementing them quite a lot easier.

@Einiemand 2019-01-10 18:26:24

This is amazing, I learnt a lot from your code, especially the placement new and memory block part. Thanks a lot!!

@Toby Speight 2019-01-10 10:55:22

Undefined type

We use size_t with no definition. It seems like we want to use std::size_t, in which case, we need a suitable include, such as <cstddef>.

We also need to include <utility> for std::move() and <stdexcept> for std::exception.

Missing types

This template accepts only one argument, but a standard vector also has an Allocator template argument (which defaults to std::allocator<T>). There's quite a lot that will need to be changed to accept and use a provided allocator class.

std::vector must provide member types value_​type, allocator_t​ype, size_t​ype, difference_​type, reference, const_​reference, pointer, const_​pointer, reverse_​iterator and const_​reverse_​iterator, but these are all missing from this implementation.

Missing member functions

There's no public assign(), at(), data(), empty(), max_​size(), reserve(), shrink_​to_​fit(), clear(), insert(), emplace(), erase(), emplace_​back(), resize() or swap() members. Were also missing the const/reverse versions of begin() and end(), such as rbegin() and crend().

Constructors and assignment

We're missing the initializer-list versions of the constructor and assignment operator.

The line lengths are very long - consider using a separate line for each initializer, like this:

template<typename Ty>
vector<Ty>::vector()
    : buffer(new Ty[10]),
      m_first(buffer),
      m_last(buffer),
      m_end(buffer + 10)
{
}

I'm not sure where the magic number 10 comes from in the above - it's probably worth defining a private constant default_initial_capacity for this.

The constructor that accepts a single count argument fails to initialize its elements (std::vector<int>(5) will create a vector containing five zeros, but our equivalent will have five uninitialized values, which may well cause bugs). This could be avoided by delegating to vector(count, T{}). We should also check for a size of zero and either avoid allocating, or round up to our default capacity in that case.

The (count, val) constructor won't compile, as it attempts to modify const count. We could make count mutable, but I think we should simply use std::fill() (from <algorithm>):

template<typename Ty>
vector<Ty>::vector(const std::size_t count, const Ty& val)
    : buffer(new Ty[count]),
      m_first(buffer),
      m_last(buffer + count),
      m_end(buffer + count)
{
    std::fill(m_first, m_last, val);
}

Copy constructor could usefully shrink to fit, using the size rather than the capacity of the source vector to determine the new vector's capacity:

template<typename Ty>
vector<Ty>::vector(const vector& other)
    : buffer(new Ty[other.size()]),
      m_first(buffer),
      m_last(buffer + other.size()),
      m_end(m_last)
{
    std::copy(other.m_first, other.m_last, m_first);
}

Again, I use a standard algorithm to avoid hand-coding my own loop.

Move-construction and move-assignment are most easily implemented using swap():

template<typename Ty>
vector<Ty>::vector(vector&& other)
    : vector()
{
    swap(other);
}

template<typename Ty>
vector<Ty>& vector<Ty>::operator=(vector<Ty>&& other)
{
    swap(other);
    return *this;
}

It certainly looks wrong to explicitly call the destructor in the assignment operator. All we're using it for is to delete[] buffer, so just do that. Better still, use the copy-and-swap idiom:

template<typename Ty>
vector<Ty>& vector<Ty>::operator=(const vector<Ty>& other)
{
    swap(vector<Ty>(other)); // copy and swap
    return *this;
}

Destructor

There's no need to assign nullptr to the members - they are about to go out of scope, so can't be accessed after the destructor finishes. Also, there's no need to test that buffer is non-null, for two reasons: first, our logic never allows a non-null buffer to exist, and secondly, delete[] will happily do nothing if its argument is null.

Modifiers

Look at push_back():

template<typename Ty>
void vector<Ty>::push_back(const Ty& val) {
    if (size() < capacity()) {
        *(m_last++) = val;
        return;
    }
    realloc(2, 2);
    *(m_last++) = val;
}

See how *(m_last++) = val; is common to both paths? We can reorder the test so that we don't duplicate that; to my eyes at least, that makes a more natural expression ("ensure there's room, then add the element"):

template<typename Ty>
void vector<Ty>::push_back(const Ty& val)
{
    if (capacity() <= size()) {
        realloc(2, 2);
    }
    *(m_last++) = val;
}

Once rbegin() is implemented, back() can be re-written to use that rather than doing arithmetic on the result of end().

Exceptions

std::exception has no constructor that accepts a string literal - we need to use a more specific sub-class, such as std::out_of_range. We should consider whether we have range-checking at all, outside of methods such as at() which mandate it - standard C++ practice is to impose minimum overhead unless it's asked for.

Private members

Mostly looks okay, though alloc could be improved using std::move() algorithm instead of a hand-written copy loop, and simple delete[] buffer instead of calling destructor, as described above. It's also wise to allow this function to shrink the buffer; we'll need that for some of the as-yet-unimplemented code:

template<typename Ty>
void vector<Ty>::alloc(const std::size_t cap) {
    Ty* new_buffer = new Ty[cap];
    auto sz = size();
    if (sz < cap) {
        sz = cap;
    }
    std::move(m_first, m_first + sz, new_buffer);
    delete[] buffer;
    buffer = new_buffer;
    m_first = buffer;
    m_last = buffer + sz;
    m_end = buffer + cap;
}

Redundant member

Is there any need for separate buffer and m_first members? They have the same type, and as far as I can see, they always hold the same value.

@RiaD 2019-01-10 18:42:43

> This could be avoided by delegating to vector(count, T{}) you can't delegate this way in general case, in case there's no copy constructor and/or default ctor does something unusual e.g. fills its element with random value (and on copy values is copied)

@RiaD 2019-01-10 18:44:15

that's why they have replaced one ctor vector (size_type n, const value_type& val = value_type() with two separate ctors since c++11

@Toby Speight 2019-01-10 18:51:36

You're right @RiaD. I was misremembering, and thought that value_type needed to be DefaultConstructible.

@RiaD 2019-01-10 20:12:48

@Incomputable, sorry, but I don't understand how copy elision is relevant at all

@Incomputable 2019-01-10 20:21:23

I apologize for my negligence. Somehow I thought the story is only about one object being constructed. Perhaps I dismissed the rest of the problem too quickly.

Related Questions

Sponsored Content

2 Answered Questions

[SOLVED] A simple Vector implementation

  • 2018-08-23 21:58:24
  • DimChtz
  • 215 View
  • 4 Score
  • 2 Answer
  • Tags:   c++ vectors

2 Answered Questions

[SOLVED] std::vector for pods

  • 2018-07-29 08:40:40
  • bluedragon
  • 419 View
  • 4 Score
  • 2 Answer
  • Tags:   c++ vectors

6 Answered Questions

[SOLVED] Modern Vector implementation

4 Answered Questions

[SOLVED] STL vector implementation

3 Answered Questions

[SOLVED] Simplified implementation of std::vector in C++

  • 2016-07-28 05:30:59
  • Mantracker
  • 322 View
  • 6 Score
  • 3 Answer
  • Tags:   c++ array vectors

1 Answered Questions

[SOLVED] Second implementation of std::vector

1 Answered Questions

[SOLVED] Implementation of std::vector class

0 Answered Questions

C++ vector implementation errors

1 Answered Questions

[SOLVED] Vector implementation

1 Answered Questions

[SOLVED] Vector implementation - simple replacement

  • 2013-01-07 19:56:03
  • Valrandir
  • 2064 View
  • 4 Score
  • 1 Answer
  • Tags:   c++ vectors

Sponsored Content