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

Question

我正在尝试用 C++ 创建一个数据结构来表示迷宫。

我需要保存的有关迷宫的所有数据都可以使用按位运算存储在 16 位整数中（以表示迷宫的每个单元格）：

_{（来源：mazeworks.com）}
16 位无符号整数

因此，我计算了一个 16 位整数的二维数组，并且我很高兴采用我的 Maze 数据结构。 我想缩小数据结构的大小，这样我就可以轻松创建非常密集的迷宫< /a>.

因此，我需要能够在运行时动态创建一个 n*m 大小的 16 位整数的二维数组。 在某处，我读到 C++ 中的 2d 数组只是 [n*m] 大小的 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++ 提供的默认实现。

Answer 2

不解决您的主要空间问题，但这是一个简单的版本，不涉及显式动态内存管理：

#include <vector>
#include <iostream>
using namespace std;

class Maze {
    public:

        Maze(int mazeWidth, int mazeHeight) {
           for ( int i = 0; i < mazeHeight; i++ ) {
              mMaze.push_back( vector <int>( mazeWidth ) );
           }
        }

        int At(int row, int col) const {
           return mMaze.at(row).at(col); 
        }

        int & At(int row, int col) {
           return mMaze.at(row).at(col); 
        }

    private:

        vector < vector <int> > mMaze;
};


int main() {
    Maze m( 5, 5 );
    m.At( 2, 2 ) = 42;
    cout << m.At( 2, 2 ) << "\n";
}

Answer 3

这将是一个很长的答案，因此它将涉及一些编程/C++ 概念：封装、RAII、初始化列表、析构函数、const-ness、定义运算符、模板类、模板函数和位字段 通过解决给定的问题。

首先，我总是从用户的角度开始设计。 为了设计迷宫的数据结构，用户将是想要使用该数据结构的程序员（可能是您）。 从这个角度来看，结构是内存优化的事实是一个实现细节，与使用无关。

有了你的知识基础，我将从更改接口开始，这样用户就不需要通过定义一个封装位操作的类来关心内部结构，与此类似（我稍后将介绍it):

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 负责释放构造函数请求的资源。 /strong> 习语。 单元格元素的访问器被标记为 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()，那么用法会更简单（关于 array-of-array 接口的 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 对象并对它应用更改，然后存储该对象，我们可以直接修改存储的对象。 现在是实现：

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_ ];
}

两种实现都很相似，唯一的区别是第一个实现告诉编译器它不会更改迷宫的内容，并返回一个常量引用以保证调用者不会更改单元格。

在研究迷宫类之后，您可以注意到，使它成为迷宫的唯一原因是存储的数据是一个单元格，但所有逻辑只是一个普通的二维数组。 我们可以利用它并将其重新定义为模板类，以便我们可以在不同情况下重用代码，并使用不同的存储类型定义：

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

用法将是：

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

测试函数只是模板化的，以便可以使用不同的单元实现来执行。 一旦您知道哪种实现最适合您的问题域，您就可以编写将使用特定单元类型的特定代码。

Answer 4

构造函数有一个问题 - 您在分配“宽度”和“高度”之前使用了它们。 您还需要一个析构函数来释放内存：

~Maze()
{
    delete [] mazeGrid;
}

除此之外，它看起来还不错。

Answer 5

在 C++ 中，构造就是初始化。 这样您就可以重写 c'tor：

    Maze(int mazeWidth, int mazeHeight) 
       :width(mazeWidth), height(mazeHeight), mazeGrid(new uint16_t[width*height])
    {
    }

请注意，数据成员按照它们在类中定义的顺序进行初始化，而不是按照您初始化它们的顺序进行初始化。
另请注意，unsinged int16_t 已转换为 uint16_t。 如果你要使用这些人，最好一路走下去。
数据成员通常称为 m_width 和 m_height，而不仅仅是 width 和 height。

我将定义一个返回 uint16_t* 的 operator[] ，而不是 set 和 get 方法，这样您就可以获得模仿原始类型的更自然的语法：

   ....
   uint16_t* operator[](int col) { return &(mazeGrid[col*width]); }
   ....

   uint16_t d = mymaze[col][row];

我将让你就会明白为什么它能正确工作。

Answer 6

尝试使用 std::vector

Answer 7

您可以使用 std::bitset

Answer 8

好吧，setArrayValue 还没有做任何事情（尽管你现在可能已经注意到了）。 此外，您没有删除功能，因此 mazeGrid 永远不会被释放。 否则对我来说看起来还不错。

Answer 9

编写一个小宏来转换二维坐标以提高可读性。 就像是。 this：

#define TWO_DIM(x,y,w) (x+y*w)

使用 STL 容器：

// Define and get memory
std::vector <int16_t> mazedata;
mazedata.resize(newsize);
// Assign values
mazedata[TWO_DIM(row,col,width)]=newvalue;

请记住，STL 实现了内存高效的 std::vector，它可以像普通数组一样使用，但每比特数据占用 1 位。 对于大型数组，您不会注意到 STL 的开销。