STL set/map find/find_if

[ekhve394]

Hi!

I am using STL data structures in my project. The main point is that I desire to get a sorted data structure where I can find an object.

Consider something similar to:

struct mypair{
int ID;
timeval when;
};

class Comp {
public:
    bool operator()( mypair c1, mypair c2) const
    { 
    if(c1.when.tv_sec < c2.when.tv_sec) return true;
    else
    	if(c1.when.tv_sec == c2.when.tv_sec)
    		{
    		if(c1.when.tv_usec < c2.when.tv_usec) return true;
    		}
    return false;
    
    }
};
set<mypair,Comp> s;

This way my set is sorted by the timestamp, but now I want to check if a particular ID is in my set and find it.

Is this possible?

I have solved it using two different maps, one sorted by the ID and the other by the timestamp. Therefore, I have to insert in both maps, which is not a good solution from the point of view of performance.

Does anyone have another idea?

Thank you in advance!

[jsmith]

If you have the boost libraries available to you, I'd recommend:

set<mypair, Comp>::iterator e = std::find_if( s.begin(), s.end(),
    &boost::lambda::_1->*&mypair::ID == 42 );

If you don't, then just write another function object and pass it to
std::find_if() instead of my lambda expression. (Either approach
is O(n) lookup)

However, if you find that you need to sort by timestamp and look up
by ID, and you have the boost libraries available, consider using a
boost::multi_index_container instead.

[ekhve394]

Thank you for your fast reply jsmith!

I'm afraid I can't use boost libraries. In any case, I trying to get a good lookup time but I don't know if using find_if will help me. Find() provides logarithmic time lookups, but if I use find_if(), the lookup time will be the same as iterating the data structure, am i right?

I will try to do my own function and see if it works :)

[ekhve394]

How can I write the predicate using bind2nd to pass the ID? I have written this, but I don't know how to use it.

class CompIDTask {
public:
    bool operator()( task* c1, task* c2) const
    { 
    return (c1->getID() == c2->getID());
    
    }
};

[jsmith]

No matter what you do, lookup based on any criterion other than the sort criterion of a set is linear.