[bitset元素迭代的C ++抽象

Question

我有一个C ++中的自定义位集类实现。我经常遍历位集中设置的位。该迭代可以如下实现：

struct Bitset {
  uint64_t* data_;
  size_t chunks_;
  std::vector<int> Elements() const {
    std::vector<int> ret;
    for (size_t i=0;i<chunks_;i++){
      uint64_t td = data_[i];
      while (td) {
        ret.push_back(i*BITS + __builtin_ctzll(td));
        td &= ~-td;
      }
    }
    return ret;
  }
};

void Iterate(Bitset bitset) {
  for (int b : bitset.Elements()) {
    std::cout << "bit: " << b << std::endl;
  }
}

上面的实现为迭代提供了干净的代码，但是它涉及到向量不必要的堆分配。基本上内联Elements（）函数的以下版本通常更快：

void Iterate(Bitset bitset) {
  int chunks = bitset.chunks_;
  for (int i = 0; i < chunks; i++) {
    uint64_t td = bitset.data_[i];
    while (td) {
      std::cout << "bit: " << i*BITS + __builtin_ctzll(td) << std::endl;
      td &= ~-td;
    }
  }
}

为迭代实现抽象的一种好方法，使它与上述版本一样干净，而且没有性能损失。

Answer 1

只需遍历您的课程。为Bitset提供您自己的迭代器类的实现，并提供begin()和end()方法。最简单（未经测试！）的实现可能如下所示：

#include <vector>
#include <cstdint>
#include <iostream>

struct Bitset {
  uint64_t* data_;
  size_t chunks_;
  struct iterator {
      uint64_t *pnt;
      uint_fast8_t pos;
      iterator(uint64_t *pnt, size_t pos) : 
        pnt(pnt), pos(pos) {}
      bool operator !=(const iterator& o) {
          return o.pnt != pnt || o.pos != pos;
      }
      void operator ++() {
          pos++;
          if (pos == 64) {
              pnt++;
              pos = 0;
          }
      }
      bool operator *() {
          return *pnt & (1 << pos);
      }
  };
  iterator begin() { return iterator(data_, 0); }
  iterator end() { return iterator(data_ + chunks_, 64); }
};

void Iterate(Bitset bitset) {
    for (auto&& b : bitset) {
        std::cout << "bit: " << b << std::endl;
    }
}

我相信您不奇怪的while (td) { ... i*BITS + __builtin_ctzll(td) ...循环，可能会一直存在（未经测试！）：

constexpr int BITS = 100000;
struct Bitset {
  uint64_t* data_;
  size_t chunks_;
  struct iterator {
      uint64_t *data_;
      int i = 0;
      uint64_t td = 0;
      iterator(uint64_t *data_, int i, uint64_t td) :
       data_(data_), i(i), td(td) {}
      bool operator !=(const iterator& o) {
          return o.data_ != data_ || o.i != i || o.td != td;
      }
      void operator ++() {
          if (td == 0) {
              td = *data_;
              data_++;
          } else {
            td &= ~-td;
          }
      }
      bool operator *() {
          return i * BITS + __builtin_ctzll(td);
      }
  };
  iterator begin() { return iterator(data_, 0, *data_); }
  iterator end() { return iterator(data_ + chunks_, 0, 0); }
};