Trying to use Hash_set

[Lindley]

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:air may be good enough.

[laserlight]

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.

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.

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

You're welcome

[darksoul_e]

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.

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.

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!

[darksoul_e]

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

[darksoul_e]

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:

set <myclass*,CompTimeStamp> s;

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

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.

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.

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:

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

[Paul McKenzie]

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

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

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

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

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

[darksoul_e]

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