使用16位无符号整数数组在C中创建一个Maze类？

class Maze {
    public:

        Maze(int mazeWidth,int mazeHeight)
        {
            mazeGrid = new unsigned int16_t[width*height];
            width = mazeWidth;
            height = mazeHeight;
        }

        unsigned int16_t getArrayValue(int row,int col)
        {
            return mazeGrid[row + col*width];
        }

        void setArrayValue(int row,int col,unsigned int16_t value)
        {
            mazeGrid[row + col*width] = value;
        }

    private:
        int width,height;
        unsigned int16_t *mazeGrid;

}

这将是一个很长的答案,因此它将触及一些编程/ 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_;
}

使用初始化列表定义构造函数.在初始化列表中,字段width_,height_和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 on array-of-array interface)：

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 ),data_( new T[ width*height ] )
{
}

同样在定义每个方法的实现时.不是那么难,是吗？

最后,我们可以回到单元格的定义,并使其更自然地使用.我们拥有一组访问器方法,它们将执行按位操作以与四个内部字段(回溯,解决方案,边界,墙壁)中的每一个进行交互.该单元格只是一个POD(普通旧数据)结构,存储四个整数字段,类似于：

struct big_cell
{
   unsigned int backtrack;
   unsigned int solution;
   unsigned int borders;
   unsigned int walls;
};

这可以用作：

int main()
{
   array_2d<big_cell> maze( 10,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;
};

并且ussage将是：

int main() 
{
   small_cell c;
   c.solution = 5; 
   c.backtrack = 3;
}

现在这个结构只需要16位内存,可以像前两个结构一样使用.由于迷宫现在只是模板化的2d阵列,因此您可以非常轻松地测试这三种结构.您可以为测试定义模板函数.

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

测试函数仅被模板化,因此可以使用不同的单元实现来执行.一旦您知道哪种实现最适合您的问题域,您就可以制作将使用特定单元类型的特定代码.