5
\$\begingroup\$

So here is an implementation of a dynarray. Many people might not know about it, so here is a reference.

Note that I am not trying to write a 100% standard conforming implementation. Also, this is for a library, so resist the urge to scold me on using a leading underscore for two of my variables.

#include <cstddef>
#include <iterator>
#include <stdexcept>
#include <initializer_list>

template<typename T>
class dynarray
{
public: //TYPE ALIASES
    using value_type      = T;
    using size_type       = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference       = T&;
    using const_reference = const T&;
    using pointer         = T*;
    using const_pointer   = const T*;

private: //ITERATOR
    template<typename U>
    class dynarray_iter : public std::iterator<std::random_access_iterator_tag, U>
    {
    private:
        U* pos = nullptr;

    public:
        constexpr explicit dynarray_iter(U* position)
            : pos(position)
        {}

        constexpr dynarray_iter() = default;
        constexpr dynarray_iter(const dynarray_iter&) = default;
        dynarray_iter& operator=(const dynarray_iter&) = default;

        //INCREMENT/DECREMENT OPERATORS
        dynarray_iter& operator++() { ++pos; return *this; }
        dynarray_iter& operator--() { --pos; return *this; }
        dynarray_iter  operator++(int) { dynarray_iter temp(*this); operator++(); return temp; }
        dynarray_iter  operator--(int) { dynarray_iter temp(*this); operator--(); return temp; }

        //ARITHMETIC OPERATORS
        dynarray_iter operator+(difference_type off) const { return dynarray_iter(pos + off); }
        dynarray_iter operator-(difference_type off) const { return dynarray_iter(pos - off); }

        dynarray_iter& operator+=(difference_type off) { pos += off; return *this; }
        dynarray_iter& operator-=(difference_type off) { pos -= off; return *this; }

        difference_type operator-(const dynarray_iter& rhs) const { return pos - rhs.pos; }

        friend dynarray_iter operator+(difference_type off, const dynarray_iter& it) { return dynarray_iter(it + off); }

        U& operator*() { return *pos; }
        U* operator->() { return  pos; }

        U& operator[](difference_type n) const { return pos[n]; }

        operator dynarray_iter<const T>() { return dynarray_iter<const T>(pos); }

        //COMPARISON OPERATORS
        constexpr bool operator==(const dynarray_iter& rhs) const noexcept { return pos == rhs.pos; }
        constexpr bool operator!=(const dynarray_iter& rhs) const noexcept { return pos != rhs.pos; }
        constexpr bool operator>(const dynarray_iter& rhs)  const noexcept { return pos > rhs.pos; }
        constexpr bool operator<(const dynarray_iter& rhs)  const noexcept { return pos < rhs.pos; }
        constexpr bool operator>=(const dynarray_iter& rhs) const noexcept { return pos >= rhs.pos; }
        constexpr bool operator<=(const dynarray_iter& rhs) const noexcept { return pos <= rhs.pos; }
    };

public:
    using iterator       = dynarray_iter<T>;
    using const_iterator = dynarray_iter<const T>;

    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

private:
    T* _data = nullptr;

    std::size_t _size = 0;

public:
    //CONSTRUCTORS
    template<typename InputIt>
    dynarray(InputIt first, InputIt last)
    {
        _data = new T[std::distance(first, last)];

        std::size_t i = 0;
        for (; first != last; ++first, ++i) {
            _data[i] = *first;
        }
        _size = ++i;
    }

    dynarray(std::size_t count, const T& fill_val = 0)
    {
        _data = new T[count];

        for (std::size_t i = 0; i < count; ++i) {
            _data[i] = fill_val;
        }
        _size = count;
    }

    dynarray(std::initializer_list<T> ilist)
        : dynarray(ilist.begin(), ilist.end())
    {}

    //COPY/MOVE CONSTRUCTORS AND ASSIGNMENT
    dynarray(const dynarray& rhs)
    {
        _data = new T[rhs.size()];

        for (std::size_t i = 0; i < _size; ++i) {
            _data[i] = rhs._data[i];
        }
        _size = rhs.size();
    }

    dynarray(dynarray&& rhs) noexcept
    {
        swap(rhs);
    }

    dynarray& operator=(const dynarray& rhs)
    {
        dynarray temp(rhs.begin(), rhs.end());
        swap(temp);
        return *this;
    }

    dynarray& operator=(dynarray&& rhs) noexcept
    {
        //clear()
        swap(rhs);
        return *this;
    }

    ~dynarray()
    {
        delete[] _data;
    }

    //ACCESS FUNCTIONS
    T& front() { return _data[0]; }
    T& back()  { return _data[_size - 1]; }

    const T& front() const { return _data[0]; }
    const T& back()  const { return _data[_size - 1]; }

          T& operator[](std::size_t i)       noexcept { return _data[i]; }
    const T& operator[](std::size_t i) const noexcept { return _data[i]; }

    T& at(std::size_t i)
    {
        if (!(i < _size)) {
            throw std::out_of_range("Index out of bounds!");
        }
        return _data[i];
    }

    const T& at(std::size_t i) const
    {
        if (!(i < _size)) {
            throw std::out_of_range("Index out of bounds!");
        }
        return _data[i];
    }

          T* data()       noexcept { return _data; }
    const T* data() const noexcept { return _data; }

    //CAPACITY FUNCTIONS
    std::size_t size() const noexcept { return _size; }
    bool empty()       const noexcept { return _size; }

    //ITERATORS
    iterator begin() noexcept { return iterator(_data); }
    iterator end()   noexcept { return iterator(_data + _size); }

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

    const_iterator cbegin() const noexcept { return const_iterator(_data); }
    const_iterator cend()   const noexcept { return const_iterator(_data + _size); }

    //REVERSE ITERATORS
    reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
    reverse_iterator rend()   noexcept { return reverse_iterator(begin()); }

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

    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }
    const_reverse_iterator crend()   const noexcept { return const_reverse_iterator(cbegin()); }

    //OTHER FUNCTIONS AND ALGORITHMS
    void swap(dynarray& rhs) noexcept
    {
        using std::swap;
        swap(_data, rhs._data);
        swap(_size, rhs._size);
    }

    //FILL
    void fill(const T& val)
    {
        for (size_t i = 0; i < _size; ++i) {
            _data[i] = val;
        }
    }
};
\$\endgroup\$
5
\$\begingroup\$

Include the appropriate headers

You need to include <algorithm> if you're going to be using std::swap. Now that we have that header included, we can use it to reduce the size of some of the functions you've implemented.

Use the standard when you can

Many of your functions can be simplified now that we've included <algorithm>. For example, your fill function.

void fill(const T& val)
{
    std::fill(_data, _data + _size, val);
}

I would also remove that unnecessary //FILL comment you have as it is clear from the function name what you're doing.

Your "fill constructor" can also be simplified:

dynarray(std::size_t count, const T& fill_val)
{
    _data = new T[count];
    fill(fill_val);
    _size = count;
}

I also removed the default-value from the constructor as I think that if we're using a fill constructor, we should be providing it with a value to fill it with.

Your "iterator constructor" can be simplified to:

template<typename InputIt>
dynarray(InputIt first, InputIt last)
{
    _size = std::distance(first, last);
    _data = new T[_size];
    std::copy(first, last, _data_);
}

Copy constructor:

dynarray(const dynarray& rhs)
{
    _data = new T[rhs.size()];
    std::copy(rhs.begin(), rhs.end(), _data);
    _size = rhs.size();
}

Wrong interface

According to the link you provided, a dynarray is:

neither copy-, nor move-assignable

Therefore, you should be delete-ing your entire copy, move, and assignment operator functions. Technically, your implementation isn't correct but you've addressed that in your post.

Memory management As it stands, your class leaks memory each time it is copied. In your copy c-tor, you never delete the memory you're holding on to before allocating a new piece. I would look into using some smart pointers to avoid having to worry about this issue(std::unique_ptr). If you do switch to a smart pointer allocator, then you don't even need to provide a destructor as cleanup is done for you by the smart pointer. Example:

// assume _data is of type std::unique_ptr<T[]>
dynarray(std::size_t count, const T& fill_val)
{
    _data = std::make_unique<T[]>(count);
    fill(fill_val);
    _size = count;
}

Then in your copy c-tor, you can do this:

dynarray(const dynarray& rhs)
{
    _data = std::make_unique<T[]>(rhs.size()); // no leak
    std::copy(rhs.begin(), rhs.end(), _data.get());
    _size = rhs.size();
}

And your swap function can be:

void swap(dynarray& rhs) noexcept
{
    _data.swap(rhs._data);
    std::swap(_size, rhs._size);
}

You'll have to adjust the rest of your interface to take into account your new unique_ptr implementation but your implementation is now leak-free.

You can simply this logic:

T& at(std::size_t i)
{
    if (!(i < _size)) {
        throw std::out_of_range("Index out of bounds!");
    }
    return _data[i];
}

to:

T& at(std::size_t i)
{
    if (i >= _size) {
        throw std::out_of_range("Index out of bounds!");
    }
    return _data[i];
}

For this function signature:

std::size_t size() const noexcept { return _size; }

you have size_type defined as std::size_t. Use it.

size_type size() const noexcept { return _size; }
\$\endgroup\$
  • \$\begingroup\$ I don't understand how it leaks memory in the copy constructor. I allocate [size] memory and I assign the address of the first block to _data. Then _data is deleted[] in the destructor. The memory allocated for the dynarray from which I'm copying will be deallocated in the respective destructor. \$\endgroup\$ – DeiDei Jan 7 '16 at 18:23
  • \$\begingroup\$ If you enter the copy constructor holding on to memory on the current object (e.g. *this), you will leak the memory. All you're doing is simply reassigning that pointer to a new block of memory. This will cause you to leak the memory you were originally holding on to since the destructor will free the memory currently pointed at but not the memory you've left behind. \$\endgroup\$ – Bizkit Jan 7 '16 at 18:38
1
\$\begingroup\$

This exists in another header already, so you should probably put this into its own namespace instead of the global one, then you can include both of them with somewhat more safety.

I'm a big fan of private hpp files for the implementation of templated types, it makes the class much cleaner to me.

You could use some header guards, or #pragma once here too.

Most of your comments are pretty inane - we can read, and recognize a constructor when we see it.

I personally don't find it helpful or more readable when people do this

      T& operator[](std::size_t i)       noexcept { return _data[i]; }
const T& operator[](std::size_t i) const noexcept { return _data[i]; }

or this

using reverse_iterator       = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

adding extra whitespace like that generally isn't more readable imo, but I do know people who feel differently. If this is your own personal preference or is required by a style guide wherever you work/code, then don't mind this.

Anytime I see this, or something similar, I consider it a (small) code smell.

unsigned i = 0;
for (; i < something; ++i)

There are certainly reasons to do this, but I don't know that this one is. You've already calculated the distance, so just save that as a variable.

template<typename InputIt>
dynarray(InputIt first, InputIt last)
{
    _size = std::distance(first, last);
    _data = new T[_size];

    for (size_t i = 0; i < _size; ++first, ++i) {
        _data[i] = *first;
    }
}

I'd like a constructor that didn't fill things up for me

dynarray(std::size_t count)
{
    _data = new T[count];
    _size = count;
}

I'd also like a default constructor, or a deleted default constructor. In this case, a default constructor doesn't really make sense, so I'd argue for deleting it.

If you're going to copy a parameter in the body, just take it by value as a parameter and if you're lucky you'll get copy elision - at worst you'll get the same performance.

dynarray& operator=(dynarray rhs)
{
    swap(rhs);
    return *this;
}

I understand that the interface calls for the data member function, but quite honestly I don't see the point of it.

Your implementation of empty is questionable at best - if we're assuming that a dynarray is always full then its fine, but in general I'd argue for a distinction between size and capacity. This is an issue throughout the code.

If you define a fill function, use it in the constructor.

As a note, the container is intended to be neither copy nor move-assignable. I understand that you aren't conforming exactly to the specification, however I'd argue that when you diverge from it you should do so with a clear, documented purpose.

I'd like to see doxygen comments all over the place.

\$\endgroup\$

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.