3 ms·

Sometimes intrusive linked lists are more efficient and require less cleanup

• nly 11y ago
  With an intrusive linked list you pay the memory cost of having node pointers all the time. If you're you're going to do that, then you may as well keep all your nodes in a list all the time, and use splice() to move them around. There are practically no performance advantages to using intrusive linked-lists in this case.
  • comex 11y ago
    There is a usability advantage, though: with a STL list, you need an iterator corresponding to an element to move it between lists, not just a pointer to the value. So all functions taking a reference to an object, if they might want to move it around at some point, need to take an iterator, and in particular, object methods cannot do so, unless the class contains a wasteful iterator-to-self field. Intrusive lists also allow an object to be in multiple lists at the same time (usually ones with different purposes) by having multiple sets of prev/next pointers.
    • nly 11y ago
      Boost multi_index solves both of these problems. To simulate multiple lists you can simply add more than one sequenced index to the container type. The sequenced index interface provides an iterator_to() method which takes a reference and returns an iterator, and the container interface allows you to project one index to another. It's incredibly powerful. http://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/seq_indices.html http://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/re... As a bonus the ownership semantics are clear and memory management remains trivial. Intrusive lists are useful, i'll grant you, but they'll always be a last resort for me. Especially if you're implementing them yourself.