I need C++ array class template, which is fixed-size, stack-based and doesn't require default constructor

Question

So, I've been looking at boost::array but it does require default constructor defined. I think the best way of filling this array with data, would be through a push_back(const T&) method. Calling it more times than SIZE (known at compile-time) would result in assert or exception, depending on build configuration. This way it would always contain meaningful data. Does anyone know efficient, portable, reliable implementation of this concept?

Answer 1

Well, I would have thought that someone would have brought the answer now, however it seems not, so let's go.

What you are wishing for is something I have myself dreamed of: a boost::optional_array<T,N>.

There are two variants:

• First: similar to boost::array< boost::optional<T>, N >, that is each element may or may not be set.
• Second: similar to a std::vector<T> (somehow), that is all beginning elements are set and all following ones are not.

Given the previous questions / comments, it seems you would like the second, but it doesn't really matter as both are quite alike.

template <typename T, size_t N>
class stack_vector
{
public:
  bool empty() const { return mSize == 0; }
  size_t size() const { return mSize; }
  size_t capacity() const { return N; }
  size_t max_size() const { return N; }

  T& operator[](size_t i) { return *(this->pfront() + i); }
  /// ...

private:
  T* pfront() const { return reinterpret_cast<T*>(&mStorage); }

  std::aligned_storage< N * sizeof(T), alignof(T) > mStorage;
  size_t mSize; // indicate how many elements are set, from the beginning
};

Let's focus on those very special operations:

template <typename T, size_t N>
void push_back(T const& t)
{
  new (this->pfront() + mSize) T(t); // in place construction
  ++mSize;
}

template <typename T, size_t N>
void clear()
{
  for (size_t i = 0; i != mSize; ++i)
  {
    (this->pfront() + i)->~T();
  }
  mSize = 0;
}

As you can notice, the main difficulty is to remember that:

• if no element has been built there yet, you need placement new + copy construction instead of assignment.
• elements that become "obsolete" (ie would be after the last element) should be properly disposed of (ie their destructor be invoked).

There are many operations on traditional STL container that may be tricky to implement. On a vector, element shuffling (due to insert or erase) are perhaps the most stricking examples.

Also note that with C++0x and initializer-lists vector get emplace_back to directly construct an element in place, thus lifting the CopyConstructible requirement, might be a nice boon dependent on your case.

Answer 2

may be store a boost::variant in your boost::array? make the first parameter an int or something..

i.e.

boost::array<boost::variant<int, foo>, 6> bar;

okay you have to deal with a variant, but it's stack allocated...

Answer 3

In C++0x you got std::array<type, size> (probably the same as boost::array). You can initialize array data by using fill() or std::fill_n():

std::array<int, 30> array;
array.fill(0);
boost::array<int, 30> barray;
std::fill_n(barray.begin(), 30, 0);

If you want to get it default-initialized at definition you can use copy-ctor:

static std::array<int, 30> const nullarray = {0, 0, 0, ..., 0}; // nullarray.fill(0);
// (...)
std::array<int, 30> array{nullarray};

Answer 4

boost::array<T, 12> ta; is no different from T[12] ta;; if you don't use an initializer list then the elements will be default constructed.

The common workaround would be boost::array<T*, 12> ta; or maybe boost::array<unique_ptr<T>, 12> ta;.

The only way to store by value is to copy, no way around that... This is what initializer lists do:

struct A {
    A(int i):_i(i){ cout << "A(int)" << endl; }
    A(const A& a){ cout << "A(const A&)" << endl; }
    ~A(){ cout << "~A()" << endl; }

    int _i;
};

int main(){
    boost::array<A, 2> ta = {{1, 2}};
}

This outputs:

A(int)
A(const A&)
A(int)
A(const A&)
~A()
~A()
~A()
~A()

http://codepad.org/vJgeQWk5

Answer 5

Why does it have to reside on the stack? Do you have empirical evidence that creating and reserveing a vector is too slow (using a vector seems like the obvious answer)?

Even if it is, you can create a pool of vectors that have space reserved and swap one of the pre-allocated vectors into a local copy. When you're done with the local one, swap it back again (much like the splice trick for lists).