Czy mogę legalnie używać struktury z przeciążonym operatorem() jako Porównaj dla std :: upper_bound?

Question

mam przypisać struktury tak (rodzaje uproszczonych na przeniesienie punktu), żyjących w std::vector:

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

W wektorze, są one uporządkowane według first. Jeśli dodasz first i count, otrzymasz first następnego regionu; więc w zasadzie ten wektor struktur opisuje metadane dla ciągłych zakresów liczb.

Teraz biorąc pod uwagę liczbę całkowitą, chcę wyszukać metadane. Ponieważ regiony są sortowane, mogę użyć std::upper_bound. I wprowadziły go w ten sposób:

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

To działa, gdy dzwoni std::upper_bound z:

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

Teraz to się dzieje do pracy, ponieważ upper_bound może wewnętrznie odebrać przeciążenie, które pasuje do jego wymagań, co wywołuje zarówno Comp()(Region, int) i Comp()(int, Region) (z tego powodu nie działa [](const Region &reg, int index){…}).

Właściwie wymyśliłem rozwiązanie, śledząc komunikaty o błędach podczas używania lambda, o którym wspomniałem wcześniej. docs for std::upper_bound at cppreference.com pisać o czwarty argument:

porównanie obiekt funkcji (czyli obiekt, który spełnia wymagania Porównaj ), która zwraca prawdziwą jeśli pierwszy argument jest mniej niż sekundę.

Podpis funkcji porównania powinny być równoważne następujący:

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

Podpis nie musi mieć const &, ale obiekt funkcja nie musi modyfikować obiekty przekazywane do niej. Rodzaje Type1 i Type2 musi być takie, aby obiekt typu T można przekształcić pośrednio do zarówno Type1 i Type2 i obiekt typu ForwardIt może dereferencjonowane i pośrednio przekształcić zarówno Type1 i Type2.

typu Type1 musi być takie, aby obiekt typu T może pośrednio przekształca się Type1. Typ Type2 musi być taki, aby obiekt typu ForwardIt można dereferencji, a następnie niejawnie przekonwertować na Type2.

(cppreference has been fixed od Zamieściłem to pytanie, dzięki @ T.C..)

Tutaj T jest trzeci argument std::upper_bound i ForwardIt jest typem pierwszych dwóch argumentów.Ten cytat nie mówi o obiekcie funkcji, który w rzeczywistości jest strukturą, która przeciąży jego operator(), aby pokryć sytuacje "do przodu" i "do tyłu".

Czy w wersji z regulaminem jest to zgodne z prawem, czy też jest artefaktem mojej konkretnej kombinacji kompilator/biblioteka standardowa (g ++ 5.3.1)?

Jestem zainteresowany odpowiedziami specyficznymi dla C++ 14 lub C++ 17.

Pełny przykład:

#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

Teraz to się dzieje do pracy, ponieważ upper_bound może wewnętrznie odebrać przeciążenie który pasuje do jego wymagań, co wywołuje zarówno Comp()(Region, int) i Comp()(int, Region) (co jest powodem, dlaczego [](const Region &reg, int index){…} nie działa).

Nie, upper_bound wywołuje tylko drugie przeciążenie Comp. Dokładnie to cytuje Twój (naprawiony - dzięki @ T.C!!): Pierwszy argument dla komparatora jest zawsze trzecim argumentem dla upper_bound. Parametry lambda powinny zostać zamienione.

Przeciążenie wewnątrz komparatora dla upper_bound/lower_bound jest z natury bez znaczenia, ponieważ tylko jedno przeciążenie zostanie wybrane przez te algorytmy.

operator() powinien być przeładowany jak już pokazano podczas pracy z equal_range, i to jest zgodne z prawem, ponieważ wewnętrzne szczegóły komparatora (lub dowolnego funktora dla tej sprawy) są nieistotne dla biblioteki: Ty tylko trzeba upewnij się, że porządek jest ścisły (tj. prawidłowa semantyka), a przeciążenia są jednoznaczne.