Visual C 的 std::map 实现
std::map 在 Visual C++ 中是如何实现的？
我知道某些树数据结构只是在删除节点时将其标记为已删除，而不是立即删除它们。我需要确保我的元素永远不会与地图中不再存在的元素进行比较。
编辑：
我知道实现可能是正确的。合同，它要求我对元素类型进行完全弱排序。但是，我只有部分排序，无法比较同时不存在的元素。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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.
一般回答数据结构实现而不是 MSVC 或 std::map ：
您似乎认为容器的用户需要了解该标志才能忽略已删除的元素。
如果实现只是将某个元素标记为不再包含，它将作为实现细节来执行此操作。这意味着从容器的任何外部用户的角度来看，该元素在容器中根本不可见。特别是，容器上的任何查找方法都会注意到该标志并忽略它附加的任何内容。只要实现正确地保留了语义，您就真的不需要担心它是否使用了标记技术。
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.
我不知道 Microsoft STL 实现中有任何您需要担心的错误。对于类来说，访问以进行比较已删除的元素将是一个错误，尽管我可以想象如何在带外进行清理。
如果您确实需要实现详细信息，请在 IDE 中运行的代码中查看
和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.