Mediumvectorlistcache
Почему std::vector обычно быстрее std::list?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::vector — непрерывная память, std::list — узлы с указателями prev/next. Vector выигрывает из-за cache locality, prefetching-а и отсутствия overhead на узлы (по 16 байт на x64).
std::vector<int> v; // один блок, обход грузит cache lines подряд
std::list<int> l; // N allocations, каждый узел — отдельный miss- cache locality — list гоняет по разрозненным allocations;
- меньше overhead — в узле list-а 2 указателя сверх данных;
- один malloc vs N маленьких (heap fragmentation);
- prefetcher угадывает следующую line для vector, для list — не может.
List выигрывает только O(1) insert/erase в middle (редкость), и то без учёта cache miss. Stroustrup показывал, что vector побеждает list вплоть до ~100000 элементов. Вывод: предпочитать vector.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.