競プロ C++ 部分集合走査ライブラリ

概要

for (auto t: subsets(s)) で s (の bit 列を集合と解釈したとき) の部分集合を走査できるようなライブラリを書きました。 単純には std::vector<int> を返せばいいのですが、速度が少し気になるので、それを解決します。 部分集合に限らず、多次元ループなども同様の方法で効率的に記述できると思います。

範囲 for ループの制限緩和 - cpprefjp C++日本語リファレンス

実装

#include <cstdint>
#include <variant>

struct subsets {
  using u64 = std::uint64_t;

  u64 s;

  subsets(u64 s_) : s(s_) {}

  struct itr {
    u64 s;
    u64 t;

    bool operator!=(std::monostate) { return t != -1; }
    void operator++() { t -= 1; }
    u64 operator*() { return t &= s; }
  };

  itr begin() { return {s, s}; }
  std::monostate end() { return {}; }
};

注意

• s 自身や 0 も走査されます。dp で使いたいときはこれらを含まないようにした方が良いかもしれません。
• s = -1 のとき壊れます。
• u64 を返しているので、必要なら適宜 int などに変えてください。
• std::monostate は何でもいい (int でも char でも) ので、変えても良いです。C++14 だと begin と end で同じ型が返る必要があるので、itr({0,0}) とかにすると良いと思います。