Частные случаи могут зависеть от реализации, но для стандартных контейнеров сложность операций выглядит следующим образом:
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 обеспечивает эффективную вставку/удаление в любой позиции (при наличии итератора), но доступ по индексу дорог. Он является двусвязным списком.Пример использования:
cpp