Как обращаться к рекурсивным структурам через указатели с использованием векторов

Question

У меня есть структуры, давайте назовем их sn, которые выглядят так:

struct sn {
    string name;
    vector<sn*> connected_to;
};

Теперь предположим, что у меня есть вектор connected_to, уже объявленный от 0 до 9;и я соединяю sn A, с sn B:

A.connected_to[0] = &B; 

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

struct sn {
    string name;
    vector<sn> connected_to;
};

// ... 

A.connected_to[0] = B; 

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

Answer 1

Ваш второй подход , вероятно, незаконен .Однако в некоторых реализациях стандартной библиотеки это может работать.В этих случаях копируемые вами объекты будут скопированы (включая все их дочерние элементы - когда копируется стандартный контейнер, копируются и все содержащиеся в нем элементы).Таким образом, такая структура данных будет подходящей только для представления дерева.

Ваш первый подход, с другой стороны, хорош, поскольку указатель на неполный тип сам по себе является допустимым типом (§3.9.2/3 - [basic.compound]) ^✝ .Поскольку вы храните только указатель, объект не будет скопирован.Вы должны быть осторожны, когда начинаете удалять этот график.В зависимости от типа графика, который вы моделируете, существует три сценария их реализации:

^{✝ _{Существуют некоторые ограничения .Обратите внимание, что в вашем случае тип является только неполным внутри определения (из sn) - в тот момент, когда вы фактически его используете, sn завершен, поэтому вы также можете удалить его.}}

Деревья

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

Чтобы реализовать это эффективно, вы можете хранить дочерние элементы в boost::ptr_vector<sn>.Таким образом, вам не придется писать деструктор самостоятельно - ptr_vector удалит все его элементы.

Направленные ациклические графы (DAG)

В DAG aузел может иметь несколько родителей, поэтому вам следует позаботиться о том, чтобы не удалять один и тот же узел дважды (это произойдет, если каждый узел просто удалит все свои дочерние узлы - по этой причине ptr_vector здесь не будет работать).Одним из способов справиться с этим является использование подсчета ссылок - каждый узел подсчитывает, сколько других узлов указывают на него, и только когда счетчик ссылок достигает нуля, узел фактически удаляется.Вы можете автоматизировать это, сохраняя узлы в std::vector<std::shared_ptr<sn> > (или boost::shared_ptr, если вы используете компилятор до C ++ 11).shared_ptr управляет внутренним подсчетом ссылок и удаляет только тот объект, на который он указывает, когда больше нет shared_ptr -инстанций, указывающих на этот объект (когда счетчик ссылок равен нулю).

Циклические графы

В циклическом графе узел также может быть своим собственным родителем (либо напрямую, если он содержит циклы, либо косвенно, через цикл).Таким образом, если каждый узел удалит все свои дочерние элементы, это приведет к бесконечному циклу вызовов деструкторов.shared_ptr также может здесь потерпеть неудачу, потому что когда у вас есть цикл shared_ptr, ссылающийся друг на друга , их счетчик ссылок никогда не достигнет нуля.Теперь пришло время подумать о разнице между владельцем объекта и ссылкой на объекта.Каждый узел должен иметь ровно одного родителя, которому он принадлежит, но может иметь несколько, ссылающихся на него.Владелец и только владелец отвечает за удаление этого узла.Как объяснено в превосходном ответе, который я связал выше, это может быть реализовано с использованием комбинации shared_ptr и weak_ptr.

Answer 2

A.connected_to[0] = &B;

Копирует ли что-то: значение временного указателя выражения &B.

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

Указатель - это очень простой тип - практически ничего не делается автоматически при использовании указателей. Под капотом это просто целое значение, соответствующее адресу в памяти. Когда вы разыменовываете указатель, компилятор просто доверяет вам, что указатель содержит адрес (или «указывает на») объекта правильного типа.

Например, для заданных классов Foo и Bar, которые не связаны наследованием:

Foo *ptr1, *ptr2;
Bar *ptr3;
  // All pointers are uninitialized. 
  // Dereferencing them is undefined behavior. Most likely a crash.
  // The compiler will almost certainly issue a warning.
ptr1= new Foo(); // ptr1 now points to a valid Foo.
ptr2 = ptr1; // ptr2 points to the same Foo.
ptr3=(Bar*)ptr1; // This is an obvious programmer error which I am making here for demonstration.
 // ptr3 points to the same block of memory as ptr1 & 2.
 // Dereferencing it is likely to do strange things.
delete ptr1; // The compiler is allowed to set ptr1 to 0, but you can't rely on it.
  // In either case dereferencing ptr1 is once again undefined behavior
  // and the value of ptr2 is unchanged.

Компилятор с гораздо меньшей вероятностью выдаст предупреждение, если увидит, что ptr1 разыменовано после удаления, чем до инициализации. Он практически никогда не выдаст предупреждение, если вы разыменуете ptr2 после удаления объекта через ptr1. Если вы не будете осторожны, как вас предупреждали другие, ваш вектор указателей может привести к непреднамеренному вызову неопределенного поведения таким образом.

Я ввел крайне неправильный приведение Foo* к Bar*, чтобы проиллюстрировать абсолютное доверие компилятора к вам. Компилятор позволяет вам сделать это и с удовольствием обработает биты, как если бы они были Bar, когда вы разыменовываете ptr3.

Стандартная библиотека C ++ предоставляет несколько шаблонных классов, которые предлагают поведение, похожее на указатель, с гораздо большей автоматической безопасностью. Например, std::shared_pointer:

std::shared_ptr - это умный указатель, который управляет временем жизни объекта, обычно выделяется с new. Несколько shared_ptr объектов могут управлять тот же объект; объект уничтожается, когда последний оставшийся shared_ptr указание на него уничтожено или сброшено. Объект уничтожено с помощью выражения удаления или предоставленного пользовательского удалителя до shared_ptr во время строительства.

Если ваша среда еще не предоставляет стандартную библиотеку c ++ 11, она может предоставить либо библиотеку boost, либо пространство имен std::tr1::. Оба обеспечивают очень похожий shared_ptr. std::auto_ptr, который вы обязательно должны иметь, аналогичен, но позволяет только одному auto_ptr ссылаться на объект в данный момент времени. _{(C ++ 11 вводит std::unique_ptr в качестве замены для auto_ptr. auto_ptr несовместим с большинством шаблонных контейнеров std. unique_ptr может быть помещен в контейнер шаблонов с std::move.)}

Можно сломать любой из этих классов, сохраняя или получая указатель и манипулируя им, например,

Foo *basic_ptr=new Foo();
std::auto_ptr<Foo> fancy_ptr(basic_ptr);
delete basic_ptr; // Oops! This statement broke our auto_ptr.

Вы также сломаете их, если передадите адрес переменной в автоматическом хранилище:

Foo aFoo;
std::auto_ptr<Foo> fancy_ptr(&aFoo); // automatic storage automatically breaks auto_ptr

Если вы просто сделаете std::shared_ptr<sn> fresh_sn(new sn()), а затем используете std::vector< std::shared_ptr<sn> >, все будет в порядке.