Что быстрее: обход вектора или обход списка?

247

29 июля 2017, 06:10

На собеседовании спросили: что быстрее, обход вектора или обход списка с выводом значений в консоль? Каким образом обходим, не уточнили. Я ответил, что разницы нет. Был ли я прав? Пояснение: имеется контейнер вектор, по которому мы пробегаемся, например, итератором:

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

имеется контейнер список, по которому мы также пробегаемся итератором:

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

Какой из циклов будет работать быстрее и почему? Какой из циклов будет работать быстрее при других способах обхода этих контейнеров? Этих циклов не было на собеседовании, я их добавил для наглядности.

P.S. После этого вопроса затем спросили: что такое кэш? Возможно, второй вопрос как-то связан с первым? Если весь вектор или список не попадает в кэш, то время обхода контейнера увеличится?

Answer 1

Вектор несколько быстрее - за счет двух факторов:

в нем нет переходов по указателям, нет лишних разыменований
в нем нет переходов по указателям - все лежит одной кучей, а значит, с высокой степенью локальности, так что высока вероятность, что все содержимое вектора разместится в кеше (а если и не все из-за очень большого вектора - то большими кусками), т.е. с существенно более высокой скоростью, чем в общем случае в списке, где элементы могут быть разбросаны по всей памяти...

Answer 2

Для вопроса "обход вектора или обход списка с выводом значений в консоль" - правильный ответ это "одинаково, т.к. время обхода пренебрежимо мало по сравнению со временем записи в консоль".

Что касается времени итерации и чтения элементов, то обход списка может быть значительно медленнее если его элементы расположены в памяти в произвольном порядке.

Расходы на разыменование указателей на следующие элементы списка незначительны по сравнению со временем на работу с элементами списка.

Answer 3

Если глянуть глубже, получиться что у вектора все элементы храняться в непрервыном участке памяти и он может поместиться в кеш. При этом сама операция обхода может быть немного быстрее у вектора, т.к. там просто сдвиг. Но если вам действительно интересно проведите тестирование на 10000000 элементах например.