Come posso cercare una mappa std :: utilizzando una chiave di un tipo diverso

Question

Se ho std::map<X, Blah>, qual è il modo migliore di cercare un elemento corrispondente nella mappa utilizzando un'istanza di Y?

Assumere l'informazioni in Y è sufficiente per trovare in modo univoco un X, ma per motivi di prestazioni non voglio creare un'istanza di X copiando Y valori.

Mi rendo conto che posso farlo creando una classe di base comune o un'interfaccia per X e Y e facendo in modo che la chiave della mappa, ma c'è un altro modo? per esempio. creando una sorta di oggetto comparatore?

Ecco il codice di esempio per chiarezza:

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

std::map<X, Details> detailsMap; 

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

Ora, se ho un'istanza di Y, in linea di massima dovrei essere in grado di trovare elementi corrispondenti nella mia mappa, dato che posso ottenere un id e Coppia subId. Ma posso farlo senza creare un'istanza di X e copiare su id e subId?

Answer 1

Con C++ 14 è possibile utilizzare la ricerca eterogenea.

Se vuoi trovare un elemento con chiave che mette a confronto equivalente all'argomento di std::map::find, è necessario fornire un comparatore come terzo parametro di template che dovrebbe avere Comparator::is_transparent indicato come un tipo. Dovrebbe anche contenere bool operator() confrontando la chiave della mappa con qualsiasi altro tipo che desideri.

descrizione divertente a parte, ecco un esempio:

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 
} 

Nota, tuttavia, che GCC didin't implementare fino revisione 219888.

Answer 2

C++ 14 aggiunto is_transparent supporto per ordini map.

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

ora ridefinire il proprio std::map:

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

e si è fatto. Ora puoi passare un Y const& a detailsMap.find o qualsiasi altra cosa.

Ora // TODO: compare lhs and rhs based off px and py è un po 'fastidioso.

Ma dovrebbe essere scrivibile.

Se sono necessarie numerose classi diverse da confrontare con X, è necessario avere una grande classe compare_helper con ciascuna salvata oppure è necessario digitare l'operazione in qualche modo.

In sostanza, compare_helper ha bisogno di memorizzare un puntatore-to-X, o un std::function< int(X const&) > che ti dice se il X è inferiore, uguale o maggiore rispetto agli altri parametri. (noterai che questo non funziona quando confronti uno Y o un contro uno contro uno Y - in tal caso, restituendo false dovrebbe essere sicuro, poiché vedrai sempre uno solo non X in una ricerca mappa specificata).

possiamo separare questo dalla definizione di compare_helper con qualche ADL:

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

ora l'utente finale deve semplicemente ignorare la funzione libera compare_with_X nello spazio dei nomi del tipo che si desidera confrontare con X a restituire un std::function<int(X const&)> e la mappa sopra consente la ricerca dal tuo tipo non-X.

Answer 3

Non c'è modo di utilizzare lo findfind con un altro tipo di dati. Ma fermati subito. Sei in realtà misurato che la creazione di un X è un problema? Dato che getId e getSubId sono non-const, c'è una possibilità che il compilatore non sia in grado di dire se hanno effetti collaterali e devono continuare a chiamarli, rendendo la creazione di uno X temporaneo più veloce.

La risposta ovvia è e basta creare lo X e farlo in modo ovvio fino a quando la misurazione non indica diversamente.