Namaran

Code daily. Without assist.

2026-10-11

collatz.cpp

#include <iostream>
#include <vector>

int collatz_steps(long n) {
    static std::vector<int> memo{-1, 0};  // memo[n] < 0: not computed yet
    if (n >= std::ssize(memo))
        memo.resize(n + 1, -1);
    int& known = memo[n];
    if (known < 0)
        known = 1 + collatz_steps(n % 2 ? 3 * n + 1 : n / 2);
    return known;
}

int main() {
    std::cout << collatz_steps(6) << ' ' << collatz_steps(7) << '\n';
}

collatz_steps は、n にコラッツの操作(偶数なら2で割り、奇数なら3倍して1を足す)を何回繰り返すと 1 になるかを、関数の中の static な表にメモしながら求める関数です。このプログラムは本来 8 16 を出力します。いまも通常のビルドでは 8 16 が出ますが、AddressSanitizer を有効にしてビルドすると、最初の collatz_steps(6) の途中で heap-use-after-free を報告して異常終了します。

Answer

Wrong

int& known = memo[n];
if (known < 0)
    known = 1 + collatz_steps(n % 2 ? 3 * n + 1 : n / 2);
return known;

関数の中の static な memo は、再帰で入れ子になったすべての呼び出しが共有する1つの表です。known はその要素を指す参照で、再帰呼び出しの前に作られます。再帰した先で memo が伸びると、std::vector は大きな領域を新しく確保して要素を移し、古い領域を解放します。呼び出し元に戻ってから known に代入すると、解放済みの領域に書き込むことになり、これは未定義動作です。

コラッツの操作は数を小さくするとは限らないので、再帰の先で表が伸びることがあります。collatz_steps(6) は memo を7要素に広げてから 6、3 の順に参照を作り、3 の次の 10 で memo を11要素に伸ばします。このとき 6 と 3 の参照は古い領域に取り残されます。通常のビルドで 8 16 が出るのは、解放したばかりの領域に書いた値を同じ参照からすぐ読み返しているからで、計算した値は新しい表には残りません。

Right

if (memo[n] < 0)
    memo[n] = 1 + collatz_steps(n % 2 ? 3 * n + 1 : n / 2);
return memo[n];

参照を取っておかずに毎回 memo[n] と書けば、そのときの memo の領域から要素を探し直します。代入 memo[n] = 1 + collatz_steps(...) では、右辺の評価が左辺より先に済むと C++17 から決まっているので1、左辺の memo[n] は再帰が表を伸ばし終えたあとに評価されます。return memo[n] も同じく新しい領域を読むので、計算した値は表に残り、2回目以降の呼び出しで使われます。

  1. C++14 までは代入の両辺のどちらを先に評価するかが決まっておらず、memo[n] = 1 + collatz_steps(...) でも左辺が先に評価され、同じ問題が起きることがありました。
  2. std::map や std::unordered_map は要素を別々のノードに持つので、挿入しても既存の要素への参照は無効になりません。unordered_map の再ハッシュで無効になるのはイテレータだけです。