10
\$\begingroup\$

I have created a heap allocated equivalent of std::array simply because I needed a lightweight fixed-size container that isn't known at compile time. Neither std::array or std::vector offered that, so I made my own. My goal is to make it fully STL compliant.

#pragma once

#include <cstddef>
#include <iterator>
#include <algorithm>
#include <initializer_list>

template<typename T>
class dynamic_array {
public:
    // types:
    using value_type             = T;
    using size_type              = size_t;
    using difference_type        = ptrdiff_t;
    using reference              = T&;
    using const_reference        = const T&;
    using pointer                = T*;
    using const_pointer          = const T*;
    using iterator               = T*;
    using const_iterator         = const T*;
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    // construct/copy/move/destroy:
    explicit dynamic_array(size_type count) noexcept :
            count(count),
            buffer(new T[size()]) { }

    dynamic_array(const std::initializer_list<T>& list) noexcept :
            count(list.size()),
            buffer(new T[size()]) {
        std::copy(list.begin(), list.end(), begin());
    }

    dynamic_array(const dynamic_array<T>& other) noexcept :
            count(other.size()),
            buffer(new T[size()]) {
        std::copy(other.begin(), other.end(), begin());
    }

    dynamic_array(dynamic_array<T>&& other) noexcept :
            count(other.size()),
            buffer(other.data()) {
        other.buffer = nullptr;
        other.count = 0;
    }

    ~dynamic_array() noexcept {
        delete[] buffer;
    }

    dynamic_array& operator=(const dynamic_array<T>& rhs) noexcept {
        resize(rhs.size());
        std::copy(rhs.begin(), rhs.end(), begin());
        return *this;
    }

    dynamic_array& operator=(const std::initializer_list<T>& list) noexcept {
        resize(list.size());
        std::copy(list.begin(), list.end(), begin());
        return *this;
    }

    dynamic_array& operator=(dynamic_array<T>&& rhs) noexcept {
        delete[] buffer;
        buffer = rhs.data();
        count = rhs.size();
        rhs.buffer = nullptr;
        rhs.count = 0;
        return *this;
    }

    // iterators:
    iterator begin() noexcept {
        return buffer;
    }

    const_iterator begin() const noexcept {
        return buffer;
    }

    iterator end() noexcept {
        return begin() + size();
    }

    const_iterator end() const noexcept {
        return begin() + size();
    }

    reverse_iterator rbegin() noexcept {
        return reverse_iterator(end());
    }

    const_reverse_iterator rbegin() const noexcept {
        return const_reverse_iterator(end());
    }

    reverse_iterator rend() noexcept {
        return reverse_iterator(begin());
    }

    const_reverse_iterator rend() const noexcept {
        return const_reverse_iterator(begin());
    }

    const_iterator cbegin() const noexcept {
        return begin();
    }

    const_iterator cend() const noexcept {
        return end();
    }

    const_reverse_iterator crbegin() const noexcept {
        return rbegin();
    }

    const_reverse_iterator crend() const noexcept {
        return rend();
    }

    // capacity:
    size_type size() const noexcept {
        return count;
    }

    size_type max_size() const noexcept {
        return count;
    }

    bool empty() const noexcept {
        return size() == 0;
    }

    // element access:
    reference operator[](size_type n) {
        return buffer[n];
    }

    const_reference operator[](size_type n) const {
        return buffer[n];
    }

    reference at(size_type n) {
        if (n < size()) {
            return buffer[n];
        }

        throw std::out_of_range("The index " + std::to_string(n) + " is out of bounds.");
    }

    const_reference at(size_type n) const {
        return at(n);
    }

    reference front() {
        return *begin();
    }

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

    reference back() {
        return *(end() - 1);
    }

    const_reference back() const {
        return *(cend() - 1);
    }

    // data access:
    pointer data() noexcept {
        return buffer;
    }

    const_pointer data() const noexcept {
        return buffer;
    }

    // modifiers:
    void fill(const T& value) noexcept {
        std::fill(begin(), end(), value);
    }

    void swap(dynamic_array<T>& other) noexcept {
        auto temp_data = other.data();
        auto temp_size = other.size();
        other.buffer = data();
        other.count = size();
        buffer = temp_data;
        count = temp_size;
    }
private:
    size_type count;
    T* buffer;

    void resize(size_type new_count) noexcept {
        if (size() != new_count) {
            delete[] buffer;
            buffer = new T[new_count];
            count = new_count;
        }
    }
};

template<typename T>
inline bool operator==(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs) {
    return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template<typename T>
inline bool operator!=(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs) {
    return !(lhs == rhs);
}

template<typename T>
inline bool operator<(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs) {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template<typename T>
inline bool operator>(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs) {
    return rhs < lhs;
}

template<typename T>
inline bool operator>=(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs) {
    return !(lhs < rhs);
}

template<typename T>
inline bool operator<=(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs) {
    return !(rhs < lhs);
}

Should I allow operations between arrays of different sizes, like swap and assignment? And if not, should I throw an exception or simply leave it as undefined behavior?

Edit: I have implemented most changes that were suggested, here is the updated version. I will leave the original code to not invalidate any answers.

\$\endgroup\$
  • 1
    \$\begingroup\$ What's wrong with vector here? You can resize it, ok. That's what you don't like, but why don't you simply create a wrapper type, expose everything you need, and hide the stuff you don't need. \$\endgroup\$ – DNKpp Dec 31 '17 at 23:36
  • \$\begingroup\$ @DNK That is true, but I also enjoyed writing my own STL container as a learning experience, and I would like to see if there were any improvements to be made. \$\endgroup\$ – Michael Smith Jan 1 '18 at 0:28
  • \$\begingroup\$ At least your const_reference at(size_type n) const has an infinit recursion. It doesn't do what you expect. That's the wrong way round, try to implement the logic in the const overload and simply do a static_cast on this in the non-const overload. That's the usual approach for this kind (sure, you have to const_cast the result back to non-const, but that is fine). \$\endgroup\$ – DNKpp Jan 1 '18 at 2:14
  • \$\begingroup\$ Please just wrap std vector with the fixed size constructor. It saves you a lot of code and bugs. Reinventing the wheel is fun and all but please don't do it in production code. \$\endgroup\$ – Emily L. Jan 1 '18 at 16:18
  • \$\begingroup\$ #pragma once is not standard or universally recognized. Prefer classic header guards. \$\endgroup\$ – Cris Luengo Jan 1 '18 at 19:31
12
\$\begingroup\$

You have invented a std::vector that can't be resized!

The first major problem I see with your implementation is noexceppt correctness.

explicit dynamic_array(size_type count) noexcept :
        count(count),
        buffer(new T[size()]) { }

What if operator new throws? What if T::T() throws? Do you want these exceptions to always terminate your program? Is this something you want to force on all of your users? The point is that this constructor shouldn't be noexcept.

dynamic_array& operator=(dynamic_array<T>&& rhs) noexcept {
    delete[] buffer;
    buffer = rhs.data();
    count = rhs.size();
    rhs.buffer = nullptr;
    rhs.count = 0;
    return *this;
}

What if I write dynamic_array<int> x{1, 2, 3}; x = std::move(x);? This is nonsensical code that should have no effect, but it will crash the program! Always always check if &rhs != this.

Also, I usually find it easier to implement assignment in terms of move-construct and swap:

dynamic_array(std::move(rhs)).swap(*this);

Why aren't operator[] noexcept? Same for front() and back().

const_reference at(size_type n) const {
    return at(n);
}

This is infinite recursion. Either const_cast<dynamic_array*>(this)->at(n) or move the logic to the const at, then const-cast away the const in the non-const at.

void fill(const T& value) noexcept {
    std::fill(begin(), end(), value);
}

See my earlier comment about noexcept correctness. The right thing to do here is make this noexcept only if the call to std::fill is noexcept. Here's how:

void fill(const T& value) noexcept(noexcept(std::fill(begin(), end(), value))) {
    std::fill(begin(), end(), value);
}

And this only works if begin() and end() are noexcept (as they should be).

void swap(dynamic_array<T>& other) noexcept {
    auto temp_data = other.data();
    auto temp_size = other.size();
    other.buffer = data();
    other.count = size();
    buffer = temp_data;
    count = temp_size;
}

Did you know that you can access the private members of another instance of the same class? Also, for primitive things like integers and pointers, std::swap is about as good as you can get? I'd recommend

std::swap(buffer, other.buffer);
std::swap(count, other.count);

If you want to be really fancy, try

std::swap(std::tie(buffer, count), std::tie(other.buffer, other.count));

If you made it this far through my answer, good job. Your question is a good one. It demonstrates some errors that I sometimes see (and make), and I think it is beneficial to point them out.

If you feel like incorporating my suggestions, please post an updated version of this question and I, or others, will share an opinion on your various constructors.

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't actually need to use conditional noexcept for a call to std::fill, because fill is never noexcept. \$\endgroup\$ – Rakete1111 Jan 1 '18 at 22:25
  • \$\begingroup\$ @Rakete1111 Cheers to that, updated my code. \$\endgroup\$ – Michael Smith Jan 2 '18 at 5:06
3
\$\begingroup\$

Constructor not noexcept

    explicit dynamic_array(size_type count) noexcept :
            count(count),
            buffer(new T[size()]) { }

This is so dangerous that it has to be wrong. If a small sub-routine fails to create your array you are terminating the app. No thanks. If a small sub routine fails then I expect an exception that I catch and take appropriate action. This is so absolutely WRONG.

Also this does not initialize the buffer. Yes you allocate space for the buffer. And if this is a class its constructor will run. But if T is not a class then the members of the buffer are not initialized. Thus reading them before initializing is undefined behavior.

What you want is to force zero initialization of POD data

            buffer(new T[size()]())
                          //    ^^  <- Notice these two.

see: Proper way to initialize C++ structs and Is uninitialized data behavior well specified?

Construction and initialiation

Here you are being very inefficient in your initialization.

    dynamic_array(const std::initializer_list<T>& list) noexcept :
            count(list.size()),
            buffer(new T[size()]) {
        std::copy(list.begin(), list.end(), begin());
    }

You allocate the buffer and force every member to default initialized. Then you turn around and immediately copy over those default initialized values. What you should be doing is constructing and using the members of the list to construct in place once.

Same problem here.

    dynamic_array(const dynamic_array<T>& other) noexcept :
            count(other.size()),
            buffer(new T[size()]) {
        std::copy(other.begin(), other.end(), begin());
    }

Double initialization of your array. First time with constructor. Second time with assignment operator. Its fine for POD classes but anything that manages its own memory this is excessively expensive.

This looks like it will fail.

    const_reference at(size_type n) const {
        return at(n);
    }

Have you tested this? I bet this goes into an infinite loop. I think you mean.

        // you need to remove the const from this so that you can
        // call the non cost version of `at()`
        return const_cast<dynamic_array&>(*this).at(n);

Swap

Why not use std::swap to swap the members?

    void swap(dynamic_array<T>& other) noexcept {
        auto temp_data = other.data();
        auto temp_size = other.size();
        other.buffer = data();
        other.count = size();
        buffer = temp_data;
        count = temp_size;
    }

Breaks the Strong Exception gurantee

As a side note: I would like to note that it does not reduce the size of the array. Which is definitely not what I expect.

This is OK for your code because everything is noexcept. But as I pointed out earlier this is wrong. Most constructors should not be noexcept as a result this function also needs to work without the noexcept.

The problem is that you are calling delete before you know that new T has succeeded. This means that if the reallocation fails your object is in an inconsistent state.

    void resize(size_type new_count) noexcept {
        if (size() != new_count) {
            delete[] buffer;
            buffer = new T[new_count];
            count = new_count;
        }
    }

Allocate first. If it works swap with the current content. Then delete the old content.

I wrote some articles on vector. These will help you do it better:

  1. Vector - Resource Management Allocation
  2. Vector - Resource Management Copy Swap
  3. Vector - Resize
  4. Vector - Simple Optimizations
  5. Vector - the Other Stuff
\$\endgroup\$
  • \$\begingroup\$ "What you should be doing is constructing and using the members of the list to construct in place once." How can this be done? I do not know how to allocate a buffer with the initializer list elements directly. \$\endgroup\$ – Michael Smith Jan 2 '18 at 17:45
  • \$\begingroup\$ @MichaelSmith: Its called placement new. I go into detail in my articles. \$\endgroup\$ – Martin York Jan 2 '18 at 17:46
  • \$\begingroup\$ As for the "force zero initialization", I have since updated my code to use unique_ptr<T[]>. Will it be zero initialized this way, or should I return to raw pointers? \$\endgroup\$ – Michael Smith Jan 2 '18 at 17:52
  • \$\begingroup\$ @MichaelSmith. Zero initialization is part of how you create the object not what it is stored in. If you use make_unique() you are probably OK. But I would check, \$\endgroup\$ – Martin York Jan 2 '18 at 17:59

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.