Item in multiple lists

Question

So I have some legacy code which I would love to use more modern techniques. But I fear that given the way that things are designed, it is a non-option. The core issue is that often a node is in more than one list at a time. Something like this:

struct T {
    T *next_1;
    T *prev_1;
    T *next_2;
    T *prev_2;
    int value;
};

this allows the core have a single object of type T be allocated and inserted into 2 doubly linked lists, nice and efficient.

Obviously I could just have 2 std::list<T*>'s and just insert the object into both...but there is one thing which would be way less efficient...removal.

Often the code needs to "destroy" an object of type T and this includes removing the element from all lists. This is nice because given a T* the code can remove that object from all lists it exists in. With something like a std::list I would need to search for the object to get an iterator, then remove that (I can't just pass around an iterator because it is in several lists).

Is there a nice c++-ish solution to this, or is the manually rolled way the best way? I have a feeling the manually rolled way is the answer, but I figured I'd ask.

Answer 1

I think the proper answer depends on how performance-critical this application is. Is it in an inner loop that could potentially cost the program a user-perceivable runtime difference?

There is a way to create this sort of functionality by creating your own classes derived from some of the STL containers, but it might not even be worth it to you. At the risk of sounding tiresome, I think this might be an example of premature optimization.

Answer 2

It sounds like you're talking about something that could be addressed by applying graph theory. As such the Boost Graph Library might offer some solutions.

Answer 3

Instead of managing your own next/previous pointers, you could indeed use an std::list. To solve the performance of remove problem, you could store an iterator to the object itself (one member for each std::list the element can be stored in).

You can extend this to store a vector or array of iterators in the class (in case you don't know the number of lists the element is stored in).

Answer 4

list::remove is what you're after. It'll remove any and all objects in the list with the same value as what you passed into it.

So:

list<T> listOne, listTwo;
// Things get added to the lists.
T thingToRemove;
listOne.remove(thingToRemove);
listTwo.remove(thingToRemove);

I'd also suggest converting your list node into a class; that way C++ will take care of memory for you.

class MyThing {
  public:
  int value;
  // Any other values associated with T
};

list<MyClass> listOne, listTwo; // can add and remove MyClass objects w/o worrying about destroying anything.

You might even encapsulate the two lists into their own class, with add/remove methods for them. Then you only have to call one method when you want to remove an object.

class TwoLists {
  private:
  list<MyClass> listOne, listTwo;

  // ...

  public:
  void remove(const MyClass& thing) {
    listOne.remove(thing);
    listTwo.remove(thing);
  }
};

Answer 5

The question to answer is why this C struct exists in the first place. You can't re-implement the functionality in C++ until you know what that functionality is. Some questions to help you answer that are,

1. Why lists? Does the data need to be in sequence, i.e., in order? Does the order mean something? Does the application require ordered traversal?
2. Why two containers? Does membership in the container indicated some kind of property of the element?
3. Why a double-linked list specifically? Is O(1) insertion and deletion important? Is reverse-iteration important?

The answer to some or all of these may be, "no real reason, that's just how they implemented it". If so, you can replace that intrusive C-pointer mess with a non-intrusive C++ container solution, possibly containing shared_ptrs rather than ptrs.

What I'm getting at is, you may not need to re-implement anything. You may be able to discard the entire business, and store the values in proper C++ containers.

Answer 6

How's this?

struct T {
    std::list<T*>::iterator entry1, entry2;
    int value;
};
std::list<T*> list1, list2;

 // init a T* item:
 item = new T;
 item->entry1 = list1.end();
 item->entry2 = list2.end();

 // add a T* item to list 1:
 item->entry1 = list1.insert(<where>, item);

 // remove a T* item from list1
 if (item->entry1 != list1.end()) {
      list1.remove(item->entry1); // this is O(1)
      item->entry1 = list1.end();
 }

 // code for list2 management is similar

You could make T a class and use constructors and member functions to do most of this for you. If you have variable numbers of lists, you can use a list of iterators std::vector<std::list<T>::iterator> to track the item's position in each list.

Note that if you use push_back or push_front to add to the list, you need to do item->entry1 = list1.end(); item->entry1--; or item->entry1 = list1.begin(); respectively to get the iterator pointed in the right place.

Answer 7

As another possible solution, look at Boost Intrusive, which has an alternate list class a lot of properties that may make it useful for your problem.

In this case, I think it'd look something like this:

using namespace boost::intrusive;

struct tag1; struct tag2;

typedef list_base_hook< tag<tag1> > base1;
typedef list_base_hook< tag<tag2> > base2;

class T: public base1, public base2
{
    int value;
}

list<T, base_hook<base1> > list1;
list<T, base_hook<base2> > list2;

// constant time to get iterator of a T item:
where_in_list1 = list1.iterator_to(item);
where_in_list2 = list2.iterator_to(item);

// once you have iterators, you can remove in contant time, etc, etc.