CODEWITHSUNDEEP
c++data-structures
James Bond
James Bond

Reputation: 7913

What's the data structure that can handle random access and key-search?

I am working on an online data stream analysis project and I have a very interesting problem:

I need to maintain (at least) a look-up-table, something like std::map <user_id, user>, where 

struct user{
   int user_id;
   bool sex;
   int age;
   double score;
};

New users will be freqently added and deleted, using the user_id as a key. I guess this is quite easy.

However, I also need to classify the users by sex and age, something like a combined key. The output of the program will intensively query something like 'give me all the male users who are 34 years old'. Please note that this part is very complexity sensitive.

I took a look at boost::multi-index and I found it's like a black box and the templates really confused me.

Is there a way I can tailor a multi-index style data structure just by myself? Anyone knows how to implement it?

Upvotes: 1

Views: 124

Answers (2)

Pandrei
Pandrei

Reputation: 4951

personally I would build my own data structure; if it's a problem you found online - I think that is the whole point...

here is a idea: since age has a limited range( like 0..100 ), build a array of pointers user * database[100]; use the index to keep the data sorted by age; e.g. dataBase[20] will hold all the users of age 20. For all the users of a certain age, you can use a linked list to hold all the users, or build a binary tree and sort them by sex (M to the left, F to the right)..or anything you can think of...

This way, getting the users of age x is O(1)+ O(count). And even more complex queries about age+sex or age+score become more efficient. Actually worst case scenario is for queries that don't involve age, since you would have to scan all of the array.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234665

Seriously, which do you think is easier?

1) Learn Boost by reading the documentation, searching the internet for examples.

2) Attempting to build your own multi-index class.

When I say easier, I mean easier to (i) program, (ii) maintain, (iii) hand over to a colleague.

Learn Boost! Good luck.

[btw, Boost is often regarded as a testing bed for new features that eventually become part of the C++ standard libraries. For example, shared_ptr.]

Upvotes: 3

Related Questions