How to serialize a tree structure in C++?

Question

I'm trying to serialize/deserialize a game scene for network sending/receiving and saving/loading from/to disk.

My game engine uses Nodes and Components and as such those are the only objects that need serializing. A scene might look like this:

Root Node
  - Node
    - SpecializedComponent
    - SpecializedComponent
    - Node 
      - Node
  - Node
    - Node
    - Node
      - Node
        - Node
          - SpecializedComponent
  - Node

A Node is basically this:

class Node {
    map<String, Node> mChildren;
    map<String, Component> mComponents;
    uuid_t mId;
    Node* mParent;
};

A SpecializedComponent is basically this:

class SpecializedComponent : public Component {
    uuid_t mId;
    Node* mNode;
};

I'd like to either use YAML or JSON for my text representation of this. I have Qt, Boost and any other library I'd like at my disposal so dependencies are not an issue. In fact, nodes are already Q_OBJECTS so I have reflection.

Despite reflection, deserializing this properly back to a C++ tree structure seems to be a problem.

Optimally, I'd like an elegant and efficient solution to serializing/deserializing a structure like this into either binary or text format.

Looks like a reasonable job for JSON, and there are several packages available, plus you can write your own in less than 1000 source lines. — Hot Licks, Oct 23 '11 at 12:50
your input file looks a lot like YAML. check this : http://stackoverflow.com/questions/365155/parse-yaml-files-in-c-c — Arunmu, Oct 23 '11 at 14:06
Your main problem here is that: `mComponents` can **NOT** hold any `SpecializedComponent` objects. Containers hold the actual value. So If you assign (or push/insert) a derived type into the container you will suffer from **`The Slicing Problem`**. This is where one `Component` part of the object is copied into the container and the extra parts of `SpecializedComponent` are sliced off. To have a heterogeneous container you need to use something like `std::map` (or a container designed for pointers `boost::ptr_map` — Martin York, Oct 23 '11 at 17:50
@LokiAstari, I'm already doing that albeit with limited success since I can't QtMetaType to construct a proper object for me. — svenstaro, Oct 23 '11 at 19:55

CapelliC · Accepted Answer · 2011-10-23T13:20:13.777

3

A descent recursive parser usually it's the simpler and sufficiently powerful option to handle the reconstruction part. I could try to setup some code to show in concrete, in pseudocode some thing like this:

 Node *parse(stream s) {
  content = new Node;
  s >> content >> nsons;
  for (int c = 0; c < nsons; ++c)
   content->addChild(parse(s));
  return content; 
 }

Of course when a component is read we must check the type.

edited Oct 23 '11 at 13:20

answered Oct 23 '11 at 13:14

CapelliC

59,646
5
47
90

1

The recursive serialization part is not the issue here, that's the simple part. How to recreate the objects again from their string representations and recreate the whole tree into memory again? – svenstaro Oct 23 '11 at 13:20
using std io operators and constructors of the appropriate type: new Node or new SpecializedComponent, the structure is obtained by the algorithm (a topdown visit of the syntax tree) – CapelliC Oct 23 '11 at 13:23
@chac showed how to deserialize (recreate) recursively. What exactly is unclear? – Andriy Tylychko Oct 23 '11 at 13:44
I don't necessarily know the concrete type I have since it could be any SpecializedComponent. I could use QtMetaType and QtMetaObject but then I still need to cast the resulting void* to a concrete type I can work with. – svenstaro Oct 23 '11 at 14:28

score 2 · Answer 2 · answered Oct 23 '11 at 12:50

2

I suggest you using protocol buffers library for this. Since you serializing C++ datas for sending on network, you will be very helpful for what this library has to offer.

answered Oct 23 '11 at 12:50

zaharpopov

16,882
23
75
93

I've looked at protobuf but how does it help to recursively serialize our tree and to recreate its objects during deserialization? – svenstaro Oct 23 '11 at 12:58
@Svenstaro: It can be used for serializing recursive data structures too – zaharpopov Oct 23 '11 at 15:35

score 1 · Answer 3 · answered Oct 23 '11 at 13:04

Serialize a node attributes Serialize the components for this node. IE serialize the number of childs components, then each component.

In order to serialize a component, you should attribute An Id ( either an int or a string) to each component type ( so you can determine how deserialize a specific component regarding of hs type ) Serialize the number of child node Serialize the childs nodes ( call the same function recursivly )

Then the deserialisation is the exact miror. Unserialize, the node attributes, then the number of components. For each component get the component type, deserialize it according to this type) and so on...

If you use Qt, QTextStream/QDataStream are the easiest options. A binary format must be well known at deserialisation time, so you should put a version number or an Id at the begenning of your serialised content, so you can add or change things later.

Also if you have to be compatible with other languages (as java ) be aware that Qt does not use the same norms for types as string

Then how do I recreate the SpecializedComponents again from their string representations? Also, the QTextStream and QDataStream seem way too limited for this kind of thing as they only serialize primitives or at best pre-defined Qt objects. — svenstaro, Oct 23 '11 at 13:19
If you want a unique ID the address of the object is great as an ID. — Martin York, Oct 23 '11 at 17:54

score 1 · Answer 4 · answered Oct 23 '11 at 13:08

1

I guess you can do this with Boost Serialization. It supports serialization of all STL containers including std::map.

answered Oct 23 '11 at 13:08

ks1322

33,961
14
109
164

That is not the issue here. No STL container is nested like this. I need to serialize/deserialize a completely custom structure that not only contains primitives (as STL containers do) but custom classes. – svenstaro Oct 23 '11 at 13:21
1

@Svenstaro: If you don't think boost Serialization will handle this simple structure then you need to re-read the documentation. – Martin York Oct 23 '11 at 17:46
@LokiAstari: It is not entirely about the structure. The likely bigger problem is getting the correct derived class of the component type while deserializing. I can't see a way around a factory there. I thought my question was quite illustrating enough for that issue. Apparently it was not. – svenstaro Oct 24 '11 at 04:15
1

@Svenstaro - If not clear yet, read http://www.boost.org/doc/libs/1_47_0/libs/serialization/doc/tutorial.html#pointers - it explains how the boost serialisation library takes care of writing the type of the object into the stream, and then later also takes care of reading the type and creating an instance of the correct concrete object type, so as to deserialize the data into it. – Daniel Earwicker Oct 24 '11 at 08:44
Mh, very well. I will take another look. – svenstaro Oct 24 '11 at 15:47
@Svenstaro, see here one more example of class hierarchy serialization [http://en.highscore.de/cpp/boost/serialization.html#serialization_class_hierarchies](http://en.highscore.de/cpp/boost/serialization.html#serialization_class_hierarchies) – ks1322 Oct 24 '11 at 19:01

How to serialize a tree structure in C++?

4 Answers4

Linked