STL

[dd76]

HI *,

I need some help regarding how to efficiently store some data, so the lookup is faster. I need to use STLs set/map/multimap/hash etc etc. Please let me know your recommendations. Was thinking of multimap, but not sure if there is any other way of doing this. Below is the data that I am interested in -

Information I want to store is as under. Each group has multiple ipaddresses and each ipaddress has its own attributes. Now I need to store many such groups.

I need to be able to lookup and
- make changes to multiple ipaddresses belonging to a group.
- Delete all ipaddresses belonging to a group
- insert new ipaddress to a group
- uplook an ipaddress given a group.


[ group 1 ]
ipaddress 1
int length
int used
....
....
ipaddress 2
.....
.....
[ group 2 ]
....
....

[doug4]

How many such groups? 10? 100? 100000?

How are the groups identified? If there an ID associated with them or are they just a group of lists that is traversed.

First off, I would create a class/struct containing all the info for a single IP address (address, length, used, etc.).

Assuming there is an ID associated with each list, you could use either a multimap<ID, IP Class> or a map<ID, set<IP Class>>. The multimap would allow multiple entries of the same IP address within a particular group, while a set of IP class objects would guarantee unique IP addresses within the group.

All that said, without knowing how the lists are created or accessed, it's pretty difficult to suggest a good design.

[dd76]

Thank you Doug,

- Number of groups is not huge, i guess the max is 100

- Groups are identified by IDs and are integers, forgot to mention that.

- ip addresses are unique within a group.

- While each group is created the parameters provided are as under
[group id, {(peerip address, other attributes), (peer ipaddress2, other attributes) ........}]

- Each group object smart ptr (boost::shared_ptr ) will need to be stored in the STL that we will choose.

[doug4]

Design is all about answering questions and coming up with new questions when the first are answered.

Are the group IDs sequential? Is the set of groups dynamic--will groups be added and subtracted during the run of the program?

If the groups are sequential and relatively static, you might want to just use a vector to contain them. They have fast lookup and don't take up a lot of excess space.

If the group IDs are more arbitrary, you probably need a map or a hash. Since you will only have 100 or so groups, the lookup time in a map shouldn't be noticeably greater than for a hash, so I might recommend that structure.

Depending on how you plan to use the members of the groups, the groups could be sets or maps themselves. If you plan to look up specific IP addresses within a group, I would go with a map keyed by the IP Address. If you will just be iterating through each group, you could go with a set (to guarantee uniqueness) or even a list or vector if the input is can be trusted to be unique. Again, I don't really know how you plan to use the groups.

So, my two suggestions are (approximate code):

If you need to look up individual IP addresses:

typedef std::string IPAddress;
typedef int GroupID;

class IPAttributes{/* "other" attributes */};
typedef std::map<IPAddress, IPAttributes> IPGroup;
typedef std::map<GroupID, IPGroup> IPGroupMap;

If you do not need to look up individual IP Addresses:

typedef std::string IPAddress;
typedef int GroupID;

class IPAttributes{IPAddress addr; /* "other" attributes */};
typedef std::set<IPAttributes> IPGroup;
typedef std::map<GroupID, IPGroup> IPGroupMap;

[dd76]

Cool thank you. This is very helpful.

Sorry this is small change in the requirement, the ipaddress are not unique in the group (considering NAT). So going by your previous reply multimap should work, correct?

I need to look up individual IP addresses aswell.

So do you suggest the below data structure?

typedef std::string IPAddress;
typedef int GroupID;

class IPAttributes{/* "other" attributes */};
typedef std::multimap<IPAddress, IPAttributes> IPGroup;
typedef std::map<GroupID, IPGroup> IPGroupMap;

Thanks in advance

[dd76]

Forgot to answer your other questions

Are the group IDs sequential? Yes

Is the set of groups dynamic--will groups be added and subtracted during the run of the program? Yes

[doug4]

That sounds like a reasonable starting point.

[dd76]

Thank you