c++ - 两个 std::map 的值是彼此的迭代器？

Question

出于性能原因，我需要两个 std::map，它们的值指向彼此的元素。
这是为了在另一个元素已经遍历时允许恒定时间插入/删除一个元素。

在 C++ 中正确实现它的最快方法是什么？请注意，显而易见的方法不起作用，因为第二个映射的类型在其迭代器可以声明为第一个映射的值的类型之前是不完整的。是Variants我唯一的选择，还是有更好的解决方案？

Answer 1

据我所知，您希望相互递归类型无法通过(前向)声明实现。但是 C++ 提供了另一种方法，即著名的 CRTP:

#include <map>

template <typename T>
struct BidirMapHelper {
    struct ReverseElt {
        ReverseElt() {}
        ReverseElt(typename T::iterator p) : v(p) {}
        typename T::iterator v;
    };
    typedef std::map<int, ReverseElt> ReverseMap;
};

struct BidirMap: BidirMapHelper<BidirMap>
{
    struct DirectElt {
        DirectElt() {}
        DirectElt(ReverseMap::iterator p) : v(p) {}
        ReverseMap::iterator v;
    };
    typedef std::map<int, DirectElt> DirectMap;
    typedef DirectMap::iterator iterator;
};

typedef BidirMap::DirectMap DirectMap;
typedef BidirMap::ReverseMap ReverseMap;

int main () {
    DirectMap m1;
    ReverseMap m2;
    m1[0] = m2.end();
    m2[0] = m1.end();
    return 0;
}

这可以在 Linux 下使用 g++ 和 clang++ 干净地编译，但我必须承认我不确定它是否不依赖于标准库的实现特征，例如具有 SCARY 迭代器。