-
March 31st, 2009, 08:14 AM
#1
STL Map Iteration Question
I have an STL map that uses a structure as a key:
Code:
typedef struct _RC_ {
UINT R;
UINT C;
} RC;
typedef struct _Data_ {
int data1;
int data2;
} DATA;
struct _RC_Compare {
bool operator() ( const RC p1, const RC p2 ) const
{
return p1.R == p2.R? p1.C < p2.C : p1.R < p2.R;
}
typedef std::map< RC, DATA, _RC_Compare > MY_MAP
I want to access every member of the map without regard to the key value, so I tried:
Code:
MY_MAP::iterator it;
for( it = MY_MAP.begin(); it != MY_MAP.end(); ++it )
{
// Bunch of code having nothing to do with the map
}
When this executes, it termiantes with the message "map/set iterator not incrementable" when it tries to execute the "++it".
Why can't I sequentially access a map? Everything I've read indicates this is possible, although all the examples have C++ primitives as keys.
Last edited by TSYS; March 31st, 2009 at 08:15 AM.
Reason: Fixed typo
Regards
Robert Thompson
-
March 31st, 2009, 08:25 AM
#2
Re: STL Map Iteration Question
You have to call begin() / end() on the map object instead of the type.
Code:
typedef struct _RC_ {
UINT R;
UINT C;
} RC;
typedef struct _Data_ {
int data1;
int data2;
} DATA;
struct _RC_Compare {
bool operator() ( const RC p1, const RC p2 ) const
{
return p1.R == p2.R? p1.C < p2.C : p1.R < p2.R;
}
typedef std::map< RC, DATA, _RC_Compare > MY_MAP;
int main()
{
MY_MAP m;
MY_MAP::iterator it;
for( it = m.begin(); it != m.end(); ++it )
{
// Bunch of code having nothing to do with the map
}
}
PS:
Symbols with leading underscores are reserved for implementation, so you probably want to rename your structures accordingly.
- Guido
-
March 31st, 2009, 08:55 AM
#3
Re: STL Map Iteration Question
One small point. You're using C syntax for your structs. In C++ you can use the following to achieve the same thing.
Code:
struct RC {
UINT R;
UINT C;
};
struct DATA {
int data1;
int data2;
};
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman
-
March 31st, 2009, 09:06 AM
#4
Re: STL Map Iteration Question
Thanks for both your prompt replies...
GNiewerth: In my rush to get this posted, I omitted the object reference in my sample code. I do, in fact, use code similar to what you've supplied (I doubt that it would compile the way I typed it in).
JohnW: Yeah, you're right - old habits die hard.
Regards
Robert Thompson
-
March 31st, 2009, 09:48 AM
#5
Re: STL Map Iteration Question
Code:
return p1.R == p2.R? p1.C < p2.C : p1.R < p2.R;
Never put a test for equality up front like that. This is almost begging for a runtime bug to occur. The map (and other algorithms and containers) require a strict weak ordering. To ensure this, you only test for greater or less, never equal on the first level of tests. A test for equality is almost always a sign that the test is wrong or will cause problems at some point.
Your code does a test for equality, and depending on the result, returns true or false on a simple assumption. This to me is a red flag that this could fail, even if it seems it's supposed to work.
As a matter of fact, many compilers insert code in their "debugging" version of these tests. What they do is pass you a pair and see what the return value is. Then they immediately pass you the same pair, only swapped. If the return value is inconsistent with the original return value, then the runtime stops dead in its tracks with an assertion error. The compiler check is making sure that the "strict weak ordering" is adhered to (even though the test is rudimentary, but it catches most problems).
What should be done first is return true or false without the equality check for pairs you are sure of. Then if they are equal, then do the extra check and return the appropriate value. However, I still feel that something is wrong with that, given the data you have (i.e. a < b < c is consistent for all values of a, b, and c).
Regards,
Paul McKenzie
Last edited by Paul McKenzie; March 31st, 2009 at 10:30 AM.
-
March 31st, 2009, 10:04 AM
#6
Re: STL Map Iteration Question
Originally Posted by TSYS
Code:
typedef struct _RC_ {
UINT R;
UINT C;
} RC;
typedef struct _Data_ {
int data1;
int data2;
} DATA;
struct _RC_Compare {
bool operator() ( const RC p1, const RC p2 ) const
{
return p1.R == p2.R? p1.C < p2.C : p1.R < p2.R;
}
typedef std::map< RC, DATA, _RC_Compare > MY_MAP
That does not compile.
-
March 31st, 2009, 10:22 AM
#7
Re: STL Map Iteration Question
Paul:
Thanks for your input. It seems to me your point would apply to arithmetic comparisons (eg., floating point), but not to integer, no? The referenced comparison actually refers to two (row, column) pairs.
Zaccheus: Yeah, I figured that out earlier. I have a propensity for typing first, thinking later.
But my lousy coding skills aside, how does one do a linear iteration through a map with a structure as a key??
Last edited by TSYS; March 31st, 2009 at 10:24 AM.
Reason: Added comment
Regards
Robert Thompson
-
March 31st, 2009, 10:36 AM
#8
Re: STL Map Iteration Question
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman
-
March 31st, 2009, 10:46 AM
#9
Re: STL Map Iteration Question
Originally Posted by TSYS
Paul:
Thanks for your input. It seems to me your point would apply to arithmetic comparisons (eg., floating point), but not to integer, no?
It doesn't matter if it's int's, doubles, or your own user-defined class.
The bottom line is that at the end of the day, you better be telling the map() that a < b < c, and this relationship is always true, regardless of what type and values a, b, and c are.
You should look at it similar to a sorting algorithm.
You have 100 of these _RC_ structs, and all have been initialized to some value. You want me to sort all of them. So here is what I do -- I give you a pair of these values -- you tell me which one of the pair comes before the other. You don't know beforehand which pair I will pick out of the 100, just that some pair will do shown to you. I keep doing this, throwing at you "random" pairs, and you tell me which comes first.
Then when I'm finished, I will have a sorted list. What makes the list sorted? You telling me which comes first. So what happens if there is an inconsitency in your logic, i.e. for the same pair, you tell me something different? The sort is not going to work, it may go into an infinite loop, etc.
http://www.sgi.com/tech/stl/StrictWeakOrdering.html
That is exactly what a strict-weak ordering means. Does your compare function fit this criteria? One way to ensure it does is to not check for equality. Comparison functions where the first thing they do is check for equality is a big sign that something is going to go wrong, either now or later.
Regards,
Paul McKenzie
-
March 31st, 2009, 11:03 AM
#10
Re: STL Map Iteration Question
I assume that you are trying to order the items by R. and for equal R,sort by C.
How about just
Code:
return p1.R < p2.R? true : p1.C < p2.C;
EDIT : Actually, that won't work
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman
-
March 31st, 2009, 11:11 AM
#11
Re: STL Map Iteration Question
Thanks to you both for your comments and the link. I see what you're getting at, but in this particular case (is (row1, col1) less than (row2, col2)) testing for "less than" first leads to pretty convoluted code - at least when I code it, it does.
I'll have to think about this
Regards
Robert Thompson
-
March 31st, 2009, 11:52 AM
#12
Re: STL Map Iteration Question
1) Can you post a small example (with map elements inserted) where
it fails ?
2) I don't see anything wrong with your comparison functor.
I think it is equivalent to:
Code:
struct _RC_Compare
{
bool operator() ( const RC p1, const RC p2 ) const
{
if (p1.R < p2.R) return true;
if (p1.R > p2.R) return false;
return p1.C < p2.C;
}
};
Last edited by Philip Nicoletti; March 31st, 2009 at 11:56 AM.
-
March 31st, 2009, 12:11 PM
#13
Re: STL Map Iteration Question
Originally Posted by Philip Nicoletti
I think it is equivalent to:
Code:
struct _RC_Compare
{
bool operator() ( const RC p1, const RC p2 ) const
{
if (p1.R < p2.R) return true;
if (p1.R > p2.R) return false;
return p1.C < p2.C;
}
};
If it is equivalent, then what you wrote is the proper way I described as to write the comparison functor. My guideline is that there shouldn't be an "up front" test for equality -- that is done after the less than/greater than tests have been ironed out and returned (when appropriate).
My habit is that anytime I see a comparison functor using "==" right away, with no preceding check (and subsequent possible return) for less or greater, I say "Oh Oh...". Bottom line, I pretend that == doesn't exist (only implied, as in your version) in the comparison function.
The other trap that programmer's can fall into is if all the tests have been exhausted except for ==, then return true/false. This usually ends up failing the strict weak ordering criteria.
Regards,
Paul McKenzie
-
March 31st, 2009, 12:16 PM
#14
Re: STL Map Iteration Question
Yes, Philip's code does what I intended, without the equality that bothers you, Paul.
But while this has certainly been an instructive morning for me, my original question remains: how can I access a <map> in a linear fashion with a structure as a key?
Here is the (corrected, I hope) code again:
Code:
typedef struct _RC_ {
UINT R;
UINT C;
} RC;
typedef struct _Data_ {
int data1;
int data2;
} DATA;
struct _RC_Compare {
bool operator() ( const RC p1, const RC p2 ) const
{
if( p1.R < p2.R ) return true;
if( p1.R > p2.R ) return false;
return p1.C < p2.C;
}
}
typedef std::map< RC, DATA, _RC_Compare > MY_MAP
//
//
// Further on in the .cpp file
//
MY_MAP m;
MY_MAP::iterator it;
for( it = m.begin(); it != m.end(); ++it )
{
// some code
}
This fails with the message "map/set iterator not incrementable" when execution of the "++it" is attempted.
Last edited by TSYS; March 31st, 2009 at 12:26 PM.
Reason: Forgot the code!
Regards
Robert Thompson
-
March 31st, 2009, 12:36 PM
#15
Re: STL Map Iteration Question
Can't you post a SSCCE??
This compiles & runs with no errors (Visual C++ 2008) after I fixed the various compiler errors:
Code:
#include<iostream>
#include<windows.h>
#include<map>
using namespace std;
typedef struct _RC_ {
UINT R;
UINT C;
} RC;
typedef struct _Data_ {
int data1;
int data2;
} DATA;
struct _RC_Compare {
bool operator() ( const _RC_ p1, const _RC_ p2 ) const
{
return p1.R == p2.R? p1.C < p2.C : p1.R < p2.R;
}
};
typedef std::map< RC, DATA, _RC_Compare > MY_MAP;
int main(int argc, char *argv[])
{
MY_MAP m;
_RC_ rc;
rc.R = 1;
rc.C = 1;
_Data_ data;
data.data1 = 1;
data.data2 = 2;
_RC_ rc2;
rc2.R = 1;
rc2.C = 1;
_Data_ data2;
data2.data1 = 1;
data2.data2 = 2;
m[rc] = data;
m[rc2] = data2;
MY_MAP::iterator it;
for( it = m.begin(); it != m.end(); ++it )
{
// Bunch of code having nothing to do with the map
}
return 0;
}
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|