これは長い答えになるので、いくつかのプログラミング/ C ++の概念に触れます：カプセル化、RAII、初期化リスト、デストラクタ、定数、定義演算子、テンプレートクラス、テンプレート関数、および特定の問題に取り組むことによるビットフィールド。
まず第一に、私は常にユーザーの視点からデザインを始めます。迷路のデータ構造を設計するには、ユーザーはデータ構造を使用したいプログラマー（おそらくあなた）になります。その観点から、構造がメモリ最適化されているという事実は、実装の詳細であり、使用法よりも関連性が低くなります。
あなたの知識ベースでは、次のように、ビット演算をカプセル化するクラスを定義することによって、ユーザーが内部構造を気にする必要がないようにインターフェイスを変更することから始めます（後で作業します）。
class cell {
public:
void setBacktrace( unsigned int value ); // value must be between 0-15
unsigned int getBacktrace() const;
// same for all other fields
private:
uint16_t data;
};
これで、ユーザーは低レベルの詳細を気にする必要がなくなります。呼び出し元のコードは次のように書くことができます。
cell c;
c.setBacktrace( 5 ); // set the backtrace value to 5
std::cout << c.getBacktrace() << std::endl;
これで、迷路はセルオブジェクトの周りのコンテナになります。他の人が指摘しているように、std :: vectorを使用して操作を簡略化するか、独自のコンテナを定義することができます。私はあなたが学んでいると思っているので、私たちは長い道のりをたどります：
class maze {
public:
maze( size_t width, size_t height );
~maze();
cell getCell( size_t row, size_t col ) const;
void setCell( size_t row, size_t col, cell c );
private:
size_t width_;
size_t height_;
cell * data_;
};
コードからのインターフェースの変更は次のとおりです。デストラクタの追加。RAIIイディオムに従って、コンストラクターが要求するリソースの解放を処理します。セル要素へのアクセサーは、構造を変更せずに値を返すだけなので、constとしてマークされます。これは、最初から使用を開始する必要があるもう1つの概念です。つまり、すべての非変更メソッドをconstとしてマークします。
次に、実装について説明します。
// Constructor and destructor
maze::maze( size_t width, size_t height )
: width_( width ), height_( height ), data_( new cell[width*height] )
{
}
maze::~maze()
{
delete [] data_;
}
コンストラクターは、初期化リストを使用して定義されます。初期化リストでは、フィールドwidth_、height_、およびdata_のフィールドコンストラクターが呼び出され、幅、高さ、および新しい文の返されたポインターが引数として渡されます。
コンストラクターブロック（{}）内に同等のコードを追加する代わりに、初期化リストを使用する理由は2つあります。初期化リストは、角かっこ内の同等のコードよりも効率的です（それほど重要ではありません）が、主に特定のコンストラクターを呼び出したり、参照を初期化したりできます。どちらもコンストラクターブロック内では実行できません。
取得したデータを解放するためのデストラクタを追加しました。クラスにデストラクタを追加しない場合、コンパイラは、クラス内のすべての属性のデストラクタを呼び出すデフォルトのデストラクタを提供します。あなたの場合、デフォルトのデストラクタは構築中に取得したメモリを解放しません。
他の方法については詳しく説明しません。これまでのところ、ユーザーの観点から見たものは次のとおりです。
int main() {
maze m( 10, 50 ); // Consctruct the maze
cell c;
c.setBacktrace( 5 );
m.setCell( 3, 4, c); // Store c in the container
assert( m.getCell( 3, 4 ).getBacktrace() == 5 );
}
インターフェイスを少し変更することで、このコードをよりユーザーフレンドリーにすることができます。2つのインデックスを取り、セル要素への参照を返すoperator（）を提供すると、使用法が簡単になります（配列の配列インターフェイスに関するC ++ FAQ lite）：
class maze {
// most everything as before, changing set/get to:
public:
cell const & operator()( size_t row, size_t col ) const;
cell & operator()( size_t row, size_t col );
};
そうすれば、使い方はもっと簡単になります：
int main()
{
maze m( 10, 10 );
m( 3, 4 ).setBacktrace( 5 );
assert( m( 3, 4 ).getBacktrace() == 5 );
}
セルオブジェクトを作成して変更を適用してからオブジェクトを保存する必要はありません。保存されたオブジェクトを直接変更できます。今実装：
cell const & maze::operator()( size_t row, size_t col ) const
{
return *data_[ row + col*width_ ];
}
cell & maze::operator()( size_t row, size_t col )
{
return *data_[ row + col*width_ ];
}
両方の実装は類似していますが、最初の実装は迷路の内容を変更しないことをコンパイラに通知し、呼び出し元がセルを変更しないことを保証するために定数参照を返すという点が異なります。
迷路クラスで作業した後、迷路にする唯一のことは、格納されたデータがセルであるということですが、すべてのロジックはプレーンな2D配列のロジックにすぎないことに気付くでしょう。これを利用してテンプレートクラスとして再定義できるため、格納されているタイプの定義を変えて、さまざまな状況でコードを再利用できます。
template <typename T> // stored data
class array_2d
{
public:
array_2d( size_t width, size_t height );
~array_2d();
T const & operator()( size_t row, size_t col ) const;
T & operator()( size_t row, size_t col );
private:
size_t width_;
size_t height_;
T* data_;
};
そして、使用法は次のようになります：
int main()
{
array_2d<cell> maze( 10, 10 );
maze( 3, 4 ).setBacktrace( 5 );
}
実装の定義は少し異なりますが、それほど複雑ではありません。
template <typename T>
array_2d<T>::array_2d( size_t width, size_t height )
: width_( width ), height_( height ), data_( new T[ width*height ] )
{
}
同様に、各メソッドの実装を定義する場合。それほど難しいことではありませんか？
最後に、セルの定義に戻って、作業をより自然にすることができます。私たちが持っているのは、4つの内部フィールド（バックトラック、ソリューション、境界線、壁）のそれぞれと相互作用するビット単位の操作を実行する一連のアクセサーメソッドです。セルは、次のような4つの整数フィールドを格納するPOD（プレーンな古いデータ）構造です。
struct big_cell
{
unsigned int backtrack;
unsigned int solution;
unsigned int borders;
unsigned int walls;
};
これは次のように使用されます。
int main()
{
array_2d<big_cell> maze( 10, 10 );
maze( 3, 4 ).backtrack = 5;
assert( maze( 3, 4 ).backtrack == 5 );
}
しかし、その構造は私たちが必要とするものよりも多くのスペースを必要とします。ストレージ実装の詳細により、クラスの使用法を変更する必要がありました。それに取り組んでみましょう。unsignedintegersをunsignedcharsに変更すると、構造体のサイズが32ビットに減少します（完全に最適化された構造体の16ビットではなく）。
struct medium_cell
{
unsigned char backtrack;
unsigned char solution;
unsigned char borders;
unsigned char walls;
};
このソリューションは、セルごとに2バイトしか浪費しません。これは、おそらくそれほど多くはありません（スペース要件は倍増しますが、最近のメモリは安価です）。また、これは32ビットプロセッサでの実行が高速になる可能性があります。一部の32ビットアーキテクチャでは、16ビット要素の取得と操作に時間がかかります。
とにかく、完全にコンパクトなメモリモデルにまだ興味がある場合は、C++のあまり知られていない機能であるビットフィールドを使用できます。これらを使用すると、構造内の一部のフィールドが数ビットかかることを定義できます。
struct small_cell {
uint16_t backtrack : 4; // take 4 bits from the uint16_t
uint16_t solution : 4;
uint16_t borders : 4;
uint16_t walls : 4;
};
そして、使用法は次のようになります。
int main()
{
small_cell c;
c.solution = 5;
c.backtrack = 3;
}
現在、この構造体はわずか16ビットのメモリを使用し、前の2つの構造体と同じように使用できます。迷路はテンプレート化された2D配列になっているため、3つの構造を非常に簡単にテストできます。テスト用のテンプレート関数を定義できます。
#include <time.h>
// templated for comparissons with cell types
template <typename CellStruct>
void test()
{
array_2d< CellStruct > maze;
// Test operations...
}
void print_test( std::string const & test, clock_t ticks )
{
std::cout << "Test: " << test << " took " << ticks
<< " ticks, or " << ticks / CLOCKS_PER_SEC << " seconds."
<< std::endl;
}
int main()
{
clock_t init = clock();
test< big_cell >();
clock_t after_big = clock();
test< medium_cell >();
clock_t after_med = clock();
test< small_cell >();
clock_t end = clock();
print_result( "big_cell", after_big - init );
print_result( "medium_cell", after_med - after_big );
print_result( "small_cell", end - after_med );
}
テスト関数は、さまざまなセル実装で実行できるようにのみテンプレート化されています。問題のドメインに最適な実装がわかったら、特定のセルタイプを使用する特定のコードを作成できます。
