Почему этот запоминающийся код segfault?

У меня есть следующий код, который вычисляет число Стирлинга второго рода для заданных n и k,

#include <cstdint>
#include <map>

#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;mp::cpp_int stirlingS2(unsigned n, unsigned k)
{
if (n == 0 && k == 0) {
return 1;
}

if (n == 0 || k == 0) {
return 0;
}

static auto memo = std::map<std::pair<unsigned, unsigned>, mp::cpp_int>();
auto nKPair = std::pair<unsigned, unsigned>(n, k);

if (memo.count(nKPair) > 0) {
return memo[nKPair];
}

auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1);

memo[nKPair] = val;

return val;
}

К сожалению, когда этот код работает, он вызывает ошибки. Кажется, он работает нормально для первых 87795 значений, вставленных в memo, но затем вылетает вскоре после этого. В частности, segfault происходит в map::count, в соответствии if (memo.count(nKPair) > 0) {, Я думал, может быть, это был вопрос memo заканчивается, поэтому я добавил следующее предостережение к назначению memo,

if (memo.size() < memo.max_size()) {
memo[nKPair] = val;
}

Но это не помогло. Я также заметил, что значение 87795 не указывает на то, когда происходит сбой. С некоторыми незначительными изменениями, изменяя первый оператор if на

if (n <= k) {
return 1;
}

изменяет это значение на 66453.

Кто-нибудь знает, что здесь происходит?

0

Решение

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

auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1)

В основном, изменить это auto в mp::cpp_int и внезапно, никакого сегфоута.

0

Другие решения

Других решений пока нет …