The question is what is the recommended way to use std::list
to achieve O(1) erasure of list items?
Usually, when I choose a doubly linked list, I want to be able to remove an element from a list in O(1) time, and then move it to a different list in O(1) time. If the element has its own prev
and next
pointers, there is no real trick to getting the job done. If the list is a doubly linked circular list, then removal doesn't necessarily require knowing the list that contains the item.
As per Iterator invalidation rules, std::list
iterators are very durable. So, it seems to me to get the behavior I desire when using std::list
on my own item is to stash an iterator within my class, and the 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 the downside that I will need to create my own decorated version of std::list
that knows to update the ref_
whenever the item is added to a list. I can't think of a way that doesn't require the embedded iterator, since not having one would mean erasure would incur a O(n) find operation first.
What is the recommended way to get O(1) erasure with std::list
? Or, is there a better approach to achieving the objective?
In the past, I have accomplished this by implementing my own list data structure, where the item placed in the list has its own next and prev pointers. Managing these pointers is natural, since they are inherent to the list operations themselves (the API to my list implementation adjusts the pointers). If I want to use the STL instead, what would be the best way to accomplish this? I offer the straw-man proposal of embedding the iterator. Are there better approaches?
If a concrete use-case is desired, consider a timer implementation. When a timer is created, it is placed into an appropriate list. If it is canceled, it is desirable to efficiently remove it. (This particular example can be solved via marking instead of removal, but it is a valid way to implement cancellation.) Additional use-cases are available upon request.
Another alternative I explored was to fuse a std::list
with a std::unordered_map
to create a specialized list for pointer types. This is more heavyweight (because of the hash table), but provides a container that is pretty close to the standard containers at the interface level, and gives me O(1) erasure of list elements. The only feature missing from the straw-man proposal is a pointer to the list which currently contains the item. I have put up the current implementation at CodeReview to solicit comment.
list::clear() is an inbuilt function in C++ STL which is declared in header file. list::clear(), clears the whole list. In other words the clear() removes all the elements present in the list container and leaves the container with size 0.
C++ String erase() This function removes the characters as specified, reducing its length by one.
Using list::erase(): The purpose of this function is to remove the elements from list. Single or multiple contiguous elements in range can be removed using this function. This function takes 2 arguments, start iterator and end iterator.
std::list::erase
is guaranteed to be O(1).
There is not an awful lot of other ways to erase elements from a standard list. (std::list::remove
and friends don't do quite the same thing so they don't count).
If you want to erase from a standard list, you need an iterator and the list itself. That's what you seem to already have. There is not very much freedom of doing it differently. I would keep the list containment separate from the objects, unlike what you have done, because why make an object that can be in only one list at a time? Seems like an unnecessary artificial restriction to me. But whatever powers your design.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With