C++ template class for variable-length arrays with maximum size for good cache locality

Question

For my problem, see this Stack Overflow question: https://stackoverflow.com/questions/49577746/is-there-standard-c-template-class-for-variable-length-arrays-with-maximum-siz

I need an array that stores its elements inline in the C++ language. The array must be variable-sized but up to the specified maximum. Most such arrays are small, thus it would be a waste on 64-bit architectures to use size_t as the array size everywhere. The code is here:

#include <stdexcept>
#include <algorithm>
#include <stdlib.h>

template<class C, class sz_t, sz_t maxsz> class inlinearray {
  private:
    typedef C value_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type &reference;
    typedef const value_type &const_reference;
    typedef value_type *iterator;
    typedef const value_type *const_iterator;
    typedef sz_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    sz_t sz;
    union {
      C realarray[maxsz]; // for correct alignment
      char array[maxsz*sizeof(C)];
    };
  public:
    inlinearray()
    {
      sz = 0;
    }
    ~inlinearray(void)
    {
      clear();
    }
    void clear(void)
    {
      sz_t i;
      for (i = 0; i < sz; i++)
      {
        data()[i].~C();
      }
      sz = 0;
    }
    template<class sz2_t, sz2_t maxsz2> inlinearray(inlinearray<C,sz2_t,maxsz2> that)
    {
      size_t i;
      sz = that.sz;
      for (i = 0; i < sz; i++)
      {
        push_back(that[i]);
      }
    }
    template<class sz2_t, sz2_t maxsz2> void operator=(inlinearray<C,sz2_t, maxsz2> val2)
    {
      swap(val2);
    }
    void fill(const C& val)
    {
      std::fill_n(begin(), size(), val);
    }
    C &operator[](sz_t i) noexcept
    {
      return data()[i];
    }
    constexpr const C &operator[](sz_t i) const noexcept
    {
      return data()[i];
    }
    C at(sz_t i)
    {
      if (i >= sz)
      {
        throw std::out_of_range("inlinerray::at() out of range");
      }
      return data()[i];
    }
    constexpr const C at(sz_t i) const
    {
      if (i >= sz)
      {
        throw std::out_of_range("inlinerray::at() out of range");
      }
      return data()[i];
    }
    void push_back(const C &c)
    {
      if (sz >= maxsz)
      {
        abort();
      }
      new (data()+sz) C(c);
      sz++;
    }
    void pop_back() noexcept
    {
      data()[sz-1].~C();
      sz--;
    }
    template <class sz2_t, sz2_t maxsz2> void swap(inlinearray<C, sz2_t, maxsz2> &that)
    {
      if (that.sz > maxsz)
      {
        abort();
      }
      if (sz > that.maxsz)
      {
        abort();
      }
      std::swap_ranges(begin(), end(), that.begin());
      std::swap(sz, that.sz);
    }
    constexpr sz_t size(void) const noexcept { return sz; }
    constexpr sz_t max_size(void) const noexcept { return maxsz; }
    constexpr bool empty() const noexcept { return sz == 0; }
    C *begin() noexcept { return data(); }
    C &front() noexcept { return data()[0]; }
    C &back() noexcept { return sz == 0 ? data()[0] : data()[sz - 1]; }
    constexpr const C &back() const noexcept { return sz == 0 ? data()[0] : data()[sz - 1]; }
    C *end() noexcept { return data() + sz; }
    C* data() noexcept { return reinterpret_cast<C*>(array); }
    const C* data() const noexcept { return reinterpret_cast<const C*>(array); }
    const C *begin() const noexcept { return data(); }
    const C *end() const noexcept { return data() + sz; }
    const C *cbegin() const noexcept { return data(); }
    const C *cend() const noexcept { return data() + sz; }
    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(end()); }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
};

Now, is there something I should improve in this code? One obvious improvement would be to add support for larger "remote" data stored via a pointer to an array to make the maximum size unbounded.

I'm not very familiar with C++ (being mostly a C programmer), so I might not be aware of all of the language features and quirks.

Answer 1

You may have issues with C in a union if it is non trivial (i.e. it has any constructors/destructors/assingment operators).

From n4727: Section 12.3 Union

if any non-static data member of a union has a non-trivial default constructor (15.1), copy constructor (15.8), move constructor (15.8), copy assignment operator (15.8), move assignment operator (15.8), or destructor (15.4), the corresponding member function of the union must be user-provided or it will be implicitly deleted (11.4.3) for the union.

An example is provided:

Example: Consider the following union:

 union U {
   int i;
   float f;
   std::string s;
 };

Since std::string (24.3) declares non-trivial versions of all of the special member functions, U will have an implicitly deleted default constructor, copy/move constructor, copy/move assignment operator, and destructor. To use U, some or all of these member functions must be user-provided. — end example

Code Review:

In C and C++ the built in array is destroyed in reverse order. Your destructor calls clear which destroys them in the standard order.

void clear(void)
{
  sz_t i;
  for (i = 0; i < sz; i++)
  {
    data()[i].~C();
  }
  sz = 0;
}

Though not technically wrong (you can define the semantics for your class). It would be nice if the behavior was the same as a normal array (and std::vector, std::array etc).

Thats a very long line:

template<class sz2_t, sz2_t maxsz2> inlinearray(inlinearray<C,sz2_t,maxsz2> that)

Normally people break these into two lines. One for the template information and the next for the function information:

template<class sz2_t, sz2_t maxsz2>
inlinearray(inlinearray<C,sz2_t,maxsz2> that)

Now that it is short. I can see that you pass by value. This means that you create a copy of the parameter. Better if you passed a const reference.

template<class sz2_t, sz2_t maxsz2>
inlinearray(inlinearray<C,sz2_t,maxsz2> const& that)
                                     // ^^^^^^

This looks like a bug:

  sz = that.sz;            // You set the size here.
  for (i = 0; i < sz; i++)
  {
    push_back(that[i]);    // But does this not increment the size.
  }                        // Looks like the resulting size is 2*this.sz

In for loops you can declare the variable in-line as part of the for.

  size_t i;
  for (i = 0; i < sz; i++)

Easier to write as:

  for (size_t i = 0; i < sz; ++i) // Prefer pre-increment

Note. It is preferable to use pre-increment whenever possible. This is because it is usually the most efficient version of increment (on non POD types). This allows you to change the underlying type of an object without having to look and make sure you were useing the correct increment.

For example. A loop variable may be an integer now. But in the future a maintainer may change it to be an iterator. If you have used the pre-increment consistently then it will always be the most efficient version. If you use post increment then now you 'may' have some performance degradation.

I would note that you don't implement move semantics. Now you can't move the whole structure as a whole (no pointers). But you could potentially move the data elements C. This could potentially be much more efficient (think of inlinearray<std::vector<int>, int, 12>).

In C++ (unlike C) we place the & and * next to the type.

 C&  operator[](sz_t i) noexcept
^^^^

This is because type information is much more important in C++ and that extra symbol conveys information about the type.

Your operator[] return references, why does the at() function not return references?

C at(sz_t i)
constexpr const C at(sz_t i) const

DRY your code:

C at(sz_t i)
{
  // This following bit of code.
  if (i >= sz)
  {
    throw std::out_of_range("inlinerray::at() out of range");
  }
  return data()[i];
}
constexpr const C at(sz_t i) const
{
  // Looks exactly like this bit of code.
  if (i >= sz)
  {
    throw std::out_of_range("inlinerray::at() out of range");
  }
  return data()[i];
}

You have the standard copy into array:

void push_back(const C &c)

But you should also enable move semantics for adding values.

void push_back(const C& c);        // Copy
void push_back(C&& c);             // Move
template<typename... Args>
void emplace_back(Args...&& args); // Build in place using constructor.

You may want to define your begin()/end() in terms of an iterator.

C *begin() noexcept { return data(); }

Should probably be defined as:

using iterator = C*;

iterator begin() noexcept { return data(); }

This separates the implementation from a specific type and allows you to modify the underlying type in the future without having to worry about users of your code changing there code.

I tend to group all the iterator calls together. Not intermix them with other calls.

Answer 2

Martin was quite thorough. I have two things to add about C++ syntax.

First, prefer using over typedef. It is easier to read, and more flexible. Instead of

typedef C value_type;

you'd write

using value_type = C;

This works with templates also.

Second, write const and other modifiers after the type they modify. Instead of

const value_type *ptr;

you'd write

value_type const* ptr;

There are several advantages, most importantly all the bugs that I've had with the former order that don't appear in the latter. For example:

using pointer = value_type*;
const pointer ptr;

ptr is not a const value_type*, as you'd get with text substitution, but a value_type* const. Thus it's the pointer itself that is const, not the data pointed to. Using the order I suggest this would have been obvious:

pointer const ptr;