Trying to use Hash_set

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!