Why removing random element from vector and list costs almost the same time?

Question

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

Because for a list the erasure is fast, but finding the i-th element has linar runtime. So for the list the most time should be spend in the next function — gerum, May 04 '22 at 08:12
Nitpicking: Your program isn't a valid C++ program, because [C++ doesn't have variable-length arrays](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). You don't even need the array `arr`, you can insert directly into the vector and list at initialization (e.g. `std::vector vec(N); std::iota(begin(vec), end(vec), 0);`) — Some programmer dude, May 04 '22 at 08:13
For lists, finding element is the slow operation and removing is fast. For vectors, removing element is the slow opration and finding it is fast. — Yksisarvinen, May 04 '22 at 08:13
Also, do you remember to build with optimizations enabled? Benchmarking unoptimized builds is pointless. — Some programmer dude, May 04 '22 at 08:16
Interesting that Apple's Objective-C and Swift have never had lists. They have arrays (in Objective-C with fast insert/remove at both start and end of the array), they have dictionaries (key / value) and they have sets. No lists at all. — gnasher729, May 04 '22 at 08:17
On my last note, you seem to think that performance and complexity are intimately related, which they aren't. An O(1) operation have small complexity but can take a long time, while an O(n) operation have linear complexity by might be very quick. — Some programmer dude, May 04 '22 at 08:19
@Someprogrammerdude: Just a note: On fixing the timing error, compiling normally vs. with `-O3` changes the timings a bit, but not enough to change conclusions. The real issue was the broken timing starboy_jb mentioned; `vector` was reporting the total time taken for *both* sets of tests. With fixed timing, and full optimizations on, `list` took nearly 10 seconds on the TIO runner, `vector` took ~0.2. — ShadowRanger, May 04 '22 at 08:27
Thanks to @starboy_jb and @ShawdowRanger, I forget reseting `start`(stupid issues). — zhixin, May 04 '22 at 08:36
*"Lists are sequence containers that allow constant time insert and erase"* Constant only means that it always takes about the same time, not that it has to be fast. For example, `O(1) = 1 minute` is more than `O(n) = 50 seconds`. — BoP, May 04 '22 at 08:46
@BoP: In fairness, it really is cheap *if* you're running an algorithm where you'd regularly hold iterators for the points you need to remove. Especially if you need to rearrange things, and the objects in question are expensive to copy/move (because `list` can avoid doing either after the elements are in the `list`). Regardless, that observation on timings is kind of facetious, because whatever that particular `n` happens to be, doubling it would double the time for the algorithm, while the `O(1)` algorithm would stay steady. If `O(1)` is fast enough, and your inputs can grow, it's safer. — ShadowRanger, May 04 '22 at 09:00
The problem here is not `O(1)` with high fixed overhead vs. `O(n)` with low fixed overhead, it's two different `O(n)` algorithms (one with much higher practical cost per item) where one of them was mistakenly thought to be `O(1)`. — ShadowRanger, May 04 '22 at 09:02

ShadowRanger · Accepted Answer · 2022-05-04T08:24:26.690

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.

Why removing random element from vector and list costs almost the same time?

1 Answers1