Qt Tree Model versus nested maps for storing a dictionary for translations

Question

I am writing a class using Qt that needs to import a dictionary that will be used to look up a command and build a command sentence. The commands are arranged in a hierarchical manner and have a corresponding hex key and value definition. For illustration purposes, it could look like this:

01 : Volume
        | - 01 : Step : 00=Down, 01=Up
        | - 02 : Set : ceil(255/100 * x)
02 : Power
        | - 01 : Power : 00=Off, 01=On
        | - 02 : Sleep : ...etc

I want to load this dictionary and then be able to search it for "Volume/Set/50" and return the command sentence "01 02 80" or look up "01 02 80" and return "Volume/Set/50."

The actual implementation is a little more complex and has commands at different levels in the tree structure and could include any number and combination of commands from different levels in a single sentence.

Edit:

The comment provided by volodymyr below introduces a concept (Trie) that I was not familiar with. It may be the best implementation for this particular scenario, but I have to research it some more. I am still interested in an answer to my original question (with the addition of Trie):

What are the advantages and disadvantages of using each of these methods for this implementation?

• Qt Tree Model
• Nested Maps
• Trie

Original question: (for context)

Would a Qt Tree Model, nested maps or some other means be better suited to store the dictionary? I realize "better" may be subjective, but I would like to know the trade offs.

I am already building a Qt Tree Model to display some other data in a QTreeView, so that code will already exist and could easily be used. Would the Tree Model allow more flexibility in loading dictionaries with different structures? Is there a better way to do this? or maybe a standard design pattern?

Answer 1

In my opinion, the number of items at each level in the command tree is too small to justify using a trie. A trie (see http://en.wikipedia.org/wiki/Trie), due to its large branching factor, is best for a large number of items -- for example a natural-language dictionary, as volodymyr has pointed out.

In fact, the number may be too small to justify even std::map. If there aren't more than a couple dozen commands or codes at a given point in the tree, a linear search is probably about as fast as a search in a map, or faster. The memory representation as a vector or list would also be more compact. That said, std::map's interface seems very well suited for what you're trying to do, so, in practice, it's probably still the best choice overall.

I can't see how QTreeModel can be better than std::map from any point of view (speed, memory, ease of use), except that it may mesh better with the rest of your code, since it's Qt-based. However, if you even vaguely suspect that this part may have a use without Qt, I would not hesitate to choose the standard library stuff (std::map). The only truly compelling reason to choose QTreeModel over std::map would be if you actually used it in a QTreeView.