Реализация std :: map в Visual C ++

Question

Как реализовано std :: map в Visual C ++?

Я знаю, что некоторые древовидные структуры просто помечают узлы как удаленные, когда они удаляются, вместо того, чтобы удалять их сразу. Мне нужно убедиться, что мои элементы никогда не сравниваются с элементами, которых больше нет на карте.

EDIT:

Я знаю, что реализация, вероятно, правильная по отношению к. контракт, который требует от меня полного упорядочения по типу элемента. Тем не менее, у меня есть только частичное упорядочение, которое не позволяет сравнивать элементы, которые не существуют одновременно.

Answer 1

Независимо от того, поддерживает ли реализация удаленные узлы или нет, она должна вызвать деструктор содержащегося объекта, когда узел удален . После этого он не может передать объект в функцию сравнения, поскольку это приведет к неопределенному поведению, что сделает его несоответствующей реализацией.

Answer 2

Ответ для реализации структуры данных в целом, а не для MSVC или std::map:

Похоже, вы думаете, что пользователь-контейнер должен знать о флаге, чтобы игнорировать удаленные элементы.

Если реализация просто помечает элемент как уже не включенный, это будет сделано как деталь реализация . Это означает, что с точки зрения любого внешнего пользователя контейнера этот элемент вообще не будет виден в контейнере. В частности, любой из методов поиска в контейнере заметит флаг и проигнорирует все, к чему он прикреплен. Поскольку реализация правильно сохраняет семантику, вам не нужно беспокоиться о том, использует ли она метод маркировки.

Answer 3

Мне не известны какие-либо ошибки в реализации Microsoft STL, о которых вам следует беспокоиться здесь.Для класса было бы ошибкой доступ для сравнения уже удаленных элементов, хотя я могу представить, как очистка может происходить вне диапазона.

Если вам действительно нужны детали реализации, возьмитепосмотрите на исходный код удаления элементов в <map> и <xtree> из вашего работающего кода в IDE.