Какова сложность удаления элемента из начала вектора (vector) в C++?

O(n), где n — количество элементов в векторе после удаляемого. Удаление элемента из начала вызывает сдвиг всех последующих элементов на одну позицию влево для заполнения освободившегося места.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Удаление первого элемента
    if (!vec.empty()) {
        vec.erase(vec.begin()); // O(n) операция
    }

    // После удаления: {2, 3, 4, 5}

    return 0;
}