Advantages of Using Arrays Instead of 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.

What advantages do arrays hold over vectors?

This is not a full answer, but one thing I can think of is, that the "ability to grow and shrink" is not such a good thing if you know what you want. For example: assume you want to save memory of 1000 objects, but the memory will be filled at a rate that will cause the vector to grow each time. The overhead you'll get from growing will be costly when you can simply define a fixed array

Generally speaking: if you will use an array over a vector - you will have more power at your hands, meaning no "background" function calls you don't actually need (resizing), no extra memory saved for things you don't use (size of vector...).

Additionally, using memory on the stack (array) is faster than heap (vector*) as shown here

*as shown here it's not entirely precise to say vectors reside on the heap, but they sure hold more memory on the heap than the array (that holds none on the heap)

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.

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.

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).

C++ std::vector vs array in the real world

A: Almost always [use a vector instead of an array]. Vectors are efficient and flexible. They do require a little more memory than arrays, but this tradeoff is almost always worth the benefits.

That's an over-simplification. It's fairly common to use arrays, and can be attractive when:

• the elements are specified at compile time, e.g. const char project[] = "Super Server";, const Colours colours[] = { Green, Yellow };

  • with C++11 it will be equally concise to initialise std::vectors with values

• the number of elements is inherently fixed, e.g. const char* const bool_to_str[] = { "false", "true" };, Piece chess_board[8][8];

• first-use performance is critical: with arrays of constants the compiler can often write a memory snapshot of the fully pre-initialised objects into the executable image, which is then page-faulted directly into place ready for use, so it's typically much faster that run-time heap allocation (new[]) followed by serialised construction of objects

  • compiler-generated tables of const data can always be safely read by multiple threads, whereas data constructed at run-time must complete construction before other code triggered by constructors for non-function-local static variables attempts to use that data: you end up needing some manner of Singleton (possibly threadsafe which will be even slower)

  • In C++03, vectors created with an initial size would construct one prototypical element object then copy construct each data member. That meant that even for types where construction was deliberately left as a no-operation, there was still a cost to copy the data elements - replicating their whatever-garbage-was-left-in-memory values. Clearly an array of uninitialised elements is faster.

• One of the powerful features of C++ is that often you can write a class (or struct) that exactly models the memory layout required by a specific protocol, then aim a class-pointer at the memory you need to work with to conveniently interpret or assign values. For better or worse, many such protocols often embed small fixed sized arrays.

• There's a decades-old hack for putting an array of 1 element (or even 0 if your compiler allows it as an extension) at the end of a struct/class, aiming a pointer to the struct type at some larger data area, and accessing array elements off the end of the struct based on prior knowledge of the memory availability and content (if reading before writing) - see What's the need of array with zero elements?

• classes/structures containing arrays can still be POD types

• arrays facilitate access in shared memory from multiple processes (by default vector's internal pointers to the actual dynamically allocated data won't be in shared memory or meaningful across processes, and it was famously difficult to force C++03 vectors to use shared memory like this even when specifying a custom allocator template parameter).

• embedding arrays can localise memory access requirement, improving cache hits and therefore performance

That said, if it's not an active pain to use a vector (in code concision, readability or performance) then you're better off doing so: they've size(), checked random access via at(), iterators, resizing (which often becomes necessary as an application "matures") etc.. It's also often easier to change from vector to some other Standard container should there be a need, and safer/easier to apply Standard algorithms (x.end() is better than x + sizeof x / sizeof x[0] any day).

UPDATE: C++11 introduced a std::array<>, which avoids some of the costs of vectors - internally using a fixed-sized array to avoid an extra heap allocation/deallocation - while offering some of the benefits and API features: http://en.cppreference.com/w/cpp/container/array.

Is there any disadvantages if I'm using Array instead of Vector?

Vector adds value in 2 aspects:

1. Provides additional functionality which is not present in C array, such as resizing, checking for current size etc. You may find better alternatives from its interface to your custom solution.
2. Catches some bugs, such as addressing an address beyond the scope of the vector.

If you are satisfied with your proprietary data management and confident in quality of your code, you don't need vector. Note, though, this might pose some software issues, such as decreased maintainability of C array compared to vector (e.g., future code may access an out of bounds value, even if your current code doesn't).

Edit:
See @Als answer for a possible alternative in your case (std::array).

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.

---

Related Topics