If you can help... (map::find and map::insert)

[Ricardo]

I have seen a lot of comments about this problem on the lists and,
even as I tried to implement the proper corrections, I was really
unable to do so... (or my problem is somehow different...).

I have a map that uses a class as its key.. something like this:

struct SFlowId {
uint32_t ingressInterface;
uint16_t VLAN;
uint32_t sourceIP;
uint32_t destinationIP;
uint16_t sourcePort;
uint16_t destinationPort;
};

I defined a < function to compare those values....

// this is short cause the problem occurs both with 2, 3 or 4
parameters being compared (anything more than 1 causes my problem).
bool operator<(const SFlowId &left,const SFlowId &right) {
return (left.destinationIP < right.destinationIP) ||
(!(left.destinationIP < right.destinationIP) && (left.sourceIP <
right.sourceIP));
}

Here is my map... :
map<SFlowId,SFlowInfo> fFlows;

After inserting some pairs on the map, I have the most strange
problem: (a) when I try to find a pair that is actually already inside
the map, I get a result with the find method that says that what I am
looking for is brand new.... (b) on the other way, if I try to insert
that same pair, using the same key, insert returns that the pair is
already on the map and no new pair is inserted on the map...

I know the < operator must obey certain rules and I do think that the
function is properly impåemented to fullfill those requirements.

The code I use is something like this:

SFlowId flid;
// just initialize the key values... omitted ...
flid.TOS = .....
map<SFlowId,SFlowInfo>::iterator it;
it = fFlows.find(flid);
if (it == fFlows.end()) {
// NOT FOUND ON THE MAP... MUST BE A NEW VALUE....
// create the value associated with the key....
pair<map<SFlowId,SFlowInfo>::iterator,bool> ret;
ret = fFlows.insert(pair<SFlowId,SFlowInfo>(flid,info));
if (ret.second) {
// REALLY A NEW VALUE...
} else {
// NOT A NEW VALUE
}
} else {
// FIND INDICATES ITS IS A NEW VALUE...
}

With this code, I often get results where find indicates a have a new
pair and insert says otherwise....
Can you help me understanding what is going on here?
If I use a single value in the comparison, I have no trouble at all...

I know I can just use insert in my code (and probably in my case this
will be better indeed), but I would like to understand what I am doing
wrong and how can two different methods behave in a different way....

Thanks in advance,
Ricardo

 

[Nils]

Hello,

you have to do the check for each member of your class separately, so
that the first member is the most significant one where the others are
less significant.

bool operator<(const SFlowId &left,const SFlowId &right)
{
if( left.foo < right.foo ) return true;
if( left.foo > right.foo ) return false;
if( left.bar < right.bar ) return true;
if( left.bar > right.bar ) return false;
if( left.xxx < right.bar ) return true;
/* if( left.xxx > right.xxx ) */ return false;
}

Regards,

Nils

 

[James Kanze]

Note that you have a redundancy here: !(left.destinationIP <
right.destinationIP) is always true if the first part of the expression
is not (left.destinationIP < right.destinationIP).

This already hints
that you have written something meaningless here. A proper weak ordering
predicate would be:

bool operator<(const SFlowId &left,const SFlowId &right) {
return (left.destinationIP < right.destinationIP) ||
((left.destinationIP == right.destinationIP) &&
(left.sourceIP < right.sourceIP));

or
return (left.destinationIP < right.destinationIP
|| ( ! (right.destinationIP < left.destinationIP)
&& left.sourceIP < right.sourceIP ) ;

That way, you only need to use '<'.

 

[Joe Greer]

// this is short cause the problem occurs both with 2, 3 or 4
parameters being compared (anything more than 1 causes my problem).
bool operator<(const SFlowId &left,const SFlowId &right) {
return (left.destinationIP < right.destinationIP) ||
(!(left.destinationIP < right.destinationIP) &&
(left.sourceIP <
right.sourceIP));
}

The problem is that this doesn't produce a strict ordering. Note that if
left.destinationIP >= right.destinationIP then the comparison relys on
sourceIP and doesn't really involve destinationIP. I thnk that what you
really want is something like:

return (left.destinationIP < right.destinationIP)
|| ((left.destinationIP == right.destinationIP)
&& (left.sourceIP < right.sourceIP));

That way, if left.destinationIP > right.destinationIP you return false.

joe

 

[Ricardo]

The problem is that this doesn't produce a strict ordering.  Note that if
left.destinationIP >= right.destinationIP then the comparison relys on
sourceIP and doesn't really involve destinationIP.  I thnk that what you
really want is something like:

return (left.destinationIP < right.destinationIP)
   || ((left.destinationIP == right.destinationIP)
      && (left.sourceIP < right.sourceIP));

That way, if left.destinationIP > right.destinationIP you return false.

joe

So, if I change the code to something like that:
bool SFlowId:perator<(const SFlowId &to) const {
if (this->destinationIP < to.destinationIP)
return true;
else if (this->destinationIP > to.destinationIP)
return false;
if (this->sourceIP < to.sourceIP)
return true;
else if (this->sourceIP > to.sourceIP)
return false;
if (this->destinationPort < to.destinationPort)
return true;
else if (this->destinationPort > to.destinationPort)
return false;
if (this->sourcePort < to.sourcePort)
return true;
else if (this->sourcePort > to.sourcePort)
return false;
if (this->protocol < to.protocol)
return true;
else if (this->protocol > to.protocol)
return false;
if (this->TOS < to.TOS)
return true;
else if (this->TOS > to.TOS)
return false;
if (this->ingressInterface < to.ingressInterface)
return true;
else if (this->ingressInterface > to.ingressInterface)
return false;
if (this->destinationMAC < to.destinationMAC)
return true;
else if (this->destinationMAC > to.destinationMAC)
return false;
if (this->sourceMAC < to.sourceMAC)
return true;
else if (this->sourceMAC > to.sourceMAC)
return false;
if (this->VLAN < to.VLAN)
return true;
return false;
}

it should work? There are several fields, indeed...

Anyways, besides that problem... I still would like to understande, if
you please, WHY insert behaves properly and find do not... even with
the function not properly written...

Thanks for now and awaiting for your comments
Ricardo

 

[Joe Greer]

it should work? There are several fields, indeed...

That should work, though it might be overkill. You only need enough fields to guarantee
uniqueness or to obtain the order you want if using multi-maps.

Anyways, besides that problem... I still would like to understande, if
you please, WHY insert behaves properly and find do not... even with
the function not properly written...

Thanks for now and awaiting for your comments
Ricardo

Well, the honest answer is that insert isn't really working correctly. The difference is
that you can't tell tell with insert. Insert basically searches through the tree until it
"thinks" that it has found the correct spot to insert the item. Then it merrily does that
insertion. However, insert makes no attempt to verify that where it inserted the item kept
the collection as a whole in a logically correct state. Lookups (find) on the otherhand,
require that the whole collection be logically consistent in order to be able to find the
individual items. If there is an inconsistency then find() will follow the tree to where
it thinks the item should be, but it may not find it.

You see the difference? Insert doesn't really care if it can find the item, it is just
going to plop its item down where it thinks it belongs. Find, on the otherhand, does care
because if the item isn't where it belongs, find is going to report it missing.

Hope that helps,
joe

 

[Joe Greer]

So, if I change the code to something like that:
bool SFlowId:perator<(const SFlowId &to) const {
if (this->destinationIP < to.destinationIP)
return true;
else if (this->destinationIP > to.destinationIP)
return false;
if (this->sourceIP < to.sourceIP)
return true;
else if (this->sourceIP > to.sourceIP)
return false;
if (this->destinationPort < to.destinationPort)
return true;
else if (this->destinationPort > to.destinationPort)
return false;
if (this->sourcePort < to.sourcePort)
return true;
else if (this->sourcePort > to.sourcePort)
return false;
if (this->protocol < to.protocol)
return true;
else if (this->protocol > to.protocol)
return false;
if (this->TOS < to.TOS)
return true;
else if (this->TOS > to.TOS)
return false;
if (this->ingressInterface < to.ingressInterface)
return true;
else if (this->ingressInterface > to.ingressInterface)
return false;
if (this->destinationMAC < to.destinationMAC)
return true;
else if (this->destinationMAC > to.destinationMAC)
return false;
if (this->sourceMAC < to.sourceMAC)
return true;
else if (this->sourceMAC > to.sourceMAC)
return false;
if (this->VLAN < to.VLAN)
return true;
return false;
}

One other thing... You need to decide how you want to lookup your data.
The above looks like every field in the structure. If you know all that,
there probably isn't any reason to look it up. You don't really need
everything for your key. Just enough to be unique within the context of
your application. For example, if you know that you will only have one
entry for any given sourceIP/port combination, that would be sufficient for
the insert/find mechanism. The problem with the previous code was that the
fields weren't used consistenly enough to give a good sorting order. The
idea in general is that you need to be able to say that if A < B and B < C
than A < C. With your previous order, that wasn't always true. The above
looks correct, but may be overkill.

joe

 

[Ricardo]

One other thing...  You need to decide how you want to lookup your data..  
The above looks like every field in the structure.  If you know all that,
there probably isn't any reason to look it up.  You don't really need
everything for your key.  Just enough to be unique within the context of
your application.  For example, if you know that you will only have one
entry for any given sourceIP/port combination, that would be sufficient for
theinsert/find mechanism.  The problem with the previous code was that the
fields weren't used consistenly enough to give a good sorting order.  The
idea in general is that you need to be able to say that if A < B and B < C
than A < C.  With your previous order, that wasn't always true.  The above
looks correct, but may be overkill.

joe

First of all, tks a lot for your help!
Maybe I can get 2 or 3 fields off the key, but I do really need so
many items to classify my map, cause I have a struct that show some
info about a network flow, and to properly identify an unique flow I
need all that info (or most of it, at least).
But as I always understood, insert do return a value showing if it has
or has not find an already existing entry in the map. For what you
said, I do understand that it only searches till the point it thinks
the member is new, am I right?

 

[Joe Greer]

First of all, tks a lot for your help!
Maybe I can get 2 or 3 fields off the key, but I do really need so
many items to classify my map, cause I have a struct that show some
info about a network flow, and to properly identify an unique flow I
need all that info (or most of it, at least).
But as I always understood, insert do return a value showing if it has
or has not find an already existing entry in the map. For what you
said, I do understand that it only searches till the point it thinks
the member is new, am I right?

Correct. It makes no effort to validate the entire collection. The design
decision was made to emphasize efficiency and assume that the user was
using it properly. This is probably best for the vast majority of the
cases where it is used.

joe