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

Question

我正在尝试创建一个数据结构来代表C++中的Maze.

我需要持有的关于迷宫的所有数据都可以使用按位运算以16位整数存储(以表示迷宫的每个单元格):

_{(来源:mazeworks.com)}
16位无符号整数

所以,我想出了一个16位16位数组的数组,我很高兴能够使用我的Maze数据结构.我希望保持数据结构的大小,以便我可以轻松创建非常密集的迷宫.

因此,我需要能够在运行时动态创建一个n*m大小的16位16位整数数组.在某处我读到C++中的2d数组只是[nm *]大小的1d数组的合成糖,你可以通过[row + col*width]访问元素.

以下是我的工作尝试:

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++知识的人对我的Maze课有什么建议吗？我对C++很新,所以这对我来说都是一次学习经历.

Answer 1

这将是一个很长的答案,因此它将触及一些编程/ c ++概念:封装,RAII,初始化列表,析构函数,const-ness,定义运算符,模板类,模板函数和位字段,通过处理给定的问题.

首先,我总是从用户的角度开始设计.要为迷宫设计数据结构,用户将是想要使用数据结构的程序员(可能是您).从这个角度来看,结构是内存优化的这一事实是一个实现细节,与使用相关性较低.

使用您的知识库,我将首先更改接口,以便用户不需要关心内部结构,方法是定义一个封装位操作的类,类似于此(我稍后将对其进行处理):

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在数组数组接口上):

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 ] )
{
}

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

最后,我们可以回到单元格的定义,并使其更自然地使用.我们拥有一组访问器方法,它们将执行按位操作以与四个内部字段(回溯,解决方案,边界,墙壁)中的每一个进行交互.该单元格只是一个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;
};

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

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

Answer 2

构造函数存在问题 - 在分配之前使用"width"和"height".你还需要一个析构函数来释放内存:

~Maze()
{
    delete [] mazeGrid;
}

除此之外,它看起来还不错.