c++ – Which is faster: vector traversal or list traversal?

Question:

At the interview they asked: which is faster, traversing a vector or traversing a list with outputting values ​​to the console? How we get around was not specified. I replied that there was no difference. Was I right? Explanation: there is a vector container that we iterate over, for example, with an iterator:

std::vector<int> vector{1, 2, 3};
for (auto it = vector.begin(); it != vector.end(); ++it)
{
    qDebug() << *it;
}

there is a container list, which we also iterate over with an iterator:

std::list<int> values{1, 2, 3};
for (auto it = values.begin(); it != values.end(); ++it)
{
    qDebug() << *it;
}

Which loop will run faster and why? Which of the loops will run faster with other ways to traverse these containers? These cycles were not present in the interview, I added them for clarity.

PS After this question, then they asked: what is cache? Perhaps the second question has something to do with the first? If the entire vector or list does not end up in the cache, will the container traversal time increase?

Answer:

The vector is slightly faster due to two factors:

  1. it has no transitions to pointers, no unnecessary dereferencing

  2. there are no transitions by pointers in it – everything lies in one heap, which means that with a high degree of locality, so there is a high probability that all the contents of the vector will fit in the processor's cache (and if not all because of a very large vector, then in large chunks) , i.e. at a significantly faster speed than in the general case in a list, where elements can be scattered throughout the memory …

PS Since this question has surfaced again 🙂 – measurable.

Million list and vector. Sorting – so that the list contains more random jumps to different memory locations.

list<int> L;
vector<int> V;

int main(int argc, const char * argv[])
{
    for(int i = 0; i < 1000000; ++i)
    {
        int r = rand();
        V.push_back(r);
        L.push_back(r);
    }
    L.sort();
    sort(V.begin(),V.end());

    {
        muTimer mu;
        long long int sum = 0;
        for(int i: V) sum += i;
        mu.stop();
        cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
    }
    {
        muTimer mu;
        long long int sum = 0;
        for(int i: L) sum += i;
        mu.stop();
        cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
    }

}

The complete code is here . As you can see, the difference is almost 200 times in favor of the vector … So "somewhat faster" – I underestimated this 🙂

Scroll to Top