Ricerca di qualsiasi elemento con prima coordinata specifica nel set <pair>>

Question

Sto cercando di capire il seguente problema.

Supponiamo che io ho il seguente contenitore in C++:

std::set<std::pair<int, int> > my_container; 

Questo set (dizionario) viene ordinato rispetto all'ordine < su std::pair<int, int>, che è l'ordine lessicografico. Il mio compito è trovare qualsiasi elemento in my_container che ha la prima coordinata uguale a, ad esempio x, e restituire l'iteratore ad esso. Ovviamente, non voglio usare find_if, perché ho bisogno di risolverlo in tempo logaritmico.

Gradirei qualche consiglio su come questo può essere fatto

Answer 1

È possibile utilizzare lower_bound per questo:

auto it = my_container.lower_bound(std::make_pair(x, std::numeric_limits<int>::min()); 

questo vi darà un iteratore al primo elemento e per il quale e < std::pair(x, -LIMIT) non regge .

Tale elemento ha la propria prima componente>x (nel qual caso non c'è x nel set), o ha il primo componente pari a x ed è il primo di questi. (Si noti che tutti i secondi componenti sono maggiori o uguali a std::numeric_limits<int>::min() per definizione).

Answer 2

Si potrebbe utilizzare std::set::lower_bound per ottenere i limiti inferiore e superiore della gamma di questo tipo:

#include <set> 
#include <iostream> 

// for readability 
typedef std::set<std::pair<int, int> > int_set; 

void print_results(const int_set& s, int i) 
{ 
    // first element not less than {i, 0} 
    int_set::const_iterator lower = s.lower_bound(std::make_pair(i, 0)); 

    // first element not less than {i + 1, 0} 
    int_set::const_iterator upper = s.lower_bound(std::make_pair(i + 1, 0)); 

    for(int_set::const_iterator iter = lower; iter != upper; ++iter) 
     std::cout << iter->first << ", " << iter->second << '\n'; 
} 

int main() 
{ 
    int_set s; 

    s.insert(std::make_pair(2, 0)); 
    s.insert(std::make_pair(1, 9)); 
    s.insert(std::make_pair(2, 1)); 
    s.insert(std::make_pair(3, 0)); 
    s.insert(std::make_pair(7, 6)); 
    s.insert(std::make_pair(5, 5)); 
    s.insert(std::make_pair(2, 2)); 
    s.insert(std::make_pair(4, 3)); 

    print_results(s, 2); 
} 

uscita:

2, 0 
2, 1 
2, 2