2
\$\begingroup\$

I wrote a Vector (dynamic array) class with an iterator usable with std::sort() . It seems to pass my tests.

I wondering about the issues one can spot on this implementation. I compiled with C++17.

#include <iostream>
#include <numeric>

using std::cout, std::endl;

template<typename T>
struct Vector
{
    struct Iterator
    {
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;
        using iterator_category = std::random_access_iterator_tag;

        Iterator(value_type* ptr) : m_ptr(ptr) {}

        value_type& operator*()
        {
            return *m_ptr;
        }

        Iterator& operator--()
        {
            m_ptr--;
            return *this;
        }

        Iterator& operator++()
        {
            m_ptr++;
            return *this;
        }

        Iterator& operator++(int)
        {
            Iterator it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const Iterator& other) const
        {
            return m_ptr == other.m_ptr;
        }

        bool operator!=(const Iterator& other) const
        {
            return !(*this == other);
        }

        bool operator<(const Iterator& other) const
        {
            return *m_ptr < *other.m_ptr;
        }
        bool operator>(const Iterator& other) const
        {
            return *m_ptr > *other.m_ptr;
        }

        bool operator>=(const Iterator& other) const
        {
            return *m_ptr >= *other.m_ptr;
        }

        Iterator operator+(const size_t n) const
        {
            Iterator it = *this;
            it.m_ptr += n;
            return it;
        }

        Iterator operator-(const size_t n) const
        {
            Iterator it = *this;
            it.m_ptr -= n;
            return it;
        }

        size_t operator-(const Iterator& other) const
        {
            return m_ptr - other.m_ptr;
        }

        Iterator operator-=(const size_t n) const
        {
            Iterator it = *this;
            it.m_ptr -= n;
            return it;
        }

        Iterator operator+=(const size_t n) const
        {
            Iterator it = *this;
            it.m_ptr += n;
            return it;
        }

    private:
        value_type* m_ptr;
    };


    void allocate(size_t capacity)
    {
        capacity += m_capacity;

        T* data = new T[capacity];
        std::copy_n(m_data, m_capacity, data);

        m_capacity = capacity;

        delete[] m_data;
        m_data = data;
    }

    void push_back(T value)
    {
        if (!(m_index < m_capacity))
            allocate(3);

        m_data[m_index++] = value;
    }

    T& operator[](size_t index) { return m_data[index]; }

    size_t size() { return m_index; }

    size_t capacity() { return m_capacity; }

    Iterator begin()
    {
        return Iterator(m_data);
    }

    Iterator end()
    {
        return Iterator(m_data + m_index);
    }

private:
    size_t m_index = 0;
    size_t m_capacity = 0;
    T* m_data = nullptr;
};

void test()
{
    int A[] = {2,7,9,1,7};

    Vector<int> V1;
    
    cout << "size of A " << std::size(A) << endl;
    for (size_t i = 0; i < std::size(A); ++i)
        V1.push_back(A[i]);

    for (size_t i = 0; i < V1.size(); ++i)
    cout << V1[i] << endl;

    cout << "V capacity is " << V1.capacity() << endl;

    Vector<int>::Iterator beg = V1.begin();
    Vector<int>::Iterator end = V1.end();

    cout << "beg is " << *beg << endl;
    cout << "end is " << *end << endl;

    for (const auto& v : V1)
        cout << v << endl;

    if (beg < end)
        cout << "<" << endl;

    std::vector<int> v1 {2,7,9,1,7};
    std::vector<int>::iterator beg1 = v1.begin();
    std::vector<int>::iterator end1 = v1.end();

    cout << "-n " << *(end-1) << endl;
    cout << "+n " << *(beg+1) << endl;
    cout << " - " << end-beg << endl;

    cout << *(end -= 2) << endl;

    std::sort(V1.begin(), V1.end());

    for (auto& v : V1)
        cout << v << endl;
}

int main()
{
    cout << "starting... " << endl;

    test();

}
\$\endgroup\$

3 Answers 3

1
\$\begingroup\$

Before I get into the review, I need to offer some advice.

std::vector is a type of dynamic array, but not the only type. The thing that makes std::vector special is that it has extra capacity. You can reserve space in a vector, and fill that space in later with actual objects. That is handy for minimizing the number of allocations, and controlling when those allocations happen. The cost is a massive increase in complexity, and almost doubling the size needed for the type.

A simple dynamic array, on the other hand, does not have extra capacity. That means that every time you push another object into the array, it needs to reallocate and shuffle stuff around. On the other hand, such a dynamic array is much simpler, and the type itself only needs to store a pointer and a size.

If you are trying to remake std::vector, my advice to you is: don’t. It is hard. It is stupidly hard. I have seen literally hundreds of coders attempt it, and fail—and I mean “literally” quite literally; just do a search for vector re-implementation here at CodeReview, and you will see thousands of results, and almost all of them are wrong. Beginners frequently fall for the trap of thinking that because std::vector is easy to understand and use, then it must be easy to implement… but it is not. It may be the hardest thing in the entire standard library to implement. Yes, it is way harder to implement than std::string, std::map, std::thread, std::shared_ptr, and anything in the IOstreams library. Just about the only things in C++20 that are harder might be std::regex and some of the floating point conversion stuff.

Beginners also assume that if they do manage to figure out how to re-implement std::vector correctly, they will have learned a lot of useful C++. False. Most of the knowledge you need to correctly re-implement std::vector is useful only for re-implementing std::vector (or similar types), and does not provide any useful skills you can translate to any other problem domain.

So to summarize:

  • Re-implementing std::vector is a lot harder than you think it is.
  • You will get it wrong. I say this with almost 100% certainty.
  • You will not learn anything useful from the attempt.

Now, if you just want to make a simple dynamic array… that is a good learning project. And, it is useful. A simple dynamic array is a very useful type; sometimes std::vector is just too heavyweight. I have a simple dynamic array in my own personal code library, and I use it often. (Granted, my simply dynamic array is not that simple at all; it optimizes for small types and small allocations, and has a bunch of other nifty features which make it technically closer to std::vector than not… but it is still simpler than std::vector.)

So my advice is:

  • Don’t try to re-implement std::vector.
  • Make a simple dynamic array.

What you have right now is basically a simple dynamic array. This is good. Make it a good simply dynamic array, and you will gain both a good C++ learning experience, and a type you can actually use.

In particular, drop the idea of “capacity”, and ignore any advice that involves having a capacity that is not equal to the size. Just make a good, simple dynamic array.

Now, onto the code review.

You mentioned you are using C++17, but the current version is C++20… and, the actual current version is C++23, but the final approval was delayed (a knock-on effect from COVID), so although C++23 is finished, it is not actually formally published yet. In any case, you should upgrade at least to C++20. C++17 is already starting to become archaic.

Whenever you are making a thing—a type, a function, whatever—that seems like it might be useful, you should either:

  1. put it in a dedicated header file; or
  2. if you have access to more modern tools, put it in a module.

You should also put everything you make in your own namespace. You should avoid putting anything in the global namespace as much as possible.

So, assuming you are still using headers, your code should look something like this:

#ifndef KCFNMI_INCLUDE_GUARD_VECTOR
#define KCFNMI_INCLUDE_GUARD_VECTOR

// any includes you need go here

namespace kcfnmi {

template <typename T>
struct Vector
{
    // ... [snip] ...
};

} // namespace kcfnmi

#endif // include guard

And that should be in a file kcfnmi/vector.hpp, or something like that.

Then your test program would be:

#include <iostream>
// any other includes you need for testing

#include <kcfnmi/vector.hpp>

// not a fan of doing this, but if you really want:
using std::cout, std::endl;

// again, if you really want:
using kcfnmi::Vector;

void test()
{
    // ... [snip] ...
}

auto main() -> int
{
    cout << "starting... " << endl;

    test();
}

But you should really look into using a proper unit testing framework.

#include <iostream>
#include <numeric>

You only need <iostream> for testing, and I can’t figure out why you need <numeric> at all.

On the flip side, you use std::ptrdiff_t and std::size_t, but you don’t include <cstddef>. You use std::random_access_iterator_tag, but don’t include <iterator>. And you use std::copy_n, but don’t include <algorithm>.

template<typename T>
struct Vector

The convention in C++ is to use class if a type has an invariant. Your class does have an invariant; several actually. One is that m_capacity must always be greater than or equal to m_index. Another is that if m_data is not nullptr, then m_index (and/or) m_capacity must be equal to the number of elements in the array pointed to by m_data.

Another way of stating the same convention is if a type has any private members you should use class, not struct. Your type has private members, therefore it should be a class, not a struct.

Something you should look into is constraining T. Right now, as the type is written, you can use anything as T, even things that make no sense. When you do use something silly, you will either get bizarre and long-winded compile errors, or, worse, strange bugs.

For example, right now I could make a Vector of references, or functions, or even Vector<void>. None of those make any sense (and will probably not compile, depending on a number of factors).

Exactly how you want to constrain T is up to you. I’d suggest a good starting point is std::semiregular (actually, a good starting point is always std::regular, but that includes comparisons, and we don’t need that, so, std::semiregular). So:

template <std::semiregular T>
struct Vector

// or, equivalently
template <typename T>
requires std::semiregular<T>
struct Vector

Prior to C++20, you could still constrain the type, but it’s more complicated and less useful. Just move to C++20.

    struct Iterator
    {

So, here’s where I point out that your vector has no concept of const-correctness. To see what I mean, just try passing an instance of your vector through a const&, and try… well… anything:

auto test_1(Vector<int> const& v)
{
    // Can't even get the size!
    std::cout << v.size();
}

auto test()
{
    Vector<int> v;

    test_1(v);
}

The hardest part of container const-correctness is getting the iterators right. A common mistake people make is assuming that const_iterator is the same thing as const iterator. I’ve even seen blog points by purported C++ “experts” get that wrong.

The canonical way to make an iterator for a container is to make a base template with a bool template parameter that controls whether the iterator is const or not:

template <typename T>
class Vector
{
private:
    template <bool Const>
    class _iterator
    {
    public:
        using value_type = std::remove_cv_t<T>;

        using pointer   = std::conditional_t<Const, T const*, T*>;
        using reference = std::conditional_t<Const, T const&, T&>;

        // ... etc.
    };

public:
    using iterator       = _iterator<false>;
    using const_iterator = _iterator<true>;

    // ... etc.

It’s a little more complicated than that (you have to take into account implicit conversions from iterator to const_iterator), but that’s the basic idea.

        using iterator_category = std::random_access_iterator_tag;

This is fine, but C++20 introduced the contiguous iterator concept, which can net you huge performance gains. The way to use that is:

        using iterator_category = std::random_access_iterator_tag;
        using iterator_concept  = std::contiguous_iterator_tag;

That is, you shouldn’t set iterator_category to std::contiguous_iterator_tag, but rather use iterator_concept instead. (The reasons for why have to do with backward compatibility with crappily-written code, and are not worth going into.)

However… and here I have to pour a bit a cold water on your implementation… starting in C++20, there is a very easy way to test whether you’ve got an iterator done correctly. All you need to do is check with one of the iterator concepts. Unfortunately…:

auto main() -> int
{
    using iter = Vector<int>::Iterator;

    std::cout.setf(std::ios_base::boolalpha);
    std::cout << "indirectly readable:      " << std::indirectly_readable<iter>      << '\n';
    std::cout << "input-or-output iterator: " << std::input_or_output_iterator<iter> << '\n';
    std::cout << "input iterator:           " << std::input_iterator<iter>           << '\n';
    std::cout << "forward iterator:         " << std::forward_iterator<iter>         << '\n';
    std::cout << "bidirectional iterator:   " << std::bidirectional_iterator<iter>   << '\n';
    std::cout << "random access iterator:   " << std::random_access_iterator<iter>   << '\n';
    std::cout << "contiguous iterator:      " << std::contiguous_iterator<iter>      << '\n';
}

… produces…:

indirectly readable:      false
input-or-output iterator: true
input iterator:           false
forward iterator:         false
bidirectional iterator:   false
random access iterator:   false
contiguous iterator:      false

See here for the actual results.

In other words, your iterator fails almost every test.

A large part of the reason for this failing is the lack of const-correctness. When std::indirectly_readable checks operator*, it does so for a const iterator. But your operator* is not const qualified, so it fails. Simply adding const qualification to operator* makes it pass std::indirectly_readable… which immediately also makes it a valid std::input_iterator as well.

Of course, there’s a long way to go from there to a valid random-access iterator (let alone a valid contiguous iterator). (For example, I think the reason it’s failing the forward iterator test has to do with the dangling reference bug @Deduplicator mentioned.) But it’s a start.

        Iterator(value_type* ptr) : m_ptr(ptr) {}

This should not be a public constructor, and it absolutely should not be an implicit converting constructor. The way the iterator is written now, any T* can be implicitly converted to a Vector<T>::Iterator. That’s bad, because any random pointer is not likely to be a valid iterator value.

This constructor should be private, and the vector class should be a friend to access that constructor. (There are other tricks you could use, but this is the simplest.)

Also, the constructor should be explicit. And constexpr, and noexcept as well. In general, you could use constexpr pretty much everywhere. noexcept should only be used if a function/constructor/operator/whatever can never fail under any circumstance. This constructor should never fail.

You also need a public default constructor. It’s fine if it just sets m_ptr to nullptr. (It doesn’t matter what it sets m_ptr to, because no-one should ever dereference or do anything with a default-constructed iterator.) The default constructor should also be constexpr and noexcept.

        value_type& operator*()
        {
            return *m_ptr;
        }

This is mostly fine (but should be constexpr… but not noexcept, because it will fail if m_ptr is nullptr, or when it points to past-the-end). However, it should return reference, not value_type&. It should also be const qualified.

You are missing operator->, though.

        Iterator& operator--()

You’re missing suffix operator--.

        bool operator==(const Iterator& other) const
        {
            return m_ptr == other.m_ptr;
        }

As @Deduplicator mentioned, the modern way to do this is:

constexpr auto operator<=>(Iterator const&) const noexcept = default;

This will eliminate the need for operator!= and all the ordering operators… which, by the way…:

        bool operator<(const Iterator& other) const
        {
            return *m_ptr < *other.m_ptr;
        }
        bool operator>(const Iterator& other) const
        {
            return *m_ptr > *other.m_ptr;
        }

        bool operator>=(const Iterator& other) const
        {
            return *m_ptr >= *other.m_ptr;
        }

These are all wrong. You should not be de-referencing the pointers before comparing them.

And you’re missing operator<=. But it would be better to throw all these out and just use a defaulted operator<=>.

        Iterator operator+(const size_t n) const
        {
            Iterator it = *this;
            it.m_ptr += n;
            return it;
        }

It’s std::size_t. The std:: is not optional, but for historical reasons, most compilers allow it… for now. That will change soon.

But, in fact, std::size_t is not the right type to use here. You should be using the difference_type… which is std::ptrdiff_t, but you should just use difference_type. This is true for all of the random-access operations.

Also, while you support it + n, you don’t support n + it.

So that’s it for the iterator. Now into the guts of the actual container.

    void allocate(size_t capacity)
    {
        capacity += m_capacity;

        T* data = new T[capacity];
        std::copy_n(m_data, m_capacity, data);

        m_capacity = capacity;

        delete[] m_data;
        m_data = data;
    }

This really shouldn’t be a public function at all. There is no reason to give the the world this kind of access. If a user wants to add more objects, let them push_back() (or emplace_back()) one or append_range() several.

Now, consider this… after you grow the space with new T[capacity], you copy the existing objects into the new array. This is not great, because copying is usually expensive, and likely to throw. What you want to do is move, because moving is usually faster, and often no-fail.

However… if moving can fail, you don’t want to do that. To understand why, imaging there are 10 elements in the container. You are adding 1 more. So you allocate a new array with 11 spaces, and then start to move/copy the 10 elements into it. But then, after 5 elements, there is a failure! If you had copied the elements, then no problem… just delete the new array, and the old data is untouched. Buf if you had moved the elements, then the 5 elements that were already moved have been messed up.

This is actually such a critical concern that the standard library has a function for it: std::move_if_noexcept(). This will do the correct thing: move if it’s safe, and copy if it’s not. So:

auto allocate(std::size_t capacity)
{
    capacity += m_capacity;

    // USE SMART POINTERS!!!
    auto data = std::make_unique<T[]>(capacity);

    for (auto i = std::size_t{}; i < m_capacity; ++i)
        data[i] = std::move_if_noexcept(m_data[i]);

    auto p = data.release();
    data.reset(m_data);
    m_data = p;

    m_capacity = capacity;
}

Unfortunately, it means you have to write a manual loop, which is not great. There are ways you can do it better, but this will do.

    void push_back(T value)
    {
        if (!(m_index < m_capacity))
            allocate(3);

        m_data[m_index++] = value;
    }

You are making unnecessary copies. At the very least you should move in the last line.

Now, here is where I get back to what I talked about in the beginning. Forget having extra capacity. Drop m_capacity completely, and just keep track of the size with m_index (which should probably be named m_size). Don’t bother to allocate 3 extra spaces, or double the space, or any such nonsense. Just add one extra space, and move the provided value into it.

And consider what happens if moving that value fails. You need to clean up after yourself. So the function should be:

auto push_back(T value)
{
    // Allocate the new space.
    //
    // If this fails, no problem; we haven't touched anything yet.
    auto data = std::make_unique<T[]>(m_index + 1);

    // Copy/move the new value in.
    //
    // If this fails, no problem; we haven't touched anything yet.
    data[m_index] = std::move(value);

    // Copy/move the existing values in.
    //
    // If anything here fails, we were copying (because we won't move if
    // moving could fail), so no big deal. The original data is still
    // intact.
    for (auto i = std::size_t{}; i < m_capacity; ++i)
        data[i] = std::move_if_noexcept(m_data[i]);

    // Now all the data is where we want it in the new space.
    // Let's replace the old data with the new data.
    auto p = data.release();
    data.reset(m_data);
    m_data = p;

    // And increment the size.
    ++m_index;

    // The old data is cleaned up automatically.
}

If you want to break the re-allocation into its own function, you need to keep in mind the order stuff has to happen.

    T& operator[](size_t index) { return m_data[index]; }

This is fine (except it should be std::size_t, but you also need a const qualified version.

    size_t size() { return m_index; }

This should be const qualified, and noexcept (and constexpr, of course).

Also, you should consider that containers require a few standard types to be defined. A container needs value_type (which is just T), but it also needs:

  • reference
  • const_reference
  • iterator
  • const_iterator
  • difference_type
  • size_type

(Also, reverse_iterator and const_reverse_iterator for any container with bidirectional iterators or better.)

size_type can be defined as std::size_t, but you should use that instead of std::size_t in places like the return type of size().

    size_t capacity() { return m_capacity; }

As I mentioned; drop this. Just let the capacity always be the size.

    Iterator begin()
    {
        return Iterator(m_data);
    }

    Iterator end()
    {
        return Iterator(m_data + m_index);
    }

These should be const qualified and noexcept (and, as always, constexpr). However, there is a little wrinkle in that you should have a non-const begin() that returns iterator and a const begin() that returns const_iterator (and also a cbegin() that returns const_iterator). Same for end().

(You should also have rbegin() and rend() in const and non-const flavours, and crbegin() and crend().)

I mentioned above some of the things you need to make your iterator a proper iterator (not to mention a proper random-access or contiguous iterator), and a way to test that you’re compliant. Unfortunately there’s no such easy test for containers.

I would say for a dynamic array, your interface should be something like:

template <typename T>
class Vector
{
public:
    // Types ===========================================================
    using value_type = /*...*/;

    using reference       = /*...*/;
    using const_reference = /*...*/;

    using iterator       = /*...*/;
    using const_iterator = /*...*/;

    using reverse_iterator       = /*...*/;
    using const_reverse_iterator = /*...*/;

    using difference_type = /*...*/;
    using size_type       = /*...*/;

    // Default initializable ===========================================
    // Should be no-fail.
    constexpr Vector() noexcept;

    // Copyable ========================================================
    constexpr Vector(Vector const&);
    constexpr auto operator=(Vector const&) -> Vector&;

    // Copyable ========================================================
    // Should be no-fail.
    constexpr Vector(Vector&&) noexcept;
    constexpr auto operator=(Vector&&) noexcept -> Vector&;

    // Other construction ==============================================
    constexpr Vector(size_type, value_type const&);

    template <std::input_iterator I, std::sentinel_for<I> S>
    constexpr Vector(I, S);

    // From C++23:
    template <std::ranges::input_range R>
    constexpr Vector(std::from_range_t, R&&);

    constexpr Vector(std::initializer_list<value_type>);

    // Destruction =====================================================
    constexpr ~Vector();

    // Querying size ===================================================
    constexpr auto empty() const noexcept -> bool;

    constexpr auto size() const noexcept -> size_type;
    constexpr auto max_size() const noexcept -> size_type;

    // Iterators =======================================================
    constexpr auto begin()       noexcept ->       iterator;
    constexpr auto begin() const noexcept -> const_iterator;
    constexpr auto end()         noexcept ->       iterator;
    constexpr auto end()   const noexcept -> const_iterator;

    constexpr auto cbegin() const noexcept -> const_iterator;
    constexpr auto cend()   const noexcept -> const_iterator;

    constexpr auto rbegin()       noexcept ->       reverse_iterator;
    constexpr auto rbegin() const noexcept -> const_reverse_iterator;
    constexpr auto rend()         noexcept ->       reverse_iterator;
    constexpr auto rend()   const noexcept -> const_reverse_iterator;

    constexpr auto crbegin() const noexcept -> const_reverse_iterator;
    constexpr auto crend()   const noexcept -> const_reverse_iterator;

    // Swap ============================================================
    // Should be no-fail.
    constexpr auto swap(Vector&) noexcept -> void;
    friend constexpr auto swap(Vector&, Vector&) noexcept -> void;

    // Comparison ======================================================
    constexpr auto operator==(Vector const&) noexcept const -> bool;
    // operator!= is automatic as of C++20.

    // Assignment from initializer list ================================
    constexpr auto operator=(std::initializer_list<value_type>) -> Vector&;

    // Emplacement =====================================================
    template <typename... Args>
    constexpr auto emplace(const_iterator, Args&&...) -> iterator;

    // Assignment ======================================================
    constexpr auto assign(size_type, value_type const&) -> void;
    template <std::input_iterator I, std::sentinel_for<I> S>
    constexpr auto assign(I, S) -> void;
    constexpr auto assign(std::initializer_list<value_type>) -> void;

    // From C++23:
    template <std::ranges::input_range R>
    constexpr auto assign_range(R&&) -> void;

    // Insertion =======================================================
    constexpr auto insert(const_iterator, value_type const&) -> iterator;
    constexpr auto insert(const_iterator, value_type&&) -> iterator;
    constexpr auto insert(const_iterator, size_type, value_type const&) -> iterator;
    template <std::input_iterator I, std::sentinel_for<I> S>
    constexpr auto insert(const_iterator, I, S) -> iterator;
    constexpr auto insert(const_iterator, std::initializer_list<value_type>) -> iterator;

    // From C++23:
    template <std::ranges::input_range R>
    constexpr auto insert_range(const_iterator, R&&) -> iterator;

    // Erasure =========================================================
    constexpr auto erase(const_iterator) -> iterator;
    constexpr auto erase(const_iterator, const_iterator) -> iterator;

    // Clear ===========================================================
    // Should be no-fail.
    constexpr auto clear() noexcept -> void;

    // *****************************************************************
    // All of the above are REQUIRED for a standard sequence container
    // with contiguous storage.
    //
    // Everything below is optional.
    // *****************************************************************

    // Element access ==================================================
    constexpr auto operator[](size_type) -> reference;
    constexpr auto operator[](size_type) const -> const_reference;

    constexpr auto at(size_type) -> reference;
    constexpr auto at(size_type) const -> const_reference;

    constexpr auto front() -> reference;
    constexpr auto front() const -> const_reference;

    constexpr auto back() -> reference;
    constexpr auto back() const -> const_reference;

    // Front operations ================================================
    template <typename... Args>
    constexpr auto emplace_front(Args&&...) -> void;

    constexpr auto push_front(value_type const&) -> void;
    constexpr auto push_front(value_type&&) -> void;

    template <std::ranges::input_range R>
    constexpr auto prepend_range(R&&) -> void;

    constexpr auto pop_front() -> void;

    // Back operations =================================================
    template <typename... Args>
    constexpr auto emplace_back(Args&&...) -> void;

    constexpr auto push_back(value_type const&) -> void;
    constexpr auto push_back(value_type&&) -> void;

    template <std::ranges::input_range R>
    constexpr auto append_range(R&&) -> void;

    constexpr auto pop_back() -> void;

    // Contiguous data access ==========================================
    constexpr auto data() -> value_type*;
    constexpr auto data() const -> value_type const*;

    // Resizing ========================================================
    constexpr auto resize(size_type) -> void;
    constexpr auto resize(size_type, value_type const&) -> void;

    // Erasure =========================================================
    template <typename U>
    friend auto erase(Vector&, U const&) -> size_type;
    template <typename Pred>
    friend auto erase_if(Vector&, Pred) -> size_type;
};

template <std::input_iterator I, std::sentinel_for<I> S>
Vector(I, S) -> Vector<typename std::iterator_traits<I>::value_type>;

// From C++23:
template <std::ranges::input_range R>
Vector(std::from_range_t, R&&) -> Vector<std::ranges::range_value_t<R>>;

Which, as you can see, is a lot. But it’s not as bad as it seems, because there are really only a handful of functions that are fundamental, then most other functions can be implemented in terms of them. For example, if you implement:

template <typename... Args>
constexpr auto emplace(const_iterator, Args&&...) -> iterator;

Then all the following are just in terms of that:

// Insertion =======================================================
constexpr auto insert(const_iterator p, value_type const& v) -> iterator
{
    return emplace(p, v);
}

constexpr auto insert(const_iterator p, value_type&& v) -> iterator
{
    return emplace(p, std::move(v));
}

constexpr auto insert(const_iterator p, size_type n, value_type const& v) -> iterator
{
    auto const pos = p - begin();

    for (size_type i = 0; i < n; ++i)
        p = std::next(emplace(p, v));

    return begin() + pos;
}

template <std::input_iterator I, std::sentinel_for<I> S>
constexpr auto insert(const_iterator p, I first, S last) -> iterator
{
    auto const pos = p - begin();

    while (first != last)
        p = std::next(emplace(p, *first++));

    return begin() + pos;
}

constexpr auto insert(const_iterator p, std::initializer_list<value_type> il) -> iterator
{
    return insert(p, il.begin(), il.end());
}

// From C++23:
template <std::ranges::input_range R>
constexpr auto insert_range(const_iterator p, R&& r) -> iterator
{
    return insert(std::ranges::begin(r), std::ranges::end(r));
}

// Front operations ================================================
template <typename... Args>
constexpr auto emplace_front(Args&&... args) -> void
{
    emplace(begin(), std::forward<Args>(args)...);
}

constexpr auto push_front(value_type const& v) -> void
{
    emplace(begin(), v);
}

constexpr auto push_front(value_type&& v) -> void
{
    emplace(begin(), std::move(v));
}

template <std::ranges::input_range R>
constexpr auto prepend_range(R&& r) -> void
{
    insert(begin(), std::forward<R>(r));
}

// Back operations =================================================
template <typename... Args>
constexpr auto emplace_back(Args&&...) -> void
{
    emplace(end(), std::forward<Args>(args)...);
}

constexpr auto push_back(value_type const&) -> void
{
    emplace(end(), v);
}

constexpr auto push_back(value_type&&) -> void
{
    emplace(end(), std::move(v));
}

template <std::ranges::input_range R>
constexpr auto append_range(R&& r) -> void
{
    insert(end(), std::forward<R>(r));
}

And there’s more. Assigns are just clear() then insert(begin(), ...). These won’t necessarily be the most efficient implementations, but you can make them work first, then make them fast.

The really important stuff that you are missing are the copy/move operations, and the destructor. I’m actually shocked that no-one has pointed that out yet, because your class is a faucet for leaking memory. You need at least a destructor to free up all the memory allocated, and as soon as you add a destructor, you also need copy and move operations to properly shuffle the managed memory around.

That’s all! In summary:

  • Don’t try to re-implement std::vector. Don’t bother with extra capacity, growth strategies, or any of that nonsense. That stuff is stupendously hard to implement correctly, and not worth the effort of learning.
  • Move to C++20, at least. C++17 is already archaic.
  • Look up the standard requirements for iterators and containers, and try to match them.
  • At the very least, add a destructor to free up the allocated memory, and copy/move operations to manage it properly.
\$\endgroup\$
1
  • \$\begingroup\$ Really appreciate it Sir. Thanks! \$\endgroup\$
    – KcFnMi
    Feb 1 at 3:54
4
\$\begingroup\$

You could separate test-code and the header-only library-code you developed in your presentation. Doing so would make it clear that you aren't polluting consumers global scope with using.

Dangling reference

Iterator& operator++(int) is the wrong signature. Consider that var++ should return the value pre-increment, which implies a copy!

Review the contract

Compound-assignment-operators are expected to modify and return a reference to *this.

Inconsistency

I'm missing the pre-decrement and less-equal operators.

Contemporary features

You forego constexpr, thus your code cannot be used where that is needed.

Nor do you use noexcept, dooming other code to make sub-optimal choices in order to achieve its exception guarantees.

The <=>-operator is the modern way (C++20) to enable comparison. Sometimes it is even more efficient, like when chained. It is always less code, especially when defaulted, and thus harder to get wrong. Thus, consider upgrading.

auto simplifies coding too...

Potential overflow

allocate() fails to check for overflow.

Initializaion

Default-initializing the elements on reserving space for them is also a dubious decision. Often premature, wrong, or even impossible.

Growth-strategy

Always growing the same amount is a bad idea. Look for Shlemiel the painter.

const

Seems halfway down your container you ran out of const. Logically non-mutating operations should be thus marked, and there should be non-mutating variants where applicable.

Maybe recycling those hanging onto the compound-assignment-operators while revising their behavior would help?

Abundant explicit manual flushing

std::endl only adds a std::flush to '\n'. Thus it is longer, cannot be combined with bordering string-literals, and wastes resources.
In the few cases you actually need it, use std::flush to show you actually mean it.

Namespacing

Consider investing in a namespace for your library-code. It might prevent headaches.

\$\endgroup\$
1
  • \$\begingroup\$ I'd also take another look at operator+= and operator-= which are const and do not modify this. \$\endgroup\$ Jan 26 at 16:44
1
\$\begingroup\$

You can the allocate method to use a more aggressive growth strategy like doubling the capacity each time it runs out of space to reduce the number of allocations and copies as the vector grows.

void allocate(size_t capacity = 0)
{
    capacity = (capacity > 0) ? capacity : (m_capacity > 0) ? (2 * m_capacity) : 1;

    T* newData = new T[capacity];
    std::copy(m_data, m_data + m_index, newData);

    delete[] m_data;
    m_data = newData;
    m_capacity = capacity;
}

Overload push_back to accept rvalue references, allowing move semantics to be used when adding elements to the vector.

void push_back(const T& value)
{
    if (m_index >= m_capacity)
        allocate();
    m_data[m_index++] = value;
}

void push_back(T&& value)
{
    if (m_index >= m_capacity)
        allocate();
    m_data[m_index++] = std::move(value);
}
```
\$\endgroup\$

Your Answer

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

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