| Операция | Асимптотическая сложность (std::list) | Примечания |
|---|---|---|
| Доступ по индексу | O(n) | Требует обхода элементов. |
| Вставка/удаление в начало | O(1) | |
| Вставка/удаление в конец | O(1) | |
| Вставка/удаление по итератору | O(1) | Если итератор действителен и указывает на место |
| Поиск элемента | O(n) | Линейный поиск. |
| Слияние | O(N+M) | Где N и M - размеры списков. |
| Разворот (reverse) | O(n) | |
| Сортировка | O(n log n) | Использует модифицированный merge sort. |
std::list - это двусвязный список.
Преимущества:
Недостатки:
std::vector из-за хранения указателей.clear).Пример вставки/удаления:
cpp