这将是一个很长的答案，因此它将涉及一些编程/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，因为它只会返回一个值而不改变结构。这是您应该从一开始就开始使用的另一个概念：将所有非变异方法标记为 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_;
}
构造函数是使用初始化列表定义的。在初始化列表中，字段宽度_、高度_和数据_的字段构造函数被称为传递宽度、高度和新句子的返回指针作为参数。
使用初始化列表而不是在构造函数块 ({}) 中添加等效代码有两个原因。初始化列表比括号内的等效代码更有效（不是那么重要），但主要允许您调用特定的构造函数或初始化引用，这两者都不能在构造函数块内完成。
我添加了一个析构函数来释放您获取的数据。如果你没有在你的类中添加析构函数，编译器将提供一个默认析构函数，它将调用你类中所有属性的析构函数。在您的情况下，默认析构函数不会释放在构造期间获得的内存。
其他方法我就不赘述了。到目前为止，我们从用户的角度来看：
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 );
}
我们可以通过稍微改变界面使这段代码更加用户友好。如果我们提供一个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 ] )
{
}
在定义每种方法的实现时也是如此。没那么难，不是吗？
最后，我们可以回到 cell 的定义，让它更自然地使用。我们拥有一组访问器方法，它们将执行按位操作以与四个内部字段（回溯、解决方案、边界、墙壁）中的每一个进行交互。单元格只是一个存储四个整数字段的 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 );
}
但这种结构将占用比我们需要的更多的空间。存储实现细节迫使我们改变类的使用。让我们尝试解决这个问题。将无符号整数更改为无符号字符会将结构的大小减少到 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 位内存，可以像前两个结构一样使用。由于迷宫现在只是一个模板化的二维数组，您可以很容易地测试这三个结构。您可以为测试定义模板函数。
#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 );
}
测试函数仅是模板化的，以便可以使用不同的单元实现来执行。一旦您知道哪种实现最适合您的问题域，您就可以制作将使用特定单元格类型的特定代码。
