When to Use Vectors and When to Use Arrays in C++

When to use vectors and when to use arrays in C++?

Generally always prefer using std::vector<T> since the destruction will be automatic once the vector goes out scope and the allocated memory will be placed neatly on the heap and all the memory will be handled for you. std::vector<T> gives you everything you get in an array and even a guarantee that the elements will be contiguously stored in memory (except for std::vector<bool>).

In the case of std::vector<bool> you have to be careful since code like this will break:

 std::vector<bool> vb;
 vb.push_back(true);
 vb.push_back(false);
 vb.push_back(true);
 bool *pB = &vb[0];
 if( *(pB+1) )
 {
     // do something
 }

Fact is, std::vector<bool> doesn't store contiguous bools. This is an exception in the standard that is fixed in C++11.

When do we use arrays over vectors in C++ and vice versa?

If vectors can do so much, under what circumstances do we still prefer arrays?

A good design is not when there is nothing left to add, rather when there is nothing left to remove. Or introducing extra complexity only when it is needed.

Using arrays or std::vectors in C++, what's the performance gap?

Using C++ arrays with new (that is, using dynamic arrays) should be avoided. There is the problem that you have to keep track of the size, and you need to delete them manually and do all sorts of housekeeping.

Using arrays on the stack is also discouraged because you don't have range checking, and passing the array around will lose any information about its size (array to pointer conversion). You should use std::array in that case, which wraps a C++ array in a small class and provides a size function and iterators to iterate over it.

Now, std::vector vs. native C++ arrays (taken from the internet):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Note: If you allocate arrays with new and allocate non-class objects (like plain int) or classes without a user defined constructor and you don't want to have your elements initialized initially, using new-allocated arrays can have performance advantages because std::vector initializes all elements to default values (0 for int, for example) on construction (credits to @bernie for reminding me).

Should I use vectors instead of arrays?

Use std::array or raw arrays for a small, static number of elements.

If you have a lot of elements (more than say 100kb), you hog the stack and are asking for stack corruption / overflow. In that case, or if the number of elements can only be known at runtime, use std::vector.

when to use a vector instead of an array?

The main advantage is dynamic memory allocation.
A vector starts with limited size, and doubles its size when more space is needed. The average insert complexity is still O(1), which is the main gain here. It's still a bit slower than arrays though.

Other than that, everything you do with a vector can be done with arrays. However, vectors are easier to use, since they can have iterators and fancy constructors and functions.

Arrays vs Vectors: Introductory Similarities and Differences

arrays:

are a builtin language construct;
come almost unmodified from C89;
provide just a contiguous, indexable sequence of elements; no bells and whistles;
are of fixed size; you can't resize an array in C++ (unless it's an array of POD and it's allocated with malloc);
their size must be a compile-time constant unless they are allocated dynamically;
they take their storage space depending from the scope where you declare them;
if dynamically allocated, you must explicitly deallocate them;
if they are dynamically allocated, you just get a pointer, and you can't determine their size; otherwise, you can use sizeof (hence the common idiom sizeof(arr)/sizeof(*arr), that however fails silently when used inadvertently on a pointer);
automatically decay to a pointers in most situations; in particular, this happens when passing them to a function, which usually requires passing a separate parameter for their size;
can't be returned from a function; (Unless it is std::array)
can't be copied/assigned directly;
dynamical arrays of objects require a default constructor, since all their elements must be constructed first;

std::vector:

is a template class;
is a C++ only construct;
is implemented as a dynamic array;
grows and shrinks dynamically;
automatically manage their memory, which is freed on destruction;
can be passed to/returned from functions (by value);
can be copied/assigned (this performs a deep copy of all the stored elements);
doesn't decay to pointers, but you can explicitly get a pointer to their data (&vec[0] is guaranteed to work as expected);
always brings along with the internal dynamic array its size (how many elements are currently stored) and capacity (how many elements can be stored in the currently allocated block);
the internal dynamic array is not allocated inside the object itself (which just contains a few "bookkeeping" fields), but is allocated dynamically by the allocator specified in the relevant template parameter; the default one gets the memory from the freestore (the so-called heap), independently from how where the actual object is allocated;
for this reason, they may be less efficient than "regular" arrays for small, short-lived, local arrays;
when reallocating, the objects are copied (moved, in C++11);
does not require a default constructor for the objects being stored;
is better integrated with the rest of the so-called STL (it provides the begin()/end() methods, the usual STL typedefs, ...)

Also consider the "modern alternative" to arrays - std::array; I already described in another answer the difference between std::vector and std::array, you may want to have a look at it.

Should I use std::vector instead of array

One interesting thing to note is that while iterators will be invalidated in many functions with vectors, that is not the case with arrays. Note: std::swap with std::array the iterator will still point to the same spot.

See more:
http://en.cppreference.com/w/cpp/container/array

Good summary of advantages of arrays:
https://stackoverflow.com/a/4004027/7537900

This point seemed most interesting:

fixed-size arrays can be embedded directly into a struct or object,
which can improve memory locality and reducing the number of heap
allocations needed

Not having tested that, I'm not sure it's actually true though.

Here is a discussion in regards to 2D Vectors vs Arrays in regards to the competitive programming in Code Chef:
https://discuss.codechef.com/questions/49278/whether-to-use-arrays-or-vectors-in-c

Apparently memory is not contiguous in 2 dimensions in 2D vectors, only one dimension, however in 2D arrays it is.

Pointers vs vectors for arrays c++

You can't use the arrb variant because the size of an array must be a compile-time constant in C++, but you are trying to use a runtime size here.

If your compiler is compiling this, then it is doing so only because it supports these so-called variable-length arrays as a non-standard extension. Other compilers will not support them or have differing degree of support or behavior. These arrays are optionally-supported in C, but even there they are probably not worth the trouble they cause.

There is no way to allocate a runtime-dependent amount of memory on the stack in C++ (except if you misuse recursive function calls to simulate it).

So yes, you should use the vector approach. But as discussed in the comments under the question, what you are doing is wrong and causes undefined behavior. You need to either reserve memory and then emplace_back/push_back elements into the vector or you need to resize the vector to the expected size and then you may index it directly. Indexing a vector outside the the range of elements already created in it causes undefined behavior.

Why should someone prefer vectors over arrays?

Vectors have a dimension that may be provided at run-time, such as a user-provided value or something derived from a file's contents.

The size of an array, by contrast, must be hard-coded into your program. It is fixed. ^†

why doesn't everyone simply use vectors for everything?

There is a run-time performance cost for using vectors over arrays when you don't need to. Personally I've never written code in which this is a bottleneck and therefore rarely use raw arrays; still, such scenarios do exist.

^† The exception is when you create a block of memory (an "array" in some sense) dynamically with new[]; this is the exact language feature that is encapsulated by std::vector.

Advantages of using arrays instead of std::vector?

In general, I strongly prefer using a vector over an array for non-trivial work; however, there are some advantages of arrays:

Arrays are slightly more compact: the size is implicit.
Arrays are non-resizable; sometimes this is desirable.
Arrays don't require parsing extra STL headers (compile time).
It can be easier to interact with straight-C code with an array (e.g. if C is allocating and C++ is using).
Fixed-size arrays can be embedded directly into a struct or object, which can improve memory locality and reducing the number of heap allocations needed.

When to Use Vectors and When to Use Arrays in C++