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

Logarithmic time is still very fast. Say it takes N time when you have 1000 objects. Now increase the size so you have a million objects----1000 times as many. Access will now take approximately N*2 time.

You would typically design a key object to contain just the relevant data. If you only need two things, a std::pair may be good enough.

Quote:

---

Originally Posted by darksoul_e

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...

---

The worse average case complexity can be mitigated somewhat by speeding up the comparison, e.g., to compare a single value instead of an array. Actually, what you could do is to create a container class to serve as an abstraction such that you can first use a set or map, then if later you find the performance intolerable, you could switch the implementation to use a hash table while maintaining the interface.

Quote:

---

Originally Posted by darksoul_e

Can I merge the mac and the seqNumber as a char array and use it as the key?

---

You do not actually have to merge them if you want to use a set. You just need to define operator< to compare objects of your class type according to mac and seqNumber and the set will make use of it.

Quote:

---

Originally Posted by darksoul_e

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

---

You're welcome :)

Now I am trying to deal with set and my idea of implementation. I want my set sorted by the TTL, buf if I use it in my comparator class, the set will only accept different TTLs.

Code:

---

class myclass
        {
public:
        MAC getOrigin();
        unsigned int getSeqNumber();
        unsigned int getTTL();

private:
        bool status; //active or inactive
        unsigned char hops;
        unsigned int seqNumber;
        MAC origin;
        unsigned int TTL;
        };

---

This is my try, but it only takes into account the TTL.

Code:

---

class comp_myClass {
public:
    bool operator()(REQFobj c1, REQFobj c2) const
    { return (c1.getTTL() < c2.getTTL()); }
};

set<REQFobj, comp_myClass> mySet;

---

Should I overload the operator == and < ? I am thinking in overloading == in order to find my object with MAC and seqNumber, and < in order to organize using the TTL. Do you know how can I do this?

Thank you in advance!

I realized that set only uses < to find and organize the data, so I will use 2 sets with the same pointers to my data. This way, I will have the same data organized by TTL and by my key (a merger of MAC and seqNumber).

As I said before, I am using 2 sets to store the pointers. The first one is working now, which stores all the objects sorted by the timestamp. This is the code:

Code:

---

set <myclass*,CompTimeStamp> s;

---

And the comparator function, that uses timestamps instead of using the TTL:

Code:

---

class CompTimeStamp {
public:
    bool operator()( myclass* c1, myclass* c2) const
    {
    if(c1->gettsTTL().tv_sec < c2->gettsTTL().tv_sec) return true;
    else
            if(c1->gettsTTL().tv_sec == c2->gettsTTL().tv_sec)
                    {
                    if(c1->gettsTTL().tv_usec < c2->gettsTTL().tv_usec) return true;
                    }
    return false;
   
    }
};

---

Now I desire to store the same objects in the second one, but with the aim of finding them in a fast way.

Code:

---

set <myclass*,CompToFind> s;

---

In the function CompToFind I should specificate first the sequence number and then the MAC, which is a char[6] array.

Code:

---

class CompToFind {
public:
    bool operator()( myclass* c1, myclass* c2) const
    {
    MAC x,y;
    if(c1->getSeqNumber() < c2->getSeqNumber()) return true;
    else
            if (c1->getSeqNumber() == c2->getSeqNumber())
                    {
                // MAC comparison

                    }
    }
};

---

How can I use find with my objects? How should I write the MAC comparison? Maybe, something like comparing char by char, if it is bigger return true...

Now myclass is:

Code:

---

class myclass
        {
public:
        timeval gettsTTL();
        MAC getOrigin();
        unsigned int getSeqNumber();
private:
        bool status; //active or inactive
        unsigned char hops;
        unsigned int seqNumber;
        MAC origin;
        timeval tsTTL;
        };

---

I do not find any information about find using an object variable.

Could someone help me? Thank you in advance

Quote:

---

Originally Posted by darksoul_e

I do not find any information about find using an object variable.

---

std::find_if()

http://www.sgi.com/tech/stl/find_if.html

Regards,

Paul McKenzie

Thank you, but what I desire is something like an example with a custom function and not with the basic types of data (int, double, char...). I will continue searching.

Quote:

---

Originally Posted by darksoul_e

Thank you, but what I desire is something like an example with a custom function and not with the basic types of data (int, double, char...). I will continue searching.

---

And that is what the link descirbes.

The only way find_if() works is by using a predicate, not a specific data type. A predicate is a function or function object (functor).

Code:

---

struct FindSomething
{
    FindSomething( /* any parameters you want to use */
  {
        /* any code */
  }

  bool operator() ( /* the type being checked ) const
  {
      /* if the type being checked is the one I want ... */
        return true;
    /* else return false */
  }
};

int main()
{
    /* ... */
  FindSomething fs( /* parameters  */ )
  whatever::iterator it = std::find_if( xxx.begin(), xxx.end(), fs);
  if ( it != xxx.end() )
  {
      /*  *it points to the item found */
  }
}

---

The FindSomething is a functor. Since it is a struct (or class), it can practically do anything you want it to do, any members can be added to it, etc. The only other way to use find_if is to give it a function pointer, but a function pointer isn't as powerful or as user-definable as a function object.

Regards,

Paul McKenzie

Ok!! I will check the predicate issue, thank you!