2つのstd :: mapの値がお互いのイテレータですか？

Question

性能上の理由から、値がお互いの要素を指す2つが必要です。
これは、ある要素がすでに横断されているときに要素を一定時間挿入/削除できるようにするためです。

これをC++で正しく実装する最も速い方法は何ですか？最初のマップの値の型としてイテレータを宣言する前に、2番目のマップの型が不完全であるため、明白なアプローチは機能しません。 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; 
} 

これは、g ++およびLinuxで打ち鳴らす++できれいにコンパイルが、私はそれが標準ライブラリの実装特性に依存していないかわからないということを認めなければなりませんSCARYイテレータを持つようなものです。

Answer 2

これは単純な解決策ですが、任意の標準準拠の実装std::mapでコンパイルすることは保証されていません。しかし、gcc 4.4.7（-std = C++ 11もサポートしていません）とgcc 5.x、gcc 6.1、clang 3.x、icc 13.0.1（-std = C++ 11）。

#include <map> 

struct It1; 
struct It2; 

typedef std::map<int, It2> Map1; 
typedef std::map<int, It1> Map2; 

struct It2 : Map2::iterator 
{ 
    It2() {} 
    It2(Map2::iterator it) : Map2::iterator(it) {} 
}; 

struct It1 : Map1::iterator 
{ 
    It1() {} 
    It1(Map1::iterator it) : Map1::iterator(it) {} 
}; 

int main() 
{ 
    Map1 m1; 
    Map2 m2; 

    m1[0] = m2.end(); 
    m2[0] = m1.end(); 
    return 0; 
}