Expression: map/set iterators incompatible

[Shiraz]

Me and my colleagues have been working on a problem since yesterday and can’t
seem to find a solution to it. It relates in a good measure to iterators and
the way we’re using them in our project. I will first give you a little
introduction to our main task. We had at our hands entire modules which were
written in C++. These were to communicate with a stack written in C, and in
turn act as a layer between the C code and C# code used in another
application.

Whoever had developed the C++ code, was building it using makefiles in the
cygwin shell, as the condition then (for whatever reasons) had been that the
code remains ANSI compatible. So the C++ code was being built using
compilers/linkers for cygwin, cygmingw, and vc7.1. A free tool called SWIG[0]
was being used to generate an export file to be compiled with the C++ code as
well as a full C# wrapper of all the C++ classes and functions. (Essentially
SWIG generates a flattened interface to all the C++ classes and then builds
the objects in C# and uses pinvoke with a pointer to access the C++ classes).
In our main C# application, we references these C# wrapper dlls in projects
depending on the functionality and all seemed to work.

Recently though, our project team decided that we should have all the code
in the Visual Studio environment, and we felt strongly that it would enable
us to debug the unmanaged code, if there is a need to, and thus have better
control over code maintainence. Furthermore, we decide to move over to the
VC8.0, which seemed the most logical thing to do.

Implications – First of all, we felt that the effort involved in translating
the makefile script to VS properties was considerable. Even though the
makefiles were done very intelligenty, they also had very specific
instructions, and these were often masked under many layers of variables. A
lot of time and energy led us finally to having a VS 2005 solution with all
the C++ projects, their corresponding C++ test console applications, C#
projects which contained the files automatically generated with SWIG, and
finally the C# unit test projects to test these C# projects.

In addition, we could also debug down to the C++ code, which was
encouraging. We were able to generate the C++ dlls and the C# wrapper dlls as
cygwin. However, with the test modules, we have run into this seemingly
unsolvable problem.

This test aims first at establishing a connection with a server on a real
device and then to compare some characteristics with it. The error we get is:

Debug Assertion Failed!

Program: C:\....\Test.exe
File: C:\Program Files\Microsoft Visual Studio 8\VC\include\xtree
Line: 293

Expression: map/set iterators incompatible

For information on how your program can cause an assertion failure, see the
Visual C++ documentation on asserts.

(Please Retry to debug the application).

As for the code samples, please bear in mind the following:

1. We are using the following typemaps

// Kind of cached item.
enum RefKind {...};

// Vector of cached items of the same kind.
typedef std::vector<string> RefsVec;

typedef std::map<RefKind, RefsVec> KindRefsMap;
typedef std::map<CoreTypes::ObjectName, KindRefsMap> LN2KindMap;
typedef std::map<CoreTypes::ObjectName, LN2KindMap> LD2LNMap;

2. LD2LNMap is instantiates as:
// Cache for References (names). Created per LD the first time a
// directory service is called for an element belonging to the LD.
// Format: {ldName; {lnName; {CDC|...|DS; vectorOfObjRefs}}}
LD2LNMap dirCache;

3. The function that was initially called:

public void useGetDataSetDirectory() {
Console.WriteLine("");
Console.WriteLine("------ useGetDataSetDirectory ----------");
foreach(LDReference ld in _server.GetServerDirectoryLogicalDevices()) {
Console.WriteLine("LD: " + ld.getRef());
foreach(LNReference ln in _server.GetLogicalDeviceDirectory(ld)) {
.......
}
}
}
4. After getLD returns null, hasLDName throws the exception and the above
assertion failure message is displayed:

// getLD()
CoreAcsi::NamingCache::LD2LNMap::const_iterator
CoreAcsi::NamingCache::getLd(const CoreTypes::ObjectName& ldName) const
{
LD2LNMap::const_iterator it1 = dirCache.find(ldName);
if (it1 != dirCache.end()) {
return it1;
}
return NULL;
}

// hasLDName
CoreTypes::P_BOOLEAN
CoreAcsi::NamingCache::hasLDName(const CoreTypes::ObjectName& ldName) const
{
return (getLd(ldName) != NULL);
}

[Sean M. DonCarlos]

Wow, this was an arcane one!

The short answer is that you can't compare iterators that don't point to the
same collection. In your hasLDName function, the runtime is converting NULL
to type LD2LNMap::const_iterator& so that the != comparison can take place,
but since the NULL doesn't actually point to the same LD2LNMap object that
the getLd function returned, you get an error.

This is hard to explain, so bear with me.

The getLd function returns an object of type LD2LNMap::const_iterator. This
const_iterator's operator!= function is called to compare the const_iterator
to the value NULL.

For the comparison to work, the NULL must be converted to type
const_iterator&. The runtime can create a temporary const_iterator object,
but this temporary iterator is not actually pointing to anything (at least
not anything meaningful).

It turns out that STL maps are based on red-black binary trees that are
defined in the <xtree> header. The const_iterator::operator== function for
these trees (operator!= is implemented simply as the negation of operator==)
first tests to see that the two iterators being compared point to the same
tree.

Since the temporary const_iterator object doesn't actually point to any tree
at all, the test fails, and you get the error "map/set iterators
incompatible".

Therefore, one way to write your hasLDName function would be:

// I don't know if you've assigned special "true" and "false" values to your
CoreTypes::P_BOOLEAN type, so I am illustrating with the primitive bool type.

bool
CoreAcsi::NamingCache::hasLDName(const CoreTypes::ObjectName& ldName) const
{
LD2LNMap::const_iterator it1 = dirCache.find(ldName);
if (it1 != dirCache.end())
{
return true;
}

return false;
}

Hopefully this makes some sense. If not, maybe someone else with a little
more experience with STL can help.

Sean

[Shiraz]

Thanks for the prompt response Sean. Your analysis of the problem was dead
on; after going back and looking through the code again, we see that
comparing an iterator with NULL will always through an exception.
Unfortunately, since this was allowed in previous versions of the STL
included with Visual Studio (and also with GCC), the code we are working with
makes heavy usage of (iterator == NULL). Just curious if you or anyone else
might have suggestions as to the best way to approach this problem.

Should we be looking at changing all the places in our code that uses
iterator == NULL [possibly substituting for iterator == container.end()]? Or
is there another way to default to the old behaviour?

[Edward Diener]

Shiraz wrote:

Thanks for the prompt response Sean. Your analysis of the problem was dead
on; after going back and looking through the code again, we see that
comparing an iterator with NULL will always through an exception.
Unfortunately, since this was allowed in previous versions of the STL
included with Visual Studio (and also with GCC), the code we are working with
makes heavy usage of (iterator == NULL). Just curious if you or anyone else
might have suggestions as to the best way to approach this problem.

Should we be looking at changing all the places in our code that uses
iterator == NULL [possibly substituting for iterator == container.end()]? Or
is there another way to default to the old behaviour?

Iterators are not pointers and should only be compared with other
iterators of the same type. If you are looking for an iterator which
says that you are not accessing anything valid, it should be set to the
end of the container to which the iterator belongs and you can check if
it is accessing a valid value by writing "if ( myIterator ==
myContainer.end() )". This is the standard notation for checking if an
iterator is accessing a valid value or not when looping through
containers. Checking an iterator against 0 ( NULL ) is just incorrect C++.

[Sean M. DonCarlos]

"Shiraz" wrote:

Unfortunately, since this was allowed in previous versions of the STL
included with Visual Studio (and also with GCC), the code we are working with
makes heavy usage of (iterator == NULL).
Every time I see a NULL being assigned or compared to something that is not
a pointer, I force myself to stop and ask why. At the very minimum it is
unclear coding (if the other object is a number, compare it to 0, not NULL!)
and a potentially unnecessary creation of a temporary object.
Should we be looking at changing all the places in our code that uses
iterator == NULL [possibly substituting for iterator == container.end()]? Or
is there another way to default to the old behaviour?

It depends on what's being done with the iterators at the time of each
comparison. If the iterator was created as a result of calling the find
function of a map, then the iterator is guaranteed to either point to an
element or to container.end, so the comparison iterator == container.end
would be a valid test of whether the find function actually found something.

Other iterators might require different tests. (Reverse iterators are the
first example that comes to mind. There might be others.)

Another option might be to have functions like your getLd function return
pointers to iterators (and NULL if the desired object is not found), and then
compare the iterator * to NULL. Whether this would be desirable or not
depends to a large degree on the other code in your project. I'm unsure of
any performance impact. On one hand, there would be more pointer derefencing
occurring when you needed to use the iterator. On the other hand, you would
eliminate all the temporary object creation that happens every time NULL has
to be converted to an iterator type.

[Sean M. DonCarlos]

"Edward Diener" wrote:

Iterators are not pointers and should only be compared with other
iterators of the same type.

Strictly speaking, iterators should only be compared to other iterators of
the same type whose containers are the same container as the first iterator.

map<int, int> m1;
map<int, int> m2;
map<int, int>::iterator i1 = m1.begin();
map<int, int>::iterator i2 = m2.begin();

if (i1 == i2) {...} // Error! - iterators don't point to same map object

Sean

[Edward Diener]

Sean M. DonCarlos wrote:

"Edward Diener" wrote:

Iterators are not pointers and should only be compared with other
iterators of the same type.

Strictly speaking, iterators should only be compared to other iterators of
the same type whose containers are the same container as the first iterator.

I agree. Thanks for the qualification.