3
\$\begingroup\$

I'm trying to expand on the implementation of static_vector on the std::aligned_storage reference page, but would like to split it into two parts. First, an aligned_storage_array that supports perfect forwarding (so that I can emplace into it) and doesn't require a default constructor, and then the actual static_vector infrastructure that builds upon it. This will let me use the aligned_storage_array for some other static data structures I plan to make in the future.

aligned_storage_array.h

#pragma once

#include <array>
#include <memory>
#include <stdexcept>

namespace nonstd
{
    template<class T, std::size_t N>
    class aligned_storage_array
    {
    public:
        aligned_storage_array()  = default;
        ~aligned_storage_array() = default;

        // Move and copy must be manually implemented per-element by the user
        aligned_storage_array(aligned_storage_array&& rhs)                 = delete;
        aligned_storage_array& operator=(aligned_storage_array&& rhs)      = delete;
        aligned_storage_array(const aligned_storage_array& rhs)            = delete;
        aligned_storage_array& operator=(const aligned_storage_array& rhs) = delete;

        // Size
        constexpr std::size_t size() const noexcept { return N; }
        constexpr std::size_t max_size() const noexcept { return N; }

        // Access
        inline T& operator[](std::size_t pos)
        {
            return *std::launder(
                reinterpret_cast<T*>(
                    std::addressof(m_data[pos])));
        }

        inline const T& operator[](std::size_t pos) const
        {
            return *std::launder(
                reinterpret_cast<const T*>(
                    std::addressof(m_data[pos])));
        }

        inline T& at(std::size_t pos)
        {
            return *std::launder(
                reinterpret_cast<T*>(
                    std::addressof(m_data.at(pos))));
        }

        inline const T& at(std::size_t pos) const
        {
            return *std::launder(
                reinterpret_cast<const T*>(
                    std::addressof(m_data.at(pos))));
        }

        // Operations
        template<typename ...Args>
        inline T& emplace(size_t pos, Args&&... args)
        {
            return
                *::new(std::addressof(m_data[pos]))
                T(std::forward<Args>(args)...);
        }

        template<typename ...Args>
        inline T& bounded_emplace(size_t pos, Args&&... args)
        {
            return
                *::new(std::addressof(m_data.at(pos)))
                T(std::forward<Args>(args)...);
        }

        inline void destroy(std::size_t pos)
        {
            std::destroy_at(
                std::launder(
                    reinterpret_cast<const T*>(
                        std::addressof(m_data[pos]))));
        }

        inline void bounded_destroy(std::size_t pos)
        {
            std::destroy_at(
                std::launder(
                    reinterpret_cast<const T*>(
                        std::addressof(m_data.at(pos)))));
        }

    private:
        std::array<std::aligned_storage_t<sizeof(T), alignof(T)>, N> m_data;
    };
}

static_vector.h

#pragma once

#include <array>
#include <stdexcept>

#include "aligned_storage_array.h"

namespace nonstd
{
    template<class T, std::size_t N>
    class static_vector
    {
    public:
        using value_type      = T;
        using pointer         = T*;
        using const_pointer   = const T*;
        using reference       = value_type&;
        using const_reference = const value_type&;
        using iterator        = value_type*;
        using const_iterator  = const value_type*;
        using size_type       = std::size_t;

        static_vector() = default;
        ~static_vector() { clear(); }

        static_vector(const static_vector& rhs)
        {
            clear(); // Sets m_size to zero for safety
            for (std::size_t pos = 0; pos < rhs.m_size; ++pos)
                m_data[pos] = rhs.m_data[pos];
            m_size = rhs.m_size;
        }

        static_vector& operator=(const static_vector& rhs)
        {
            if (this != std::addressof(rhs))
            {
                clear(); // Sets m_size to zero for safety
                for (std::size_t pos = 0; pos < rhs.m_size; ++pos)
                    m_data[pos] = rhs.m_data[pos];
                m_size = rhs.m_size;
            }
            return *this;
        }

        static_vector(static_vector&& rhs)
        {
            // Start by clearing sizes to avoid bad data
            // access in the case of an exception
            std::size_t count_self = m_size;
            std::size_t count_rhs = rhs.m_size;
            m_size = 0;
            rhs.m_size = 0;

            // Can't swap because the destination may be uninitialized
            destroy_n(count_self);
            for (std::size_t pos = 0; pos < count_rhs; ++pos)
                m_data[pos] = std::move(rhs.m_data[pos]);
            m_size = count_rhs;
        }

        static_vector& operator=(static_vector&& rhs)
        {
            // Start by clearing sizes to avoid bad data
            // access in the case of an exception
            std::size_t count_self = m_size;
            std::size_t count_rhs = rhs.m_size;
            m_size = 0;
            rhs.m_size = 0;

            // Can't swap because the destination may be uninitialized
            destroy_n(count_self);
            for (std::size_t pos = 0; pos < count_rhs; ++pos)
                m_data[pos] = std::move(rhs.m_data[pos]);
            m_size = count_rhs;
            return *this;
        }

        // Size and capacity
        constexpr std::size_t size()      const { return m_size; }
        constexpr std::size_t max_size()  const { return N; }
        constexpr bool empty()            const { return m_size == 0; }

        // Iterators
        inline iterator begin()                 { return &m_data[0]; }
        inline const_iterator begin()     const { return &m_data[0]; }
        inline iterator end()                   { return &m_data[m_size]; }
        inline const_iterator end()       const { return &m_data[m_size]; }

        // Access
        inline T& operator[](std::size_t pos)
        {
            return m_data[pos];
        }

        inline const T& operator[](std::size_t pos) const
        {
            return m_data[pos];
        }

        inline T& at(std::size_t pos)
        {
            if ((pos < 0) || (pos >= m_size))
                throw std::out_of_range("static_vector subscript out of range");
            return m_data[pos];
        }

        inline const T& at(std::size_t pos) const
        {
            if ((pos < 0) || (pos >= m_size))
                throw std::out_of_range("static_vector subscript out of range");
            return m_data[pos];
        }

        // Operations
        template<typename ...Args>
        inline T& emplace_back(Args&&... args)
        {
            T& result = m_data.bounded_emplace(m_size, args...);
            ++m_size;
            return result;
        }

        inline void clear()
        {
            std::size_t count = m_size;
            m_size = 0; // In case of exception
            destroy_n(count);
        }

    private:
        void destroy_n(std::size_t count)
        {
            for (std::size_t pos = 0; pos < count; ++pos)
                m_data.destroy(pos);
        }

        aligned_storage_array<T, N> m_data;
        std::size_t m_size = 0;
    };
}

A full testing apparatus is available here (wandbox). Mostly I'd like some extra eyes to help determine:

  1. Is this actually safe for placement new with respect to alignment?
  2. Is the use of std::launder correct?
  3. Is the use of reinterpret_cast correct (or should it be two static_casts instead?)
  4. Are there any hidden pitfalls I should watch out for here (aside from the maximum capacity)?
  5. Am I being sufficiently paranoid (::new, std::address_of, std::destroy_at)? Any other safety features I can put in to handle risky operator overloads?
  6. Is this approach to copy/move correct? I feel as though I need to be hands-on because the underlying array may have unknown uninitialized fields. Am I doing the right thing about exception safety? I decided I'd rather have the vector appear empty than have it appear full with malformed entries.
  7. What should I do, if anything, about an std::swap on either data structure?

I'm told this is similar to something like boost::small_vector, but I want the aligned_storage_array generalized because I want to use it for a number of different static structures later. Also, I would like to learn more about alignment/placement new, forwarding, and launder.

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$ 
static_vector(const static_vector& rhs)
{
    clear(); // Sets m_size to zero for safety
    for (std::size_t pos = 0; pos < rhs.m_size; ++pos)
        m_data[pos] = rhs.m_data[pos];
    m_size = rhs.m_size;
}

clear() is not needed (m_size is already zero because of the default member initializer).

bug: We are assigning to elements that haven't been constructed yet! We need to use placement new (either through the emplace function, or std::uninitialized_copy_n) to construct each element in place. The move constructor has the same issue.

static_vector(static_vector&& rhs)
{
    // Start by clearing sizes to avoid bad data
    // access in the case of an exception
    std::size_t count_self = m_size;
    std::size_t count_rhs = rhs.m_size;
    m_size = 0;
    rhs.m_size = 0;

    // Can't swap because the destination may be uninitialized
    destroy_n(count_self);
    for (std::size_t pos = 0; pos < count_rhs; ++pos)
        m_data[pos] = std::move(rhs.m_data[pos]);
    m_size = count_rhs;
}

Same issue as above (assignment to non-constructed elements).

We could call clear() to set the size to zero and destroy the elements in this.

bug: It's incorrect to alter the size of rhs like this. Although we have moved from the rhs elements, they still "exist", and we need to call their destructors. (Note that unlike std::vector, std::array isn't empty after a "move").

If we want rhs to be empty afterwards, we can call rhs.clear() after moving the elements.

The copy / move construction / assignment can be simplified quite a bit:

static_vector(const static_vector& rhs)
{
    std::uninitialized_copy(rhs.begin(), rhs.end(), begin());
    m_size = rhs.m_size;
}

static_vector& operator=(const static_vector& rhs)
{
    clear();
    std::uninitialized_copy(rhs.begin(), rhs.end(), begin());
    m_size = rhs.m_size;
    return *this;
}

static_vector(static_vector&& rhs)
{
    std::uninitialized_move(rhs.begin(), rhs.end(), begin());
    m_size = rhs.m_size;
}

static_vector& operator=(static_vector&& rhs)
{
    clear();
    std::uninitialized_move(rhs.begin(), rhs.end(), begin());
    m_size = rhs.m_size;
    return *this;
}

Swapping is never going to be fast because we're storing the elements on the stack, and have to swap them all in turn. We could write something with std::swap_ranges, and then std::uninitialized_move any extra elements if there's a size mismatch, but I'd probably just do this:

    // member function
    void swap(static_vector& rhs)
    {
        auto temp = std::move(*this);
        *this = std::move(rhs);
        rhs = std::move(temp);
    }

...

// free function in the nonstd namespace
template<class T, std::size_t N>
void swap(static_vector<T, N>& a, static_vector<T, N>& b)
{
    a.swap(b);
}

I think preventing copy and move (and not defining swap) on aligned_storage_array is fine.

inline T& at(std::size_t pos)
{
    if ((pos < 0) || (pos >= m_size))
    ...
}

pos is (correctly) unsigned, so (pos < 0) isn't needed.

Use the size_type typedef for the function argument (same with the other element access functions).

There's no need to use the inline keyword for functions defined in a class body.

    inline iterator begin()                 { return &m_data[0]; }
    inline const_iterator begin()     const { return &m_data[0]; }
    inline iterator end()                   { return &m_data[m_size]; }
    inline const_iterator end()       const { return &m_data[m_size]; }

bug: This is undefined behaviour. The array elements at [m_size] or even [0] may not exist. (So the std::array implementation may sensibly throw or crash if we try to access them).

We can fix this with:

    // in aligned_storage_array:
    T* data()
    {
        return std::launder(
            reinterpret_cast<T*>(m_data.data()));
    }

    T const* data() const
    {
        return std::launder(
            reinterpret_cast<T const*>(m_data.data()));
    }

    ...

    // in static_vector:
    iterator begin()                 { return m_data.data(); }
    const_iterator begin()     const { return m_data.data(); }
    iterator end()                   { return m_data.data() + m_size; }
    const_iterator end()       const { return m_data.data() + m_size; }

This gives us pointer access, which is what we need for iterators. As long as we only dereference pointers to valid elements, we avoid undefined behaviour (i.e. don't dereference end(), and only use begin() if size() isn't zero).

    template<typename ...Args>
    inline T& emplace_back(Args&&... args)
    {
        T& result = m_data.bounded_emplace(m_size, args...);
        ...
    }

We should use std::forward here (it's correctly used in the aligned_storage_array::emplace functions).

I'm really not very familiar with std::launder, so hopefully someone else can comment on that.

\$\endgroup\$
4
  • \$\begingroup\$ These are great. I have two follow-up questions. (1) Should I retain the if (this != std::addressof(rhs)) check in static_vector's copy? I noticed you removed it in your simplication. (2) Would std::destroy_n be a safe/viable alternative to use in the static_vector destroy_n() function? \$\endgroup\$ Commented Jan 14, 2019 at 1:16
  • \$\begingroup\$ One additional note, after testing. The new move constructor and assignment of the static_vector doesn't set the rhs structure's m_size to zero, which means that that that rhs static_vector will destruct its (now potentially unknown) contents when going out of scope. Should I add a line to set it to zero in this case and avoid that behavior? \$\endgroup\$ Commented Jan 14, 2019 at 1:30
  • 1
    \$\begingroup\$ (1) It's not needed. Copy / swap works for self-assignment too. Note that checking would add overhead for the non-self-assignment cases, which are the ones we want to be faster! (2) Yes. \$\endgroup\$ Commented Jan 14, 2019 at 7:52
  • 1
    \$\begingroup\$ Yes. We still need to call destructors on moved-from objects, so directly setting m_size to zero is wrong. But if we want the static_vector to be empty after move (probably a good design choice), we can call clear() on rhs just before returning from the constructor / operator. \$\endgroup\$ Commented Jan 14, 2019 at 8:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.