C++ реализация игрового дерева

Question

Я собираюсь представить шахматную игру как структуру C++. Я думаю, что лучшим вариантом будет древовидная структура (потому что у каждой глубины есть несколько возможных ходов).

Это хороший подход?

struct TreeElement{ 
    SomeMoveType move; 
    TreeElement *parent; 
    std::vector<TreeElement*> children; 
}; 

Как эффективно хранить этот вид данных в файле? Есть ли способ убедиться, что вся древовидная структура будет храниться в той же части памяти, что позволит использовать функцию mmap?

Answer 1

Чтобы сохранить данные в том же разделе памяти, вы, вероятно, захотите предоставить объект Allocator для используемого вами std::vector<TreeElement *> и выделить его из своего блока.

Чтобы иметь возможность сериализовывать его, вместо хранения фактических указателей вы можете рассмотреть возможность смещения в блоке. Затем, когда вы снова читаете данные, вы можете добавить адрес начала блока в каждое смещение, чтобы вернуть его обратно в адрес.

В зависимости от используемого ОС/компилятора, для этого может быть некоторая поддержка. Например, компилятор Microsoft поддерживает указатели __based, которые в значительной степени описаны мной: базовый адрес, и каждый указатель, основанный на этом адресе, на самом деле является просто смещением, а не полным указателем. Упоминание mmap указывает, что, вероятно, не доступно вам напрямую, но возможно , что у вашего компилятора/операционной системы есть что-то подобное. В противном случае вам, вероятно, придется выполнять работу самостоятельно (например, с классом based_pointer).

Реальный вопрос: почему вы пытаетесь сериализовать дерево перемещения вообще. В типичном случае вам лучше сэкономить текущую позицию на доске (или, примерно, историю движения) и перегенерировать дерево перемещения из этого при необходимости. Этого достаточно меньше, что его очень легко хранить.

Answer 2

Я думаю, что использование std :: vector - это не лучший способ создать дерево, одноименная структура дерева стилей, вероятно, проще и лучше.