Znajdowanie elementu o określonej pierwszej współrzędnej w zestawie <pair>>

Question

Próbuję znaleźć następujący problem.

Załóżmy, że ma następujący kontener w C++

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

ten zestaw (słownik) jest sortowany w odniesieniu do kolejności < na std::pair<int, int>, która jest leksykograficznym kolejności. Moim zadaniem jest znaleźć dowolny element w , który ma pierwszą współrzędną równą, powiedzmy x, i zwrócić iterator do niego. Oczywiście nie chcę używać find_if, ponieważ muszę rozwiązać ten problem w czasie logarytmicznym.

Byłbym wdzięczny za wszelkie wskazówki, w jaki sposób można to zrobić

Answer 1

Można użyć lower_bound na to:

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

to daje iterator do pierwszego elementu e dla których e < std::pair(x, -LIMIT) nie wytrzymuje .

Taki element ma swój pierwszy komponent>x (w tym przypadku nie ma w zestawie x) lub ma pierwszy komponent równy x i jest pierwszym takim. (Zauważ, że wszystkie drugie komponenty są z definicji większe lub równe std::numeric_limits<int>::min()).

Answer 2

Można użyć std::set::lower_bound dostać dolne i górne granice zakresu tak:

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

wyjściowa:

2, 0 
2, 1 
2, 2