Элемент в нескольких списках

Question

Итак, у меня есть код устаревшего кода, который я хотел бы использовать более современные методы. Но я боюсь, что с учетом того, что все разработано, это не вариант. Основная проблема заключается в том, что часто узел имеет более одного списка за раз. Что-то вроде этого:

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

это позволяет ядро ​​имеет один объект типа T быть выделены и вставлены в 2 дважды связанных списков, красиво и эффективно.

Очевидно, что я мог бы просто иметь 2 std::list<T*> и просто вставлять объект в оба ... но есть одна вещь, которая была бы менее эффективной ... удаление.

Часто код должен «уничтожать» объект типа T, и это включает удаление элемента из всех списков. Это хорошо, потому что с учетом T* код может удалить этот объект из всех его списков. С чем-то вроде std::list мне нужно было бы искать объект для получения итератора, а затем удалить его (я не могу просто пройти мимо итератор, потому что он находится в нескольких списках).

Есть ли хорошее решение C++ - ish для этого, или это способ ручного проката наилучшим образом? У меня такое чувство, что это ответ вручную, но я решил, что спрошу.

Answer 1

В качестве еще одного возможного решения см. Boost Intrusive, в котором есть an alternate list class много свойств, которые могут помочь вам в решении этой проблемы.

В этом случае, я думаю, было бы выглядеть примерно так:

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. 

Answer 2

Я думаю, что правильный ответ зависит от того, насколько критично это приложение. Является ли это во внутреннем цикле, который потенциально может стоить программе разницу во времени выполнения пользователя?

Существует способ создания такого рода функциональных возможностей, создавая собственные классы, полученные из некоторых контейнеров STL, но он может даже не стоить того. С риском утомительного, я думаю, что это может быть примером преждевременной оптимизации.

Answer 3

Похоже, вы говорите о чем-то, к чему можно обратиться, применяя теорию графов. Таким образом, библиотека Boost Graph может предлагать некоторые решения.

Answer 4

Вместо того, чтобы управлять своими следующими/предыдущими указателями, вы действительно можете использовать std :: list. Чтобы решить проблему с удалением, вы можете сохранить итератор самому объекту (один член для каждого std :: list, который может быть сохранен в элементе).

Вы можете расширить это, чтобы хранить вектор или массив итераторов в классе (если вы не знаете количество списков, в котором хранится элемент).

Answer 5

list::remove - это то, что вам нужно. Он удалит все и все объекты в списке с тем же значением, что и вы в него.

Итак:

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

Я также предлагаю преобразовать список вашего узла в классе; таким образом C++ позаботится о вашей памяти.

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. 

Вы можете даже инкапсулировать эти два списка в свой класс с помощью методов добавления/удаления. Затем вам нужно только вызвать один метод, когда вы хотите удалить объект.

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

    // ... 

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

Answer 6

Вопрос в том, почему эта структура C существует в первую очередь. Вы не можете повторно реализовать функциональность на C++, пока не узнаете, что это за функциональность.Некоторые вопросы, которые помогут вам ответить, являются:

1. Почему списки? Должны ли данные быть в последовательности, то есть в порядке? Означает ли заказ что-то? Требуется ли приложение для заказа?
2. Почему контейнеры? Имеет ли членство в контейнере какое-либо свойство элемента?
3. Почему a двойной -связанный список конкретно? Важна ли вставка и удаление O (1)? Важное значение имеет обратная итерация?

Ответ на некоторые или все из этих вопросов может быть «без реальной причины, именно так они реализовали его». Если это так, вы можете заменить этот интрузивный беспорядок C-указателем на неинтрузивное контейнерное решение C++, возможно, содержащее shared_ptrs, а не ptrs.

То, что я получаю, может не понадобиться для повторного внедрения. Вы можете отказаться от всего бизнеса и сохранить значения в соответствующих контейнерах C++.

Answer 7

Как это?

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 

Вы можете сделать класс T и использовать конструкторы и функции-члены, чтобы сделать большую часть этого для вас. Если у вас есть переменное количество списков, вы можете использовать список итераторов std::vector<std::list<T>::iterator> для отслеживания позиции позиции в каждом списке.

Обратите внимание, что если вы используете push_back или push_front добавить в список, что вам нужно сделать item->entry1 = list1.end(); item->entry1--; или item->entry1 = list1.begin(); соответственно, чтобы получить итератор в правильном месте.