Bench Vector vs List

I’ve been asked this question a whole bunch in interviews.

When would you use a list vs a vector?

The answer is - almost never use a list. This is because inserting and removing from a vector costs less than iterating across a list.

This code runs along a container and removes an element.

  • A vector with Itererators
  • A vector without
  • A list
#include <list>
#include <vector>
#include <string>
#include <iostream>


int main() {

        struct foo {
                int bar = {0}; /* hey */
                char padding[256] = {0};
        };

        constexpr size_t count = 10000;
        constexpr size_t remove_from_end = 3;
        static_assert(count > remove_from_end, "count needs to be bigger");

        std::vector<foo> base_vec(count);
        base_vec.at(count - remove_from_end).bar = 1; /* needle */

        /* iterate and remove element from vector */
        {
                std::vector<foo> vec1 = base_vec;

                auto it = std::begin(vec1);
                auto end_it = std::end(vec1);

                auto start = __builtin_ia32_rdtsc();
    
                for(; it != end_it; ++it) {
                        if(it->bar == 1) {
                                vec1.erase(it);
                                break;
                        }
                }

                auto end = __builtin_ia32_rdtsc();

                std::cout << "vec1 find remove: " << end - start << "\n";
        }

        /* iterate and remove element from vector */
        {
                std::vector<foo> vec2 = base_vec;

                auto start = __builtin_ia32_rdtsc();

                for(int i = 0; i < count; ++i) {
                        if(vec2[i].bar == 1) {
                                vec2.erase(std::begin(vec2) + i);
                                break;
                        }
                }

                auto end = __builtin_ia32_rdtsc();

                std::cout << "vec2 find remove: " << end - start << "\n";
        }

        /* iterate and remove element from list */
        {
                std::list<foo> list(std::begin(base_vec), std::end(base_vec));

                auto start = __builtin_ia32_rdtsc();
    
                for(auto it = std::begin(list); it != std::end(list); ++it) {
                        if(it->bar == 1) {
                                list.erase(it);
                                break;
                        }
                }

                auto end = __builtin_ia32_rdtsc();

                std::cout << "list find remove: " << end - start << "\n";
        }

        return 0; 
}

Compile and Run in C

c++ vec_vs_list.cpp -std=c++11 && ./a.out

Results

| Count  | Vec1      | Vec2      | List       |
|--------|-----------|-----------|------------|
| 10     | 10,146    | 279       | 873        |
| 100    | 10,515    | 654       | 2,322      |
| 1,000  | 19,278    | 6,801     | 36,279     |
| 10,000 | 305,325   | 353,646   | 997,494    |
| 100,000| 6,540,924 | 3,077,586 | 13,878,894 |