Implementing a templated Array class

Question

I have implemented an Array class using templates. I have used a std::allocator object for memory allocation. Will it be better to use operator new along with placement new for memory allocation?

array.h

#ifndef ARRAY_H
#define ARRAY_H

#include <memory>
#include <cstddef>

template <typename T> class Array;

template<typename T> void swap(Array<T> &first, Array<T> &second);

template <typename T> class Array {
    friend void swap <> (Array<T> &first, Array<T> &second);
public:
    typedef T *iterator;
    typedef const T *const_iterator;
    typedef std::size_t size_type;
    typedef T value_type;

    explicit Array(size_type size, const T& value = T());
    Array(const_iterator range_begin, const_iterator range_end);
    Array(const Array&);

    Array& operator=(const Array);

    size_type size() const;

    T& operator[](size_type i);
    const T& operator[](size_type i) const;

    iterator begin();
    const_iterator begin() const;

    iterator end();
    const_iterator end() const;

    ~Array();
private:
    iterator data; // points to the first element of the array
    iterator limit; // points to one past the last element
    iterator avail; // points to one past the allocated memory

    std::allocator<T> alloc; // for memory allocation
};

// implementation
#include <algorithm>

template<typename T> void swap(Array<T> &first, Array<T> &second)
{
    using std::swap;

    swap(first.data, second.data);
    swap(first.limit, second.limit);
    swap(first.avail, second.avail);
}

template<typename T> Array<T>::Array(size_type size, const T& value):
    data(alloc.allocate(size)), limit(data), avail(data + size)
{
    while (limit < data + size)
        alloc.construct(limit++, value);
}

template<typename T> Array<T>::Array(const_iterator range_begin,
        const_iterator range_end):
    data(alloc.allocate(range_end - range_begin)), limit(data),
    avail(data + range_end - range_begin)
{
    const_iterator it = range_begin;
    while (limit < data + range_end - range_begin) {
        alloc.construct(limit++, *it);
        ++it;
    }
}

template<typename T> Array<T>::Array(const Array &original):
    data(alloc.construct(original.size())), limit(data),
    avail(data + original.size)
{
    iterator it = original.begin();
    while (it != original.limit()) {
        alloc.construct(limit++, *it);
        ++it;
    }
}

template<typename T> Array<T>& Array<T>::operator=(const Array rhs)
{
    swap(*this, rhs);

    return *this;
}

template<typename T> typename Array<T>::size_type Array<T>::size() const
{
    return limit - data;
}

template<typename T> T& Array<T>::operator[](size_type i)
{
    return data[i];
}

template<typename T> const T& Array<T>::operator[](size_type i) const
{
    return data[i];
}

template<typename T> typename Array<T>::iterator Array<T>::begin()
{
    return data;
}

template<typename T> typename Array<T>::const_iterator Array<T>::begin() const
{
    return data;
}

template<typename T> typename Array<T>::iterator Array<T>::end()
{
    return limit;
}

template<typename T> typename Array<T>::const_iterator Array<T>::end() const
{
    return limit;
}

template<typename T> Array<T>::~Array()
{
    while (limit != data)
        alloc.destroy(--limit);

    alloc.deallocate(data, avail - data);
}
#endif

Answer 1

When trying to use this, I found some things just failed to compile, as if the class had not been fully tested. First example:

template<typename T> Array<T>::Array(const_iterator range_begin,
        const_iterator range_end):
    data(alloc.allocate(range_end - range_begin)), limit(data),
    avail(data + range_end - range_begin)

It doesn't make sense to add two iterators in the computation of avail. I guess that was meant to be data + (range_end - range_begin)?

In the copy constructor we call alloc.construct(original.size()) - I think that should be alloc.allocate(original.size()). And data + original.size makes no sense - data + original.size() is probably intended.

iterator it = original.begin() needs to be const_iterator given that original is const. And it != original.limit() shouldn't be attempting to call limit as a function.

In assignment, we attempt to swap(*this, rhs) when rhs is a constant. We should be accepting a mutable copy if we intend to use the copy-and-swap idiom.

---

When we declare that swap() is a friend, we can simply write Array instead of Array<T>:

    friend void swap<>(Array& first, Array& second);

---

The limit member is unnecessary. It's only used in constructor and destructor, and at all other times it's equal to avail.

---

The constructors are not exception-safe. If any construct() fails, we need to destruct everything constructed so far and deallocate data. Remember that the destructor is not called when a constructor throws.

---

We really ought to provide move-constructor and move-assignment operator, as these can be implemented much more efficiently by swapping with no need to copy elements.

---

We should be able to construct from any range, not just the Array's own iterator type.

And it would be nice to be able to construct from an initializer list.

---

The copy constructor can simply delegate to the iterator constructor, rather than repeating the whole logic.

---

Most C++ developers prefer using to typedef. For the same functionality, using is usually easier to read, as it has similar layout to variable declaration, with the name being defined in the position left of the =.

---

Modified code

I changed from storing an end pointer to storing the size - I think this makes the arithmetic slightly simpler, but it's a close call.

I've also replaced the use of removed functions std::allocator::construct() and std::allocator::destroy() with their modern equivalents.

#include <cstddef>
#include <memory>
#include <utility>

template<typename T, typename Allocator = std::allocator<T>>
class Array
{
    std::size_t length;
    T *data;
    Allocator alloc = {};

    // private helper to teardown elements
    void destroy(T *p)
    {
        while (p != data) {
            std::destroy_at(--p);
        }
        if (data) {
            alloc.deallocate(data, length);
        }
    }

public:
    using iterator = T*;
    using const_iterator = T const*;
    using size_type = std::size_t;
    using value_type = T;

    explicit Array(size_type size, T const& value = T())
        : length{size},
          data{alloc.allocate(size)}
    {
        auto p = data;
        try {
            while (p != data + length) {
                std::construct_at(p, value);
                ++p;
            }
        } catch (...) {
            destroy(++p);
            throw;
        }
    }

    template<typename Iter>
    Array(Iter range_begin, Iter range_end)
        : length{static_cast<size_type>(range_end - range_begin)},
          data{alloc.allocate(length)}
    {
        const_iterator it = range_begin;
        auto p = data;
        try {
            while (p < data + length) {
                std::construct_at(p++, *it++);
                ++p;
            }
        } catch (...) {
            destroy(++p);
            throw;
        }
    }

    Array(std::initializer_list<T> list)
        : Array(list.begin(), list.end())
    {}

    Array(Array const& other)
        : Array(other.begin(), other.end())
    {}

    Array(Array&& other)
        : length{std::exchange(other.length, 0)},
          data{std::exchange(other.data, nullptr)}
    {}

    ~Array()
    {
        destroy(data + length);
    }

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

    friend void swap(Array& first, Array& second)
    {
        using std::swap;
        swap(first.length, second.length);
        swap(first.data, second.data);
    }

    size_type size() const { return length; }

    T& operator[](size_type i) { return data[i]; }
    const T& operator[](size_type i) const { return data[i]; }

    iterator begin() { return data; }
    const_iterator begin() const { return data; }
    const_iterator cbegin() const { return data; }

    iterator end() { return data + length; }
    const_iterator end() const { return data + length; }
    const_iterator cend() const { return data + length; }
};