Абстракция для итерации битового элемента

Question

У меня есть собственная реализация класса bitset в C ++. Я часто перебираю индексы битов, которые установлены в наборе битов (т.е. для набора битов '10011' я хочу перебирать числа 0, 3, 4.) Эта итерация может быть реализована следующим образом:

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

Как предложил KamilCuk, я использовал итератор для решения этой проблемы. Теперь реализация выглядит следующим образом:

struct Bitset {
  uint64_t* data_;
  size_t chunks_;
  class BitsetIterator {
   private:
    const Bitset* const bitset_;
    size_t pos_;
    uint64_t tb_;
   public:
    BitsetIterator(const Bitset* const bitset, size_t pos, uint64_t tb) :
      bitset_(bitset), pos_(pos), tb_(tb) { }
    bool operator!=(const BitsetIterator& other) const {
      return pos_ != other.pos_ || tb_ != other.tb_;
    }
    const BitsetIterator& operator++() {
      tb_ &= ~-tb_;
      while (tb_ == 0 && pos_ < bitset_->chunks_) {
        pos_++;
        if (pos_ < bitset_->chunks_) {
          tb_ = bitset_->data_[pos_];
        }
      }
      return *this;
    }
    int operator*() const {
      return pos_*BITS + __builtin_ctzll(tb_);
    }
  };

  BitsetIterator begin() const {
    size_t pos = 0;
    while (pos < chunks_ && data_[pos] == 0) {
      pos++;
    }
    if (pos < chunks_) {
      return BitsetIterator(this, pos, data_[pos]);
    } else {
      return BitsetIterator(this, pos, 0);
    }
  }
  BitsetIterator end() const {
    return BitsetIterator(this, chunks_, 0);
  }
};

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

Это позволяет избежать выделения кучи и намного быстрее, чем версия, использующая вектор. Я не уверен, обеспечивает ли это точно такую ​​же производительность, как версия без каких-либо абстракций, но она должна быть очень близкой.

Answer 2

Просто переберите свой класс. Предоставьте собственную реализацию класса итератора для ваших 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) ... l oop я не понимаю, что может быть что-то в этом роде (непроверено!):

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); }
};