標準的な解答。オブジェクトのポインタを std::set で管理しているよ。

std::set は、中で二分木構造でデータを持っており、insertでの格納のオーダはO(log n)になって多少のオーバヘッドはあるけど、find での検索がバイナリサーチでできるから、検索のオーダはO(log n)になるよ。set の替わりに std::vector にした場合は挿入はO(1)で済むけど、find は線形検索になってしまってオーダは O( n )になるから、とても遅くなるよ。全体の負荷を比べると、オブジェクトの数がn個だったら std::setの場合は O( 2n log n ) になって、std::vector の場合は、O( n + n²)になるよ。例えば n = 10000 個だったら、std::set はO( 2n log n ) = 80000だから8万回くらいの計算が行われて、std::vector は、O( n + n²) = 10000 + 100000000 ≒ 100万回くらい計算が行われるよ。

今度はオブジェクトのポインタではなく、オブジェクトの名前で遭遇したかどうかを確認しているよ。この問題ではオブジェクトの名前はユニークであることを前提として良いことになっているので、これでもいいよ。ただし、解答例１はオブジェクトのポインタを比較するだけだけど、こちらは文字列比較になるので、若干、遅くなるよ。

再帰関数を使った解答例。オブジェクトの数が少ない場合は再帰の数(すなわち関数が消費するメモリのスタックの数)も少なくて済むけど、多くなるとスタックオーバフローになる可能性があるよ。

3行目と17行目はまったく同じ名前の関数が定義されているけど、引数が異なれば、関数名は同じでもいいんだよ。引数をきちんと分けて呼べば、識別できるから問題ないんだよ。

遭遇したことがあるかどうかを確認するためのset を3行目にグローバル変数として持った場合の例。こうするとどこからでもアクセスできるので関数の引数にしなくていいけど、その代わり、IsLooped() が2回以上呼ばれたときのことを考えて、24行目でやっているように初期化して中身を空にする必要があるよ。引数が同じなので、5行目の関数と19行目の関数は同じ名前にできないから、違う名前にしているよ。Impl は"実装"という意味の"Implement"からとっているよ。こうすると、IsLooped 関数はユーザに向けて公開し、IsLoopedImpl は、IsLooped 関数の中で実装に使われている関数という意味だよ。これはあくまで参考だから、必ずこうしなければいけないわけではないよ。