Puis-je légalement utiliser un struct avec operator() surchargé comme Compare for std::upper_bound ?

Question

J'ai des structures comme celle-ci (types simplifiés pour poursuivre l'objectif), qui vivent dans un système de gestion de l'information. std::vector :

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

Dans le vecteur, ils sont classés par first . Si vous ajoutez first et count vous obtenez le first de la région suivante ; en gros, ce vecteur de structs décrit les métadonnées pour des plages contiguës de nombres.

Maintenant, étant donné un nombre entier, je veux rechercher les métadonnées. Comme les régions sont triées, je peux utiliser std::upper_bound . Je l'ai mis en œuvre de cette façon :

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

Cela fonctionne, lorsque l'on appelle std::upper_bound avec :

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

Il se trouve que ça marche, parce que upper_bound peut choisir en interne la surcharge qui correspond à ses besoins, car il appelle les deux Comp()(Region, int) et Comp()(int, Region) (c'est la raison pour laquelle un [](const Region &reg, int index){…} ne fonctionnerait pas).

En fait, j'ai trouvé la solution en retraçant les messages d'erreur lors de l'utilisation du lambda que j'ai mentionné précédemment. Le site docs pour std::upper_bound à cppreference.com écrire sur le quatrième argument :

objet de la fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de exigences de Compare) qui renvoie vrai si le premier argument est inférieur au second.

La signature de la fonction de comparaison doit être équivalente à celle de la fonction de comparaison de l'UE. suivante :

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

La signature ne doit pas nécessairement avoir const & mais l'objet fonction ne doit pas modifier les objets qui lui sont passés. Les types Type1 et Type2 doit être tel qu'un objet de type T peut être implicitement converti en les deux Type1 et Type2 et un objet de type ForwardIt peut être déréférencée et ensuite implicitement convertie à la fois en Type1 et Type2 .

Le type Type1 doit être tel qu'un objet de type T peut être implicitement converti en Type1 . Le type Type2 doit être telle qu'une objet de type ForwardIt peut être déréférencé et ensuite implicitement converti en Type2 .

(cppreference a été fixé depuis que j'ai posté cette question, merci @T.C.)

Ici, T est le troisième argument de std::upper_bound et ForwardIt est le type des deux premiers arguments. Cette citation ne parle pas du fait que l'objet de la fonction est en fait un struct qui surcharge sa fonction operator() pour couvrir les situations "avant" et "arrière".

Donc, dans les Règles-Ecrites, est-ce légal, ou est-ce un artefact de ma combinaison spécifique de compilateur/bibliothèque standard (g++ 5.3.1) ?

Je suis intéressé par les réponses spécifiques à C++14 ou C++17.

Exemple complet :

#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

Il se trouve que ça marche, parce que upper_bound peut choisir en interne le qui correspond à ses besoins, car elle appelle les deux Comp()(Region, int) et Comp()(int, Region) (c'est la raison pour laquelle un [](const Region &reg, int index){…} ne fonctionnerait pas).

Non, upper_bound uniquement les appels Comp La deuxième surcharge de l'entreprise. C'est précisément le sujet de votre citation (corrigée - merci @T.C. !): Le premier argument au comparateur est toujours le troisième argument à upper_bound . Les paramètres de la lambda doivent être échangés.

Surcharge de travail operator() à l'intérieur d'un comparateur pour upper_bound / lower_bound est intrinsèquement dénuée de sens, car une seule surcharge sera jamais choisie par ces algorithmes.

operator() devrait être surchargé comme vous l'avez montré en travaillant avec equal_range Il est légal de le faire puisque les détails internes d'un comparateur (ou de tout autre foncteur) ne sont pas pertinents pour la bibliothèque : Vous devez seulement vous assurer que l'ordre est strict (c'est-à-dire que la sémantique est correcte) et que les surcharges ne sont pas ambiguës.