3
\$\begingroup\$

I've wrote a FixedArray to fit seamlessly (function-wise) with the default C++ containers, including working with algorithms/etc. It is a dynamically allocated, but fixed size array.

Code


#pragma once

#include <cstddef>
#include <initializer_list>
#include <algorithm>
#include <limits>
#include <concepts>
#include <iterator>
#include <stdexcept>

namespace Util {
    
    template<typename C, typename T=typename C::value_type>
    concept Container = std::input_iterator<typename C::iterator> && std::is_same_v<typename C::value_type,T> && requires(C c,const C cc,size_t i) {
        { c.begin() } -> std::same_as<typename C::iterator>;
        { c.end() } -> std::same_as<typename C::iterator>;
        { cc.begin() } -> std::same_as<typename C::const_iterator>;
        { cc.end() } -> std::same_as<typename C::const_iterator>;
        { c.size() } -> std::same_as<typename C::size_type>;
    };
    
    template<typename T, bool _reassignable=false, typename Alloc=std::allocator<T>>
    class FixedArray {
    public:
        
        using value_type=T;
        using allocator_type=Alloc;
        using size_type=size_t;
        using difference_type=std::ptrdiff_t;
        
        using reference=T&;
        using pointer=T*;
        using iterator=T*;
        using reverse_iterator=std::reverse_iterator<T*>;
        
        using const_reference=const T&;
        using const_pointer=const T*;
        using const_iterator=const T*;
        using const_reverse_iterator=std::reverse_iterator<const T*>;
        
    private:
        
        value_type * _data;
        size_type _size;
        
        [[no_unique_address]] Alloc allocator;
        
        void _cleanup() { // destroy all objects, deallocate all memory, leaves container in a valid empty state
            if(_data) {
                for(size_t i=0;i<_size;i++) {
                    _data[i].~value_type();
                }
                allocator.deallocate(_data,_size);
                _data=nullptr;
            }
            _size=0;
        }
        
        template<typename C>
        void _container_assign(const C &container) { // allocate memory and copy contents from generic container of type C
            if(container.size()==0) {
                _size=0;
                _data=nullptr;
            } else {
                _size=container.size();
                _data=allocator.allocate(_size);
                typename C::const_iterator it=container.begin();
                for(size_t i=0;i<_size;i++,it++){
                    new(_data+i) value_type(*it);
                }
            }
        }
        
    public:
        
        FixedArray() : _data(nullptr), _size(0) {
            
        }
        
        FixedArray(std::nullptr_t) : _data(nullptr), _size(0) {
            
        }
        
        FixedArray(std::initializer_list<T> data) requires std::is_copy_constructible_v<value_type> {
            _container_assign(data);
        }
        
        template<typename U>
        FixedArray(std::initializer_list<U> data) requires (!std::is_same_v<T,U>) && requires (U x){ T(x); }
        {
            _container_assign(data);
        }
        
        FixedArray(const FixedArray & other) requires std::is_copy_constructible_v<value_type> {
            _container_assign(other);
        }
        
        FixedArray(FixedArray && other) : _data(other._data), _size(other._size) {
            other._data=nullptr;
            other._size=0;
        }
        
        template<typename C>
        FixedArray(const C& container) requires Container<C,value_type> && std::is_copy_constructible_v<value_type> {
            _container_assign(container);
        }
        
        template<typename C>
        FixedArray(const C& container) requires Container<C> && (!std::is_same_v<T,typename C::value_type>) && requires (typename C::value_type v) { T(v); }
        {
            _container_assign(container);
        }
        
        FixedArray(size_t n) requires std::is_default_constructible_v<value_type> : _data(nullptr), _size(n) {
            if(_size>0){
                _data=allocator.allocate(_size);
                for(size_t i=0;i<_size;i++){
                    new(_data+i) value_type();
                }
            }
        }
        
        ~FixedArray() {
            _cleanup();
        }
        
        // --- optional reassignment methods ---
        
        void operator=(std::nullptr_t) requires _reassignable {
            _cleanup();
        }
        
        void clear() requires _reassignable {
            _cleanup();
        }
        
        FixedArray & operator=(std::initializer_list<T> data) requires _reassignable {
            _cleanup();
            _container_assign(data);
            return *this;
        }
        
        template<typename U>
        FixedArray & operator=(std::initializer_list<U> data) requires _reassignable &&  requires (U x){ T(x); }
        {
            _cleanup();
            _container_assign(data);
            return *this;
        }
        
        FixedArray & operator=(const FixedArray & other) requires _reassignable {
            _cleanup();
            _container_assign(other);
            return *this;
        }
        
        FixedArray & operator=(FixedArray && other) requires _reassignable {
            _cleanup();
            _data=other._data;
            _size=other._size;
            other._data=nullptr;
            other._size=0;
            return *this;
        }
        
        template<typename C>
        FixedArray & operator=(const C& container) requires _reassignable && Container<C,value_type> {
            _cleanup();
            _container_assign(container);
            return *this;
        }
        
        template<typename C>
        FixedArray & operator=(const C& container) requires _reassignable && Container<C> && (!std::is_same_v<T,typename C::value_type>) && requires (typename C::value_type v) { T(v); }
        {
            _cleanup();
            _container_assign(container);
            return *this;
        }
        
        void swap(FixedArray & other) requires _reassignable {
            value_type * temp_data=_data;
            size_t temp_size=_size;
            _data=other._data;
            _size=other._size;
            other._data=temp_data;
            other._size=temp_size;
        }
        
        static void swap(FixedArray & lhs,FixedArray & rhs) requires _reassignable {
            lhs.swap(rhs);
        }
        
        // --- container boilerplate after this ---
        
        template<typename C>
        bool operator==(const C& container) const {
            return _size==container.size()&&std::equal(container.begin(),container.end(),begin(),end());
        }
        
        template<typename C>
        bool operator!=(const C& container) const {
            return _size!=container.size()||!std::equal(container.begin(),container.end(),begin(),end());
        }
        
        size_type size() const noexcept {
            return _size;
        }
        
        static size_type max_size() noexcept {
            return (std::numeric_limits<size_type>::max()/sizeof(value_type))-1;
        }
        
        size_type empty() const noexcept {
            return _size==0;
        }
        
        iterator begin() noexcept {
            return _data;
        }
        
        iterator end() noexcept {
            return _data+_size;
        }
        
        const_iterator begin() const noexcept {
            return _data;
        }
        
        const_iterator end() const noexcept {
            return _data+_size;
        }
        
        const_iterator cbegin() const noexcept {
            return _data;
        }
        
        const_iterator cend() const noexcept {
            return _data+_size;
        }
        
        reverse_iterator rbegin() noexcept {
            return std::make_reverse_iterator(end());
        }
        
        reverse_iterator rend() noexcept {
            return std::make_reverse_iterator(begin());
        }
        
        const_reverse_iterator rbegin() const noexcept {
            return std::make_reverse_iterator(end());
        }
        
        const_reverse_iterator rend() const noexcept {
            return std::make_reverse_iterator(begin());
        }
        
        const_reverse_iterator crbegin() const noexcept {
            return std::make_reverse_iterator(end());
        }
        
        const_reverse_iterator crend() const noexcept {
            return std::make_reverse_iterator(begin());
        }
        
        pointer data() noexcept {
            return _data;
        }
        
        const_pointer data() const noexcept {
            return _data;
        }
        
        reference front() noexcept {
            return _data[0];
        }
        
        const_reference front() const noexcept {
            return _data[0];
        }
        
        reference back() noexcept {
            return _data[_size-1];
        }
        
        const_reference back() const noexcept {
            return _data[_size-1];
        }
        
        reference operator[](size_t i) noexcept {
            return _data[i];
        }
        
        const_reference operator[](size_t i) const noexcept {
            return _data[i];
        }
        
        reference at(size_t i) {
            if(i>=_size) throw std::out_of_range("Index "+std::to_string(i)+" is out of range for FixedArray of size "+std::to_string(_size));
            return _data[i];
        }
        
        const_reference at(size_t i) const {
            if(i>=_size) throw std::out_of_range("Index "+std::to_string(i)+" is out of range for FixedArray of size "+std::to_string(_size));
            return _data[i];
        }
        
    };
}

After testing it, it seems to work without any problems, but a second pair of eyes could help find anything i might have overlooked.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Can you outline any important differences between this and std::Array? \$\endgroup\$ – Edward Dec 27 '20 at 21:23
  • 1
    \$\begingroup\$ It looks like a lot of work for what is basically a std::vector that you just never resize. Why would someone want to use this class over std::vector? The latter also allows construction from any other container-like object, given two iterators. \$\endgroup\$ – G. Sliepen Dec 27 '20 at 21:35
  • 1
    \$\begingroup\$ @TomGebel I'm asking this because it is important to understand what the code is intended for. Is it for the OP to excercise building a C++ container? Or is it meant for actual production code? \$\endgroup\$ – G. Sliepen Dec 27 '20 at 21:59
  • 1
    \$\begingroup\$ Nice: The one thing I would note is that arrays/std::vector/std::array etc destroy the objects in reverse order of creation. I would change your clean up to call destructors from (n --> 0] to mimik this behavior. \$\endgroup\$ – Martin York Dec 28 '20 at 1:23
  • 1
    \$\begingroup\$ Some more optimizations that I implemented for vector that may help here: lokiastari.com/blog/2016/03/19/vector-simple-optimizations/… \$\endgroup\$ – Martin York Dec 28 '20 at 1:24
4
\$\begingroup\$

Consider not using this class

Your class basically reimplements almost all of std::vector, except the functions that resized the container. The only feature I can see that it has over regular std::vector is that you can easily assign another container to it without using a pair of iterators. In this case, I would recommend considering not using this class, but just a regular std::vector, so that you don't have to maintain this code.

Alternatively, you could perhaps consider deriving your class from std::vector, but delete all the functions that resize. For example:

template<typename T, typename Alloc = std::allocator<T>>
class FixedArray: public std::vector<T, Alloc> {
public:
    // Delete functions you don't want:
    void resize(size_t) = delete;
    ...

    // Pull in the constructors of the parent class:
    using std::vector<T, Alloc>::vector;

    // Add more constructors/functions if needed:
    template<typename C>
    FixedArray(const C& container) : std::vector<T, Alloc>(std::begin(container), std::end(container)) {}
    ...
};

Inheriting from a container class this way has its own drawbacks, so I wouldn't recommend this either, but I do think this approach will require much less code to be written.

For the rest of the review I'm assuming you do want to use your own class as it is.

Make better use of existing concepts

Instead of defining your own concept Container, make use of the concepts from the Ranges library, like std::ranges::range, or even better the more specific ones like std::ranges::input_range.

Also, instead of writing requires (typename C::value_type v) { T(v); }, consider using requires std::is_constructible_v<T, C::value_type>.

Use concepts directly inside a template parameter list

A nice thing about concepts is that you can use them instead of typename in a template parameter list. This avoids some typing, and makes the code a little easier to read. For example, instead of:

template<typename C>
FixedArray(const C& container) requires Container<C> && (!std::is_same_v<T,typename C::value_type>) && requires (typename C::value_type v) { T(v); }
{
    _container_assign(container);
}

You can write:

template<std::ranges::input_range C>
FixedArray(const C& container) requires (!std::is_same_v<T,typename C::value_type> && std::is_constructible_v(T, C::value_type))
{
    _container_assign(container);
}

Use default member value initialization

You can avoid some typing by using member value initialization:

pointer _data{};
size_type _size{};

This avoids repeating the default initialization in several of the constructors. In fact, this way the default constructor can really be made default:

FixedArray() = default;

Avoid code duplication

There are several ways you can reduce the amount of code you have written:

Reuse your own functions

You can make use of your own member functions and iterators. For example, you can use range-for to loop over the elements of _data:

void _cleanup() { // destroy all objects, deallocate all memory, leaves container in a valid empty state
    if(_data) {
        for(auto &el: *this) {
            el.~value_type();
        }
        allocator.deallocate(_data, _size);
        _data = nullptr;
    }
    _size = 0;
}

Also, when moving data from another container, make use of your own swap() function. Combined with the default member initialization, this removes a lot of lines, for example the move constructor becomes:

FixedArray(FixedArray && other) {
    swap(other);
}

Merge (template) overloads where possible

There are several places where you have multiple overloads for dealing with other containers of the same value_type or of another, when they can be merged into one. For example, the constructors taking initializer lists can be merged into this single one:

template<typename U>
FixedArray(std::initializer_list<U> data) requires std::is_constructible_v<value_type, U>
{
    _container_assign(data);
}

Since this will also handle the case of a std::initializer_list<value_type> just fine. The same goes for the other cases where you used !std::is_same_v<>.

Define operator!= in terms of operator==

It's always best to define one of those operators in terms of the other, so you cannot have a small mistake give subtly different behaviour. So:

template<std::ranges::input_range C>
bool operator!=(const C& container) const {
    return !operator==(container);
}

Be consistent using std::size(), std::begin() and std::end()

To ensure your class works with all possible containers, don't use member functions .size(), .begin() and .end() directly, but use the free-standing std::size() and related functions. For example:

template<std::ranges::input_range C>
bool operator==(const C& container) const {
    return std::equal(std::begin(container), std::end(container), begin(), end());
}

Note that you also don't need to use std::size() in this example, std::equal() will already check whether the sizes match.

Use your own type aliases consistently

If you define an alias, you should use it yourself as well. This ensures that if you need to change a type, you only need to do it on one line. So replace size_t with size_type everywhere, use value_type instead of T in a few places, and so on.

Use consistent code formatting

Your code does not use consistent formatting, in some places there are spaces around operators, in other places there are none. I recommend using a code formatting tool to do this for you, for example Artistic Style or ClangFormat.

\$\endgroup\$
3
  • \$\begingroup\$ I'd argue that it's better to use a std::vector as a member, or to inherit from it privately, than to use public inheritance like that (where one could find it used as the base class, and therefore resized unexpectedly). \$\endgroup\$ – Toby Speight Dec 28 '20 at 15:06
  • \$\begingroup\$ @TobySpeight Indeed, that's one of the issues that inheritance has. But either private inheritance or making it a member value would mean writing a lot of wrapper functions. \$\endgroup\$ – G. Sliepen Dec 28 '20 at 15:41
  • \$\begingroup\$ I think private inheritance would just need lots of using base-class functions rather than wrappers. Still lots of them, of course (but only one for each identifier, not for each override). \$\endgroup\$ – Toby Speight Dec 28 '20 at 16:30

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.