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

Question

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

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

Answer 1

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

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

Answer 2

Для основного Односвязного класса списка, я бы рекомендовал:

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

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

---

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

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

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

Answer 3

Если вы имели односвязанны список:

A1 -> B1 -> C1 

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

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

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

 A2 
     | 
     v 
A1 -> B1 -> C1 

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

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