Выбор ответа Middle Производительность и кеш обновлено
vector или list для вставок
Вопрос
Почему std::vector часто быстрее std::list даже при вставках в середину коллекции из нескольких тысяч элементов?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Поиск позиции в list даёт промах кеша на каждом узле, сдвиг массива дёшев. Асимптотика вставки по готовому итератору у списка лучше, но позицию обычно ищут линейным проходом, а он у списка медленный: узлы разбросаны по куче, плюс аллокация на каждый узел.
Варианты ответа
listвставляет за O(n), аvectorза O(1) в любую позицию- Поиск позиции в list даёт промах кеша на каждом узле, сдвиг массива дёшевправильный ответ
vectorне выделяет память при вставке, аlistвыделяет на каждый узелlistкопирует все элементы при вставке, чтобы сохранить порядок узлов
Разбор
Асимптотика вставки по готовому итератору у списка лучше, но позицию обычно ищут линейным проходом, а он у списка медленный: узлы разбросаны по куче, плюс аллокация на каждый узел. У вектора поиск и сдвиг идут по непрерывной памяти через memmove, это очень быстро для тысяч элементов.
- У list вставка по итератору O(1), у vector в середину O(n), но константы решают.
- vector при росте выделяет память.
- list при вставке не копирует элементы.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.