Связанный список и конструктор копирования - PullRequest
Новая
       28

Связанный список и конструктор копирования

0 голосов
/ 01 октября 2009

Я пытаюсь написать простой, односвязный класс списка в C ++. Я делал это в своем классе структур данных несколько лет назад, но я не могу вспомнить детали.

Должен ли мой класс Node иметь конструктор копирования? Он имеет Node * в качестве переменной-члена, и, насколько я знаю, вы всегда должны писать конструктор копирования, деструктор и оператор присваивания для классов, которые имеют динамические члены. Но из того, что я видел в сети, класс List заботится о копировании узлов. Действительно ли это так, и если да, то почему?

Ответы [ 3 ]

3 голосов
/ 01 октября 2009

Для basic класса односвязных списков я бы порекомендовал:

  • После того, как вы выделите каждый узел, не перемещайте и не копируйте узел после того, как он выделен
  • Поэтому отключите конструктор копирования класса Node и оператор присваивания

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

Но из того, что я видел в сети, класс List заботится о копировании узлов. Действительно ли это так, и если да, то почему?

Он заботится о копировании узлов, поскольку поддерживает копирование (создание копии) всего списка (что означает создание копии каждого узла в списке).

Вам не нужно поддерживать копирование узлов, если вы не поддерживаете копирование всего списка.

1 голос
/ 01 октября 2009

Вы могли бы сделать хуже, чем скопировать дизайн sgi's slist - библиотека шаблонов sgi ("stl") была основой для части стандартной библиотеки C ++, которая часто до сих пор (не технически правильно; - ) упоминается как "STL". К сожалению, slist не сделал этого (его двоюродный брат list OTOH сделал это и стал std::list), но мне это нравится.

Если вы не хотите задавать шаблон типа полезной нагрузки и распределителя, я думаю, это хорошо, если жестко закодировать их; но ключевым моментом, который следует сохранить, является то, что «узлы» являются внутренней деталью реализации - вы раскрываете только тип container со всеми приятными, каноническими аспектами (и, конечно, тип полезной нагрузки должен быть известен - это не сложно шаблонировать, кстати ;-), и вы делаете «нод» непрозрачным классом в вашем .h (который просто содержит class node;, и указатели на него в вашем class slist) .

0 голосов
/ 01 октября 2009

Если у вас был односвязный список: 

A1 -> B1 -> C1

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

A1 -> B1 -> C1
A2 -> B2 -> C2

Что вы не должны делать, это вызывать неявно сгенерированный конструктор копирования, который не будет выполнять каскадное копирование, то что вы получите: 

      A2
      |
      v
A1 -> B1 -> C1

Так что либо напишите свой собственный конструктор копирования, чтобы сделать глубокое копирование, либо определите частный конструктор копирования, который реализует запрет операции.

Кстати, std :: list реализует двусвязный список и реализует семантику глубокого копирования.

...