4 ms·
> removing an item from a random location: with erase() which has a complexity of O(1) for one element This is not considering the time you need to get to that
by jeffreygoesto 3y ago
> removing an item from a random location: with erase() which has a complexity of O(1) for one element
This is not considering the time you need to get to that element before erasing, which is O(n). The most frequent fallacy about lists.
Someone had to do it, sorry.
- verall 3y agoBut std::list doesn't invalidate iterators, so in situations where you can keep a reference back to whatever item you need, it's quite nice.
- gpderetta 3y agoI haven taken advantage of O(1) removal on linked lists (although typically intrusive ones, not std::list) many times, but I'm pretty sure not once I did a linear scan specifically to find the element to be removed. Typically you save the iterator on some index on insertion.