Конструктор копирования для двусвязного списка с

Обновлено: 02.05.2024

Я пытаюсь внедрить конструктор копирования в свой круговой двусвязный список, но не могу заставить его работать. Файлы копируются, но не в правильном порядке. (ПРИМЕЧАНИЕ: plate определяется как template , и я постараюсь включить только соответствующие функции)

Моя попытка конструктора копирования:

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

Проблема, похоже, в последнем из методов addAtCurrent. Вы обновляете узлы в неправильном порядке. Только для того, чтобы сделать пример с направлением «назад»: current-> prev-> next = tmp-> prev, который, в свою очередь, является current-> prev .. и поэтому элемент после current-> prev сам является current-> prev.

@NathanOliver Хорошо, я исправил свой компилятор, но не получаю никаких ошибок, за исключением максимального уровня предупреждения, когда мне говорят, что я пропускаю несколько встроенных строк, которые я уже знаю. Я разместил здесь, потому что считаю, что опытные программисты могут найти некоторые проблемы, которые не может найти компилятор. Но я сохраню ссылку.

@Henke Я ничего не говорил о компиляторе. Я сказал, используйте свой отладчик. Отладчик - это отдельный инструмент, который позволяет вам просматривать код во время его выполнения и позволяет наблюдать за тем, что происходит. Это важный инструмент / навык, которому нужно научиться, если вы хотите стать программистом.

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

Я вижу еще одну проблему в конструкторе копирования: если currentDirection имеет значение Backward, вы читаете элементы слева направо, но добавляете элементы «после» с последующей потерей порядка. Есть два решения: вы можете соблюдать порядок во время сканирования или установить для currentDirection значение FORWARD, а затем установить его на правильное значение.

чисто для себя пытаюсь написать Stack и возникла такая проблема, возможно ли как-то избавится от вектора в конструкторе и операторах присваивания? Как это правильно сделать? Ну и если не затрудни, укажите на ошибки если таковые имеются и что бы вы изменили.

Если вы посмотрите стандарт stl, std::stack, то увидите, что там можно задавать контейнер, с помощью которого будут храниться элементы стэка, и по сути std::stack это интерфейс LIFO, реализованный над подходящим контейнером. То есть в stl по дефолту стэк - это двусвязный список. И в конструкторе копирования стэк просто копирует контейнер другого стэка. То есть Вам для начала надо сделать свой двусвсязный список на шаблонах, а потом уже поверх него писать стэк. А у вас получается стэк это и стэк и односвязный список одновременно

Непонятно, как принимались решения о том, где для полей класса использовать новый синтаксис с инициализатором, а где - классическую инициализацию в конструкторе. Почему int count = 0; , но при этом Node* tail; инициализируется дальше в конструкторе. В чем тут идея?

@AnT Не внимательность. По ходу создания класса обнулил счётчик и забыл про него. Благодарю за исправление.

2 ответа 2

Избавиться от вектора никакого труда не составит. Никакого двусвязного списка для этого не нужно

В реализации вашего копирующего оператора присваивания стоило бы воспользоваться идиомой copy-and-swap, вместо того, чтобы по второму разу переписывать код конструктора копирования и деструктора

Что за ужас у вас понаписан в перемещающем операторе присваивания - вообще не понятно. Ваш перемещающий оператор присваивания по сути занимается полноценным копированием. Но зачем он такой нужен, если у вас уже есть копирующий оператор присваивания. Если уж вы взялись писать перемещающий оператор присваивания, то перемещайте, а не копируйте. Например, один из возможных вариантов реализации - просто swap

И, если самоприсваивание не является частой ситуацией в вашем коде, то оба оператора присваивания (копирующий и перемещающий) можно будет слить в один

(обратите внимание на передачу параметра по значению).

В ситуациях, допускающих перемещение ( a = std::move(b) ), такое присваивание будет выливаться в вызов конструктора перемещения (из b в stk ), за которым последует обмен внутри оператора присваивания, и деструкция stk (вместо со "старыми" данными из a ).

В ситуациях, требующих копирования ( a = b ), такое присваивание будет выливаться в вызов конструктора копирования (из b в stk ), за которым последует обмен внутри оператора присваивания, и деструкция stk (вместо со "старыми" данными из a ).

Я сейчас пытаюсь определить list(const list &cctorList); //cctor но у меня проблемы.

Вот что у меня есть на данный момент:

Все ли до этого момента правильно? Есть ли способ рекурсивно назначить another->next ? Кроме того, есть ли более простой способ сделать это с помощью итераторов?

Любая причина избегать std::list ? - sje397

1 ответы

Вы должны использовать std::list . На самом деле, вы должны использовать std::vector , потому что это быстрее для большинства практических целей (список работает быстрее только в том случае, если объекты действительно большие или очень дорогие для создания), и вам не нужен произвольный доступ.

new T(*(cctorList->info)); не компилируется, потому что cctorList ( list& ) не имеет operator-> и у него нет info либо член.

Конструктор копирования лучше всего реализуется в терминах других, более примитивных операций, таких как push_back и итерация. Итак, сначала сделайте это, а затем конструктор копирования станет:

На самом деле я бы просто шаблон этого конструктора:

(тело остается прежним). Он работает как конструктор копирования, но также позволяет копировать из любой другой коллекции любого типа, которая может быть неявно преобразована в T.

Фактические данные должны храниться ценностное . Т.е. node следует определять как

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

Редактировать: вы говорите, что хотите изучить концепции. Но самая важная концепция современного C++ — это композиция алгоритмов. Их определения часто тривиальны. Базовая реализация std::copy просто:

Теперь это, кажется, ничего не выделяет. Хитрость заключается в back_insertion_iterator . Итератор вставки - это уловка, позволяющая сделать это без предварительного выделения последовательностей. Он определяет operator* через push_back в базовой коллекции и игнорирует operator++ . Это соответствует концепции «выходного итератора», потому что он гарантирует работу только тогда, когда эти два вызова строго чередуются, и заставляет алгоритмы работать со многими вещами, от простых старых массивов до выходных потоков.

Другая часть заключается в том, что, хотя тривиальные определения верны, они не являются фактическими определениями, используемыми в библиотеке. Фактические определения в библиотеке оптимизированы. например обычно std::copy проверит, знают ли входные итераторы свое расстояние и являются ли выходные данные оператором вставки для последовательности с reserve операцию и вызовите ее, чтобы избежать некоторых распределений. Это оптимизации, которые зависят от деталей реализации стандартной библиотеки.

Вы можете пойти и записать базовые реализации вещей из стандартной библиотеки и проверить, что они работают одинаково, если хотите понять их. Но вы должны следовать тому, как стандартная библиотека определяет вещи, создавая их из простых вспомогательных битов, таких как std::copy , std::swap , адаптеры итераторов вставки и тому подобное. Если вы посмотрите в стандартной библиотеке, большинство функций там однострочные!

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

Связанный список состоит из структур, называемых Elems:

info - это отдельный настраиваемый класс, который хранится в элементе Elem.

подпись для конструктора копирования:

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

Установить голову на v.head (head = v.head)
Установите значения Elem на v (pri = v.pri, info = v.info, next = v.next)
Выполните итерации, повторяя шаг 2.

Спасибо за ваше время

Всем спасибо за уделенное время!

Думаю, я разобрался:

Я почти уверен, что это работает. Я нарисовал несколько логичных картинок, чтобы помочь, и не столкнулся с какими-либо проблемами.

Что именно должен делать конструктор копирования? Создание копии каждого узла с соответствующими ссылками звучит разумно, но это не единственная возможность. - David Thornley

Спасибо за правильный намек! Я реализовал конструктор глубокой копии для своих узлов, чтобы иметь возможность возвращать объект «последнего» узла со ссылочной структурой для родительского узла и его родительского узла . чтобы оставаться в тактике. Использовал его для алгоритмов поиска по дереву - mtosch

5 ответы

Вы должны быть осторожны с Шагом 1 и частью Шага 2. Шаг 1 должен выделить новый узел и использовать его как head . На шаге 2 часть о next = v.next , если вы не собираетесь делать неглубокую копию, неверно.

Когда вы копируете контейнер, такой как связанный список, вам, вероятно, понадобится глубокая копия, поэтому необходимо создавать новые узлы и копировать только данные. В next и prior указатели в узлах нового списка должны ссылаться на новые узлы, которые вы создаете конкретно для этого списка, а не узлов из исходного списка. Эти новые узлы будут иметь копии соответствующих данных из исходного списка, так что новый список может считаться по значению или глубокой копией.

Вот изображение, показывающее разницу между мелким и глубоким копированием:

Обратите внимание, как в Глубокая копия части диаграммы, ни один из узлов не указывает на узлы в старом списке. Дополнительные сведения о разнице между мелкими и глубокими копиями см. В статье Википедии о копирование объекта.

Ой! Фотографий! Это определенно поможет прояснить ситуацию. +1 - Мычание утки

Вы не должны устанавливать this->head = v.head . Потому что голова - это просто указатель. Что вам нужно сделать, так это создать новую голову и скопировать значения по отдельности из v.head в твою новую голову. В противном случае у вас были бы два указателя, указывающие на одно и то же.

Затем вам нужно будет создать временный Elem указатель, который начинается с v.head и перебираем список, копируя его значения в новый Elem указатели на новую копию.

ответ дан 18 окт '11, 19:10

Примечание. Когда вы копируете его значения, сделайте не скопируйте его указатель. В общем, никогда не копируйте указатель в конструкторе копирования. Скопируйте объект, на который указывает. - Мычание утки

Что должен копировать ваш конструктор копирования? Он должен копировать pri - легкий. Он должен копировать info - тоже легко. И если next не равно нулю, он тоже должен его скопировать. Как можно копировать next ? Думайте рекурсивно: ну, next есть Elem * и Elem имеет конструктор копирования: просто используйте его, чтобы скопировать указанный Elem и обратитесь к нему.

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

Мне трудно обойти указатели. Я могу представить, что кто-то здесь может сделать концептуализацию конструктора копирования более интуитивной. Я понимаю, что вы не можете просто назначать указатели друг другу (неглубокая копия), но мне трудно копировать объекты.

Вот образец моего кода:

Спасибо за помощь!

3 ответа

Когда вы пишете конструктор копирования X(const T& other) для объекта X , который содержит динамически выделяемый T* p (возможно, Node* в вашем случае), вы, скорее всего, в конечном итоге напишите такую строку:

Это создает копию объекта, на который указывает копируемый объект, давая вам глубокую копию этого объекта. В вашем случае это закончится рекурсивным глубоким копированием списка.

Создание полной копии связанного списка эквивалентно созданию нового связанного списка с теми же значениями данных.

Просмотрите свой текущий список
Извлечение информации из каждого узла
Передайте его новому узлу (по сути копируя все, кроме указателей списка)
Добавьте это в новый список (который является глубокой копией).

В вашем случае вам нужно соблюдать o, извлечь данные, выделить новый блок, назначить данные, а затем добавить их в новый узел.

Не проверено, но это может частично отражать вашу идею. Я бы попытался использовать вместо этого std::list :) Вы должны добавить оператор присваивания копии и деструктор, который также выделяет / освобождает должным образом . См. здесь.

Если ваш value является указателем, вы захотите скопировать его таким же образом, как элемент указателя next копируется выше, то есть:

Итак, для приведенного выше списка примеров вы можете попробовать что-то вроде этого:

Непроверено, но это идея . конструкторы работают рекурсивно, работая со следующим элементом. Пункты «TODO» важны, как объясняется по ссылке. Вы также можете изучить интеллектуальные указатели - они устраняют необходимость помнить об удалении, повышают безопасность исключений и, как правило, являются гораздо более безопасным вариантом, чем необработанные указатели.

Читайте также: