例如,libstdc++ 使用在节点中带有父指针的红黑二叉树来实现 std::map。这意味着迭代器可以只是指向节点的指针。
标准库是否可以在不在节点中存储父指针的情况下实现 std::map?我认为这意味着迭代器需要包含一堆父指针,因此需要动态分配对数数量的内存。这会违反迭代器的标准性能约束吗?父指针不会违反接口(interface)其余部分的任何其他性能限制吗?
C++17 中的新节点内容/接口(interface)怎么样?
最佳答案
他们可能不会这样做。 std::map
保证从中删除键值对不会使除被删除的对之外的任何迭代器无效。
如果迭代器将存储一堆父代,并且删除了一个父代,那么这些迭代器也会失效。并且保证将不再有效。
关于c++ - std::map 没有父指针?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48878089/