I 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 line

I 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.