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

Question

Я создал структуру динамического графа, в которой как узлы, так и дуги являются классами (я имею в виду, что дуги являются фактическим экземпляром в памяти, они не подразумеваются списком смежности узлов с узлами). У каждого узла есть список указателей на дуги, с которыми он связан. Каждая дуга имеет 2 указателя на 2 узла, которые она соединяет.

Удаление узла вызывает delete для каждой из его дуг. Каждое удаление дуги удаляет свой указатель из списков дуг в 2 узлах, которые он соединяет. Упрощенный:

~node()
    {
    while(arcs_list.size())
        {
        delete arcs_list[arcs_list.size()-1];
        }
    }

~arc()
    {
    node_from.remove_arc(this);
    node_to.remove_arc(this);
    }

Если я хочу начать использовать умные указатели здесь, как мне действовать? Владеет ли каждая дуга 2 узлами, или 2 узла совместно владеют отдельной дугой? Я думал о shared_ptr, но разделяемый указатель будет удалять дугу только тогда, когда оба узла удаляются. Если я удаляю только один узел, мне все равно пришлось бы явно удалить все его дуги, если бы я использовал shared_ptr. И это полностью лишает смысла не использовать необработанные указатели.

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

Есть ли какой-нибудь другой вид умного указателя, который я должен использовать, чтобы справиться с этим? Или необработанный указатель - просто простой путь?

Answer 1

Имеет ли каждая дуга 2 узла или 2 узла совместно владеют отдельной дугой?

Вы сами ответили на этот вопрос:

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

Когда объект A владеет объектом B, тогда объект A может существовать после уничтожения B, но уничтожение A подразумеваетУничтожение B. Применительно к вашему случаю два узла совместно владеют дугой.

Есть ли какой-нибудь другой вид интеллектуального указателя, который я должен использовать для обработки этого?Или же необработанный указатель - это просто простой путь?

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

1: написать свой умный указатель

Напишите класс, который может инкапсулировать необходимую логику уничтожения.Классы узлов и / или дуг будут использовать ваш новый класс вместо стандартных интеллектуальных указателей (и вместо необработанных указателей).Потратьте некоторое время, чтобы убедиться в правильности ваших дизайнерских решений.Я предполагаю, что вашему новому классу понадобится какой-то функционал / метод вызова, который скажет ему, как удалить себя из списков, в которых он находится. Или, возможно, перенести некоторые данные (например, указатели на узлы) из класса дуги в новыйкласс.

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

2: Отметить недопустимые дуги

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

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

Как бы дуга была помечена как недействительная? Наивным подходом было бы присвоить ей логический флаг.Установите флаг false в конструкторах и true, когда дугу следует считать удаленной.Эффективно, но требует нового поля.Можно ли это сделать без раздувания класса дуги?Ну, по-видимому, каждая дуга нуждается в указателях на ее узлы.Поскольку дуга не владеет своими узлами, это, вероятно, слабые указатели.Поэтому один из способов определить, что дуга недействительна, - это проверить, является ли слабый указатель expired()(Обратите внимание, что слабые указатели могут быть вручную reset(), когда дуга удаляется напрямую, а не посредством удаления узла. Поэтому слабый указатель с истекшим сроком действия не должен означать, что связанный узел исчез, только то, что дуга больше не указывает на него.)

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

3: использовать Boost.Bimap

Если вы можете использовать Boost, у них есть контейнер, который выглядит так, как будто он решит вашу проблему: Boost.Bimap . Но вы спрашиваете, разве я уже не делал скидку, используя список смежности? Да, но этот Bimap - больше, чем просто способ связать узлы друг с другом. Этот контейнер поддерживает наличие дополнительной информации , связанной с каждым отношением. То есть каждое отношение в Bimap будет представлять дугу , а будет иметь связанный объект с информацией дуги. Кажется, она хорошо подходит для вашей ситуации, и вы сможете позволить кому-то еще беспокоиться об управлении памятью (это всегда хорошо, если вы можете доверять чьим-то способностям).

Answer 2

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

struct Node;
struct Arc {
  Node *a,*b;
private:
  std::shared_ptr<Arc> skyhook{this};
public:
  void free() {skyhook.reset();}
};
struct Node {
  std::vector<std::weak_ptr<Arc>> arcs;
  ~Node() {
    for(const auto &w : arcs)
      if(const auto a=w.lock()) a->free();
  }
};

Очевидно, что другие Node операции должны проверять наличие пустых слабых указателей и, возможно, периодически очищать их.

Обратите внимание, что исключительная безопасность (включая против bad_alloc при построении shared_ptr) требует большей осторожности при построении Arc.