Does Std::Array<> Guarantee Allocation on the Stack Only

Does std::array<> guarantee allocation on the stack only?

I could not find more explicit answer in the standard, but [array.overview]/2:

An array is an aggregate ([dcl.init.aggr]) that can be list-initialized with up to N elements whose types are convertible to T.

And [dcl.init.aggr]/1:

An aggregate is an array or a class (Clause [class]) with

• no user-provided, explicit, or inherited constructors ([class.ctor]),

...

That about covers it. No way an aggregate could allocate memory dynamically (or perhaps, do anything at all at its own during the construction). There's only an implicitly-declared trivial constructor.

^{Of course, if you new std::array<...>, you get an array on "the heap".}

---

Some may be more satisfied by what we can get on cppreference:

std::array is a container that encapsulates fixed size arrays.

This container is an aggregate type with the same semantics as a struct holding a C-style array T[N] as its only non-static data member.

---

Thirdly, std::array was introduced in C++11. Why? For example, to complement std::vector in some ways, like usage in constexpr functions, where dynamic allocation is not allowed.

Heap allocation for std::array

The code

map.at(0) = &value;

introduces bounds checking, which might in turn need to use stuff allocated dynamically (e.g. from the <iostream> library).

You may try again with

map[0] = &value;

which doesn't apply bound checks.

Is the memory in std::array contiguous?

Yes, it is contiguous, as it is basically (and actually) a type arr[10];, but with STL like interface. It also doesn't decay to a pointer on the slightest provocation.

You can safely pass &arr[0] to a function expecting a C-style array, that's the design goal of it. To use it with the STL algorithms however, just use the begin and end functions:

// either members
std::sort(arr.begin(), arr.end());
// or free from <iterator>
std::sort(std::begin(arr), std::end(arr));

---

For the language lawyer part, §23.3.2.1 [array.overview] p1:

The header <array> defines a class template for storing fixed-size sequences of objects. An array supports random access iterators. An instance of array<T, N> stores N elements of type T, so that size() == N is an invariant. The elements of an array are stored contiguously, meaning that if a is an array<T, N> then it obeys the identity &a[n] == &a[0] + n for all 0 <= n < N.

And §23.3.2.1 [array.overview] p2:

An array is an aggregate (8.5.1) that can be initialized with the syntax

• array<T, N> a = { initializer-list };

Also, in p3, listing the members of std::array:

T elems[N]; // exposition only

[ Note: The member variable elems is shown for exposition only, to emphasize that array is a class aggregate. The name elems is not part of array’s interface. —end note ]

When vectors are allocated, do they use memory on the heap or the stack?

vector<Type> vect;

will allocate the vector, i.e. the header info, on the stack, but the elements on the free store ("heap").

vector<Type> *vect = new vector<Type>;

allocates everything on the free store.

vector<Type*> vect;

will allocate the vector on the stack and a bunch of pointers on the free store, but where these point is determined by how you use them (you could point element 0 to the free store and element 1 to the stack, say).

Are std::vector elements guaranteed to be contiguous?

This was missed from C++98 standard proper but later added as part of a TR. The forthcoming C++0x standard will of course contain this as a requirement.

From n2798 (draft of C++0x):

23.2.6 Class template vector [vector]

1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized)
constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage
management is handled automatically, though hints can be given to improve efficiency. The elements of a
vector are stored contiguously, meaning that if v is a vector where T is some type other
than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

std::array's allocation on stack and stack overflow errors

printf("%llu\n", sizeof(*new std::vector<uint64_t>(10)));
printf("%llu\n", sizeof(*new std::array<uint64_t, 10>));

First, Neither an object of std::vector<uint64_t> nor std::array<uint64_t, 10> is created here because that expression appears in an Unevaluated Contexet.

Defining an std::array defines/allocates it's
array/collection/buffer on the stack - so why doesn't
std::array<uint64_t, 1000000000000000> array (1 PB) cause a stack
overflow?

you probably still did that in an unevaluated context. Demo.

However, in evaluated contexts such as:

int main(){
    std::array<uint64_t, 1000000000000000> arr;
}

Now, you are likely to get a segfault depending on your environment. You should also know that, the compiler may optimize the code away, (since there's no access to the elements).

Secondly, your code snippet - is not the way to estimate the memory consumed by a container with elements. For std::array we may make assumptions and accept a variant of your code, but certainly not std::vector.

std::vector versus std::array in C++

std::vector is a template class that encapsulate a dynamic array¹, stored in the heap, that grows and shrinks automatically if elements are added or removed. It provides all the hooks (begin(), end(), iterators, etc) that make it work fine with the rest of the STL. It also has several useful methods that let you perform operations that on a normal array would be cumbersome, like e.g. inserting elements in the middle of a vector (it handles all the work of moving the following elements behind the scenes).

Since it stores the elements in memory allocated on the heap, it has some overhead in respect to static arrays.

std::array is a template class that encapsulate a statically-sized array, stored inside the object itself, which means that, if you instantiate the class on the stack, the array itself will be on the stack. Its size has to be known at compile time (it's passed as a template parameter), and it cannot grow or shrink.

It's more limited than std::vector, but it's often more efficient, especially for small sizes, because in practice it's mostly a lightweight wrapper around a C-style array. However, it's more secure, since the implicit conversion to pointer is disabled, and it provides much of the STL-related functionality of std::vector and of the other containers, so you can use it easily with STL algorithms & co. Anyhow, for the very limitation of fixed size it's much less flexible than std::vector.

For an introduction to std::array, have a look at this article; for a quick introduction to std::vector and to the the operations that are possible on it, you may want to look at its documentation.

---

1. Actually, I think that in the standard they are described in terms of maximum complexity of the different operations (e.g. random access in constant time, iteration over all the elements in linear time, add and removal of elements at the end in constant amortized time, etc), but AFAIK there's no other method of fulfilling such requirements other than using a dynamic array. As stated by @Lucretiel, the standard actually requires that the elements are stored contiguously, so it is a dynamic array, stored where the associated allocator puts it.

What is the difference between std::array and std::vector? When do you use one over other?

std::array is just a class version of the classic C array. That means its size is fixed at compile time and it will be allocated as a single chunk (e.g. taking space on the stack). The advantage it has is slightly better performance because there is no indirection between the object and the arrayed data.

std::vector is a small class containing pointers into the heap. (So when you allocate a std::vector, it always calls new.) They are slightly slower to access because those pointers have to be chased to get to the arrayed data... But in exchange for that, they can be resized and they only take a trivial amount of stack space no matter how large they are.

[edit]

As for when to use one over the other, honestly std::vector is almost always what you want. Creating large objects on the stack is generally frowned upon, and the extra level of indirection is usually irrelevant. (For example, if you iterate through all of the elements, the extra memory access only happens once at the start of the loop.)

The vector's elements are guaranteed to be contiguous, so you can pass &vec[0] to any function expecting a pointer to an array; e.g., C library routines. (As an aside, std::vector<char> buf(8192); is a great way to allocate a local buffer for calls to read/write or similar without directly invoking new.)

That said, the lack of that extra level of indirection, plus the compile-time constant size, can make std::array significantly faster for a very small array that gets created/destroyed/accessed a lot.

So my advice would be: Use std::vector unless (a) your profiler tells you that you have a problem and (b) the array is tiny.

How do I create an array in C++ which is on the heap instead of the stack?

You'll want to use new like such:

int *myArray = new int[SIZE];

I'll also mention the other side of this, just in case....

Since your transitioning from the stack to the heap, you'll also need to clean this memory up when you're done with it. On the stack, the memory will automatically cleanup, but on the heap, you'll need to delete it, and since its an array, you should use:

delete [] myArray;

---

Related Topics