Suchen irgendein Element mit bestimmten ersten Koordinaten in Set <pair>>

Question

Ich versuche, das folgende Problem herauszufinden.

glaube, ich habe folgende Behälter in C++:

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

Dieser Satz (Wörterbuch) in Bezug auf die Reihenfolge < auf std::pair<int, int> sortiert ist, das die lexikographische Ordnung ist. Meine Aufgabe ist es irgendein Element in my_container zu finden, das die erste Koordinate hat, die gleich ist, sagen x, und den Iterator dorthin zurückzubringen. Offensichtlich möchte ich nicht find_if verwenden, weil ich dies logarithmisch lösen muss.

ich irgendwelche Ratschläge zu schätzen wissen würde, wie kann diese

Answer 1

Sie dafür verwenden können lower_bound erfolgen:

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

Dies gibt Ihnen einen Iterator auf das erste Element e für die e < std::pair(x, -LIMIT) nicht hält .

Ein solches Element hat entweder seine erste Komponente>x (in diesem Fall gibt es in dem Satz keine x ist), oder nur die erste Komponente gleich x und ist die erste. (Beachten Sie, dass alle zweiten Komponenten definitionsgemäß größer oder gleich std::numeric_limits<int>::min() sind).

Answer 2

Sie std::set::lower_bound verwenden könnten die unteren und oberen Grenzen des Bereichs wie folgt zu erhalten:

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

Ausgang:

2, 0 
2, 1 
2, 2