data type to represent nodes at levels

[rozick1]

Hi

I'm currently writing a library which will store items related in a certain way (x is a parent of y, y is a child of z etc).

I'd like to write a function which returns the items within a certain depth (e.g. find all parents no further than 3 levels away). I'd like to return this in a format so that it is clear which items are at which level e.g.

Level 1 (direct parent): items z,q
Level 2 (indirect parent): items f,l,i
Level 3 (indirect parent): items k,v,c

I've written the function itself but I'm uncertain which data structure to return the result in. Two come to find:

1. a vector of vector<item_type> e.g. the first vector contains (z,q), second (f,l,i) etc

2. a map of <level[int],vector<item_type> e.g. map[3] = k,v,c

I can see the advantages and disadvantages of both. One thing I like about the map is that you start the key at '1' which represents the actual level (unlike vector where the first vector would be [0]).

Comments on either of the above or alternative approaches much appreciated.

Thanks

[dutch]

Does anyone else understand this?
What's up with all the random letters?
We aren't even told what kind of data structure it is.
Presumably a binary tree?

[rozick1]

I thought I explained it clearly but apologies if not. The letters just represent the different items.

[dutch]

I thought I explained it clearly

No thought was involved.

What items?
Give a concrete example of exactly what you are talking about.

[rozick1]

it really doesn't matter what an 'item' is for these purposes, it's a thing which is being stored. treat as a custom type.

[jonnin]

how are the relationships... one to many, one to one, many to many... ?
what kind of operations dominate the processing (insert/deletes? fetch? relational access (groups that are related somehow fetches))?
what kind of data volume (before doing anything exotic for performance, if you only have like 100 entries, anything will do..)

anything else you can share about how it will be used? Or if its a generic thing where you don't know the use case, what is the purpose of it?

[keskiverto]

Overall, the data sounds to form a directed graph. The operation returns a subset. While a (smaller) directed graph (with same data structure as the original graph) could be returned, the point seems to be to get the subset in format suitable for specific type of iteration.

Choice of structure should be based on how the result is gathered and how it will be used.

[Enoizat]

a map of <level[int],vector<item_type> e.g. map[3] = k,v,c

What’s the advantage compared to a std::unordered_map?