Двоичный поиск по вектору

Question

структур У меня есть вектор структур, содержащий-структуру с этой архитектурой

struct Main{ 

    int mainID; 
    string mainDIV; 
    string mainNAME; 

} 

возможно использовать бинарный поиск на структуры? Я знаю, что его легко использовать на значения, используя

binary_search(vector.begin() , vector.end() , 5) 

Но есть способ, как пройти обратный вызов или что-то на самом деле найти атрибут структуры? Я не могу найти что-либо, связанное с этой темой.

Answer 1

Да, это возможно. value, который принимает std::binary_search, имеет смысл только по сравнению с элементами контейнера. В простейшем случае (если Main поддерживает operator< где-то), вы должны указать элемент типа Main в качестве значения:

// check if this specific Main exists 
bool yes = std::binary_search(v.begin(), v.end(), Main{0, "some", "strings"}); 

// does exactly the same thing as above 
bool yes = std::binary_search(v.begin(), v.end(), Main{0, "some", "strings"} 
    , std::less<Main>{}); 

Если он не поддерживает operator< (или ваш контейнер заказан чем-то другое, например, mainID), то вы должны будете предоставить компаратор себя, что алгоритм будет использовать:

// check if there is a Main with mainID 5 
bool yes = std::binary_search(v.begin(), v.end(), 5, 
    [](const Main& element, const int value) { 
     return element.mainID < value; 
    }); 

Answer 2

вы должны предоставить информацию binary_search(), чтобы сказать ему, как сравнить свои объекты. Два наиболее распространенных способа: либо добавить operator<() в struct, если это возможно, либо предоставить вспомогательную функцию, которая может сравнивать два struct с.

Первая форма будет выглядеть примерно так:

struct Main { 
    int mainID ; 
    string mainDIV ; 
    string mainNAME ; 
    bool operator<(const Main & other) const 
    { 
    return mainID < other.mainID ; 
    } 
} 

Это будет сравнивать только на на mainID, но вы можете расширить его оттуда.

Кроме того, это только учит компилятору, как сравнивать два struct Main, в то время как ответ Барри выше будет соответствовать int и struct Main. Но давайте продолжим этот ответ.

Теперь, чтобы найти запись для 5, мы должны сделать это в struct Main:

struct Main search_key = { 5 } ; 
bool yes = std::binary_search(v.begin(), v.end(), search_key) ; 

Теперь, это не очень элегантно, и к тому же, если у вас есть конструктор для struct Main (и гаванью» t положите его в свой пример), это даже не сработает. Поэтому мы добавляем еще один конструктор только для int.

struct Main 
{ 
    Main(int id, const string & a_div, const string & a_name) : id(id), div(a_div), name(a_name) { } 
    Main(int id) : id(id) { } 
    int id ; 
    string div, name ; 

    bool operator<(const Main &o) const { return id < o.id ; } 
} ; 

Теперь мы можем сделать немного короче вид:

bool has_3 = std::binary_search(v.begin(), v.end(), Main(3)) ; 

Историческая справка: Бьярне пытается в течение некоторого времени, чтобы получить операторы сравнения по умолчанию в стандарте, но не все были взволнованы на совещаниях по стандартам. Хотя на последнем собрании был некоторый прогресс, и, возможно, это может появиться, когда C++ 17 - это вещь.