std::list can be used in 2 ways:
* With an std::list::iterator in each of your data nodes that represents its own position in the list (this is called the "intrusive style")
* Without an std::list::iterator in each of your data nodes
If you use the (more common) latter form: whenever you have a reference to your own object, you cannot do any of the linked list operations without an O(N) penalty to go and re-find your element in the list!
i.e: Say you have a list of requests, and a timeout callback pops up with a pointer to your request, you cannot use a request pointer to do an O(1) deletion from the list. This kind of operation is what lists are for, and std::list canonically cannot do it.
Any other operation you might want to do relating to the list, given such a pointer is impossible (e.g: create a new request that is immediately between the old request and its next).
All this assumes your object is within just one list. If it is within 2 lists, you have to use an extra indirection: std::list , which makes the problem worse. Even if you do find your request via one of the lists, there is no way to get an iterator for the other list. That means you cannot do any of the list operations on the other list. Again: This is the canonical thing lists were designed for, and std::list cannot do it.
Say that to solve this, you use the intrusive style with std::list. i.e: for every list this object is a member of, you hold an iterator inside your object.
Now the onus is on your to maintain these iterators, in addition to the common list operations. i.e: If you add an element, you need to both call std::list::add, and update the iterator.
Additionally, instead of paying with 2 pointers for each node, as an ordinary doubly-linked list should cost, you have to pay with an extra pointer or two (depending on how the iterator is implemented)!
If you use multiple lists with std::list, you pay with an extra pointer yet!
So if your data structure is within 2 doubly-linked lists, instead of paying the ideal 4 pointers per item, you pay those 4 + 1(indirection) + (2 for two iterators). 75% memory overhead, ruining your cache lines.
The code will be a mess too, due to the duplicate maintenance.
The alternative is much simpler:
http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/i...
Use the intrusive approach exclusively. So that you don't need to use a list::add in addition to maintaining the two iterators. You only maintain the "iterators" (now called "list heads").
So your request would look like:
struct request { struct list_head list1, list2; };
To add it to a list:
list_add(&request->list1, &some_list_head);
Given a request, you can delete it in O(1) from both lists:
list_del(&request->list1);
list_del(&request->list2);
Easy to use and optimal memory use (exactly 2 pointers per list head).
Now, given some pointer from list2, to get back a request, you use:
struct list_head *some_ptr = ...;
struct request *req =
containerof(some_ptr, struct request, list2);
This is slightly-boilerplatey, so I tend to write a little wrapper:
struct request *request_of_list2(struct list_head *ptr) {
return containerof(ptr, struct request, list2);
}
EDIT: almost completely forgot that std::list also uses new to dynamically allocate elements. This effectively means the cost of adding to lists is many times greater than the simple list_add function. Even if you supply your own allocator, this is unnecessarily expensive and by default means that list::add, like remove, are both not O(1) like they ought to be.