Array VS Vector VS List

array vs vector vs list

Use STL vector. It provides an equally rich interface as list and removes the pain of managing memory that arrays require.

You will have to try very hard to expose the performance cost of operator[] - it usually gets inlined.

I do not have any number to give you, but I remember reading performance analysis that described how vector<int> was faster than list<int> even for inserts and deletes (under a certain size of course). The truth of the matter is that these processors we use are very fast - and if your vector fits in L2 cache, then it's going to go really really fast. Lists on the other hand have to manage heap objects that will kill your L2.

Difference between vector and list

A vector is a resizable array. It's elements are stored next to each other in a contiguous block of memory, so that the position of each can be calculated quickly; this is known as random access. Inserting and removing elements from the middle requires moving all the later elements, so can be rather slow.

A list is a linked list. The elements are scattered around memory, and each has pointers to the next and previous element. You can only find an element by following the chain of pointers, which might be rather slow; this is known as sequential access. But elements can be inserted and removed just by modifying a few pointers, so that can be quite fast.

vector vs. list in STL

Situations where you want to insert a lot of items into anywhere but the end of a sequence repeatedly.

Check out the complexity guarantees for each different type of container:

What are the complexity guarantees of the standard containers?

std::vector vs std::array vs normal array

push_back takes a long time compared to arr[i]=x;.

Sorry but you are showing your lack of experience with vectors here, because your examples do two different things.

You are comparing something like this code

vector<int> vec;       // vector created with size zero
for (...)
vec.push_back(x); // vector size increases

with this code

int arr[N];
for (...)
arr[i] = x;

The difference is that in the first case the vector has size 0 and it's size increases as you add items to it (this takes extra time), but in the second case the array starts out at it's final size. With an array this is how it must be, but with vectors you have a choice. If you know what the final size of the vector is you should code it like this

vector<int> vec(N); // vector created at size N, note use () not []
for (...)
vec[i] = x;

That is the code you should be comparing with the array code for efficiency,

You might also want to research the resize and reserve methods of a vector. Vectors (if nothing else) are much more flexible than arrays.

Array vs vector vs tuples?

Short answer -

Arrays - Fixed size container of same type of objects

Vectors - Dynamic size container of same type of objects

Tuples - Dynamic size container of different type of objects

All of them preserve the order of insertions.

The difference between vector and array varies largely from language to language. For instance, in C++, vector is dynamic array (wrapper over primitive array). For java, there is ArrayList and Vector for dynamic container - the latter is thread safe.

Relative performance of std::vector vs. std::list vs. std::slist?

As usual the best answer to performance questions is to profile both implementations for your use case and see which is faster.

In general if you have insertions into the data-structure (other than at the end) then vector may be slower, otherwise in most cases vector is expected to perform better than list if only for data locality issues, this means that if two elements that are adjacent in the data-set are adjacent in memory then the next element will already be in the processor's cache and will not have to page fault the memory into the cache.

Also keep in mind that the space overhead for a vector is constant (3 pointers) while the space overhead for a list is paid for each element, this also reduces the number of full elements (data plus overhead) that can reside in the cache at any one time.

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.

In Racket, what is the advantage of lists over vectors?

Since list-ref uses time linear to the index, it is rarely okay to use unless for short lists. If the access pattern is sequential however and the number of elements can vary, then lists are fine. It would be interesting to see a benchmark for summing the elements of a 50 element long list of fixnums.

The access pattern to a data structure is not always sequential though.

Here is how I choose which data structure to use in Racket:

DATA STRUCTURE   ACCESS       NUMBER     INDICES
List: sequential Variable not used
Struct: random Fixed names
Vector: random Fixed integer
Growable vector: random Variable integer
Hash: random Variable hashable
Splay: random Variable non-integer, total order

What is a Stack, Queue, Vector, Array and List?

These are different data structures that you are talking about. Why are we using different ones then? The reason for this is that different data structures are good at different things.

Data structures differ from themselves by relationships between their elements, and the actions that can be done on the data structure.

Different operations on different data structures can have a different complexity. A complexity is a measure of how much the number of operations grow by an increase in the amount of data.

Since your question is about C++, I will talk about 2 data structures: vector and list.
There is one more sequential container - deque, which is similar to a vector, the major difference is that operations such as inserting an element at the front are much faster.

Vector

This is a really useful data structure that is an auto growing array. Since an array is stored in a continuous chunk of memory, some operations are less computation intensive than others.

Let's look at the operations that we can do on a vector.

Element access

Since all elements are in a continuous chunk of memory, getting the nth element is O(1).

Adding to the end

If we have space left, and we know the size of the vector, this operation is O(1). If we do not have space, we need to allocate more space, and copy all the data to the new space. This is O(n), but this happens rarely.

Insert and Removal

This involves moving all the elements after the place of inserting to the right. This is O(n)

List

This structure has some advantages over a vector. The elements are not in a continuous chunk of memory, which makes the insert operations much faster.

Element access

To get to the nth element, you have to go through each list node from the beginning until you reach the nth element. This operation is O(n)

Adding to the end

If we have a pointer to the last element, this operation is O(1).

Insert and Removal

This involves finding the place to insert - O(n) and fixing up the pointers. This seems like the same complexity, but a vector has to copy elements, while a list only looks for the right place. A big difference would be seen if we want to insert an element at the very beginning. A list, would have to look through nothing, while a vector would have to move almost all the elements.

Stack and Queue

These are container adapters. They wrap the above containers, implement stronger relationships, and add new operations.

The difference between these two is that a stack is LIFO - last in first out, while the queue is FIFO - first in first out. Different algorithms use different data structures, since the operations available are faster.

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 you have to keep track of the size, and you need to delete them manually and do all sort 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 boost::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 the 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).



Related Topics



Leave a reply



Submit