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

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 , в котором имеется альтернативный класс списка , множество свойств, которые могут сделать его полезным для вашей проблемы.

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

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

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

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

Answer 3

Как это?

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(); соответственно, чтобы итератор указывал в нужном месте.

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

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 7

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