Назад к вопросам
Middle
277
questionbank
Какова сложность операций для контейнеров std::vector и std::list в C++?
Sobes Copilot
Получайте ответы в реальном времени
Ответ от нейросети
sobes.tech AI
Частные случаи могут зависеть от реализации, но для стандартных контейнеров сложность операций выглядит следующим образом:
std::vector
| Операция | Средняя сложность | Худшая сложность | Примечание |
|---|---|---|---|
| Доступ по индексу | O(1) | O(1) | operator[], at() |
| Вставка в конец | O(1) амортизированная | O(N) | push_back() (при необходимости перераспределения) |
| Вставка в произвольное место | O(N) | O(N) | |
| Удаление с конца | O(1) | O(1) | pop_back() |
| Удаление из произвольного места | O(N) | O(N) | |
| Поиск элемента | O(N) | O(N) | std::find (независимо от контейнера) |
| Изменение размера | O(N) | O(N) | resize(), reserve() (при увеличении емкости) |
std::list
| Операция | Средняя сложность | Худшая сложность | Примечание |
|---|---|---|---|
| Доступ по индексу | O(N) | O(N) | Требует итерации от начала или конца к нужному элементу |
| Вставка в конец | O(1) | O(1) | |
| Вставка в произвольное место | O(1) | O(1) | При наличии итератора на место вставки |
| Удаление с конца | O(1) | O(1) | |
| Удаление из произвольного места | O(1) | O(1) | При наличии итератора на удаляемый элемент |
| Поиск элемента | O(N) | O(N) | std::find (независимо от контейнера) |
Основные отличия:
std::vectorобеспечивает эффективный доступ по индексу и к последнему элементу, но вставка/удаление в середине требуют перемещения элементов.std::listобеспечивает эффективную вставку/удаление в любой позиции (при наличии итератора), но доступ по индексу дорог. Он является двусвязным списком.
Пример использования:
#include <vector>
#include <list>
#include <numeric> // Для std::iota
// Пример для std::vector
std::vector<int> vec(1000);
std::iota(vec.begin(), vec.end(), 0); // Заполнение вектора
int value = vec[500]; // O(1) доступ по индексу
vec.push_back(1000); // O(1) амортизированная вставка в конец
vec.insert(vec.begin() + 100, 5000); // O(N) вставка в середину
// Пример для std::list
std::list<int> lst(1000);
std::iota(lst.begin(), lst.end(), 0); // Заполнение списка
auto it = lst.begin();
std::advance(it, 500); // O(N) поиск элемента
int value_list = *it;
lst.push_back(1000); // O(1) вставка в конец
lst.insert(it, 5000); // O(1) вставка в середину (при наличии итератора)