9

最近ビットベクトルについて聞いたことがありますが、このトピックに関する有用な情報やチュートリアルを実際に見つけることはできません。独自のビット ベクトル クラスを実装する方法についての書籍または簡単なチュートリアルを提案していただけますか? ありがとうございました。

---/// 自分の質問への回答を投稿できないので、この投稿を編集することにしました。ここに私が見つけたものがあります：「ゲームプログラマーのためのデータ構造 - ロン・ペントンとアンドレ・ラモス」。第 4 章、ビットベクトル。この本には、ビットベクトルの完全な説明と、ビットベクトルクラスを自分で作成する方法が記載されています。楽しんで。

4

2 に答える 2

5

これは、非常に単純な静的サイズのビット ベクトルの実装です。ヘッダーに依存しているため、機能するには C++11 が必要です<cstdint>が、このヘッダーは C99 機能に基づいているため、かなり一般的に見られます。ピンチでは、C<stdint.h>ヘッダーを使用して、代わりにグローバル名前空間の型を使用することができます。

注:これはオンザフライで入力されたものであり、まったくテストされていません。私はそれがコンパイルされることさえ確認しませんでした。そのため、エラーが発生する可能性があります。

#include <cstdint>  // ::std::uint64_t type
#include <cstddef> // ::std::size_t type
#include <algorithm>

class my_bitvector_base {
 protected:
   class bitref { // Prevent this class from being used anywhere else.
    public:
      bitref(::std::uint64_t &an_int, ::std::uint64_t mask)
           : an_int_(an_int), mask_(mask)
      {
      }

      const bitref &operator =(bool val) {
         if (val) {
            an_int_ |= mask_;
         } else {
            an_int_ &= ~mask_;
         }
         return *this;
      }
      const bitref &operator =(const bitref &br) {
         return this->operator =(bool(br));
      }
      operator bool() const {
         return ((an_int_ & mask_) != 0) ? true : false;
      }

    private:
      ::std::uint64_t &an_int_;
      ::std::uint64_t mask_;
   };
};

template < ::std::size_t Size >
class my_bitvector : public my_bitvector_base {
 private:
   static constexpr ::std::size_t numints = ((Size + 63) / 64);
 public:
   my_bitvector() { ::std::fill(array, array + numints, 0); }

   bool operator [](::std::size_t bitnum) const {
      const ::std::size_t bytenum = bit / 64;
      bitnum = bitnum % 64;
      return ((ints_[bytenum] & (::std::uint64_t(1) << bitnum)) != 0) ? true : false;
   }
   bitref operator[](::std::size_t bitnum) {
      const ::std::size_t bytenum = bit / 64;
      bitnum = bitnum % 64;
      ::std::uint64_t mask = ::std::uint64_t(1) << bitnum;
      return bitref(ints_[bytenum], mask);
   }

 private:
   ::std::uint64_t ints_[numints];
};

// Example uses
void test()
{
    my_bitvector<70> bits; // A 70 bit long bit vector initialized to all false
    bits[1] = true; // Set bit 1 to true
    bool abit = bits[1]; // abit should be true.
    abit = bits[69]; // abit should be false.
}

すべてmy_bitvector_baseは、一種のプライベート タイプを作成することです。であるため、派生クラスのインターフェイスまたは実装でprotected言及できますが、他のコンテキストで言及することはできません。これにより、人々がbitref. これは重要です。実際には、C++ 標準委員会が配列要素への代入などを実装していないためbitref、結果への代入を許可するためだけに存在するからです。operator []operator []=

ご覧のとおり、ビット ベクトルは基本的にビットの配列です。手の込んだビット ベクトルは、すべて true または false に初期化されたビットの「無限」配列をシミュレートします。これは、設定された最後のビットとその前のすべてのビットを追跡することによって行われます。その後、少し要求すると、初期化された値が返されます。

優れたビット ベクトルはoperator &、ビット操作操作に関して非常に大きな符号なし整数のように動作するように、その他のそのような機能も実装します。

于 2011-12-19T19:29:17.960 に答える
3

vector <bool>は、ベクターテンプレートの特殊化です。通常のbool変数には少なくとも1バイトが必要ですが、boolには2つの状態しかないため、ベクトルの理想的な実装では、各bool値に必要なビットは1つだけです。これは、イテレータを特別に定義する必要があり、bool*にすることはできないことを意味します。

Thinking CPP Vol-2 from Bruce Eckel Chapter 4：STL Containers＆Iterators

この本はhttp://www.mindviewinc.com/Books/downloads.htmlから無料でダウンロードでき 、ビットとC++に関する詳細情報が含まれています。

于 2011-12-19T18:53:54.477 に答える