Как определить циклы при использовании shared_ptr

Ответ 1

Я не нашел гораздо лучшего метода, чем рисовать большие графики UML и смотреть на циклы.

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

template <DWORD id>
class CDbgInstCount
{
public:
#ifdef _DEBUG
   CDbgInstCount()   { reghelper.Add(id, 1); }
   CDbgInstCount(CDbgInstCount const &) {  reghelper.Add(id, 1); }
   ~CDbgInstCount()  { reghelper.Add(id, -1); }
#else
#endif
};

Мне просто нужно добавить это к рассматриваемым классам и посмотреть на реестр.

(Идентификатор, если он указан, например, "XYZ!", будет преобразован в строку. К сожалению, вы не можете указать строчную константу в качестве параметра шаблона)

Ответ 2

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

Я не понимаю, почему предложение weak_ptr считается бесполезным.

Ответ 3

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

Спросите, как именно вы определяете циклические ссылки. Правда в том, что в сложном проекте некоторые ссылочные циклы косвенны и трудно распознаются.

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

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

Для владельцев использовать shared_ptr

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

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

Ответ 4

Довольно легко обнаружить циклы:

• установить количество до большого количества, скажем 1000 (точный размер зависит от вашего приложения)
• начните с интересующего вас пользователя pionter и следуйте указателям от него.
• для каждого указателя, который вы используете, уменьшите счетчик
• если счетчик падает до нуля, прежде чем вы достигнете конца цепочки указателей, у вас есть цикл

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

Ответ 5

Возможно ли сочетание boost::weak_ptr и boost::shared_ptr? Эта статья может представлять интерес.

Ответ 6

Смотрите этот пост в определении циклов на графике.

Ответ 7

Общее решение для поиска цикла можно найти здесь:

Лучший алгоритм проверки, если связанный список имеет цикл

Это предполагает, что вы знаете структуру объектов в списке и можете следовать всем указателям, содержащимся в каждом объекте.

Ответ 8

Вам, вероятно, нужна техника сбора мусора, такая как Mark and Sweep. Идея этого алгоритма:

• Сохраните список со ссылками на все выделенные блоки памяти.
• В какой-то момент вы начинаете сборщик мусора:
  • Он сначала маркирует все блоки, которые он может получить, без использования списка ссылок.
  • Он проходит через список, стирающий каждый элемент, который не может быть помечен, подразумевая, что он больше недоступен, поэтому он не является полезным.

Поскольку вы используете shared_ptr, все существующие существующие указатели, которых вы не можете достичь, должны рассматриваться как члены цикла.

Реализация

Ниже я описываю очень наивный пример того, как реализовать часть sweep() алгоритма, но он будет reset() всех остальных указателей на коллекторе.

В этом коде хранятся указатели shared_ptr<Cycle_t>. Класс Collector отвечает за отслеживание всех указателей и их удаление при выполнении sweep().

#include <vector>
#include <memory>

class Cycle_t;
typedef std::shared_ptr<Cycle_t> Ref_t;

// struct Cycle;
struct Cycle_t {
  Ref_t cycle;

  Cycle_t() {}
  Cycle_t(Ref_t cycle) : cycle(cycle) {}
};

struct collector {
  // Note this vector will grow endlessy.
  // You should find a way to reuse old links
  std::vector<std::weak_ptr<Cycle_t>> memory;

  // Allocate a shared pointer keeping
  // a weak ref on the memory vector:
  inline Ref_t add(Ref_t ref) {
    memory.emplace_back(ref);
    return ref;
  }
  inline Ref_t add(Cycle_t value) {
    Ref_t ref = std::make_shared<Cycle_t>(value);
    return add(ref);
  }
  inline Ref_t add() {
    Ref_t ref = std::make_shared<Cycle_t>();
    return add(ref);
  }

  void sweep() {
    // Run a sweep algorithm:
    for (auto& ref : memory) {
      // If the original shared_ptr still exists:
      if (auto ptr = ref.lock()) {
        // Reset each pointer contained within it:
        ptr->cycle.reset();

        // Doing this will trigger a deallocation cascade, since
        // the pointer it used to reference will now lose its
        // last reference and be deleted by the reference counting
        // system.
        //
        // The `ptr` pointer will not be deletd on the cascade
        // because we still have at least the current reference
        // to it.
      }
      // When we leave the loop `ptr` loses its last reference
      // and should be deleted.
    }
  }
};

Затем вы можете использовать его следующим образом:

Collector collector;

int main() {
  // Build your shared pointers:
  {
    // Allocate them using the collector:
    Ref_t c1 = collector.add();
    Ref_t c2 = collector.add(c1);

    // Then create the cycle:
    c1.get()->cycle = c2;

    // A normal block with no cycles:
    Ref_t c3 = collector.add();
  }

  // In another scope:
  {
    // Note: if you run sweep an you still have an existing
    // reference to one of the pointers in the collector
    // you will lose it since it will be reset().
    collector.sweep();
  }
}

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

Некоторые примечания по этой реализации:

• Вектор памяти будет расти бесконечно, вы должны использовать некоторую технику выделения памяти, чтобы убедиться, что она не занимает всю вашу рабочую память.
• Можно утверждать, что нет необходимости использовать shared_ptr (который работает как GC подсчета ссылок) для реализации такого сборщика мусора, поскольку алгоритм Mark и Sweep уже выполнил бы работу.
• Я не реализовал функцию mark(), потому что это осложнило бы этот пример, но это возможно, и я объясню это ниже.

Наконец, если вы обеспокоены (2), такого рода реализация не является неслыханной. CPython (основная реализация Python) использует смесь ссылок Count, Mark и Sweep, но главным образом для исторических причин.

Реализация функции mark():

Для реализации функции mark() вам необходимо внести некоторые изменения:

Требуется добавить атрибут bool marked; в Cycle_t и использовать его для проверки того, отмечен ли указатель или нет.

Вам нужно будет написать функцию Collector::mark(), которая будет выглядеть так:

void mark(Ref_t root) {
  root->marked = true;

  // For each other Ref_t stored on root:
  for (Ref_t& item : root) {
    mark(item);
  }
}

И тогда вы должны изменить функцию sweep(), чтобы удалить метку, если указатель отмечен, или reset() указатель:

void sweep() {
  // Run a sweep algorithm:
  for (auto& ref : memory) {
    // If it still exists:
    if (auto ptr = ref.lock()) {
      // And is marked:
      if (ptr->marked) {
        ptr->marked = false;
      } else {
        ptr->cycle.reset();
      }
    }
  }
}

Это было длинное объяснение, но я надеюсь, что это кому-то поможет.

Ответ 9

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

#include <cstdlib>
#include <iostream>

#include <boost/intrusive_ptr.hpp>

class some_resource
{
    size_t m_counter;

public:
    some_resource(void) :
        m_counter(0)
    {
        std::cout << "Resource created" << std::endl;
    }

    ~some_resource(void)
    {
        std::cout << "Resource destroyed" << std::endl;
    }

    size_t refcnt(void)
    {
        return m_counter;
    }

    void ref(void)
    {
        m_counter++;
    }

    void unref(void)
    {
        m_counter--;
    }
};

void
intrusive_ptr_add_ref(some_resource* r)
{
    r->ref();
    std::cout << "Resource referenced: " << r->refcnt()
              << std::endl;
}

void
intrusive_ptr_release(some_resource* r)
{
    r->unref();
    std::cout << "Resource unreferenced: " << r->refcnt()
              << std::endl;
    if (r->refcnt() == 0)
        delete r;
}

int main(void)
{
    boost::intrusive_ptr<some_resource> r(new some_resource);
    boost::intrusive_ptr<some_resource> r2(r);

    std::cout << "Program exiting" << std::endl;

    return EXIT_SUCCESS;
}

Здесь результат возвращается.

Resource created 
Resource referenced: 1 
Resource referenced: 2 
Program exiting 
Resource unreferenced: 1
Resource unreferenced: 0 
Resource destroyed
*** Program Exit ***

Ответ 10

Я знаю, что вы сказали "no weak_ptr", но почему бы и нет? У вас будет голова со слабым_требом до хвоста, а хвост со слабой_ptr на голову предотвратит цикл.