Wie kann ich eine std :: map mit einem Schlüssel eines anderen Typs suchen?

Question

Wenn ich std::map<X, Blah> habe, was ist die beste Möglichkeit, ein passendes Objekt in der Karte mit einer Instanz von Y zu suchen?

Angenommen, die Informationen in Y genug sind, ein X, aber aus Leistungsgründen eindeutig finden Ich möchte nicht über eine Instanz von X durch Kopieren Y Werte erstellen.

Ich weiß, ich kann dies tun, indem Sie eine gemeinsame Basisklasse oder Schnittstelle für X und Y erstellen und dass die Karte Schlüssel, aber gibt es andere Wege? z.B. eine Art Vergleichsobjekt erstellen?

Hier ist der Beispielcode für Klarheit:

class X 
{ 
public: 
    int id; 
    int subId; 
}; 

std::map<X, Details> detailsMap; 

class Y 
{ 
public: 
    int getId(); 
    int getSubId(); 
    int someOtherUnrelatedThings1; 
    int someOtherUnrelatedThings2; 
}; 

Nun, wenn ich eine Instanz von Y haben, grundsätzlich sollte ich in der Lage sein, Einzelteile in meiner Karte finden passende, da ich eine id bekommen kann und subId Paar. Aber kann ich es tun, ohne eine Instanz von X erstellen und über die id und subId kopieren?

Answer 1

Mit C++ 14 können Sie heterogene Lookup verwenden.

Wenn Sie möchten, dass ein Element mit Schlüsseln finden, äquivalent das Argument von std::map::find vergleicht, sollten Sie einen Komparator als dritte Template-Parameter bereitzustellen, die Comparator::is_transparent als Typ bezeichnet haben soll. Es sollte auch bool operator() enthalten, um Ihren Kartenschlüssel mit einem beliebigen anderen Typ zu vergleichen.

Lustige Beschreibung beiseite, hier ein Beispiel:

struct X 
{ 
    int id; 
    int subid; 
}; 

struct Details {}; 

struct Comparator 
{ 
    using is_transparent = std::true_type; 

    // standard comparison (between two instances of X) 
    bool operator()(const X& lhs, const X& rhs) const { return lhs.id < rhs.id; } 

    // comparison via id (compares X with integer) 
    bool operator()(const X& lhs, int rhs) const { return lhs.id < rhs; } 
    bool operator()(int lhs, const X& rhs) const { return lhs < rhs.id; } 

    // Same thing with Y 
    bool operator()(const X& lhs, const Y& rhs) const { return lhs.id < rhs.getId(); } 
    bool operator()(const Y& lhs, const X& rhs) const { return lhs.getId() < rhs.id; } 
}; 

int main() 
{ 
    std::map<X, Details, Comparator> detailsMap = { 
     { X{1, 2}, Details{} }, 
     { X{3, 4}, Details{} }, 
     { X{5, 6}, Details{} } 
    }; 

    // it1 and it2 point to the same element. 
    auto it1 = detailsMap.find(X{1, 2}); 
    auto it2 = detailsMap.find(1); 

    std::cout << detailsMap.size() << std::endl; 
    std::cout << std::boolalpha << (it1 == detailsMap.end()) << std::endl; // false 
    std::cout << std::boolalpha << (it1 == it2) << std::endl; // true 
} 

ist jedoch zu beachten, dass GCC es bis Revision 219888 implementieren didin't.

Answer 2

C++ 14 hinzugefügt is_transparent Unterstützung zu map Ordnungen.

struct compare_helper { 
    X const* px = nullptr; 
    Y const* py = nullptr; 
    compare_helper(compare_helper&&)=default; 
    compare_helper(X const& x):px(&x) {} 
    compare_helper(Y const& y):py(&y) {} 
    explicit operator bool()const{return px&&py;} 
    friend bool operator<(compare_helper&& lhs, compare_helper&& rhs) { 
    if (!lhs || !rhs) { 
     return !rhs < !lhs; 
    } 
    // TODO: compare lhs and rhs based off px and py 
    } 
}; 
struct ordering_helper { 
    using is_transparent=std::true_type; 
    bool operator()(compare_helper lhs, compare_helper rhs)const{ 
    return std::move(lhs)<std::move(rhs); 
    } 
}; 

jetzt neu definieren Ihre std::map:

std::map<X, Details, ordering_helper> detailsMap; 

und Sie sind fertig. Sie können jetzt eine Y const& an detailsMap.find oder was auch immer übergeben.

Jetzt ist // TODO: compare lhs and rhs based off px and py ein bisschen nervig.

Aber es sollte beschreibbar sein.

Wenn Sie viele verschiedene Klassen benötigen, um mit X vergleichen zu können, und Sie entweder eine große compare_helper Klasse mit jedem gespeicherten benötigen, oder Sie müssen die Operation irgendwie tippen-löschen.

Grundsätzlich compare_helper Bedürfnisse speichern einen Zeiger-to-X oder ein std::function< int(X const&) >, die Sie sagt, wenn die X kleiner als, gleich oder größer als die anderen Parameter. (Sie werden feststellen, dass dies fehlschlägt, wenn Sie eine Y mit einer Y oder einer Z mit einer Y vergleichen. In diesem Fall sollte die Rückgabe von false sicher sein, da Sie in einer Kartensuche immer nur eine Nicht-X sehen.

Wir können dies aus der Definition von compare_helper mit einigen ADL entkoppeln:

struct compare_helper { 
    X const* px = nullptr; 
    using f_helper = std::function< int(X const&) >; 
    f_helper not_X; 
    compare_helper(compare_helper&&)=default; 
    compare_helper(X const& x):px(std::addressof(x)) {} 
    template<class NotX, 
    class=std::enable_if_t< std::is_convertible< 
     decltype(compare_with_X(std::forward<NotX>(notx))) 
     , f_helper 
    >{} 
    > 
    compare_helper(NotX&& notx): 
    not_X(compare_with_X(std::forward<NotX>(notx))) 
    {} 
    explicit operator bool()const{return px&&not_X;} 
    friend bool operator<(compare_helper&& lhs, compare_helper&& rhs) { 
    if (!lhs || !rhs) { 
     return !rhs < !lhs; 
    } 
    if (lhs.px && rhs.px) { return *lhs.px < *rhs.px; } 
    if (lhs.px && rhs.not_X) { return rhs.not_X(*lhs.px) < 0; } 
    if (lhs.not_X && rhs.px) { return lhs.not_X(*rhs.px) > 0; } 
    else return false; 
    } 
}; 

jetzt der Endbenutzer einfach hat die freie Funktion compare_with_X im Namensraum des Typs außer Kraft setzen Sie mit X vergleichen wollen geben Sie eine std::function<int(X const&)> zurück, und die obige Karte ermöglicht das Suchen von Ihrem Typ X.

Answer 3

Es gibt keine Möglichkeit, die mapfind mit einem anderen Datentyp zu verwenden. Aber hör jetzt auf. Haben Sie tatsächlich gemessen, dass ein X erstellen ein Problem ist? Vorausgesetzt, dass getId und getSubId nicht-const sind, gibt es tatsächlich eine Chance, dass der Compiler nicht in der Lage ist zu sagen, ob sie Nebenwirkungen haben und sie weiter aufrufen müssen, was die Erstellung eines temporären X tatsächlich beschleunigt.

Die offensichtliche Antwort hier ist zu erstellen Sie einfach die X und tun Sie es auf die offensichtliche Art und Weise, bis Messung anders angibt.