c++ - How to achieve O(1) erasure from a std::list -

the question recommended way use std::list achieve o(1) erasure of list items?

usually, when choose doubly linked list, want able remove element list in o(1) time, , move different list in o(1) time. if element has own prev , next pointers, there no real trick getting job done. if list doubly linked circular list, removal doesn't require knowing list contains item.

as per iterator invalidation rules, std::list iterators durable. so, seems me behavior desire when using std::list on own item stash iterator within class, , containing list.

class item {     typedef std::shared_ptr<item> ptr;     struct ref {         std::list<ptr>::iterator iter_;         std::list<ptr> *list_;     };     ref ref_;     //... }; 

this has downside need create own decorated version of std::list knows update ref_ whenever item added list. can't think of way doesn't require embedded iterator, since not having 1 mean erasure incur o(n) find operation first.

what recommended way o(1) erasure std::list? or, there better approach achieving objective?

---

in past, have accomplished implementing own list data structure, item placed in list has own next , prev pointers. managing these pointers natural, since inherent list operations (the api list implementation adjusts pointers). if want use stl instead, best way accomplish this? offer straw-man proposal of embedding iterator. there better approaches?

if concrete use-case desired, consider timer implementation. when timer created, placed appropriate list. if canceled, desirable efficiently remove it. (this particular example can solved via marking instead of removal, valid way implement cancellation.) additional use-cases available upon request.

---

another alternative explored fuse std::list std::unordered_map create specialized list pointer types. more heavyweight (because of hash table), provides container pretty close standard containers @ interface level, , gives me o(1) erasure of list elements. feature missing straw-man proposal pointer list contains item. have put current implementation @ codereview solicit comment.

std::list::erase guaranteed o(1).

there not awful lot of other ways erase elements standard list. (std::list::remove , friends don't quite same thing don't count).

if want erase standard list, need iterator , list itself. that's seem have. there not freedom of doing differently. keep list containment separate objects, unlike have done, because why make object can in 1 list @ time? seems unnecessary artificial restriction me. whatever powers design.