Multiple keys data structure

[Djerba]

Hi,

What is the best data structure to use when you have a lot of data to process and you need to later search using different keys. Say you have to store tons of data of this form

struct node
{

string name;
Date date;
Number number;
};

Once you have stored this data you want to get all data for a given name or Date or number.

Also if anyone knows of good data structures in C++ groups please let me know.

Thanks
Jack

[weaknessforcats]

Do you have a SQL database handy?

Otherwise you will need to build the database and the association tables yourself. Multiple indexes to the same element s tricky since i the element is deleted tor moved, all of the keys to it become invalid.

If you have to do this yourself, manage the database in a linked list and do not delete or move items after they are added. You just mark a node as emtpy but it still remains in the list. This will require an index of empty nodes. I might even go so far as to suggest you generate an empty list and use the index of empty nodes to access the next available node in the list.

This empty list can be an STL map container. The key is node position (which never changes) and the valus is a pointer( or handle) to the node

When you need add an element in the list, you read the map of empy nodes for the first node available. You delete the key from the map.

Then using multimaps for a) name + pointer to node
b) date + pointer to node
c) number + pointer to node

you add keys using the values of the node you just changed.

For removal, a) you add the node to the map of empty nodes.
b) you read the other multimaps using the values of the node
and delete every key that has a pointer to the node being deleted.

For change, delete all keys using the original values and add new keys for the new values.

This approach has the advantage that if you run out of empty nodes, you can add more nodes to the end of the list and add keys to them to the map of empty nodes.

Also, the linked list can be more than one list.

Also, you can add members to your struct because you can always create new multimaps for the new members.

You might consider keeping the node number in the node itself for reference during the add/change/revise operations.

Do all of this using a class to avoid propagating the database code thorughout the application. Be sure it is self-contained.

Finally, consider a SQL inteface to your database. That is, instead of having users call member functions, have then submit an SQL query that youy can parse yourself.

I hope that if you are using Windows that you use SQL Server or Access instead of reinventing the wheel. On Unix, you can call Oracle directly from C++ using Oracle's Pro-C.

Good luck.

[Djerba]

Hi,

Thank you very much - this looks promising. can you please give more hints on how to implement this in C++. I do not have a database of any kind, this is for an embedded system and I am new to data structures and algorithm - I'm trying to get up to speed if anyone knows of a good book or news group please let me know.

Thanks agin and I hope to hear from you soon.

Do you have a SQL database handy?

Otherwise you will need to build the database and the association tables yourself. Multiple indexes to the same element s tricky since i the element is deleted tor moved, all of the keys to it become invalid.

If you have to do this yourself, manage the database in a linked list and do not delete or move items after they are added. You just mark a node as emtpy but it still remains in the list. This will require an index of empty nodes. I might even go so far as to suggest you generate an empty list and use the index of empty nodes to access the next available node in the list.

This empty list can be an STL map container. The key is node position (which never changes) and the valus is a pointer( or handle) to the node

When you need add an element in the list, you read the map of empy nodes for the first node available. You delete the key from the map.

Then using multimaps for a) name + pointer to node
b) date + pointer to node
c) number + pointer to node

you add keys using the values of the node you just changed.

For removal, a) you add the node to the map of empty nodes.
b) you read the other multimaps using the values of the node
and delete every key that has a pointer to the node being deleted.

For change, delete all keys using the original values and add new keys for the new values.

This approach has the advantage that if you run out of empty nodes, you can add more nodes to the end of the list and add keys to them to the map of empty nodes.

Also, the linked list can be more than one list.

Also, you can add members to your struct because you can always create new multimaps for the new members.

You might consider keeping the node number in the node itself for reference during the add/change/revise operations.

Do all of this using a class to avoid propagating the database code thorughout the application. Be sure it is self-contained.

Finally, consider a SQL inteface to your database. That is, instead of having users call member functions, have then submit an SQL query that youy can parse yourself.

I hope that if you are using Windows that you use SQL Server or Access instead of reinventing the wheel. On Unix, you can call Oracle directly from C++ using Oracle's Pro-C.

Good luck.

[weaknessforcats]

I cannot provide a code solution. My reply gave you some suggestions. Until you start a code solution and get stuck, I cannot help you further.