Posso usare legalmente una struct con operatore overload() come Compare per std :: upper_bound?

Question

devo le strutture di questo tipo (tipi semplificati di riportare il punto), che vive in un std::vector:

struct Region { 
    int first; 
    int count; 
    struct Metadata region_metadata; 
}; 

nel vettore, che sono ordinate per first. Se si aggiunge first e count, si ottiene first della regione successiva; quindi in pratica questo vettore di strutture descrive i metadati per intervalli di numeri contigui.

Ora dato un numero intero, voglio cercare i metadati. Poiché le regioni sono ordinate, posso usare std::upper_bound. Ho implementato in questo modo:

struct Comp 
{ 
    inline bool operator()(const Region &region, int index) const 
    { 
     return region.first < index; 
    } 

    inline bool operator()(int index, const Region &region) const 
    { 
     return index < region.first; 
    } 
}; 

Questo funziona, quando si chiama std::upper_bound con:

auto iter = std::upper_bound(m_regions.begin(), 
          m_regions.end(), 
          index, 
          Comp()); 

Ora, questo accade a lavorare, perché upper_bound può prendere internamente il sovraccarico che soddisfa le sue esigenze, come si chiama, sia Comp()(Region, int) e Comp()(int, Region) (che è il motivo per cui un [](const Region &reg, int index){…} non funzionerebbe).

In realtà ho trovato la soluzione rintracciando i messaggi di errore quando si utilizzava la lambda che ho menzionato prima. Il docs for std::upper_bound at cppreference.com scrittura sul quarto argomento: funzione

confronto oggetti (cioè un oggetto che soddisfa i requisiti di Confronto) che restituisce true se il primo argomento è minore della seconda.

La firma della funzione di confronto deve essere equivalente al seguente:

bool cmp(const Type1 &a, const Type2 &b); 

La firma non necessario avere const &, ma l'oggetto funzione non deve modificare gli oggetti passati. I tipi Type1 e Type2 devono essere tali che un oggetto di tipo T può essere convertito in modo implicito sia Type1 e Type2, e un oggetto di tipo ForwardIt possono essere dereferenziati e poi convertito implicitamente sia Type1 e Type2.

Il tipo Type1 deve essere tale che un oggetto di tipo T può essere implicitamente convertito Type1. Il tipo Type2 deve essere tale che un oggetto di tipo ForwardIt possa essere dereferenziato e quindi implicitamente convertito in Type2.

(cppreference has been fixed da quando ho postato questa domanda, grazie @ T.C.)

Qui, T è il terzo argomento di std::upper_bound e ForwardIt è il tipo dei primi due argomenti.Questa citazione non parla del fatto che l'oggetto funzione sia effettivamente una struttura che sovraccarica il suo operator() per coprire le situazioni "avanti" e "indietro".

Quindi in Regole come scritto, è legale, oppure è un artefatto della mia specifica combinazione di compilatore/libreria standard (g ++ 5.3.1)?

Sono interessato a risposte specifiche per C++ 14 o C++ 17.

esempio completa:

#include <algorithm> 
#include <iostream> 
#include <vector> 


struct Region { 
    Region(int first, int count, int n): 
     first(first), 
     count(count), 
     n(n) 
    { 

    } 

    int first; 
    int count; 
    int n; // think struct Metadata 
}; 


struct Comp 
{ 
    inline bool operator()(const Region &region, int index) const 
    { 
     return region.first < index; 
    } 

    inline bool operator()(int index, const Region &region) const 
    { 
     return index < region.first; 
    } 
}; 


int main() { 
    std::vector<Region> regions; 
    regions.emplace_back(0, 10, 1); 
    regions.emplace_back(10, 10, 2); 
    regions.emplace_back(20, 10, 3); 

    const int lookup = 10; 

    auto iter = std::upper_bound(
     regions.begin(), 
     regions.end(), 
     lookup, 
     Comp()); 

    // yes, I omitted error checking here, with error being iter == regions.begin() 
    std::cout << lookup << " is in region with n = " << (iter-1)->n << std::endl; 
} 

Answer 1

Ora, questo accade a lavorare, perché upper_bound può prendere internamente la sovraccarico che soddisfa le sue esigenze, come si chiama sia Comp()(Region, int) e Comp()(int, Region) (che è il motivo per cui un [](const Region &reg, int index){…} non funzionerebbe).

No, upper_bound chiama solo il secondo sovraccarico Comp. Questo è esattamente ciò che la tua citazione (fissa - grazie @ T.C!!) Riguarda: Il primo argomento per il comparatore è sempre il terzo argomento a upper_bound. I parametri di lambda dovrebbero essere scambiati.

Il sovraccarico di operator() all'interno di un comparatore per upper_bound/lower_bound è intrinsecamente privo di significato, poiché solo un sovraccarico verrà mai selezionato da tali algoritmi.

operator() deve essere sovraccarico come è stato dimostrato quando si lavora con equal_range ed è legale farlo poiché i dettagli interni di un comparatore (o qualsiasi altro fintoreio per quella materia) sono irrilevanti per la libreria: è necessario solo assicurati che l'ordine sia rigoroso (ad es. semantica corretta) e che i sovraccarichi siano chiari.