Это будет длинный ответ, так что он затронет некоторые концепции программирования / 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 на интерфейсе массив-массив ):
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_ ];
}
Обе реализации похожи, с той лишь разницей, что первая говорит компилятору, что он не изменит содержимое лабиринта, и возвращает постоянную ссылку, чтобы гарантировать, что вызывающая сторона не изменит ячейку.
После работы с классом лабиринта вы можете заметить, что единственное, что делает его лабиринтом, это то, что сохраненные данные являются ячейкой, но вся логика - это просто логика простого двумерного массива. Мы можем воспользоваться этим и переопределить его как шаблонный класс , чтобы мы могли повторно использовать код в различных ситуациях с различными определениями хранимого типа:
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 бит памяти и может использоваться как две предыдущие структуры. Поскольку лабиринт теперь представляет собой просто шаблонный 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 );
}
Функция тестирования является шаблонной только для того, чтобы ее можно было выполнять с различными реализациями ячеек. Как только вы узнаете, какая реализация лучше всего подходит для вашей проблемной области, вы можете создать специальный код, который будет использовать определенный тип ячейки.