Bench Vector vs List
Last updated on
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.outResults
| 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 |