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

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

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

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


c++ templates pointers doubly-linked-list
person Slims    schedule 23.11.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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

Номер 1 выше довольно прямолинеен.

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

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

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

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

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

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

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
person paddy    schedule 23.11.2012
comment
В (3), когда вы говорите «передать право собственности вашему контейнеру», вы имеете в виду просто установку item = null? - person Slims; 23.11.2012
comment
Я имею в виду, просто не удаляйте это. Вы можете установить его в NULL, если хотите, но это просто указатель (т.е. число), хранящийся в переменной. Под «передачей владения» я подразумеваю ТОЛЬКО если ваш контейнер определен с семантикой владения: т.е. он всегда будет удалять содержащиеся указатели по завершении. В этом случае вызывающей стороне никогда не нужно удалять или запоминать указатель - все это делает контейнер. Обычно я предпочитаю указывать тип указателя в моем шаблоне (а не неявный тип указателя), потому что никогда не может быть путаницы в отношении того, владеет ли контейнер указателями. - person paddy; 23.11.2012
comment
Прохладный. Спасибо, падди, все это было очень полезно. - person Slims; 23.11.2012
comment
Эээ .. Извините, если это сбивает с толку. Нет никакой физической разницы между тем, чтобы позволить контейнеру владеть вашим указателем или самому владеть им. Это концептуальная разница. Вы можете хранить значение указателя в любом количестве мест, но его следует удалять только один раз и никогда не следует использовать после удаления. - person paddy; 23.11.2012