The Differences Between STL Vector and STL List in C++

This article explains and demonstrates the main differences between STL vector and list containers in C++.

Determine When to Use std::vector as Opposed to std::list Container in C++

C++ STL containers often share similar interfaces to manipulate elements. Still, one should explore these data structures’ internal differences to choose the most optimal container for the given problem. The std::vector function is generally known as a dynamic array. It automatically manages the dynamic memory internally and keeps the elements stored contiguously similar to a C-style array. The latter feature makes it possible to access elements in constant time.

On the other hand, the std::list command implements a data structure where elements are managed as a doubly-linked list. We formulate the previous sentence as it is because the C++ standard usually does not enforce the exact implementation to be a doubly-linked list. Still, it specifies certain characteristics that need to be satisfied by the standard library implementers.

The std::list command is provided as the template class, storing any type of object similar to the std::vector. We can store new elements into the std::list object using the push_back or push_front member functions, which all have constant time complexity. As for the std::vector, we only have push_back, which has the average constant complexity. Note that these functions are used to add elements at the beginning/end of the given objects.

The example code below demonstrates the basic usage of the functions above on each container type.

#include <algorithm>
#include <iostream>
#include <list>

using std::cout;
using std::endl;
using std::list;
using std::vector;

int main() {
  vector<int> v = {1, 2, 13, 84};
  list<int> l = {1, 2, 13, 84};

  v.push_back(25);
  v.push_back(13);

  l.push_back(25);
  l.push_front(13);

  return EXIT_SUCCESS;
}

In contrast, we need to utilize the insert member function if we want to insert a new element at the given position. Now, this operation is one of the main differences between std::list and std::vector. Generally, the insert operation is more costly on vector objects than the list objects.

Since the vector contents are stored contiguously, each newly inserted element forces the following elements to be moved to the right, which is dependant on the size of the vector itself. Thus, we should avoid using the vector container if we need to conduct many insertions in the middle of the beginning of the object. If the latter is the case, we’d rather use the list container because it takes constant time to insert a new element anywhere in the list once the position is known.

We demonstrate the insertion time difference in the next code example, where both containers are initialized with arbitrary 100000 integers, and then we time a single insertion operation into each object. Note that we chose a relatively middle position (39999) for both containers, retrieved with the std::search function. As a result, it takes multiple hundreds of factors to insert a new element in the vector that of the list.

Since the element removal operation is similar to the insertion, it’s more efficient on the list object compared to the vector. On the downside, list elements don’t have constant time access operation except for the first and the last elements.

#include <sys/time.h>

#include <algorithm>
#include <iostream>
#include <list>
#include <random>

using std::cout;
using std::endl;
using std::list;
using std::vector;

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

const int MIN = 1;
const int MAX = 100;
const int CAPASITY = 100000;

int main() {
  struct timeval start {};
  struct timeval end {};

  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  vector<int> vec1;
  list<int> list1;

  vec1.reserve(CAPASITY);
  for (int i = 0; i < CAPASITY; ++i) {
    if (i % 39999 == 0) {
      vec1.push_back(111);
      continue;
    }
    vec1.push_back(distr(eng));
  }

  for (int i = 0; i < CAPASITY; ++i) {
    if (i % 39999 == 0) {
      list1.push_back(111);
      continue;
    }
    list1.push_back(distr(eng));
  }

  auto iter = std::find(vec1.begin(), vec1.end(), 111);
  gettimeofday(&start, nullptr);
  vec1.insert(iter, 1111);
  gettimeofday(&end, nullptr);
  printf("insert vector: %0.8f sec\n", time_diff(&start, &end));

  auto iter2 = std::find(list1.begin(), list1.end(), 111);
  gettimeofday(&start, nullptr);
  list1.insert(iter2, 1111);
  gettimeofday(&end, nullptr);
  printf("insert list  : %0.8f sec\n", time_diff(&start, &end));

  return EXIT_SUCCESS;
}

Output:

insert vector: 0.00053000 sec
insert list  : 0.00000100 sec