Ricerca eterogenea nei contenitori ordinati, funzionalità C++14

Ricerca eterogenea nei contenitori ordinati, funzionalità C++14

Se hai una mappa di stringhe, come std::map<std::string, int> m; e vuoi trovare qualche elemento per m.find("abc") . Devi pagare il prezzo e costruire un std::string oggetto? Puoi ottimizzarlo?

Diamo un'occhiata a una funzionalità abilitata in C++14 che potrebbe aiutare a ottimizzare l'accesso ai container.

Introduzione

Espandiamo l'esempio menzionato in precedenza.

std::map<std::string, int> intMap { 
    { "Hello Super Long String", 1 }, 
    { "Another Longish String", 2 }, 
    { "This cannot fall into SSO buffer", 3 }
};

if (intMap.find("Hello Super Long String") != intMap.end())
    std::cout << "Found \n";
else
    std::cout << "Not found\n";

Nel codice sopra, sebbene "Hello Super Long String" sia una stringa letterale, deve essere convertito in un normale std::string (quindi qui è necessaria un'allocazione di memoria), quindi viene eseguita la ricerca.

Il std::string supporta il confronto con const char* , quindi perché non possiamo usarlo qui?

Il motivo:la definizione del comparatore nella mappa (di default è std::less<Key> ). Richiede il confronto degli stessi tipi. Se usi std::string come chiave, puoi confrontare solo con std::string , nemmeno con qualcosa di compatibile.

Diamo un'occhiata a una chiave più grande per std::set . In tal caso, il costo di ricerca potrebbe essere ancora più elevato.

Un esempio di chiave più grande

Che ne dici di un set contenitore che conserva i prodotti:

struct Product {
    std::string mName;
    std::string mDescription;
    double mPrice;
};

bool operator<(const Product& p1, const Product& p2) { 
    return p1.mName < p2.mName; 
}

std::set<Product> products {
    { "Car", "This is a super car that costs a lot", 100'000.0 },
    { "Ball", "A cheap but nice-looking ball to play", 100.0 },
    { "Orange", "Something to eat and refresh", 50.0 }
};

I prodotti vengono confrontati per Nome, che è una variabile membro.

Se vuoi trovare una "Auto", devi creare un Product temporaneo e inserisci il suo nome:

if (products.find({"Car", "", 0.0}) != products.end())
    std::cout << "Found\n"; 

Ma non possiamo specificare products.find("Car") e fornisci ulteriori opzioni di confronto (confronto con string_view per esempio)?

Nota a margine :Un altro motivo per la ricerca eterogenea potrebbe essere quando si dispone di un insieme di oggetti solo mobili (un esempio è un insieme di unique_ptr ). In tal caso, non puoi confrontare creando oggetti temporanei.

Sebbene non fosse possibile in C++11, possiamo farlo utilizzando la ricerca eterogenea, disponibile dal C++14.

Ricerca eterogenea, C++14

Ora possiamo dare un'occhiata a un possibile miglioramento:ricerca eterogenea nei contenitori ordinati.

E sorprendentemente è semplice da abilitare.

Tutto quello che devi fare è usare std::less<> (o qualche altro funtore, ne parleremo più avanti) e implementa le corrette funzioni di confronto!

Ad esempio per il primo esempio con mappa di std::string :

std::map<std::string, int, std::less<>> intMap;

E ora puoi trovarlo usando const char* o string_view :

if (intMap.find("Hello Super Long String"))
    std::cout << "Found \n";
else
    std::cout << "Not found\n";

Puoi giocare con il codice @Coliru.

Ricerca in std::set e ricerca eterogenea

Nella sezione precedente, ho mostrato l'implementazione per una mappa di stringhe, ora copriamo l'esempio con un insieme di prodotti. In questo caso, la chiave è molto più grande.

Creiamo un'implementazione che confronti i prodotti tramite string_view .

bool operator<(const Product& prod, const std::string_view& sv) { 
    return prod.mName < sv; 
}
bool operator<(const std::string_view& sv, const Product& prod) { 
    return sv < prod.mName; 
}

E ora possiamo cercare:

std::set<Product, std::less<>> products { ... };

if (products.find(std::string_view("Car")) != products.end())
    std::cout << "Found \n";
else
    std::cout << "Not found\n";

Grande! Possiamo cercare i prodotti per nome senza creare oggetti temporanei

Come viene implementata la ricerca eterogenea?

Sai come utilizzare questo nuovo modello di ricerca, ma come viene implementato?

Qual è la differenza tra queste due righe:

std::map<std::string, int> myMap;
std::map<std::string, int, std::less<>> myOtherMap;

La prima cosa è che myMap la dichiarazione si risolve in

std::map<std::string, int, std::less<std::string>> myMap; 
// allocator omitted above...

La dichiarazione completa è la seguente:

template<class Key, class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

Nota :il testo fa riferimento a std::less , ma le regole si applicano a tutti i functor standard come std::greater , std::plus , ecc, ecc. E anche i tuoi functor personalizzati.

La scelta progettuale per la ricerca eterogenea ha suggerito di utilizzare il più possibile la sintassi esistente, senza la necessità di inventare nuovi nomi extra (come Maggiore vs maggiore).

std::less ha operator () definito come segue:

template <class _Ty = void>
struct less {
    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const {
        return _Left < _Right;
    }
};

Il tipo deve essere lo stesso per _Left e _Right .

La soluzione era specializzarsi in std::less per vuoto (vuoto) e miglioralo anche con la proprietà `is_transparent”.

Ora possiamo definire un metodo modello (piuttosto che un tipo) che utilizza due tipi diversi (ma compatibili):

template <>
struct less<void> { 
    using is_transparent = int;

    // simplified version...
    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const
        return static_cast<_Ty1&&>(_Left) < static_cast<_Ty2&&>(_Right);
    }
};

Ora _Left e _Right possono essere tipi distinti, ma devono essere comparabili.

Il find L'overload del metodo può essere definito come:

template <class _Other, class _Mycomp = key_compare, 
          class = typename _Mycomp::is_transparent>
iterator find(const _Other& _Keyval) { ... }

In altre parole, se il comparatore è trasparente (avendo is_transparent tag), quindi l'implementazione può sfruttare la ricerca eterogenea.

Puoi anche implementare le tue funzioni personalizzate che espongono is_transparent . C'era anche un articolo simile su fluentcpp:is_transparent:come cercare un set C++ con un tipo diverso dalla sua chiave - Fluent C++.

Puoi leggere ulteriori informazioni sulla funzionalità nelle proposte accettate in C++14:Incremento dei funtori degli operatori<> N3421 e Aggiunta di una ricerca di confronto eterogenea ai contenitori associativi - N3657.

Una cattura:non cercare utilizzando una chiave diversa

I contenitori ordinati vengono implementati come alberi bilanciati. L'ordine è specificato dalla chiave fornita nella dichiarazione del contenitore. Se provi a cercare un'altra chiave, la ricerca potrebbe non riuscire.

Ad esempio, per il nostro std::set<Product> caso potresti essere tentato di cercare in base al prezzo:

Devi aggiungere funzioni di confronto:

bool operator<(const Product& prod, const double& price) { 
    return prod.mPrice < price; 
}
bool operator<(const double& price, const Product& prod) { 
    return price < prod.mPrice; 
}

E poi il codice:

std::set<Product, std::less<>> products {
    { "Car", "This is a super car that costs a lot", 100'000.0 },
    { "Ball", "A cheap but nice-looking ball to play", 100.0 },
    { "Orange", "Something to eat and refresh", 50.0 }
};

std::cout << "Lookup by Price: \n";
if (products.find(50.0) != products.end())
    std::cout << "Found \n";
else
    std::cout << "Not found\n";

L'uscita:

Not Found

C'è un oggetto che ha il prezzo di 50 unità... allora perché la ricerca è fallita?

La chiave primaria che usiamo qui è il nome. L'implementazione potrebbe creare la seguente struttura ad albero:

       "Ball"
     /      \
   "Car"    "Orange" 

Quando confrontiamo 50,0 con "Ball", confrontiamo i prezzi e 50 è inferiore al prezzo di 100,0 di Ball. Quindi entriamo nel sottoalbero di sinistra. Quindi vediamo solo “Auto”, che ha un prezzo diverso da “50”.

Forse è abbastanza ovvio, ma assicurati di cercare chiavi che siano anche uguali alla chiave primaria utilizzata.

Cosa sta arrivando in C++20?

In C++14 abbiamo ottenuto una ricerca eterogenea per i contenitori ordinati (std::map , std::set , ecc.) e l'estensione naturale doveva avere un approccio simile per i contenitori non ordinati (std::unorederd_map , std::unordered_set , ecc).

Se tutto va bene, lo avremo in C++20 attraverso il documento:P0919 di Mateusz Pusz. In questo momento, il documento è stato accettato per la bozza C++20.

Puoi anche provare la tua implementazione e utilizzare le idee di questo video.
https://www.youtube.com/watch?v=0QFPKgvLhao

I guadagni in termini di prestazioni con la ricerca eterogenea

Uno dei motivi per cui abbiamo una ricerca eterogenea è aumentare le prestazioni della ricerca. Ma quanto puoi ottenere?

Il vantaggio principale verrà dalla riduzione del numero di oggetti temporanei e dalle allocazioni di memoria extra. Quindi meno memoria temporanea devi allocare, migliore è la spinta finale.

Possiamo trarre alcuni numeri dall'articolo P0919 in cui l'autore - Mateusz - presenta diversi esperimenti per contenitori non ordinati (repo Github qui:mpusz/unordered_v2):

  • 20% di aumento delle prestazioni per il testo breve (SSO utilizzato in std::string temporaneo).
  • 35% di aumento delle prestazioni per il testo lungo (allocazione dinamica della memoria in std::string temporaneo).

Possiamo ottenere le stesse prestazioni con i contenitori ordinati? Spero di trattarlo nel mio prossimo articolo. Quindi resta sintonizzato. Ma se hai già dei risultati, condividili nei commenti.

Riepilogo

Con C++14 abbiamo ottenuto un modo nuovo e flessibile per cercare nei contenitori ordinati. L'idea principale era quella di fornire funtori "trasparenti" in grado di confrontare due oggetti "compatibili" che rappresentano una chiave. Ad esempio, in una mappa di stringhe, puoi cercare per string_view o const char* . Ciò ha ridotto il numero di oggetti temporanei. Questa tecnica è utile anche quando le tue chiavi sono grandi.

In C++ 20 probabilmente otterremo un modello simile ma per i contenitori non ordinati. Dobbiamo aspettare lo Standard finale.

Hai già utilizzato la ricerca eterogenea? Pensi che potrebbe aiutare nei tuoi progetti? Fatecelo sapere nei commenti.