How operations are performed for dynamic array?

Question

I have studied everywhere in books about Dymanic arrays. I have used them in STL of C++. But I am still unclear about what are Dynamic arrays. How the operations over Dynamic arrays are implemented.

Answer 1

In C++ there are (well, pretty soon will be!) 4 kinds of arrays: C-style static arrays, C++11 static arrays, C++ dynamic vectors and C++14 dynamic arrays.

The C-style and C++11 static arrays take a compile-time constant size parameter and cannot be enlarged / shrunk after their initialization. C++ dynamic vectors can take any runtime number of elements at initialization, and can be enlarged / shrunk afterwards. With the upcoming C++14 Standard, there will also be std::dynarray that fills a smal gap between the existing containers: it will take a runtime number of elements during initialization, but cannot be enlarged / shrunk afterwards.

Here are some basic use cases:

static const int N = 4;                // compile-time constant int
int M = 4;                             // run-time int

int c[N] = { 0, 1, 2, 3 };             // C-style static array: compile-time constant size
std::array<int, N> a = { 0, 1, 2, 3 }; // C++11 static array: compile-time constant size

int rc[M] = { 0, 1, 2, 3 };             // ERROR: M is not a compile-time constant expression
std::array<int, M> ra = { 0, 1, 2, 3 }; // ERROR: M is not a compile-time constant expression

std::vector<int> v { std::begin(a), std::end(a) };   // C++ dynamic vector: runtime size, but can be enlarged afterwards
v.push_back(4);                                      // v enlarged to { 0, 1, 2, 3, 4 } now
v.pop_back();                                        // v shrunk back to { 0, 1, 2, 3 }

std::dynarray<int> d { std::begin(v), std::end(v) }; // C++14 dynamic array: runtime size, but cannot be enlarged afterwards

Static arrays (C-style arrays, std::array) do static memory allocation on the stack. Dynamic arrays (std::vector<T> and std::dynarray<T>) can take an Allocator template parameter. For std::vector this Allocator defaults to std::allocator<T>, which does dynamic low-level memory management behind the scenes using new. For std::dynarray the memory is allocated from an unspecified source, which may, or may not, invoke the global operator new.

By supplying a user-defined allocator, both std::vector and std::dynarray can be made to work with stack-based memory allocation, e.g. using @HowardHinnant 's stack allocator.