Реализация шаблонного двусвязного списка указателей на объекты
Я немного озадачен реализацией двусвязного списка, где данные в списке являются указателями.
Закрытая часть моего класса связанного списка выглядит так:
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-разработчик, просто освежающий мои навыки работы с указателями, выполняя старый школьный проект.
Решение
Когда у вас есть контейнер указателей, у вас есть один из двух следующих сценариев использования:
-
Указатель дается контейнеру, и контейнер берет на себя ответственность за удаление указателя при удалении содержащей его структуры.
-
Указатель дается на контейнер, но принадлежит вызывающей стороне. Вызывающая сторона берет на себя ответственность за удаление указателя, когда он больше не нужен.
Номер 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
Другие решения
Других решений пока нет …