#cpp #cpp11 #std_list #unique_ptr
Как пройти по списку, содержащему std::unique_ptr, используя следующий синтаксис:
for ( auto i : myList )
Ответ 1
Смотрите, unique_ptr не копируется (иначе уникальность указателя нарушилась бы). Поэтому вам нужно итерировать не по копиям ваших элементов массива, а по ссылкам на них. for (auto& i : myList) ...
#c++ #оптимизация #vector #std_list
На собеседовании спросили: что быстрее, обход вектора или обход списка с выводом значений в консоль? Каким образом обходим, не уточнили. Я ответил, что разницы нет. Был ли я прав? Пояснение: имеется контейнер вектор, по которому мы пробегаемся, например, итератором: std::vectorvector{1, 2, 3}; for (auto it = vector.begin(); it != vector.end(); ++it) { qDebug() << *it; } имеется контейнер список, по которому мы также пробегаемся итератором: std::list values{1, 2, 3}; for (auto it = values.begin(); it != values.end(); ++it) { qDebug() << *it; } Какой из циклов будет работать быстрее и почему? Какой из циклов будет работать быстрее при других способах обхода этих контейнеров? Этих циклов не было на собеседовании, я их добавил для наглядности. P.S. После этого вопроса затем спросили: что такое кэш? Возможно, второй вопрос как-то связан с первым? Если весь вектор или список не попадает в кэш, то время обхода контейнера увеличится?
Ответ 1
Вектор несколько быстрее - за счет двух факторов: в нем нет переходов по указателям, нет лишних разыменований в нем нет переходов по указателям - все лежит одной кучей, а значит, с высокой степенью локальности, так что высока вероятность, что все содержимое вектора разместится в кеше процессора (а если и не все из-за очень большого вектора - то большими кусками), т.е. с существенно более высокой скоростью, чем в общем случае в списке, где элементы могут быть разбросаны по всей памяти... P.S. Раз уж этот вопрос всплыл заново :) - измерим. Миллионный список и вектор. Сортировка - чтоб в списке побольше случайных переходов в разные места памяти было. listL; vector 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"; } } Полный код - здесь. Как видим, разница практически в 200 раз в пользу вектора... Так что "несколько быстрее" - это я преуменьшил :) Ответ 2
Для вопроса "обход вектора или обход списка с выводом значений в консоль" - правильный ответ это "одинаково, т.к. время обхода пренебрежимо мало по сравнению со временем записи в консоль". Что касается времени итерации и чтения элементов, то обход списка может быть значительно медленнее если его элементы расположены в памяти в произвольном порядке. Расходы на разыменование указателей на следующие элементы списка незначительны по сравнению со временем на работу с элементами списка.Ответ 3
Это коварный многослойный вопрос. Получив его, можно поумничать. С точки зрения математики ассимптотически скорость равна: O(N). Разница в обоих случаях определяется коэффициентом перед N, который зависит от скорости конкретных операций: разыменование, чтение, вывод и так далее. Константой можно пренебречь, но вообще-то она тоже есть. С точки зрения доступа к элементам с учётом аппаратуры быстрее будет вектор, потому что кэш процессора оптимизирован для доступа к последовательным блокам памяти, а не потенциально разбросанным по всей памяти небольшим элементам. С практической точки зрения доступ к консоли — несоразмеримо медленная операция относительно всех остальных, поэтому скорость будет определяться ей. Соответственно, разница между вектором и списком будет пренебрежимо мала. В качестве особенного выпендрёжа рассказываем про возможность использования кастомных аллокаторов у коллекций STL, что делает рассуждения о скорости невалидными, так как мы можем для хранения данных использовать устройство, которое не даёт преимущества последовательному доступу. Скажем, делаем маппинг памяти на файл с файловой системой без кэша... В этот момент у собеседующего пропадает желание с сами разговаривать.Ответ 4
Если глянуть глубже, получится что у вектора все элементы хранятся в непрерывном участке памяти, и он может поместиться в кэш. При этом сама операция обхода может быть немного быстрее у вектора, т.к. там просто сдвиг. Но если вам действительно интересно, проведите тестирование на 10000000 элементах, например.
Есть цикл:
for ( auto& whizbang : m_whizbangs )
{
if ( IsClush((*whizbang), (*whizbang).GetDirection(), time) )
{
(*whizbang).Hit();
m_whizbangs.remove(whizbang);
}
else
{
(*whizbang).Move(time);
}
}
Выдаёт ошибку, что итератор не увеличиваемый. У меня была такая ошибка, когда я работал с таким синтаксисом:
for (std::list
И я её исправил, тогда я удалял так:
if (...)
i = m_whizbangs.erase(i);
else
++i;
Как нужно удалять при таком синтаксисе? И можно ли как-нибудь использовать erase, а не remove, так как remove по сути ничего не удаляет, а просто заполняет конец списка мусором.
Диапазонная версия цикла for обеспечивает доступ к элементу, а не к итератору, т.е. нормальное удаление элементов в таком цикле не является возможным (можно модифицировать элемент в контейнере, но нельзя модифицировать сам контейнер). Чтобы это понимать достаточно взглянуть на то, во что по Стандарту разворачивается range-based-for
The range-based for statement
for ( for-range-declaration : for-range-initializer ) statement
is equivalent to
{
auto &&__range = for-range-initializer ;
auto __begin = begin-expr ;
auto __end = end-expr ;
for ( ; __begin != __end; ++__begin ) {
for-range-declaration = *__begin;
statement
}
}
Как пройти по списку, содержащему std::unique_ptr, используя следующий синтаксис:
for ( auto i : myList )
Смотрите, unique_ptr не копируется (иначе уникальность указателя нарушилась бы). Поэтому вам нужно итерировать не по копиям ваших элементов массива, а по ссылкам на них.
for (auto& i : myList) ...
На собеседовании спросили: что быстрее, обход вектора или обход списка с выводом значений в консоль? Каким образом обходим, не уточнили. Я ответил, что разницы нет. Был ли я прав?
Пояснение: имеется контейнер вектор, по которому мы пробегаемся, например, итератором:
std::vector
имеется контейнер список, по которому мы также пробегаемся итератором:
std::list
Какой из циклов будет работать быстрее и почему?
Какой из циклов будет работать быстрее при других способах обхода этих контейнеров?
Этих циклов не было на собеседовании, я их добавил для наглядности.
P.S. После этого вопроса затем спросили: что такое кэш? Возможно, второй вопрос как-то связан с первым? Если весь вектор или список не попадает в кэш, то время обхода контейнера увеличится?
Вектор несколько быстрее - за счет двух факторов:
в нем нет переходов по указателям, нет лишних разыменований
в нем нет переходов по указателям - все лежит одной кучей, а значит, с высокой степенью локальности, так что высока вероятность, что все содержимое вектора разместится в кеше процессора (а если и не все из-за очень большого вектора - то большими кусками), т.е. с существенно более высокой скоростью, чем в общем случае в списке, где элементы могут быть разбросаны по всей памяти...
