In the case of random insert, in theory, the list should be much faster, its insert operation being in O(1) versus O(n) for a vector.
The container is filled with all the numbers in [0, N] and shuffled. Then, 1000 random values are inserted at a random position in the container. The random position is found by linear search. In both cases, the complexity of the search is O(n), the only difference comes from the insert that follow the search.
When, the vector should be slower than the list, it is almost an order of magnitude faster. Again, this is because finding the position in a list is much slower than copying a lot of small elements.
If we increase the size:
The two lines are getting closer, but vector is still faster.
Increase it to 1KB:
This time, list outperforms vector by an order of magnitude ! The performance of random insert in a list are not impacted much by the size of the data type, where vector suffers a lot when big sizes are used. We can also see that list doesn’t seem to care about the size of the collection. It is because the size of the collection only impact the search and not the insertion and as few search are performed, it does not change the results a lot.
If the iterator was already known (no need for linear search), it would be faster to insert into a list than into the vector.
In theory, random remove is the same case than random insert. Now that we’ve seen the results with random insert, we could expect the same behavior for random remove.
The container is filled with all the numbers in [0, N] and shuffled. Then, 1000 random values are removed from a random position in the container.
Again, vector is several times faster and looks to scale better. Again, this is because it is very cheap to copy small elements.
Let’s increase it directly to 1KB element.
The two lines have been reversed !
The behavior of random remove is the same as the behavior of random insert, for the same reasons.