Как избежать переполнения стека деструктора с глубоко вложенной структурой данных в C ++? - PullRequest
Новая
       10

Как избежать переполнения стека деструктора с глубоко вложенной структурой данных в C ++?

0 голосов
/ 10 декабря 2011 
int count;

class MyClass {
    std::shared_ptr<void> p;
public:
    MyClass(std::shared_ptr<void> f):p(f){
        ++count;
    }
    ~MyClass(){
        --count;
    }
};

void test(int n){
    std::shared_ptr<void> p;
    for(int i=0;i<n;++i){
        p = std::make_shared<MyClass>(p);
    }
    std::cout<<count<<std::endl;
}

int main(int argc, char* argv[])
{
    test(200000);
    std::cout<<count<<std::endl;
    return 0;
}

Приведенная выше программа вызывает переполнение стека при сборке "release" в IDE Visual Studio 2010.

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

ОБНОВЛЕНИЕ: Теперь я видел один значимый ответ.Однако этого недостаточно.Пожалуйста, учтите, что я обновил MyClass, чтобы он содержал два (или более) shared_ptr с, и каждый из них может быть экземпляром MyClass или некоторыми другими данными.

ОБНОВЛЕНИЕ: Кто-то обновил заголовок длямне и говорят "глубоко пересчитанная структура данных", что не обязательно связано с этим вопросом.На самом деле, shared_ptr является лишь удобным примером;Вы можете легко перейти на другие типы данных с той же проблемой.Я также удалил тег C++11, потому что это не только проблема C ++ 11.

Ответы [ 3 ]

2 голосов
/ 10 декабря 2011
  • Сделайте стек явным образом (т.е. поместите его в контейнер в куче).
  • Имеют непрозрачные указатели (не пустые), чтобы вы могли обходить свою структуру.
  • Удалите вложенную глубоко рекурсивную структуру в контейнер с кучей, делая структуру нерекурсивной (отключая ее по мере продвижения).
  • Распределите все, перебирая указатели, собранные выше.

Примерно так, с измененным типом p, чтобы мы могли его проверить. 

std::shared_ptr<MyClass> p;

~MyClass() {
    std::stack<std::shared_ptr<MyClass>> ptrs;
    std::shared_ptr<MyClass> current = p;

    while(current) {
        ptrs.push_back(current);
        current = current->p;
        ptrs.back()->p.reset(); // does not call the dtor, since we have a copy in current
    }

    --count;
    // ptrs dtor deallocates every ptr here, and there's no recursion since the objects p member is null, and each object is destroyed by an iterative for-loop
}

Несколько заключительных советов:

  • Если вы хотите распутать любую структуру, ваши типы должны предоставлять интерфейс, который возвращает и освобождает все внутренние shared_ptr, то есть что-то вроде: std::vector<shared_ptr<MyClass>> yieldSharedPtrs(), возможно, в интерфейсе ISharedContainer или что-то, если вы не можете ограничиться MyClass.
  • Для рекурсивных структур вам следует убедиться, что вы не добавляете один и тот же объект в ваш ptr-контейнер дважды.
0 голосов
/ 14 декабря 2011

Благодаря советам @ Macke у меня есть улучшенное решение, подобное следующему: 

~MyClass(){
   DEFINE_THREAD_LOCAL(std::queue< std::shared<void> >, q)
   bool reentrant = !q.empty();
   q.emplace(std::move(p)); //IMPORTANT!
   if(reentrant) return;

   while(!q.empty()){
       auto pv = q.front();
       q.pop();
   }
}

DEFINE_THREAD_LOCAL - это макрос, который определяет переменную (параметр 2) в качестве указанного типа (параметр 1) с потокомтип локального хранилища, что означает, что для каждого запущенного потока не более одного экземпляра.Поскольку ключевое слово thread_local по-прежнему недоступно для основных компиляторов, я должен предположить, что такой макрос будет работать для компиляторов.

Для однопоточных программ DEFINE_THREAD_LOCAL(type, var) это просто 

static type var;

Преимущество этого решения в том, что оно не требует изменения определения класса.

В отличие от решения @ Macke, я использую std::queue вместо std::stack, чтобы сохранить порядок уничтожения.

В данном тестовом примере q.size() никогда не будет больше 1. Однако это только потому, что этот алгоритм является первым в ширину.Если MyClass имеет больше ссылок на другой экземпляр MyClass, q.size() достигнет больших значений.

ПРИМЕЧАНИЕ. Важно помнить, что std :: move используется для передачи p в очередь.Вы не решили проблему, если забыли это сделать, вы просто создаете и уничтожаете новую копию p, и после видимого кода уничтожение все равно будет рекурсивным.

ОБНОВЛЕНИЕ: исходный опубликованный код имеетпроблема: q будет изменено в pop() вызове.Решением является кэширование значения q.front() для последующего уничтожения.

0 голосов
/ 10 декабря 2011

Если вам действительно нужно работать с таким странным кодом, вы можете увеличить размер своего стека.Вы должны найти эту опцию в свойствах проекта Visual Studio.

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

...