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

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
``````

### >Solution :

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.