std::map

[EnTn]

Hi Everyone...

I've been trying to use a std::map to do some storage. Basically, i'm
storing double values using a Key Object. The Key object is quite
simple and is just a pair of int's (conceptually these are 2d coords).

[ I'm not using a true stl or stlport, instead I'm using MS's native
stuff (MSVC6).]

My problem is: I have setup a simple test probgram that populates a
map with 9 <key,value> pairs. When I try to query the map using
map::find(key) i get failures but when I query using a combination of
map::insert and map:perator[] my tests pass....


Is there a problem in my implementation of HorizonKey? (especially
with operator<() ).
Or am I not using the map correctly?
Or is this some non-standard behaviour from the MS stuff(?). ie.
should this work in a true stl implementation?

I've included my code below.

Thanks for any help or advice....
Cheers,
Steve






<CODE>
//
// First of all my simple key object.
//
class HorizonKey
{
public:
HorizonKey(const size_t& inl, const size_t& xl) :
inl_(inl),
xl_(xl)
{
}

HorizonKey(const HorizonKey& r) :
inl_( r.inl_ ),
xl_( r.xl_ )
{
}

const HorizonKey& operator=(const HorizonKey& r)
{
inl_ = r.inl_;
xl_ = r.xl_;
}

bool operator==(const HorizonKey& r) const
{
return ((inl_ == r.inl_) && (xl_ == r.xl_));
}

bool operator<(const HorizonKey& r) const
{
if (inl_ < r.inl_)
{
return true;
}
else if (xl_ < r.xl_)
{
return true;
}
return false;
}

private:
size_t inl_;
size_t xl_;
};



//
//
// To test the behaviour of a map using this key I wrote the following
code
// in a test program.
//
// NOTE: this test works fine...!
//
//
std::map<HorizonKey, double> mymap;

typedef std::map<HorizonKey, double>::const_iterator
HorizonMapIterator;
typedef std:air< HorizonKey, double > HorizonMapPair;
typedef std:air< HorizonMapIterator, bool > HorizonMapReturnPair;

HorizonMapReturnPair pr;
double val = 1.0;

//
// 1st loop - populate map with 9 elements,each with unique value.
//
int inl, xl;
for (inl = 0; inl < 3; ++inl)
{
for (xl = 0; xl < 3; ++xl)
{
HorizonMapPair pin( HorizonKey(inl, xl), val );
pr = mymap.insert( pin );

_test( pr.second );

val += 1.0;
}
}


//
// Test - verify the contents....
//
_test(mymap.size() == 9);

val = 1.0;
for (inl = 0; inl < 3; ++inl)
{
for (xl = 0; xl < 3; ++xl)
{
HorizonMapPair pin( HorizonKey(inl, xl), val );
pr = mymap.insert( pin );

//
// We should not be inserting any new elements into the map
//
_test( pr.second == false );


HorizonKey k(inl, xl);
double mapval = mymap[k];

//
// check for a value match
//
_test( mapval == val );

val += 1.0;
}
}



//
//
// BUT if I now use the map::find() member function in my tests, I get
// failures for keys initialised as k(1,0), k(1,1), k(2,1), k(2,2)
//
// Below is the second loop of the test code re-written using find...
//
val = 1.0;
for (inl = 0; inl < 3; ++inl)
{
for (xl = 0; xl < 3; ++xl)
{
HorizonKey k(inl, xl);
HorizonMapIterator itr = mymap.find( k );

HorizonKey newk = itr->first;
double newval = itr->second;

_test( itr != mymap.end() );
_test( newval == val );

val += 1.0;
}
}




</CODE>

 

[Ali Cehreli]

My problem is: I have setup a simple test probgram that populates a
map with 9 <key,value> pairs. When I try to query the map using
map::find(key) i get failures but when I query using a combination of
map::insert and map:perator[] my tests pass....


Is there a problem in my implementation of HorizonKey? (especially
with operator<() ).

Yes; the operator< does not define the ordering correctly.

<CODE>
//
// First of all my simple key object.
//
class HorizonKey
{
public:
HorizonKey(const size_t& inl, const size_t& xl) :
inl_(inl),
xl_(xl)
{
}

HorizonKey(const HorizonKey& r) :
inl_( r.inl_ ),
xl_( r.xl_ )
{
}

const HorizonKey& operator=(const HorizonKey& r)
{
inl_ = r.inl_;
xl_ = r.xl_;
}

You don't need to define the two functions above for this class.

bool operator==(const HorizonKey& r) const
{
return ((inl_ == r.inl_) && (xl_ == r.xl_));
}

bool operator<(const HorizonKey& r) const
{
if (inl_ < r.inl_)
{
return true;
}
else if (xl_ < r.xl_)
{
return true;
}
return false;
}

The above function returns true for (1,1)<(2,0), but it return true for
(2,0)<(1,1) too! That is against what std::map expect from that function.

Try this:

else if ((inl_ == r.inl_) && (xl_ < r.xl_))

Ali

 

[EnTn]

else if ((inl_ == r.inl_) && (xl_ < r.xl_))

Thanks for the reply Ali.

The above does indeed make my tests pass....
However, on a larger scale I am getting inconsistent behaviour in my
program which I think is down to my use of the map or definition of
the key being in error...


Interestingly enough this:

bool operator<(const HorizonKey& r) const
{
return !((inl_ >= r.inl_) && (xl_ >= r.xl_));
}

also satifies my tests, but causes my program to hang... (looks like
infinite loop in the map code.... )

 

[tom_usenet]

Thanks for the reply Ali.

The above does indeed make my tests pass....
However, on a larger scale I am getting inconsistent behaviour in my
program which I think is down to my use of the map or definition of
the key being in error...


Interestingly enough this:



also satifies my tests, but causes my program to hang... (looks like
infinite loop in the map code.... )

Map only works with a strict weak ordering - crashes and hangs are
common if you don't use such an ordering. Here's the definition:
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

Yours fails because of this:

!((inl_ >= r.inl_) && (xl_ >= r.xl_))
=
!(inl_ >= r.inl_) || !(xl_ >= r.xl_)
=
inl_ < r.inl || xl_ < r.xl_

which clearly isn't antisymetric ((1, 0) < (0, 1) but (0, 1) < (1,
0)). You need to update your test cases to properly test for a strict
weak ordering.

Tom

 

[P.J. Plauger]

Yours fails because of this:

!((inl_ >= r.inl_) && (xl_ >= r.xl_))
=
!(inl_ >= r.inl_) || !(xl_ >= r.xl_)
=
inl_ < r.inl || xl_ < r.xl_

which clearly isn't antisymetric ((1, 0) < (0, 1) but (0, 1) < (1,
0)). You need to update your test cases to properly test for a strict
weak ordering.

Our latest library available at our web site has an "iterator
debugging" option that also tests every call to a strict-weak-
ordering function. If fun(a, b) returns true, the code warns
if fun(b, a) would also return true. This can save many hours
of debugging, not to mention the occasional crash in the field.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[EnTn]

Thanks for the informative reply Tom.

Map only works with a strict weak ordering - crashes and hangs are
common if you don't use such an ordering. Here's the definition:
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

Yours fails because of this:

!((inl_ >= r.inl_) && (xl_ >= r.xl_))
=
!(inl_ >= r.inl_) || !(xl_ >= r.xl_)
=
inl_ < r.inl || xl_ < r.xl_

which clearly isn't antisymetric ((1, 0) < (0, 1) but (0, 1) < (1,
0)). You need to update your test cases to properly test for a strict
weak ordering.

Tom