Trying to use Hash_set

Hi,

I have been reading about hash_set and now is questions and doubts time. First, let me explain what I am trying to do.

I have a class with different variables and functions. I want to store the objects in the hash_set using the merge of two variables as a key, but I am not sure which is the best way to do that. The variables are the following:

Code:

---


unsigned int seqNumber;
MAC origin;

typedef struct        /* in order to use MAC addresses */
{
  unsigned char addr[6];
} MAC;

---

Therefore, I need to define a hash function for them. Any suggestion?

I understand the case of inserting integers in the hash_set, because the variable is the key:

Code:

---

hash_set<int, hash<int>, eqstr> hs;

---

If I want to store pointers to the objects of the class being the key a variable of the object, how can I do that? Something like this maybe?

Code:

---

hash_set<myclass, hash<myclass.somevalue>, eqstr> hs;

---

Finally, I don't know if I understand this example:

Code:

---

hash_set <int, hash_compare <int, greater<int> > > hs2;

---

Is there any possibility of using a hash_set ordered by a value that is not the key?

Thank you in advance!!

p.d.: maybe, someone can recommend me a good book with examples or a web page, I am confused...

Quote:

---

Originally Posted by darksoul_e

I have been reading about hash_set and now is questions and doubts time.

---

Just checking: hash_set is not part of the C++ standard library, though it is available as an SGI extension. Are you sure you can/want to use hash_set? If a TR1 implementation is available, you should consider using std::tr1::unordered_set instead, since it will be incorporated into the next version of the C++ standard library. If a TR1 implementation is not available, but Boost is available, then you should consider using boost::unordered_set since it formed the basis for std::tr1::unordered_set (but if Boost is available, then arguably a TR1 implementation is available since Boost has wrappers for TR1).

Quote:

---

Originally Posted by darksoul_e

If I want to store pointers to the objects of the class being the key a variable of the object, how can I do that?

---

Sorry, but I do not understand what you mean by "store pointers to the objects of the class being the key a variable of the object".

Quote:

---

Originally Posted by darksoul_e

Is there any possibility of using a hash_set ordered by a value that is not the key?

---

Are you thinking of a map instead of a set?

I am writing the code for Symbian using open c/c++, and I realized that I can use hash_set. Is there something similar that ensures portability? I do not mind using another data storage container.

Sorry about the first explanation. I will try to explain it better:

I desire to store my objects efficiently. The value that distinguish an object from another is the combination of the sequenceNumber and the MAC. (I can have more than one identical sequenceNumber, but the MAC will be different). I need fast data access in order to find my object directly. I do not desire to search in an array one by one, the system should be efficient. Using hash_set, if I hash(key) I will get the value (or that is what I understood). Therefore, I will have something that stores all my objects and the key that distinguish an object from another will be a variable inside each object (myclass.mykeyvariable).

Perhaps, there is a better way to do this.

Quote:

---

Originally Posted by darksoul_e

I am writing the code for Symbian using open c/c++, and I realized that I can use hash_set. Is there something similar that ensures portability? I do not mind using another data storage container.

---

You can check if the compiler has a TR1 implementation available. I am not sure if the Boost unordered containers implementation supports your compiler.

Quote:

---

Originally Posted by darksoul_e

I desire to store my objects efficiently. The value that distinguish an object from another is the combination of the sequenceNumber and the MAC. (I can have more than one identical sequenceNumber, but the MAC will be different). I need fast data access in order to find my object directly. I do not desire to search in an array one by one, the system should be efficient. Using hash_set, if I hash(key) I will get the value (or that is what I understood). Therefore, I will have something that stores all my objects and the key that distinguish an object from another will be a variable inside each object (myclass.mykeyvariable).

---

If you want the combination of the sequenceNumber and the MAC to be the key, but you have other data associated with that key, then what you want is a hash_map, not hash_set.

I will check if it is compatible.

I do not understand what do you mean with "other data associated with that key". Clarifying what I desire to store, I show you the basic parts of the class:

Code:

---

class myclass
        {
public:
        // not interesting
private:
        bool status; //active or inactive
        unsigned char hops;
        unsigned int seqNumber;
        MAC origin;
        unsigned int TTL;
        };

---

I will use the MAC and the seqNumber as the key. Are you sure that is better using hash_map instead of hash_set?

By the way, can I arrange the objects somehow using the TTL value? It would be very useful for me.

Thank you in advance, and thank you for the replies :)

A map is appropriate if the lookup object is separate from the object containing the interesting data. If all the fields are in the same object, a set seems more appropriate.

However, there's a reason why TR1 calls it's hash table implementation "unordered_set/map". Hash tables have no notion of ordering. So while you *could* order these things by TTL, you'd need to use a second data structure to do it.

The std::map and std::set are ordered containers, by contrast. Slightly slower to access on average (but not significantly so in most cases), but they have a better worst-case bound.

Oh, if they are all part of the same object then hash_set should be appropriate. I thought that the sequence number and MAC were going to be combined into some key object.

Quote:

---

Originally Posted by darksoul_e

By the way, can I arrange the objects somehow using the TTL value? It would be very useful for me.

---

A hash table does not really have order. What you can do is to create say, a std::set (or other balanced binary tree based set) that stores pointers to these objects, but the pointers are ordered according to the TTL of these objects. You can use this set as an index to find the object based on TTL, or otherwise access them in sorted order according to TTL.

Good, so if I want to use a hash_set (referring to my first post), does anybody know how can I do it?

I do not know if I have understood the last part. Are you suggesting to use the hash_set to store pointers to all the data and the set to store the same pointers in an ordered way?

Thank you!

I would suggest storing the objects themselves in a std::set ordered by TTL, and then store pointers to those objects indexed by seqNumber and MAC in a hash_map (or underordered_map).

The reason why is because the pointers need to be stable; you can't have the objects moving around unexpectedly in memory. I know that std::set assures this won't happen, but I'm not sure what guarantees hash_map or hash_set provide.

Thank you for the reply!

Now I have to check if I can use tr1/hash_set in Symbian. Otherwise, if hash_set is not part of the standard, I can have problems of portability in my code.

Where can I check what is part of the standard and what is going to be part of it?

If your compiler doesn't throw an error at you when you #include <tr1/unordered_map> (or <unordered_map>), then it supports either TR1 or C++0x. If it does throw an error, you need to look at other options.

It does not work. :( Is there any data structure similar to hash_set within the standard? I can use hash_set, but if I want to port my code to another platform I do not know if I am going to have problems. Is not part of the standard but, is not supported in other platforms?

std::set and std::map are not hash tables, but in most cases they will provide similar performance, and in the interface is almost identical. The primary difference is that your class needs to define operator< rather than needing to define the hash() function.

Quote:

---

Originally Posted by darksoul_e

Is there any data structure similar to hash_set within the standard?

---

Not yet, but as we mentioned there is in the TR1 extension. However, yesterday Yuriy Krasnoschek (rider at jazzgames dot net) posted to the Boost users mailing list about "efforts to make several libraries from boost compile and run on Symbian Series 60 with winscw (Code warrior by Nokia)". After modification to the Boost source, he/she claimed that:

Quote:

---

Originally Posted by Yuriy Krasnoschek

Libraries that ran on S60 3rd Edition Feature Pack 2 + are:
thread, date_time, system, regex, asio (partially) and of cource libraries that don't depend on platfom so much smart_pointers / type_traits / integer / etc.

---

It is possible that boost::unordered_set is among them, along with the TR1 wrapper, thus you could contact him/her for the patch and thus use std::tr1::unordered_set.

On the other hand, Lindley has a point: despite having worse average case complexity, the balanced binary tree based set and map class templates that are already in the C++ standard library may be sufficient for your purposes.

I have been reading how to use set. It seems easier to use, but if I have a lot of objects I am worried about the performance. Using hash_set it takes a constant amount of time for each query, but in set is logarithmic... Can I merge the mac and the seqNumber as a char array and use it as the key?

Thank you for your replies, they are very useful for me :D