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.

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.

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;
};

---

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.

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

Quote:

---

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. :(

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??

http://www.sgi.com/tech/stl/StrictWeakOrdering.html

Quote:

---

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

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 :blush:

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

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;
  }
};

---

Quote:

---

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

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.

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;
}

---

Quote:

---

Originally Posted by TSYS

Yes, Philip's code does what I intended, without the equality that bothers you, Paul.

---

It's not a matter of bothering me, it's really for your benefit to write comparisons this way (without the test for equality). As mentioned, testing for equality as early as you did is the foundation of badly written comparison operators that ultimately break the strict weak ordering rule, maybe not now, but later if the ordering becomes more complex.

I suggest you take Martin O's code, compile it, run it, and see if it works. If it does work, then it's your job to make it not work by adding something to it and repost the changed example. Or if not that, figure out what the code he posted does and your's doesn't do.

Regards,

Paul McKenzie

Well, Martin's code certainly works, so now I have to find out what's on the periphery screwing things up.

Thanks to everybody for your help.

In Visual Studio 2005, the iterator's operator++ seems to be checking whether the iterator does not belong to a map at all and/or whether it has reached the last element in the map - in which case the "map/set iterator not incrementable" error is issued.

So it is not saying that this type of iterator cannot be incremented, but the specific instance cannot be incremented.