What is faster: search in lists or deletion from vector

Problem: given a container, in which we have to find arbitrary elements and delete them. If to skip initial requirements, its alternative implementations, or example, using an extra index to avoid linear search time, and to focus on our implementation only, it turns to a question: is it faster to search with O(N) in lists and delete with O(1), or to index an element with O(1) in the vector and delete with O(N). Intuition says that the vector may beat them all (bunk shifts of data in the vector looks more suitable for an optimization rather than a traversal over the list), but I wanted some numbers.

#include <future>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <typeinfo>
#include <iterator>
#include <iostream>

template <typename T>
void go(T f) {
  auto start = std::chrono::high_resolution_clock::now();
  auto stop = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration<double>(stop - start).count();
  std::cout << duration << "\n";

void erase(std::forward_list<int>& c, std::forward_list<int>::iterator i) {

template <typename T> void erase(T& c, typename T::iterator i) {

template <typename T> void test() {
  std::cout << typeid(T).name() << "\n";
  size_t const N = 100000;
  T v(N, 0);
  for (auto t = N; t > 0; --t) {
    auto i = v.begin();
    std::advance(i, std::rand() % t);
    erase(v, i);

int main() {
  go (test<std::vector<int>>);
  go (test<std::list<int>>);
  go (test<std::forward_list<int>>);
  go (test<std::deque<int>>);

The overloaded erase function is for uniformity of the test funtcion.

Compiling in VS11:

cl /O2 /EHsc test.cpp && test


class std::vector<int,class std::allocator<int> >
class std::list<int,class std::allocator<int> >
class std::forward_list<int,class std::allocator<int> >
class std::deque<int,class std::allocator<int> >

The difference isn’t huge but also not negligible at all as for list and forward_list.