Ordered Tree in C++

Question

The C++ STL apparently is missing an ordered tree data structure. See here. Boost is also missing an ordered tree, but it does have an "un"ordered one, Property Tree where the data is ordered by insertion. I want the order to be irrespective of memory.

The boost page on Property Trees says that this is conceptually the boost::ptree structure.

struct ptree
{
   data_type data;                         // data associated with the node
   list< pair<key_type, ptree> > children; // ordered list of named children by insertion
};

I want to extend boost to keep track of order.

Is this the correct way?

class ordered_ptree : public boost::property_tree::ptree {
public:
  ordered_ptree(int id) : _id{id}{};

 protected:
  int _id;
};

@Pubby If I can, that would be fine. How do you setup std::map to handle root / node relationships (effectively std::tree)? That said, boost's ptree XML import will be helpful for the next step. — USERID_UNK, Jun 14 '16 at 23:15

score 2 · Accepted Answer · answered Jun 14 '16 at 23:26

(From the comments in your question, I understand you want something like Python's OrderedDict but taking into account keys' relative order.)

Since none of the standard library's (or boost's) containers are exactly what you want, you might want to extend std::map (especially if you don't need all of the interface).

Say you start with

template<
    typename Key, 
    typename Value, 
    class Compare=std::less<Key>,
    class Alloc=std::allocator<pair<const Key, Value> >
class ordered_map
{
    // This needs to be filled.
};

Now inside, you can hold an insertion counter:

    std::size_t m_ins_count;

which is initialized to 0 and incremented at each insert.

Internally, your new keys will be std::pairs of the original key and the insertion count. Standard properties of binary search trees imply that nodes with keys differing only by the second pair item (which is the insertion count), will be consecutive in an in-order walk, which means that

you retain order of different keys
you retain order of insertion within a key
the operations are logarithmic time
traversing same-key items is (amortized) linear time

So, internally you'd have something like

    typedef
        std::map<
            std::pair<Key, std::size_t>,
            Value,
            lex_compare<Compare>,
            std::allocator<std::pair<std::pair<Key, std::size_t>,     Value> >
        internal_map_t;

(where lex_compare<Compare> compares first by the given functor, then by the insertion index).

Now you can choose a (minimal) interface, and implement it, by translating keys in the "outer world" and pairs of keys + insertion indices in the "inner world" of the tree.

If you plan on providing an iterator interface as well, you might find the boost iterator library useful, as you simply want to modify std::map's iterators.

Ordered Tree in C++

1 Answers1