4
\$\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\$
10
  • 1
    \$\begingroup\$ Can you outline any important differences between this and std::Array? \$\endgroup\$
    – Edward
    Commented Dec 27, 2020 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
    Commented Dec 27, 2020 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
    Commented Dec 27, 2020 at 21:59
  • 2
    \$\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\$ Commented Dec 28, 2020 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\$ Commented Dec 28, 2020 at 1:24

2 Answers 2

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\$ Commented Dec 28, 2020 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
    Commented Dec 28, 2020 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\$ Commented Dec 28, 2020 at 16:30
3
\$\begingroup\$

G. Sliepen's answer covers some good ideas already, but here are some additional points.

Memory leak: Exception safety

If a T has a constructor that throws, and a constructor does throw in the loop of _container_assign, you've got a leak. You'll have allocated memory already, and the pointer member might have been "constructed", but since it's a raw pointer, its "destructor" won't release the memory. Similarly, because your class's constructor hasn't finished, the object itself wasn't fully constructed, so its own destructor won't be called, meaning any T objects whose construction finished won't have their destructors called (and if they in turn also own resources, those will also leak).

You could change your requirements to require noexcept constructors, or you could include try/catch logic to handle cleanup before rethrowing.

There's a similar, but different, concern if an exception is thrown in the loop of _cleanup, but throwing an exception in a destructor is such a bad practice that you might just refuse to support it. You might consider a static_assert or requires clause that the destructor of T is noexcept to enforce that refusal at compile-time.

Concept: finish meeting Allocator_Aware by supporting stateful allocators

If the allocator is always default-constructed, there is no way to get state in there, which means stateful allocators cannot be used. Some kinds of custom allocators make more sense to implement with state, even if it is just a pointer to some other object.

This can be remedied by adding constructor overloads that accept an allocator as a parameter (see: allocator-aware containers on cppreference). Make use of std::allocator_traits to check if the allocator needs to be propagated on copies, swaps, moves.

You probably want to be using std::allocator_traits anyway so your size_type, pointer, and difference_type aliases to be consistent with your allocator.

Generality: Support types that are movable but not copyable

Your requires clauses in the constructor overloads and copy function are all about copy construction, which is fine if you don't want to modify the contents of a container, but if you add overloads for non-const references for objects that are move-constructible, you could have things like arrays of std::unique_ptr.

You might use something like std::move_iterator in the implementation of those overloads, so that your assignment implementation could be templated on iterator type, taking move_iterators from the non-const overloads and const_iterators from the const overloads.

Potential improvement: more noexcept

Move constructor in particular most likely can be noexcept, and this can improve performance if someone wants a std::vector of your array. To be safe, you can use the noexcept operator to make it noexcept if and only if size_type and pointer can be noexcept copied.

Swap and move assignment could do the same; though the linked answer suggests the standard library probably won't notice or care, libraries evolve over time, and there may be other code you end up using that does notice and care.

You might also consider making the destructor (and thus _cleanup) noexcept as well, maybe conditionally so if ~T() and allocator.deallocate(pointer) are noexcept. Especially so if you followed the earlier suggestion of enforcing that ~T() has to be noexcept, and want to be able to have an array of arrays.

Potential improvement: more constexpr

The default (and nullptr) constructors could have been constexpr even before c++20, but now that for example std::allocator can be constexpr, you could very well have a non-empty constexpr object of your class, which means more member functions might also make sense as constexpr, which would also be consistent with the updates to the standard library containers.

Note that unlike noexcept, you can usually just put constexpr on templates as long as it could be constexpr for some type.

Consider construction from raw pointer, size, and allocator

This would allow you to emulate move ("stealing") construction for arrays that were already created without RAII, so long as you know what their allocator is. For example, arrays obtained from a C function that is known to allocate them via malloc could be "moved" into an object provided with an allocator that wraps malloc/free ( std::allocator calls ::operator new which might not call malloc, so wrapping malloc/free is the way to guarantee their usage).

If you never deal with C libraries nor older c++ code, this probably wouldn't come up, since newer c++ code mostly uses RAII, but it is not so difficult to add this support if you are already supporting custom allocators, and this is something std::vector does not do.

Very minor nitpick about the move assignment:

In addition to G. Sliepen's point about reducing duplication, having the move assignment call swap has the benefit of better tolerance of self-assignment. Doing so defers the cleanup until the object referred to by the passed rvalue reference is destroyed, instead of cleaning up first, but you already had to clean up an expiring object, so there's no extra cost in the normal case, you just pay the same cost some number of instructions later. What you gain is that self move-assignment aka *this = std::move(*this) no longer destroys contents. While it would be silly to purposefully self move-assign, it might come up accidentally in some generic template code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.