Zwei std :: maps, deren Werte die Iteratoren des jeweils anderen sind?

Question

Ich brauche zwei std::map s, deren Werte aus Leistungsgründen auf die Elemente der anderen verweisen.
Dies ermöglicht das konstante Einfügen/Entfernen von Elementen, wenn das andere bereits durchlaufen wurde.

Was ist der schnellste Weg, um dies korrekt in C++ zu implementieren? Beachten Sie, dass der offensichtliche Ansatz nicht funktioniert, da der Typ der zweiten Map unvollständig ist, bevor ihr Iterator als der Typ des Werts der ersten Map deklariert werden kann. Sind Variants meine einzige Option, oder gibt es eine bessere Lösung?

Answer 1

Sie wollen gegenseitig rekursive Typen in einer Weise, die, soweit ich weiß, nicht mit (forward) Deklarationen erreicht werden kann. Aber C++ bietet ein weiteres Mittel, das die berühmte CRTP ist:

#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; 
} 

Dies kompiliert sauber mit g ++ und Klirren ++ unter Linux, aber ich muss zugeben, dass ich nicht sicher bin, es hängt nicht von einer Implementierung Merkmal der Standardbibliothek wie zum Beispiel SCARY-Iteratoren.

Answer 2

Hier ist eine einfachere Lösung, die jedoch nicht für eine beliebige normkonforme Implementierung von std::map kompiliert werden kann. Dennoch kompiliert es mit gcc 4.4.7 (was nicht einmal -std = C++ 11 unterstützt) und mit gcc 5.x, gcc 6.1, clang 3.x und icc 13.0.1 (sowohl mit als auch ohne -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; 
}