Tìm bất kỳ thành phần nào có toạ độ đầu tiên cụ thể trong bộ <pair>>

Question

Tôi đang cố gắng tìm ra vấn đề sau.

Giả sử tôi có container sau đây trong C++:

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

bộ này (từ điển) được sắp xếp liên quan đến trật tự < trên std::pair<int, int>, đó là trật tự tự từ điển. Nhiệm vụ của tôi là tìm bất kỳ phần tử nào trong my_container có toạ độ đầu tiên bằng, ví dụ x và trả về trình lặp đó cho nó. Rõ ràng, tôi không muốn sử dụng find_if, bởi vì tôi cần phải giải quyết điều này trong thời gian logarit.

tôi sẽ đánh giá cao bất kỳ lời khuyên về cách thức này có thể được thực hiện

Answer 1

Bạn có thể sử dụng lower_bound cho việc này:

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

này sẽ cung cấp cho bạn một iterator tới phần tử đầu tiên e mà e < std::pair(x, -LIMIT) không giữ .

Thành phần như vậy hoặc có thành phần đầu tiên>x (trong trường hợp này không có x trong bộ) hoặc có thành phần đầu tiên bằng x và là thành phần đầu tiên. (Lưu ý rằng tất cả các thành phần thứ hai lớn hơn hoặc bằng std::numeric_limits<int>::min() theo định nghĩa).

Answer 2

Bạn có thể sử dụng std::set::lower_bound để có được các giới hạn trên và dưới của dãy núi này như thế này:

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

Output:

2, 0 
2, 1 
2, 2