CODEWITHSUNDEEP
c++data-structures
user1673206
user1673206

Reputation: 1711

data structure advice on c++

I am looking for data structure in c++ and I need an advice.

I have nodes, every node has unique_id and group_id:

1 1.1.1.1
2 1.1.1.2
3 1.1.1.3

4 1.1.2.1
5 1.1.2.2
6 1.1.2.3

7 2.1.1.1
8 2.1.1.2

I need a data structure to answer those questions:

  1. what is the group_id of node 4
  2. give me list (probably vector) of unique_id's that belong to group 1.1.1
  3. give me list (probably vector) of unique_id's that belong to group 1.1
  4. give me list (probably vector) of unique_id's that belong to group 1

Is there a data structure that can answer those questions (what is the complexity time of inserting and answering)? or should I implement it?

I would appreciate an example.

EDIT:

at the beginning, I need to build this data structure. most of the action is reading by group id. insertion will happen but less then reading.

the time complexity is more important than memory space

Upvotes: 5

Views: 229

Answers (5)

Peter - Reinstate Monica
Peter - Reinstate Monica

Reputation: 16112

To me, hierarchical data like the group ID calls for a tree structure. (I assume that for 500 elements this is not really necessary, but it seems natural and scales well.)

Each element in the first two levels of the tree would just hold vectors (if they come ordered) or maps (if they come un-ordered) of sub-IDs.

The third level in the tree hierarchy would hold pointers to leaves, again in a vector or map, which contain the fourth group ID part and the unique ID.

Questions 2-4 are easily and quickly answered by navigating the tree.

For question 1 one needs an additional map from unique IDs to leaves in the tree; each element inserted into the tree also has a pointer to it inserted into the map.

Upvotes: 5

Mario The Spoon
Mario The Spoon

Reputation: 4869

Depends...

How often do you insert? Or do you mostly read? How often do you access by Id or GroupId?

With a max of 500 nodes I would put them in a simple Vector where the Id is the offset into the array (if the Ids are indeed as shown). The group-search can than be implemented by iterating over the array and comparing the partial gtroup-ids.

If this is too expensive and you really access the strcuture a lot and need very high performance, or you do a lot of inserts I would implement a tree with a HashMap for the Id's.

If the data is stored in a database you may use a SELECT/ CONNECT BY if your systems supports that and query the information directly from the DB.

Sorry for not providing a clear answer, but the solution depends on too many factors ;-)

Upvotes: 2

Matt
Matt

Reputation: 15196

First of all, if you are going to have only a small number of nodes then it would probably make sense not to mess with advanced data structuring. Simple linear search could be sufficient.

Next, it looks like a good job for SQL. So may be it's a good idea to incorporate into your app SQLite library. But even if you really want to do it without SQL it's still a good hint: what you need are two index trees to support quick searching through your array. The complexity (if using balanced trees) will be logarithmic for all operations.

Upvotes: 3

Pratik
Pratik

Reputation: 1138

I am not sure of the perfect DS for this. But I would like to make use of a map. It will give you O(1) efficiency for question 1 and for insertion O(logn) and deletion. The issue comes for question 2,3,4 where your efficiency will be O(n) where n is the number of nodes.

Upvotes: 0

Component 10
Component 10

Reputation: 10507

Sounds like you need a container with two separate indexes on unique_id and group_id. Question 1 will be handled by the first index, Questions 2-4 will be handled by the second.

Maybe take a look at Boost Multi-index Containers Library

Upvotes: 0

Related Questions