How can I represent a key-value-tree in C++ / STL

Question

I try to code a representation of a tree of key-value pairs with the option of multiple values for a key. What I try to do with that is reading a "data-tree" at the start of my program and then give each part of the program the "branch" of data it requires. The Libs I use so far are OpenCV and Intel TBB.

An example of the data in XML looks like this:

<key_1> value_1 </key_1>
<key_2> value_2 </key_2>
<!--  -->
<key_3> 
    <subkey_1> value_3 </subkey_1>
    <subkey_2> value_4 value_5 value_6 </subkey_1>
</key_3>
<key_4> value_1 </key_4>

So far what I came up with are two classes:

• A Class for holding a single key-value pair, named KeyValue
• A Class KeyValueGroup representing a collection of KeyValues and capable of holding other KeyValueGroups.

The Code would be:

class KeyValue {
    std::string mKey;
    std::vector<std::string> mValues;
}

class KeyValueGroup {
    // setters, getters, etc
    std::vector<KeyValue> mKeyValues;
    std::vector<KeyValueGroup> mKeyValueGroups;
    std::string mKey;
}

The values can be of different types but I convert them to std::string. My solution works, but my gut tells me this solution is probably awkward. So how would a professional tackle this problem?

Another question I ask myself is, wether I should wrap both classes in std::shared_ptr for speed (average string length is about 5 chars).

Answer 1

How much effort you put in depends on how performance critical this data is to your program, what access/update patterns you expect etc..

For undemanding use...

std::map<std::string, std::string> tree;

...where the map's key is a concatenation of the XML-specified keys, using a suitable separator or delimiter (e.g. a space, '|', ';'...?). std::unordered_map is another option. If necessary, a "Key" class can be written to hold a std::string and provide some convenience functions such as stripping the trailing element etc..

If I needed something fancier, I'd consider a third-party library e.g. boost::graph. See also this question/answers for background on C++ and trees.