4
\$\begingroup\$

Out of the majority of my c++ projects, the most used thing is std::vector because it allows me to not have to my own memory management. However previously I had never really thought much about how std::vector works internally. Until recently and that's when I decided that to better understand std::vector I should attempt to reimplement it. Here is the code

vector.hh

#ifndef VECTOR_H
#define VECTOR_H

#include <memory>
#include <new>


/*https://en.cppreference.com/w/cpp/container/vector is very helpful*/
namespace turtle {
    namespace helper {
        constexpr size_t upper_power_of_two(size_t v) {
            v--;
            v |= v >> 1;
            v |= v >> 2;
            v |= v >> 4;
            v |= v >> 8;
            v |= v >> 16;
            if constexpr (sizeof(size_t) == 8) { v |= v >> 32; }
            v++;
            return v;
        }

        template<typename Pointer>
        constexpr auto distance(Pointer first, Pointer last) -> decltype(last - first) {
            return last - first;
        }
    }
    template<typename T, typename Alloc = std::allocator<T>>
    class vector
    {
    public:
        using value_type = T;
        using pointer = typename std::allocator_traits<Alloc>::pointer;
        using const_pointer = typename std::allocator_traits<Alloc>::const_pointer;
        using iterator = pointer;
        using const_iterator = const_pointer;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = const std::reverse_iterator<iterator>;
        using size_type = typename std::allocator_traits<Alloc>::size_type;
        using allocator_type = Alloc;
        using difference_type = typename std::allocator_traits<Alloc>::difference_type;
        using reference = T &;
        using const_reference = const T &;

        constexpr vector() noexcept(noexcept(Alloc())) = default;

        constexpr explicit vector(const allocator_type &alloc) noexcept: allocator_(alloc) {}

        constexpr vector(const size_type count, const T &value, const allocator_type &alloc = allocator_type())
                : allocator_(alloc) { resize(count, value); }

        constexpr explicit vector(size_type count, const allocator_type &alloc = allocator_type()) : allocator_(
                alloc) { resize(count); }

        template<typename InputIt>
        constexpr vector(InputIt first, InputIt last, const allocator_type &alloc = allocator_type()) : allocator_(
                alloc) { insert(begin(), first, last); }

        constexpr vector(const vector &other) { insert(cbegin(), other.cbegin(), other.cend()); }

        constexpr vector(const vector &other, const allocator_type &alloc) : allocator_(alloc) {
            insert(cbegin(), other.cbegin(), other.cend());
        }

        constexpr vector(vector &&other) noexcept: data_(other.data_), size_(other.size_), capacity_(other.capacity_) {
            other.data_ = nullptr;
            other.capacity_ = 0;
            other.size_ = 0;
        }

        constexpr vector(vector &&other, const Alloc &alloc) {
            *this = vector(other);
            allocator_ = alloc;
        }

        constexpr ~vector() {
            T_destroy(begin(), end());
            std::allocator_traits<allocator_type>::deallocate(allocator_, data_, capacity_);
        }

        constexpr vector(const std::initializer_list<T> &list, const Alloc &alloc = Alloc()) : allocator_(alloc),
                                                                                               size_(list.size()) {
            reallocate(list.size());
            std::uninitialized_move(list.begin(), list.end(), begin());
        }

        constexpr vector &operator=(const vector &other) {
            vector temp = other;
            swap(temp);
            return *this;

        }

        constexpr vector &operator=(const std::initializer_list<T> &other) {
            *this = vector(other);
            return *this;
        }

        constexpr void resize(const size_type &size) {
            if (size > capacity_) {
                reallocate(size);
                std::uninitialized_default_construct(begin() + size_, begin() + capacity_);
            } else if (size < size_) {
                T_destroy(begin() + size, begin() + size_);
            }
            size_ = size;
        }

        constexpr void resize(const size_type &size, const T &x) {
            if (size > capacity_) {
                reallocate(size);
                std::uninitialized_fill(begin() + size_, begin() + capacity_, x);
            } else if (size < size_) {
                T_destroy(begin() + size, begin() + size_);
            }
            size_ = size;
        }

        constexpr void reserve(const size_type &size) {
            if (size < capacity_) return;
            reallocate(size);
        }

        constexpr void clear() noexcept {
            T_erase_at_true_end(cbegin() + (capacity_ - size_));
            size_ = 0;
        }

        constexpr void shrink_to_fit() {
            reallocate(0);
            capacity_ = 0;
        }

        constexpr void push_back(const T &item) { emplace_back(item); }

        constexpr void push_back(T &&item) { emplace_back(std::move(item)); }

        template<typename... Args>
        constexpr void push_back(Args &&... args) { (push_back(std::forward<Args>(args)), ...); }

        constexpr void push_back(std::initializer_list<T> list) { insert(end(), list); }

        constexpr void pop_back() { resize(size_ - 1); }

        constexpr iterator insert(const_iterator pos, const T &item) {
            return T_insert(helper::distance(cbegin(), pos), item);
        }

        constexpr iterator insert(const_iterator pos, T &&item) {
            return T_insert(helper::distance(cbegin(), pos), std::move(item));
        }

        constexpr iterator insert(const_iterator pos, size_type count, const T &value) {
            return T_fill_insert(helper::distance(cbegin(), pos), count, value);
        }

        template<typename InputIterator>
        constexpr void insert(const_iterator pos, InputIterator first, InputIterator last) {
            T_fill_range(helper::distance(cbegin(), pos), first, last);
        }

        constexpr void insert(const_iterator pos, std::initializer_list<T> list) {
            T_fill_range(helper::distance(cbegin(), pos),
                         list.begin(),
                         list.end());
        }

        constexpr iterator erase(iterator pos) { return T_erase_at(pos); }

        constexpr iterator erase(iterator first, iterator last) { return T_erase_range(first, last); }

        template<typename... Args>
        constexpr void emplace_back(Args &&... args) {
            emplace(end(), std::forward<Args>(args)...);
        }

        template<typename... Args>
        constexpr void emplace(iterator pos, Args &&... args) {
            difference_type offset = pos - begin();
            T_grow(size_ + 1);
            size_++;
            /*shift array*/
            std::uninitialized_move(begin() + offset, end() - 1, begin() + offset + 1);
            std::allocator_traits<allocator_type>::construct(allocator_, data_ + offset, std::forward<Args>(args)...);
        }

        constexpr void swap(vector &other) {
            std::swap(other.data_, data_);
            std::swap(other.size_, size_);
            std::swap(other.capacity_, capacity_);
        }

        constexpr void assign(size_type count, const T &value) {
            if (count > size_) { resize(count); } //resize if necessary
            std::fill(begin(), end(), value);  // fill array
        }

        constexpr void assign(iterator first, iterator last) {
            clear();
            insert(begin(), first, last);
        }

        constexpr void assign(const std::initializer_list<T> &list) {
            clear();
            insert(begin(), list); //insert list
        }


        constexpr reference operator[](const size_type &index) noexcept { return *std::launder(begin() + index); }

        constexpr const_reference operator[](const size_type &index) const noexcept {
            return *std::launder(begin() + index);
        }

        constexpr reference at(const size_type &index) { return (*this)[index]; }

        constexpr const_reference at(const size_type &index) const { return (*this)[index]; }

        constexpr const T *data() const { return data_; }

        constexpr T *data() { return data_; }

        constexpr const_reference front() const { return *cbegin(); }

        constexpr const_reference back() const { return *cend(); }

        constexpr reference front() { return (*this)[0]; }

        constexpr reference back() { return (*this)[size_ - 1]; }

        constexpr const size_type &size() const { return size_; }

        constexpr const size_type &capacity() const { return capacity_; }

        constexpr bool empty() { return !size_; }

        constexpr size_type max_size() { return std::allocator_traits<allocator_type>::max_size(allocator_); }

        constexpr allocator_type get_allocator() const { return allocator_; }

        constexpr iterator begin() noexcept { return iterator(data_); }

        constexpr iterator end() noexcept { return iterator(data_) + size_; }

        constexpr const_iterator begin() const noexcept { return const_iterator(data_); }

        constexpr const_iterator end() const noexcept { return const_iterator(data_) + size_; }

        constexpr const_iterator cbegin() const noexcept { return const_iterator(data_); }

        constexpr const_iterator cend() const noexcept { return const_iterator(data_) + size_; }

        constexpr reverse_iterator rbegin() noexcept { return std::reverse_iterator(end()); }

        constexpr reverse_iterator rend() noexcept { return std::reverse_iterator(begin()); }

        constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }

        constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }

        constexpr bool operator==(const vector &rhs) const {
            if (size_ != rhs.size()) {
                return false;
            }  // if the to vectors size's don't match return false
            for (size_type i = static_cast<size_type>(0); i < size_; ++i) {
                if (rhs[i] != data_[i]) return false;
            }  // compare each item in both vectors
            return true;
        }

    private:
        T *data_ = nullptr;
        size_type size_ = 0;
        size_type capacity_ = 0;
        allocator_type allocator_;

        constexpr iterator T_fill_insert(difference_type offset, size_type n, const T &x) {
            T_grow(size_ + n);
            size_ += n;
            iterator pos = begin() + offset;
            std::uninitialized_move(pos, end() - n, pos + n);
            std::uninitialized_fill(pos, pos + n, x);  // fill
            return pos;
        }

        constexpr iterator T_insert(difference_type offset, const T &x) {
            T_grow(size_ + 1);
            size_++;
            iterator pos = begin() + offset;
            std::uninitialized_move(pos, end() - 1, pos + 1);
            std::allocator_traits<Alloc>::construct(allocator_, pos, x);
            return begin() + offset;
        }

        constexpr iterator T_insert(difference_type offset, T &&x) {
            T_grow(size_ + 1);
            size_++;
            iterator pos = begin() + offset;
            std::uninitialized_move(pos, end() - 1, pos + 1);
            std::allocator_traits<Alloc>::construct(allocator_, pos, std::move(x));
            return begin() + offset;
        }

        template<typename InputIterator>
        constexpr void T_fill_range(difference_type offset, InputIterator first, InputIterator last) {
            difference_type n = helper::distance(first, last);
            iterator pos;
            T_grow(size_ + n);
            size_ += n;
            pos = begin() + offset;
            std::uninitialized_move(pos, end() - n, pos + n);
            std::uninitialized_copy(first, last, pos);
        }

        constexpr bool T_grow(size_type size) {
            if (size > capacity_) {
                reallocate(helper::upper_power_of_two(size));
                return true;
            }
            return false;
        }

        constexpr void T_erase_at_end(const_iterator pos) {
            difference_type offset = helper::distance(cbegin(), pos);
            T_destroy(begin() + offset, end());
        }

        constexpr void T_erase_at_true_end(const_iterator pos) {
            difference_type offset = helper::distance(cbegin(), pos);
            T_destroy(begin() + offset, begin() + capacity_);
        }

        constexpr void reallocate(const size_type &newSize) {
            if (!data_) {
                data_ = allocator_.allocate(newSize);
                capacity_ = newSize;
            } else {
                T *temp = allocator_.allocate(newSize > capacity_ ? newSize : capacity_);
                std::uninitialized_move(data_, data_ + capacity_, temp);
                T_destroy(begin(), end());
                allocator_.deallocate(data_, capacity_);
                data_ = temp;
                capacity_ = newSize > capacity_ ? newSize : capacity_;
            }
        }

        constexpr iterator T_erase_range(iterator first, iterator last) {
            size_type offset = last - begin();
            size_type rangeSize = helper::distance(first, last);
            std::copy(first + rangeSize, end(), first);
            if (rangeSize) T_erase_at_end(begin() + capacity_ - rangeSize);
            size_ -= rangeSize;
            return (begin() + offset) >= end() ? end() : last == first ? begin() + offset : begin() + offset + 1;
        }

        constexpr iterator T_erase_at(iterator pos) {
            size_type offset = pos - begin();
            std::copy(pos + 1, end(), pos);
            T_erase_at_end(end() - 1);
            --size_;
            return (begin() + offset) >= end() ? end() : begin() + offset;
        }

        constexpr void T_destroy(iterator first, iterator last) {
            for (; first != last; first++)
                std::allocator_traits<allocator_type>::destroy(allocator_, first);
        }
    };

    template<typename T, typename Alloc, typename U>
    constexpr auto erase(vector<T, Alloc> &c,
                                               const U &value) {
        auto it = std::remove(c.begin(), c.end(), value);
        auto r = helper::distance(it, c.end());
        c.erase(it, c.end());
        return r;
    }

    template<typename T, typename Alloc, typename Pred>
    constexpr auto erase_if(vector<T, Alloc> &c,
                                                  const Pred &pred) {
        auto it = std::remove_if(c.begin(), c.end(), pred);
        auto r = helper::distance(it, c.end());
        c.erase(it, c.end());
        return r;
    }

    namespace pmr {
        template<typename T>
        using vector = turtle::vector<T, std::pmr::polymorphic_allocator<T>>;
    }
}  // namespace turtle

#endif  // VECTOR_H
\$\endgroup\$
7
\$\begingroup\$

First of all, I have to commend you on even attempting this undertaking. As you probably discovered, std::vector is a lot more complicated than it first appears. I believe implementing std::vector is a very good learning exercise… especially if you’re going to go whole hog and make it allocator-aware (whenever I’ve had students reimplement std::vector, I don’t ask them to add allocator support, because it’s so complicated (and, historically, woefully underspecified)).

And reimplmenting std::vector is not even really a waste of time, because there are ways you can actually improve on std::vector: for example, by implementing the “small string optimization” trick, which is illegal for std::vector due to iterator invalidation requirments, but could be a massive performance gain. I note you’ve actually added some extra functions.

So kudos for even attempting this. And it’s a really good attempt, too!

So, let’s dive into the review:

constexpr size_t upper_power_of_two(size_t v) {
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    if constexpr (sizeof(size_t) == 8) { v |= v >> 32; }
    v++;
    return v;
}

One of my biggest pet peeves when reviewing people’s code—and pretty much the first thing I look for—is bad comments… or worse, no comments. Now, in your case you can mostly get away without comments, because you’re simply reimplementing std::vector… it doesn’t really make a lot of sense to have a bunch of comments like /* void push_back(T const&): Does what std::vector::push_back(T const&) does. */. But for things like this function… you really do need comments to explain what you’re doing, and why.

So, what I’m assuming is that you want your vector’s size when automatically growing—when the size isn’t specifically being set, such as in a call to resize() or reserve()—to always be a power of 2. That’s cool; there’s nothing wrong with that… but I can’t help but wonder if that’s not just based on a misunderstanding of growth factors. Most standard library vectors have a growth factor of 2 (I think Dinkumware’s is 1.5)… but that doesn’t mean the vector’s size is a power of 2. It just means they multiply the current size by 2. So your T_grow() function’s guts would look something like: reallocate(max(capacity_ * 2, size));.

The thing with what you’re doing is that in the worst case scenario, the vector’s size will grow to almost double the requested size… as opposed to double the current size. For example, imagine the current capacity is 10,000, and I want to put 17,000 elements in it. If you do max(10'000 * 2, 17'000), that will give you a new capacity of 20,000. But if you do upper_power_of_two(17'000), that will give you 32,768… almost 13,000 more than with a growth factor of 2, and almost 16,000 more than we actually need. In fact, your vector will never allocate less than with a growth factor of 2 strategy. The benefit of that: much less frequent allocations. The downside: much more memory used. That may or may not be a trade-off that works for you.

Anywho, as for the function itself, I should note that you’ve wisely checked to make sure that std::size_t is 64 bits before doing the last bit shift. Buuuuut….

  1. You assume that sizeof(std::size_t) == 8 means 64 bits. No, that just means that 8 bytes… and a byte is not necessarily 8 bits. If you’re going to assume 8 bit bytes, you should confirm that by checking CHAR_BIT.
  2. You check that the size is equal to 8 bytes… but what if you’re on a system with 8 bit bytes and 128 bit std::size_t (it could happen!). Then sizeof(std::size_t) would be 16. I think what you meant was sizeof(std::size_t) >= 8.
  3. You don’t take into account that std::size_t could be 16 bits. It could be!

This functon could actually be greatly simplified by not unrolling the loop. For example:

constexpr auto upper_power_of_two(std::size_t v)
{
    constexpr auto bit_size = std::size_t(CHAR_BIT * sizeof(std::size_t));
    
    --v;
    for (auto i = std::size_t{1}; i < bit_size; ++i)
        v |= v >> i;
    return ++v;
}

Now it will correctly handle any size of std::size_tany size of byte… and you count on any half-decent compilier automatically unrolling the loop for you (or, if it’s really smart, maybe recognizing what you’re doing and using some intrinsics).

template<typename Pointer>
constexpr auto distance(Pointer first, Pointer last) -> decltype(last - first) {
    return last - first;
}

The trailing return type is a little redundant here. I assume the point of this function is so you don’t need to include <iterator>? But, thing is, you already need <iterator> anyway because you’re using std::reverse_iterator (and, in fact, your code is wrong for not including it, though I suppose it “works” because it’s picking the header up transitively somehow, probably via <memory>).

So you might as well include <iterator>, and then use std::distance().

template<typename T, typename Alloc = std::allocator<T>>
class vector
{

Now, I would recommend that you always practice safe specialization with your templates, and check that the types the template is being instantiated with are types that make sense. That generally means that you should have a bunch of static_assert statements, verifying your template parameters.

What things should you check for? Well, figuring that out is a large part of figuring out your type and its interface. But as an example, in this case, it might be wise to make sure that T isn’t a reference type with static_assert(not std::is_reference_v<T>).

constexpr vector(const vector &other) { insert(cbegin(), other.cbegin(), other.cend()); }

You copy the other vector’s contents here… but you don’t copy its allocator.

And unfortunately, doing so isn’t as simple as allocator_(other.allocator_). What you need to do is:

constexpr vector(const vector &other) :
    allocator_(std::allocator_traits<Alloc>::select_on_container_copy_construction(other.allocator_))
{ insert(cbegin(), other.cbegin(), other.cend()); }

You also forget to move the allocator when moving the vector:

constexpr vector(vector &&other) noexcept: data_(other.data_), size_(other.size_), capacity_(other.capacity_) {
    other.data_ = nullptr;
    other.capacity_ = 0;
    other.size_ = 0;
}

Luckily this is an easy fix, because you can just do allocator_(std::move(other.allocator_)) and everything else is cool.

Unfortunately…

constexpr vector(vector &&other, const Alloc &alloc) {
    *this = vector(other);
    allocator_ = alloc;
}

… things are not going to be so simple here.

If alloc and other._allocator compare equal, then you can safely treat them as indistinct, meaning you can deallocate stuff using alloc even if it was originally allocated by other._allocator. That allows you to do a simple move of the pointer:

constexpr vector(vector &&other, const Alloc &alloc) :
    _allocator(alloc)
{
    if (_allocator == other._allocator)
    {
        using std::swap;
        
        swap(data_, other.data_);
        swap(size_, other.size_);
        swap(capacity_, other.capacity_);
    }
    else
    {
        // ...
    }
}

But if the allocators don’t compare equal, then you can’t use allocator_ to deallocate data_ that was allocated by other.allocator_. In that case, your only recourse is to copy:

constexpr vector(vector &&other, const Alloc &alloc) :
    _allocator(alloc)
{
    if (_allocator == other._allocator)
    {
        using std::swap;
        
        swap(data_, other.data_);
        swap(size_, other.size_);
        swap(capacity_, other.capacity_);
    }
    else
    {
        insert(begin(), other.cbegin(), other.cend());
    }
}

Now you’re probably guessing that if the copy and move constructors were that complicated, the assignment ops are going to be much, much worse. If so, you’d be right.

But first, there’s one more major allocator complication I have to mention:

constexpr vector(const std::initializer_list<T> &list, const Alloc &alloc = Alloc()) : allocator_(alloc),
                                                                                       size_(list.size()) {
    reallocate(list.size());
    std::uninitialized_move(list.begin(), list.end(), begin());
}

Now, you use std::uninitialized_move() and its siblings quite a bit, and that’s good… but… the problem is that what you should be using is std::allocator_traits<Alloc>::construct(). And unfortunately, std::uninitialized_move() doesn’t use that.

What that means is—and you’re going to hate me for telling you this—you need to reimplment all those uninitialized functions in terms of std::allocator_traits<Alloc>::construct(). Yeah. All of them. (Well, the ones you use anyway.)

You may be think that’s madness, and why doesn’t the standard library have uninitialized functions for allocators?! I wholeheartedly agree. I’ve seen some proposals for them in the past, but I don’t think they’ve been championed yet. But yes, the standard library absolutely should support allocators with those uninitialized algorithms. It should also have a smart pointer for allocator-allocated memory (which you’re going to see come up later). Unfortunately, we have to work with what we’ve got.

So you’ll need to reimplement all those uninitialized algorithms you use in terms of allocators, and use them instead of the ones you’re using now. I’m sorry to be the one to tell you this. Yeah, this is why I don’t push my students to work with allocators.

Anywho, moving on….

constexpr vector &operator=(const vector &other) {
    vector temp = other;
    swap(temp);
    return *this;
}

This is great; this would be the correct thing to do… if allocators weren’t a factor. Let’s put allocators aside for the moment, though. Although this creates an entire third vector, with a possibly redundant internal memory buffer, that’s what you need to do to account for exceptions.

Except… not always though, eh?

Because if T is noexcept copyable, then all you need to do is possibly grow the internal memory buffer (if and only if other.size() > this->capacity()… then just copy over whatever’s there. In other words:

constexpr auto operator=(vector const& other) -> vector&
{
    if constexpr (std::is_nothrow_copy_constructible<T>)
    {
        if (capacity() < other.size())
            // This might conceivably throw.
            reserve(other.size());
        
        // This shouldn't throw, because all it should do is destruct
        // all existing elements (and destructors shouldn't throw),
        // then copy construct all the new ones (and we've confirmed
        // that this can't throw).
        assign(other.cbegin(), other.cend());
    }
    else
    {
        auto temp = other;
        swap(temp);
    }
    
    return *this;
}

If you don’t have to worry about allocators, this can be a much more efficient pattern if, for example, you’re copying a million ints over a vector that already held a million ints.

Buuuut we do have to worry about allocators…

… or do we?

First let’s fix what we already have, assuming we don’t need to copy the allocator from other. The first branch of that if is fine. The else branch, however, has a problem, because when temp is constructed, it is constructed with a copy of other.allocator_. That’s not what we want; we want a copy of this->allocator_. So at the very least you’d need:

    else
    {
        auto temp = vector(other, allocator_);
        swap(temp);
    }

But even that’s problematic, because allocator copying and swapping and so on… it’s a goddam mess that you’d be better off avoiding.

A better strategy is simply to use this->allocator_ to allocate the memory you directly, copy into it, and then just swap the data_ pointer. Assuming you’ve got a std::unique_ptr-like-type for allocators called allocator_ptr type—which is trivial to make—you could do something like:

    else
    {
        // Maintain the existing capacity.
        auto const new_capacity = std::max(capacity_, other.size());
        
        // Internally calls std::allocator_traits<Alloc>::allocate()
        // with the given args to allocate the memory.
        auto p = allocator_ptr<Alloc>{
            allocator_,
            new_capacity,
            data_  // try for locality if possible
        };
        
        // Do the copy.
        std::uninitialized_copy(other.cbegin(), other.cend(), p.get());
        
        // Swap the pointers.
        auto old_p = data_;
        data_ = p.release();
        p.reset(old_p);
        
        // Clean up old data.
        for (auto p = old_p; p < (old_p + size_); ++p)
            std::allocator_traits<Alloc>::destroy(allocator_, p);
        
        // Make sure the other members are kosher.
        size_ = other.size();
        capacity_ = new_capacity;
        
        // And we're done. Old data will be automatically freed.
    }

But I note that all of the above is simply assign(other.cbegin(), other.cend())… assuming assign() is exception-safe (the current one isn’t).

So if you don’t need to propagate the allocator, all you need is the code above (which is ultimately just assign(other.cbegin(), other.cend())). But what if you do? First, you should check to see if you do:

constexpr auto operator=(vector const& other) -> vector&
{
    if constexpr (std::allocator_traits<Alloc>::propagate_on_container_copy_assignment)
    {
        // ...
    }
    else // no need to propagate the allocator
    {
        assign(other.begin(), other.end());
    }
    
    return *this;
}

Now you can just copy the allocator, use it to allocate new memory, and copy the contents of other into it, using exactly the same pattern that was used above (except the allocator has to be transferred as well):

constexpr auto operator=(vector const& other) -> vector&
{
    if constexpr (std::allocator_traits<Alloc>::propagate_on_container_copy_assignment)
    {
        auto alloc = other.allocator_;
        
        // Maintain the existing capacity.
        auto const new_capacity = std::max(capacity_, other.size());
        
        // Internally calls std::allocator_traits<Alloc>::allocate()
        // with the given args to allocate the memory.
        auto p = allocator_ptr<Alloc>{
            alloc,
            new_capacity,
            data_  // try for locality if possible
        };
        
        // Do the copy.
        std::uninitialized_copy(other.cbegin(), other.cend(), p.get());
        
        // Swap the pointers.
        auto old_p = data_;
        data_ = p.release();
        p.reset(old_p);
        
        // Clean up old data.
        for (auto p = old_p; p < (old_p + size_); ++p)
            std::allocator_traits<Alloc>::destroy(allocator_, p);
        
        // Make sure the other members are kosher.
        size_ = other.size();
        capacity_ = new_capacity;
        
        // And of course, the allocator.
        allocator_ = std::move(alloc);
        
        // And we're done. Old memory will be automatically freed.
    }
    else // no need to propagate the allocator
    {
        assign(other.begin(), other.end());
    }
    
    return *this;
}

And that’ll work just fine.

BUT! You can do even better! You can test if alloc and this->allocator_ are equal and T objects are no-throw copyable and other.size() < capacity_. If all those things are true, you don’t need to allocate new memory… you can simply overwrite what’s in data_ (and of course, don’t forget to copy alloc). I’ll leave that for you to figure out.

constexpr void reserve(const size_type &size) {
    if (size < capacity_) return;
    reallocate(size);
}

This function isn’t wrong, but its structure is a little bizarre. The return is hidden off to the right, so it’s easy to miss, leading one to misread the function logic. In fact, I think the logic might actually be wrong—do you really want to call reallocate() if size == capacity_?

It just seems much more straightforward to do things the other way around:

constexpr void reserve(size_type size) {
    if (size > capacity_)
        reallocate(size);
}

(That also presumes you don’t want to reallocate if the requested size equals the existing capacity.)

constexpr void shrink_to_fit() {
    reallocate(0);
    capacity_ = 0;
}

This… seems wrong.

If I’m reading the code right, then reallocate(0) will simply reallocate the existing capacity. But that’s not the point of shrink_to_fit(). In fact, it seems completely pointless to just reallocate the existing buffer at the exact same size.

What shrink_to_fit() should do is reallocate the buffer if the capacity doesn’t equal the size. And in that case, it should allocate a buffer where the capacity does equal the size. You can’t do that with your existing interface for reallocate(), because reallocate() will never allocate less than the current capacity.

And setting capacity_ to zero? Why? That just seems completely wrong.

What you want seems something more like:

constexpr void shrink_to_fit() {
    if (size_ != capacity_)
    {
        auto p = allocator_ptr{allocator_, size_};
        // or allocator_ptr{allocator_, size_, data_}; for locality
        
        std::unitialized_copy_n(data_, size_, p.get());
        
        auto old_p = data_;
        data_ = p.release();
        p.reset(old_p);
        for (auto p = old_p; p < (old_p + size_); ++p)
            std::allocator_traits<Alloc>::destroy(allocator_, p);
        
        capacity_ = size_;
    }
}

And because shrink_to_fit() is non-binding, you could also use a more intelligent heuristic to decide whether or not to actually reallocate. Like, only reallocate if the current capacity is greater than 1.5 times the size; otherwise ignore the request. That’s up to you.

template<typename... Args>
constexpr void push_back(Args &&... args) { (push_back(std::forward<Args>(args)), ...); }

I’m not sure this is a wise interface choice, given the similarity between push_back() and emplace_back(). For example, suppose you have a type that is constructible from either a single int or a number of ints:

// These both do the same thing:
v.push_back(0);
v.emplace_back(0);

// These do very different things:
v.push_back(0, 1, 2);
v.emplace_back(0, 1, 2);

But a careless code maintainer might be following the rule-of-thumb to replace push_back() with emplace_back(). The new code will compile without any warnings, but behave differently.

I’d also take careful consideration of whether push_back() is allowed to take zero arguments. Does vec.push_back(); makes sense? Bear in mind:

// These do very different things:
v.push_back();
v.emplace_back();

Now, a function that appends a number of items isn’t a bad idea. I just don’t think push_back() is a good name, given its symmetry with emplace_back(). Perhaps push_back_n()? In any case, if you’re going to do it, I suggest reserving size_ + sizeof...(Args).

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

// ...

template<typename... Args>
constexpr void emplace(iterator pos, Args &&... args) {

Just FYI, emplace() and emplace_back() return references to the emplaced object, which is really handy for emplace() especially, because you can do auto&& x = v.emplace(/* ... */); and then play with the emplace-constructed x.

constexpr void swap(vector &other) {
    std::swap(other.data_, data_);
    std::swap(other.size_, size_);
    std::swap(other.capacity_, capacity_);
}

Ah, here we go again with allocators.

So the code above is fine if you don’t need to propagate the allocator on swap and the two allocators are equal. If you need to propagate the allocator, well then, you need to propagate the allocator. If the two allocators aren’t equal, then you can’t use allocator 1 to deallocate the stuff allocated by allocator 2. And logically, if you’re not supposed to swap the allocators, then you can’t swap the pointers if the allocators are not equal. In fact, the standard vector says if the allocators are not equal, then swapping is UB.

So here’s what the standard actually asks of vector’s swap, as of C++17 (well, with constexpr from C++20 added):

constexpr void swap(vector& other)
    noexcept(std::allocator_traits<Alloc>::propagate_on_container_swap::value
        || std::allocator_traits<Alloc>::is_always_equal::value)
{
    using std::swap;
    
    if constexpr (std::allocator_traits<Alloc>::propagate_on_container_swap)
    {
        swap(allocator_, other._allocator);
    }
    else if constexpr (not std::allocator_traits<Alloc>::is_always_equal)
    {
        assert(allocator_ == other.allocator_);
    }
    
    swap(data_, other.data_);
    swap(size_, other.size_);
    swap(capacity_, other.capacity_);
}

You don’t actually need the assert if you’re okay with just allowing UB. Or maybe you could just have it assert in debug mode or something.

constexpr void assign(size_type count, const T &value) {
    if (count > size_) { resize(count); } //resize if necessary
    std::fill(begin(), end(), value);  // fill array
}

This… seems a little dodgy. I’m all for code reuse, but what this function is actually doing is not what it advertises. First it resizes the internal buffer… except, no, that’s not all it does; it resizes the internal buffer and possibly fills it out by default-constructing a bunch of Ts. That will “work” assuming two things:

  1. T’s default constructor and copy constructor have no observable side effects; and
  2. T actually has a default constructor.

One of the reasons I use the assign(n, t) function in vectors is specifically for types that don’t have a default constructor. But that won’t work with this vector.

The other issue here is exception safety. What happens if one of the copy constructors throws? Your vector will be in an unknown (though valid) state.

I’m afraid you’re going to need to rethink this. It’s a lot more complicated at first glance:

  1. If the capacity is less than count, you need to allocate a new buffer. No problem: allocate, then std::uninitialized_fill_n(), then swap the newly allocated buffer with the old one and clean up the old stuff. This can all be done exception-safe. Job done.
  2. Otherwise, if capacity is greater than or equal to count AND copy construction and assignment are non-throwing, you can assign-in-place safely, but it’s potentially a multi-stage job. a. First you can use std::fill(begin(), end(), value) to overwrite the existing elements, if any. b. Then you can use std::uninitialized_fill(end(), begin() + count, value) to initialize the remaining elements, if any. c. Then just set size_ to count and you’re done.

Though I’d recommend against using std::fill() specifically, because that would require including <algorithm>… and <algorithm> is a heavyweight header.

constexpr void assign(iterator first, iterator last) {
    clear();
    insert(begin(), first, last);
}

This is a rather destructive assign(), that doesn’t offer the strong exception guarantee. I also think you’ve got the interface wrong.

For starters, I think this should actually be a function template that takes two Iterator arguments… not a non-template that takes two turtle::vector<T>::iterator arguments. Right now, this function can only assign from another turtle::vector<T> (note: not even a const one, either, because it takes non-const iterators).

So I think you want:

template <typename InputIterator>
constexpr void assign(InputIterator first, InputIterator last) {
    // ...

(or, using future-style iteration…)

template <typename InputIterator, typename Sentinel>
constexpr void assign(InputIterator first, Sentinel last) {
    // ...

(but let’s ignore future-style iteration for now)

Now if the iterator category really is InputIterator… then yeah, all you can do is clear() and insert().

However! If the iterator category is ForwardIterator or better… then you can be smarter. You can first determine the size, and if copy construction/assignment is non-throwing, and potentially assign right into the existing buffer. Even if you can’t assign into the existing buffer, knowing the size lets you allocate a properly-sized buffer and then you can std::uninitialized_fill() right into that.

And for the next function, this is definitely the case…:

constexpr void assign(const std::initializer_list<T> &list) {
    clear();
    insert(begin(), list); //insert list
}

… because you know for a fact that std::initializer_list’s iterators are random access. (Plus, std::initializer_list has a size() function.) If the iterator version of assign() is done properly, then this could just be:

constexpr void assign(std::initializer_list<T> list) {
    assign(list.begin(), list.end());
}

(Incidentally, you should never need to pass std::initializer_list around by const&. It’s like std::string_view or std::span in that it’s designed to be passed around by-value.)

constexpr reference operator[](const size_type &index) noexcept { return *std::launder(begin() + index); }

constexpr const_reference operator[](const size_type &index) const noexcept {
    return *std::launder(begin() + index);
}

Why are you using std::launder() here? You’re not doing any type-punning or other mischief so far as I can see.

constexpr reference at(const size_type &index) { return (*this)[index]; }

constexpr const_reference at(const size_type &index) const { return (*this)[index]; }

You’re kinda missing the whole point of at() here, which is to throw std::out_of_range if index is greater than or equal to size().

Also, there’s no point in taking size_type by const& (or returning it by const&, as you do in some other functions). By definition size_type must be an unsigned integer type. You gain nothing by working with references to it (and probably lose out because it’s harder to optimize).

constexpr const_reference back() const { return *cend(); }

You got a little bug here, because cend() points to one-past-the-last-element… not the last element.

constexpr iterator T_fill_insert(difference_type offset, size_type n, const T &x) {
    T_grow(size_ + n);
    size_ += n;
    iterator pos = begin() + offset;
    std::uninitialized_move(pos, end() - n, pos + n);
    std::uninitialized_fill(pos, pos + n, x);  // fill
    return pos;
}

There are some problems here due to being sloppy about keeping track of when you can just move or fill, and when you need to do an uninitialized move or fill. There are multiple possibilities here:

  1. All new elements are overwriting existing elements; all moved elements are going into uninitialized space.
  2. All new elements are overwriting existing elements; some moved elements are overwriting existing elements, others are going into uninitialized space.
  3. Some new elements are overwriting existing elements, others are going into uninitialized space; all moved elements are going in uninitialized space.
  4. All new elements are going into uninitialized space (no moved elements; this would be a pure append).

You also need to take exception safety into account.

If you need to reallocate, then things are easy: just uninitialized copy the before and after elements, and uninitialized fill the space between. (But do keep exception safety in mind!)

But if moves are non-throwing, and your capacity is enough, then you can move and fill in-place, even if copy assignment might throw. (If a copy does throw, then just “un-move” what you moved at the beginning.)

constexpr iterator T_insert(difference_type offset, const T &x) {

To help you simplify things, note that this is just T_fill_insert(offset, 1, x).

template<typename InputIterator>
constexpr void T_fill_range(difference_type offset, InputIterator first, InputIterator last) {
    difference_type n = helper::distance(first, last);
    iterator pos;
    T_grow(size_ + n);
    size_ += n;
    pos = begin() + offset;
    std::uninitialized_move(pos, end() - n, pos + n);
    std::uninitialized_copy(first, last, pos);
}

If you tried this function with an actual InputIterator, you’d be in for a rude surprise.

First of all, it won’t compile, because helper::distance() will only work with random access iterators or better. Only random access iterators or better support operator-().

But even if you fixed helper::distance() (or, better, used std::distance() instead), while this would now compile, it still won’t work. That’s because input iterators only allow a single pass. Once you’ve done distance(), you’ve burned up your single use. So the call to std::uninitialized_copy() at the end will copy nothing.

What you need here is two functions—or a single function with two implementations via if constexpr.

For input iterators… there’s simply no option other than doing a for loop inserting elements one at a time. This isn’t so bad because you’ll either have enough capacity to avoid a reallocation, or you’ll grow by your growth factor, so you won’t be reallocating on every iteration of the for loop.

For forward iterators or better… well now you can use distance(), then pre-allocate if necessary, and so on. From that point, you just need to take the usual precautions regarding exception safety (that is, either using a whole new buffer, or—if moves are non-throwing—possibly trying to do the fill in-place).

constexpr void reallocate(const size_type &newSize) {
    if (!data_) {
        data_ = allocator_.allocate(newSize);
        capacity_ = newSize;
    } else {
        T *temp = allocator_.allocate(newSize > capacity_ ? newSize : capacity_);
        std::uninitialized_move(data_, data_ + capacity_, temp);
        T_destroy(begin(), end());
        allocator_.deallocate(data_, capacity_);
        data_ = temp;
        capacity_ = newSize > capacity_ ? newSize : capacity_;
    }
}

The first part of this function is fine.

The second part is fine if moves are non-throwing. If moves can throw, you have to do copies instead. (Fun fact: there’s actually a function called std::move_if_noexcept() that was created specifically for this problem… that, hilariously, is actually useless in practice because you’re usually moving/copying into uninitialized memory, as you are here.)

Luckily, the fix here is trivial:

constexpr void reallocate(size_type newSize)
{
    if (!data_)
    {
        data_ = std::allocator_traits<Alloc>::allocate(allocator_, newSize);
        capacity_ = newSize;
    }
    else
    {
        auto const newCapacity = newSize > capacity_ ? newSize : capacity_; // DRY
        
        auto temp = std::allocator_traits<Alloc>::allocate(allocator_, newCapacity); // possibly with _data as hint for locality
        if constexpr (std::is_nothrow_move_constructible_v<T>)
        {
            std::uninitialized_move_n(std::to_address(data_), size_, std::to_address(temp));
        }
        else
        {
            try
            {
                std::uninitialized_copy_n(std::to_address(data_), size_, std::to_address(temp));
            }
            catch (...)
            {
                std::allocator_traits<Alloc>::deallocate(allocator_, temp, newCapacity);
                throw;
            }
        }
        
        T_destroy(begin(), end());
        std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
        
        data_ = temp;
        capacity_ = newCapacity;
    }
}

Finally, your data members:

T *data_ = nullptr;
size_type size_ = 0;
size_type capacity_ = 0;
allocator_type allocator_;

data_ should really be pointer, not T*.

As for allocator_… the thing is that allocators quite often are empty. However, if you include an allocator data member like this, then it takes up space in your class even though it doesn’t need to. In C++20, you can use [[no_unique_address]]. Prior to that, you’d use the empty base optimization trick. Frankly, I’d suggest not bothering with EBO; it’s going to be obsolete in a few months.

I think that’s it!

Summary

There are only a very small number of critical bugs in the code:

  • Your custom helper::distance() function only supports random access iterators, though you use it for other iterator categories.
  • In a couple places, you copy/move pointers without copying the allocators as well. This could cause a situation where you’re deallocating memory with the wrong allocator.
  • In shrink_to_fit() you set the capacity to zero… which is almost sure to lead to crashes and/or leaks.
  • In the const version of back(), you dereference past-the-end.

There are a few potential problems that aren’t necessarily bugs (though could become bugs depending on your intended usage):

  • There are a few places where exception safety doesn’t even meet the minimal weak guarantee (where an exception will not only leave the object in an unknown state, it will almost certanly lead to UB).
  • There are a few places where you don’t keep track of which parts of your memory are initialized and which are not, and possibly use the wrong type of algorithm.
  • There are a few places where you seem to intend to use iterator categories your code doesn’t actually support (for example, making multiple passes through what are supposed to be input iterators).
  • There are a few functions that don’t offer the same guarantees as the std::vector versions, like where std::vector promises they will work even with non-default constructible types, but your versions do default constructions.

Other than that, the only issues worth mentioning are:

  • some efficiency gains that could be achieved, for example, by taking advantage cases where you can reuse existing capacity; and
  • some correctness issues regarding the use of allocators (mostly revolving around using uninitialized memory algorithms that don’t use the allocator’s construct() or destroy() functions.

And for style issues:

  • lack of comments; and
  • unnecessary use of const& for simple types.

Almost all of the issues are really complex, low-level-detail stuff. Overall, if I were grading this, I’d give it an “A”.

Extended answer

constexpr iterator T_fill_insert(difference_type offset, size_type n, const T &x) {
    const auto old_size = size_;
    /* check if reallocation is needed */
    T_grow(size_ + n);
    size_ += n;
    /* get the iterator at offset */
    iterator pos = begin() + offset;
    /* we can move already initialized parts of memory
     * that we can move */
    std::move(pos,begin()+old_size-n,pos+n);
    std::uninitialized_move(pos+old_size-n, end(), end()-n);
    std::uninitialized_fill(pos, pos + n, x);
    return pos;
}

Alright, let’s logic through this together to see if it works. (I honestly don’t know if it does yet! I’m working through it as I write.)

Let’s skip over the reallocation part, on the assumption that it works fine, and start our reasoning on the line where pos is initialized. Let’s assume the size is 10, containing the digits ‘0’, ‘1’, ‘2’, …. The capacity is 16. We want to insert 3 ‘X’s starting at position 5.

So at the start, the vector’s contents are:

0  1  2  3  4  5  6  7  8  9  _  _  _  _  _  _
               ^
               | insert position

Where the underscores represent uninitialized memory.

So offset is 5, and pos points to the position shown.

This is the before and after states we want:

start:
0  1  2  3  4  5  6  7  8  9  _  _  _  _  _  _

final:
0  1  2  3  4  X  X  X  5  6  7  8  9  _  _  _
                        ~  ~  +  +  +

Note that two of the elements (5 and 6) are moved onto already initialized memory, while three (7, 8, and 9) are moved onto uninitialized memory. In this case, all three new elements are copied over already initialized elements (but that won’t always be true!).

The first operation moves everything from pos to the end over to pos+n:

start:
0  1  2  3  4  5  6  7  8  9  _  _  _  _  _  _

std::move(pos,begin()+old_size-n,pos+n):
0  1  2  3  4  ?  ?  7  5  6  _  _  _  _  _  _

final:
0  1  2  3  4  X  X  X  5  6  7  8  9  _  _  _

(The question mark means a valid but moved-from value.)

Already you can see a problem. You’ve completely lost 8 and 9. Your steps are out of order. You should have done the following uninitialized move first.

Let’s try that—let’s swap those two lines (and fix the last argument to std::uninitialized_move(), because it’s exactly the same as the first one, meaning the function ultimately does nothing—it moves from pos+size-n to pos+size-n) and keep going:

start:
0  1  2  3  4  5  6  7  8  9  _  _  _  _  _  _

std::uninitialized_move(pos+old_size-n, end(), end()):
0  1  2  3  4  5  6  ?  ?  ?  7  8  9  _  _  _

std::move(pos,begin()+old_size-n,pos+n):
0  1  2  3  4  ?  ?  ?  5  6  7  8  9  _  _  _

final:
0  1  2  3  4  X  X  X  5  6  7  8  9  _  _  _

So far, so good. Ah, but the next step should be a fill… not an uninitialized fill.

Okay, let’s try replacing it with a normal fill:

start:
0  1  2  3  4  5  6  7  8  9  _  _  _  _  _  _

std::uninitialized_move(pos+old_size-n, end(), end()):
0  1  2  3  4  5  6  ?  ?  ?  7  8  9  _  _  _

std::move(pos,begin()+old_size-n,pos+n):
0  1  2  3  4  ?  ?  ?  5  6  7  8  9  _  _  _

std::fill(pos, pos + n, x):
0  1  2  3  4  X  X  X  5  6  7  8  9  _  _  _

final:
0  1  2  3  4  X  X  X  5  6  7  8  9  _  _  _

Perfect.

But… does it always work? Let’s try adding 6 elements instead of 3:

start:
0  1  2  3  4  5  6  7  8  9  _  _  _  _  _  _

std::uninitialized_move(pos+old_size-n, end(), end()):
0  1  2  3  ?  ?  ?  ?  ?  ?  4  5  6  7  8  9

// nope (note the 4 was moved) ...

final:
0  1  2  3  4  X  X  X  X  X  X  5  6  7  8  9

Looks like it’s back to the drawing board. Like I said, this is really a lot more complicated than it looks at first.

I always tell people I teach programming to that 95% of programming is done before you hit the first keystroke. You can always tell a good programmer from a bad programmer by, ironically, noting who doesn’t start programming right away. It’s all about understanding the problem, the algorithm, and the tools you’re using to implement it. If you start coding before you’ve completely worked through those things, then your code is already broken. If it even works at all, that’s just a fluke.

My advice is to sit down and work through pictorial representations like the ones above, and try to suss out all the possible cases—What if n is greater than size, for example? Then what would pos+old_size-n do? Crash!

Then try to determine a set of general rules that work for all cases. That might not even be possible! You might need to use if branches to handle different cases. I honestly don’t know what the solution is; I’d have to do exactly what I’m recommending to you, and sit down and work it through.

Or, alternately, rather than that method, you may prefer to try to think conceptually about the required steps first, and then try the pictorial representations to test your ideas. Either way is fine; it just boils down to your style.

But the bottom line is that you shouldn’t even try writing a single line of code until you understand the problem, and the solution, however you choose to do that. Seat-of-your-pants coding can be fun sometimes, but it’s not a serious way to write real code.

And write tests! I even recommend writing the tests before you write the code! You could make a simple test type that can detect when it hasn’t been initialized (for example, in the constructor, record its address in a static list, and if you’re trying to move-assign over an object whose address isn’t in the list, you’ve detected a bug), and use that in your vector. You could test inserts at the beginning, middle, and end of a 10 element vector, with insert sizes from 1 to 12. Test! Test! Test! Code without tests is just garbage—just throwaway crap you might have fun playing with for a while, but can’t use in serious projects. Pick a test library—I like Boost.Test, but something simpler like Catch2 is also great; you can even use Google Test if you’re masochistic, I suppose. (Actually, Catch2’s tutorial even shows some basic testing of std::vector.) I’d even argue that being able to write good tests is a more important skill than being able to just code from the hip.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback, but I have a question how much better would this be than the current T_fill_insert function pastebin.com/Bj6jptDv. \$\endgroup\$ – user222866 Jul 3 at 19:39
  • \$\begingroup\$ I'll have to extend the answer a bit for that, because it's a bit too much work out in a comment, so check above. \$\endgroup\$ – indi Jul 7 at 12:01
  • \$\begingroup\$ I read only half of this answer and I'm already scared >_> \$\endgroup\$ – Noone AtAll Aug 7 at 11:18

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.