2026-10-02
clear_list.cpp
#include <memory>
struct Node {
int value;
std::unique_ptr<Node> next;
};
void clear(std::unique_ptr<Node>& head) {
}
head から next でつながる単方向リストのノードをすべて解放し、head を空にする clear を書いてください。ノードが100万個あっても、使うスタックの深さはノードの数によらず一定にします。head がもともと空なら何もしません。
入力例 1
std::unique_ptr<Node> h; for (int i = 0; i < 3; ++i) h = std::make_unique<Node>(i, std::move(h)); clear(h); std::cout << (h == nullptr);
出力例 1
1
入力例 2
std::unique_ptr<Node> h; for (int i = 0; i < 1'000'000; ++i) h = std::make_unique<Node>(i, std::move(h)); clear(h); std::cout << (h == nullptr);
出力例 2
1
入力例 3
std::unique_ptr<Node> h; clear(h); std::cout << (h == nullptr);
出力例 3
1
Reference
#include <memory>
struct Node {
int value;
std::unique_ptr<Node> next;
};
void clear(std::unique_ptr<Node>& head) {
while (head)
head = std::move(head->next);
}
head.reset() の1行でもノードはすべて解放されますが、先頭のノードを破棄すると、メンバの next のデストラクタが次のノードを破棄し、それがさらに次のノードを破棄します。デストラクタの中から次のデストラクタを呼ぶ連鎖なので、ノード1つにつきスタックフレームが1つ積まれ、例2の100万個ではスタックが足りずに落ちます。コンパイラがこの連鎖をループに直してくれる保証はありません。
参考実装は、先頭のノードを1つずつ外していきます。head = std::move(head->next) のムーブ代入は、まず右辺の head->next から所有権を取り出して空にし、それから head が持っていた古い先頭ノードを破棄します1。破棄される時点でそのノードの next はもう空なので、デストラクタは次のノードへ連鎖しません。ループの1周で1ノードずつ解放され、スタックの深さは一定のままです。
掲載したのは参考実装で、唯一の正解ではありません。auto next = std::move(head->next); で次のノードを退避してから head = std::move(next); と代入する、手順を2行に分けた書き方もあります。
- 規格は
unique_ptrのムーブ代入の効果をreset(u.release())と定めています。resetも、新しいポインタを先に格納してから古いポインタを削除します。