As cppreference says

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

Considering the continuous memory used by std::vector where erase should be linear time. So it is reasonable that random erase operations on std::list should be more efficient than std::vector.

But I the program shows differently.

int randi(int min, int max) {
    return rand()%(max-min) min; // Generate the number, assign to variable.
}

int main() {
    srand(time(NULL)); // Seed the time

    int N = 100000;
    int M = N-2;
    int arr[N];
    for (int i = 0; i < N; i  ) {
        arr[i] = i;
    }
    list<int> ls(arr, arr N);
    vector<int> vec(arr, arr N);

    std::chrono::time_point<std::chrono::system_clock> start, end;
  
    start = std::chrono::system_clock::now();
    for (int i = 0; i < M; i  ) {
        int j = randi(0, N - i);
        ls.erase(next(ls.begin(), j));
    }
    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds_1 = end - start;
    cout << "list time cost: " << elapsed_seconds_1.count()) << "\n";

    for (int i = 0; i < M; i  ) {
        int j = randi(0, N - i);
        vec.erase(vec.begin()   j);
    }
    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds_2 = end - start;
    cout << "vector time cost: " << elapsed_seconds_2.count()) << "\n";

    return 0;
}

~/cpp_learning/list$ ./demo
list time cost: 8.114993171
vector time cost: 8.306458676

CodePudding user response：

Because it takes a long time to find the element in the list. Insertion or removal from list is O(1) if you already hold an iterator to the desired insertion/deletion location. In this case you don't, and the std::next(ls.begin(), j) call is doing O(n) work, eliminating all savings from the cheap O(1) erase (frankly, I'm a little surprised it didn't lose to vector; I'd expect O(n) pointer-chasing operations to cost more than a O(n) contiguous memmove-like operation, but what do I know?) Update: On checking, you forgot to save a new start point before the vector test, and in fact, once you fix that issue, the vector is much faster, so my intuition was correct there: Try it online!

With -std=c 17 -O3, output was:

list time cost: 9.63976
vector time cost: 0.191249

Similarly, the vector is cheap to get to the relevant index (O(1)), but (relatively) expensive to delete it (O(n) copy-down operation after).

When you won't be iterating it otherwise, list won't save you anything if you're performing random access insertions and deletions. Situations like that call for using std::unordered_map and related containers.