Looking for tree-like structure

[mathieu]

Hello there,

I am looking for the proper structure for the following problem. I
would like to read in memory a file that has the following structure:

k1, v1
k2, v2
k3, v3
k4 /
k1, v11
k3, v33
k5, v5
k1, v11
k8/
k1, v111
k2, v222
k7, v7

In the previous example k(i) is an uint32_t where k1 < k2 < ... < k7
< k8 and v(i) is just some data associated with the k(i). Note that
there is no data associated with k4 or k8 for instance (k4 and k8 are
special keys). There can be gap (k6 is missing), and the tree can be
any level deep.

I do not need any rebalancing operation, since the order of k(i) is
important. All I need is:
* Parsing (read and write the tree from/to disk)
* Insertion/Deletion of elements or sub-tree (e.g k4)
* Access (find a specific key k(i) a particular level)

Thanks for pointer to documentation and/or code,
Mathieu

[mlimber]

mathieu wrote:

Hello there,

I am looking for the proper structure for the following problem. I
would like to read in memory a file that has the following structure:

k1, v1
k2, v2
k3, v3
k4 /
k1, v11
k3, v33
k5, v5
k1, v11
k8/
k1, v111
k2, v222
k7, v7

In the previous example k(i) is an uint32_t where k1 < k2 < ... < k7
< k8 and v(i) is just some data associated with the k(i). Note that
there is no data associated with k4 or k8 for instance (k4 and k8 are
special keys). There can be gap (k6 is missing), and the tree can be
any level deep.

I do not need any rebalancing operation, since the order of k(i) is
important. All I need is:
* Parsing (read and write the tree from/to disk)
* Insertion/Deletion of elements or sub-tree (e.g k4)
* Access (find a specific key k(i) a particular level)

Thanks for pointer to documentation and/or code,
Mathieu

You could use a standard container (probably, std::set, std::map,
std::list, or std::vector) in conjunction with the Composite design
pattern, which calls for a class that represents both the primitive
(i.e., key and value) and their containers (e.g., your k4).

Cheers! --M

[mathieu]

Thanks for your comment. But I am not convinced sorry :-P
I posted my question with lot more details to comp.programming

Thanks anyway !
-M