2026-09-26
two_phase_set.cpp
struct TwoPSet {
std::set<std::string> added;
std::set<std::string> removed;
};
std::set<std::string> visible(const TwoPSet& a, const TwoPSet& b) {
}
TwoPSet は、要素を追加した記録 added と削除した記録 removed を別々に持つ集合で、どちらの記録も増えるだけで減りません。2つのレプリカ a と b の状態を統合したときに見える要素を返す visible を書いてください。見えるのは、どちらかのレプリカで追加され、どちらのレプリカでも削除されていない要素です。どちらも空なら空集合を返します。visible({{"x", "y"}, {}}, {{"x"}, {"x"}}) → {"y"}、visible({{"x"}, {}}, {{"y"}, {}}) → {"x", "y"}、visible({}, {}) → {}
Reference
std::set<std::string> visible(const TwoPSet& a, const TwoPSet& b) {
std::set<std::string> result = a.added;
result.insert(b.added.begin(), b.added.end());
std::erase_if(result, [&](const std::string& x) {
return a.removed.contains(x) || b.removed.contains(x);
});
return result;
}
統合は2段で考えます。まず両方の added の和集合を取り、そこから両方の removed に入っている要素を除きます。和集合は、a.added をコピーしてから insert に b.added の範囲を渡せば作れます。std::set は同じ要素を2つ持たないので、両方で追加された "x" も1つです。除く方は、C++20 の std::erase_if と contains を使うと、条件を1つのラムダにそのまま書けます。
和集合は、どの順で何回取っても結果が変わりません。added も removed も和集合で統合するので、レプリカ同士がどの順で状態を送り合っても、同じ状態を2回受け取っても、最後には同じ集合に収束します。その代わり、一度 removed に入った要素は二度と見えなくなります。1つ目の例で a は "x" を持ったままですが、b の削除が勝つのはそのためです。削除した要素をもう一度追加できるようにしたいなら、追加のたびに一意なタグを付ける OR-Set のような別の設計が要ります。
掲載したのは参考実装で、唯一の正解ではありません。std::set_union と std::set_difference を続けて使っても、両方の added を1つずつ見て条件に合うものだけを insert しても、同じ結果になります。