Какая асимптотическая сложность удаления в list?

Какая асимптотическая сложность удаления в list?

Асимптотическая сложность удаления в std::list зависит от того, уже ли у вас есть итератор на элемент, который нужно удалить. Это важное различие, которое часто упускается.

Если у вас уже есть итератор на элемент

Сложность: O(1) — константная

Это главное преимущество std::list. Если вы знаете позицию элемента (имеете валидный итератор), удаление выполняется за одну операцию:

std::list<int> lst = {1, 2, 3, 4, 5};

// Получили итератор (O(1) или O(n), зависит от метода получения)
auto it = lst.begin();
std::advance(it, 2);  // итератор на элемент 3

// Удаление: O(1)
lst.erase(it);  // Результат: {1, 2, 4, 5}

Механизм удаления элемента с известным итератором:

// Концептуально это выглядит так:
template<typename T>
class list {
public:
    iterator erase(iterator pos) {
        // 1. Обновляем указатели соседних узлов
        pos->prev->next = pos->next;
        pos->next->prev = pos->prev;
        
        // 2. Удаляем узел
        delete pos.node;
        
        // 3. Возвращаем следующий элемент (O(1))
        return iterator(pos->next);
    }
};

Если нужно найти элемент по значению

Сложность: O(n) — линейная

std::list<int> lst = {1, 2, 3, 4, 5};

// Поиск элемента: O(n)
auto it = std::find(lst.begin(), lst.end(), 3);

// Удаление: O(1)
if (it != lst.end()) {
    lst.erase(it);  // Общая сложность: O(n)
}

Или используя метод remove-erase:

// Удаление всех элементов со значением 3: O(n)
lst.remove(3);

// Или с предикатом
lst.remove_if([](int x) { return x % 2 == 0; });  // O(n)

Сравнение с другими контейнерами

Почему std::list быстро удаляет с итератором?

std::list — это двусвязный список (doubly-linked list). Каждый узел содержит:

template<typename T>
struct Node {
    T data;
    Node* next;
    Node* prev;
};

template<typename T>
class list {
private:
    Node<T>* head;
    Node<T>* tail;
    size_t size;
};

При удалении узла с известным адресом нужно просто обновить два указателя соседних узлов:

// Удаляем узел X
// Было: A ↔ X ↔ B
// Стало: A ↔ B

prev_node->next = next_node;
next_node->prev = prev_node;

Практические примеры

Хороший паттерн (O(1) удаление):

std::list<int> lst = {1, 2, 3, 4, 5};

// Итерируем и удаляем элементы, удовлетворяющие условию
for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it % 2 == 0) {
        it = lst.erase(it);  // O(1) удаление, итератор обновляется
    } else {
        ++it;
    }
}

Плохой паттерн (O(n²) сложность):

std::list<int> lst = {1, 2, 3, 4, 5};

// Поиск каждого элемента — O(n), умножается на количество удалений
for (int val : {2, 4}) {
    auto it = std::find(lst.begin(), lst.end(), val);  // O(n)
    if (it != lst.end()) {
        lst.erase(it);  // O(1)
    }
}
// Общая сложность: O(n²)

Когда использовать std::list

• Часто удаляешь/вставляешь в середину — std::list (O(1) если есть итератор)
• Часто обращаешься по индексу — std::vector
• Частые поиски и удаления — std::map/std::unordered_map