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

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.

• Your code does not compile as-is. Please add everything you left out, especially the includes. Mar 30, 2018 at 18:29

## 2 Answers

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.

• It seems like you're on the way to become a language lawyer :) on the more serious note, I believe alignas(T) unsigned char storage[sizeof(T) * maxsz]; should be enough to deal with aligning. Not sure with unsigned part though. Mar 30, 2018 at 19:15

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;

• Do you have more examples why const after is better? To me it seems it's easier to overlook the * in int const* p thus thinking the pointer is const instead of const int* p where the const clearly refers to the value.
– yuri
Mar 31, 2018 at 9:16
• @yuri: If you think it's easy to miss the asterisk it is because you're not used to this order. It took me 2 days to get used to it, I find the "old" order awkward now. Consistently reading types right to left is a lot easier. And it prevents misunderstandings such as "const ref", which is a misnomer. Mar 31, 2018 at 19:52
• You're probably right about needing to get used to it. Do you happen to know which style is more common or which one is endorsed by Bjarne, Scott, Herb and other language lawyers?
– yuri
Mar 31, 2018 at 20:05
• The C++ standard uses const int, not int const, but that was the norm back in the day and they're not going to change the whole document over this. But what I've seen in replies to related questions on Stack Overflow, and in answers pointing out bugs in code, it seems that the people that write int const have a strong opinion about it, and the people that write const int just do it because they've always done it. Mar 31, 2018 at 21:44
• Thanks for the explanation, I'll try to get used to this as it does seem more logical.
– yuri
Mar 31, 2018 at 21:52