Visual C++'s implementation of std::map

Question

How is std::map implemented in Visual C++?

I know that some tree data structures just flag nodes as deleted when they are removed, instead of removing them right away. I need to make sure that my elements are never compared to elements which are no longer in the map.

EDIT:

I know that the implementation is probably correct wrt. the contract, which requires me to have a total weak ordering on the element type. However, I only have a partial ordering, which is not able to compare elements which are not live at the same time.

Answer 1

Answering for data structure implementation in general rather than for MSVC or std::map:

You seem to think that the user the container needs to be aware of the flag in order to ignore elements that have been removed.

If the implementation simply flags an element as no longer being included, it will do so as an implementation detail. That means that from the point of view of any outside user of the container, that element will not be visible in the container at all. In particular, any of the lookup methods on the container will notice the flag and ignore anything it's attached to. As long is the implementation is correctly preserving the semantics, you really don't need to worry about whether it's using a flagging technique.

Answer 2

I am not aware of any bugs in the Microsoft STL implementation that you have to worry about here. It would be a bug for the class to access for comparison already-removed elements, though I can imagine how cleanup might happen out of band.

If you really need implementation details, take a look at the source code behind element removal in <map> and <xtree> from within your running code in the IDE.

Answer 3

Whether the implementation maintains nodes that have been erased or not, it must call the contained object destructor when the node is erased. After that, it cannot possibly pass the object to a comparison function as that would cause undefined behavior, which would make it a non-conforming implementation.