Easyконтейнеры
Чем vector отличается от list и когда что выбирать?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
vector — динамический массив с непрерывной памятью: O(1) доступ по индексу, отличная cache locality. list — двусвязный: O(1) вставка/удаление в любой позиции (есть итератор), но O(n) доступ и плохая cache locality.
std::vector<int> v; // массив, push_back O(1) amortized
std::list<int> l; // узлы, l.insert(it, x) O(1)
// Вставка в середину: vector копирует элементы, list перекомпоновывает указатели- На практике vector почти всегда выигрывает благодаря кэшу, даже для вставок в середину;
- list выбирать при частых вставках/удалениях в середине большого контейнера, при нужде в стабильных итераторах, или для очень больших дорогих элементов;
- По умолчанию — vector, list — редкое исключение.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.