Реализация шаблонного двусвязного списка указателей на объекты

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

Закрытая часть моего класса связанного списка выглядит так:

 private:
struct node {
node* next;
node* prev;
T* o;
};
node* first; // The pointer to the first node (NULL if none)
node* last;  // The pointer to the last node (NULL if none)
unsigned int size_;

Как вы можете видеть, список полон указателей на объекты, а не просто старых объектов, что делает его немного более запутанным для меня.

Ниже приведено описание в спецификации:

Обратите внимание, что, хотя этот список основан на содержании типа T, он вставляет и удаляет только указатели на T, а не экземпляры T. Это гарантирует, что реализация Dlist знает, что она владеет вставленными объектами, но она отвечает за их копирование, если список копируется, и он должен уничтожить их, если список уничтожен.

Вот моя текущая реализация insertFront (T * o):

void Dlist::insertFront(T* o) {
node* insert = new node();
insert->o = new T(*o);
insert->next = first;
insert->prev = last;
first = insert;
}

Это кажется неправильным, хотя. Что если T не имеет конструктора копирования? И как это обеспечивает единоличное владение объектом в списке?

Могу ли я просто сделать:

insert->o = o;

Кажется, что это не безопасно, потому что если у вас было:

Object* item = new Object();
dlist.insertFront(item);
delete item;

Тогда предмет будет также уничтожен для списка. Это правильно? Мое понимание где-нибудь?

Спасибо за прочтение.

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

3

Решение

Когда у вас есть контейнер указателей, у вас есть один из двух следующих сценариев использования:

  1. Указатель дается контейнеру, и контейнер берет на себя ответственность за удаление указателя при удалении содержащей его структуры.

  2. Указатель дается на контейнер, но принадлежит вызывающей стороне. Вызывающая сторона берет на себя ответственность за удаление указателя, когда он больше не нужен.

Номер 1 выше довольно прост.

В случае номера 2 ожидается, что владелец контейнера (предположительно также вызывающий) удалит элемент из контейнера перед удалением элемента.

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

Другая причина, по которой это не нужно использовать, заключается в том, что вам может потребоваться контейнер, который может принимать не указательные типы. Требуя, чтобы он был указателем, всегда используя T* вместо T может быть не так гибко, как вы хотите. Есть моменты, когда вы должны заставить его указатель, но я не могу думать о каком-либо использовании (вне головы) для этого для контейнера.

Если вы позволите пользователю объявить Dlist<MyClass*> вместо Dlist<MyClass> затем владелец этого списка неявно осознает, что он использует указатели, и это заставляет их принять сценарий № 2 сверху.

Во всяком случае, вот ваши примеры с некоторыми комментариями:


1. Не выделяйте новый T пункт, если у вас нет очень веских причин. Эта причина может быть просто инкапсуляция. Хотя я упоминал выше, что вы не должны этого делать, бывают случаи, когда вы можете захотеть. Если конструктора копирования нет, то ваш класс, вероятно, обычный-старый-data. Если копирование не тривиально, вы должны следовать Правило трех.

void Dlist::insertFront(T* o) {
node* insert = new node();
insert->o = new T(*o);         //<-- Follow rule of three
insert->next = first;
insert->prev = last;
first = insert;
}

2. Это то, что вы обычно делаете

insert->o = o;

3. Вы не должны удалять свой элемент после вставки. Либо передайте право собственности на ваш контейнер, либо удалите элемент, если он больше не требуется ни вам, ни контейнеру.

Object* item = new Object();
dlist.insertFront(item);
delete item;                     //<-- The item in the list is now invalid
4

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector