All geek questions in one place

Creating a Maze class in C ++ using a 16-bit unsigned int array?

I am trying to create a data structure to represent a maze in C ++.

All the data that I have to store in the maze can be saved in 16-bit integers using bitwise operations (to represent each maze cell):
alt text http://www.mazeworks.com/mazegen/mazetut/tut5.gif
16 unsigned integer

So, I figured out the 2nd array of 16-bit integers, and I am good at going to my Maze data structure. I wanted to preserve the size of the data structure, so I can easily create very dense mazes .

So, I need to be able to create a 2-dimensional array from 16-bit integers of size n * m, dynamically at runtime. Somewhere in SO, I read that 2d arrays in C ++ are just syntactic sugar for 1d arrays [n *m], and you can access elements through [row + col * width].

Here is my working attempt:

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;

}

Does anyone with C ++ know some suggestions for my Maze class? I am very new to C ++, so for me it is just a learning experience.

+3
source share
9 answers

, /++: , 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_;
};

: . , ,

. 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(), , (++ 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- .

, , ++: . , - :

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

, . , , , .

+10

- "" "" . :

~Maze()
{
    delete [] mazeGrid;
}

, .

+5

++ - . 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, .

set get operator[], uint16_t* , , :

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

   uint16_t d = mymaze[col][row];

, .

+3

std::vector

+2

std:: bitset

+1

, setArrayValue ( , , ). , mazeGrid . .

0

, 2d-, . - . :

#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<bool>, , 1 . STL.

0

, , :

#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";
}
0

The previous answers did not mention that if your class contains a pointer to allocated memory, you should either provide a constructor and an assignment operator, or simply prevent them from using the default implementations that C ++ provides for them.

0
source

Source: https://habr.com/ru/post/1703218/

More articles:


All Articles