Monday, 3 August 2015

STL - Vector vs List differences in C++


STL:Vector vs List differences in Cpp with examples

Vector:

1. Vector is similar to array
&v[i] == &v[0] + i; 

2. vectors allocates contiguous memory.
3. Vectors allocates memory space at the time of declaration for future elements, in future extra space may be required.
4. Compared to the list here additional space for a pointer is needed, each element only requires the space for the element type itself.
5. Vectors re-allocate memory for the entire vector at any time that we add an element.
6. Insertions at the end are constant. And the insertions at any place are costly O(n).
7. Erasing an element at the end of the vector is constant time, but for the other locations it's O(n).
8. Another advantage for the vector is it provides random access of its elements.
9. Iterators, pointers, and references are invalidated if we add or remove elements to or from the vector.



Simple code snippet that can be helpful to understand the vector v/s list:
  vector::iterator vIter = vect.begin();

  for(vIter = vect.begin(); vIter != vect.end (); ++vIter) {

      if(*vIter == 10) vect.erase (vIter);

  }


So, after the * vIter == 10, at the line the code may crash.

It is very easy to get at the underlying array if we need an array of the elements, let us see the sample code below
  vector<int> vect;

  for(int iInd = 0; iInd < 10; ++iInd) vect.push_back(i);

  int *aVal = &vect[0];


Coming to the list and its features, the below are the features of the list

List:

1. List is a Non-contiguous memory.
2. There is no chance to pre-allocate memory like vector. The memory for the list itself is constant.
3. Each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
4. Never has to re-allocate memory for the whole list just because we add an element.
5. Cost of Insertion and deletion are cheap no matter where in the list they occur.
6. The cost of combining the list is cheap with splicing.
7. Using the list it is not possible to randomly access elements, so getting at a particular element in the list can be expensive.
8. Iterators remain valid even when we add or remove elements from the list.
9. If we need an array of the elements, we'll have to create a new one and add them all to it, since there is no underlying array.

No comments: