Chức năng nào trong thư viện std là ở đó để tìm kiếm nhị phân một vector và tìm một phần tử?

Question

Tôi có cấu trúc nút

struct Node{CString text, int id;}; 

trong một véc tơ được sắp xếp.

Tôi tự hỏi nếu có một hàm trong thuật toán sẽ thực hiện tìm kiếm nhị phân vectơ và tìm phần tử.

Answer 1

std::binary_search() sẽ cho bạn biết nếu một giá trị tồn tại trong thùng sơn.

std::lower_bound()/std::upper_bound() sẽ trả về một trình lặp cho lần xuất hiện đầu tiên/cuối cùng của giá trị

Đối tượng của bạn cần triển khai operator< để các thuật toán này hoạt động.

Answer 2

Vâng, có một chức năng gọi là "binary_search" std :: binary_search

Bạn cho nó đầu tiên, cuối cùng và một giá trị hoặc một vị.

Xem here cho một mẫu

Kết hợp với Martin York's toán tử == và bạn sẽ có OK (hoặc bạn có thể viết một functor vị

Answer 3

Thay vì vector được sắp xếp < Nút >
Tại sao không sử dụng bản đồ. Đây là một container được sắp xếp. Vì vậy, bất kỳ tìm kiếm được thực hiện trên điều này thông qua std :: find() tự động có các thuộc tính giống như một tìm kiếm nhị phân.

Answer 4

Sử dụng std::equal_range để tìm một loạt các phần tử trong một véc tơ được sắp xếp. std::equal_range trả về số std::pair của vòng lặp, cho bạn phạm vi trong vectơ của các phần tử bằng đối số bạn cung cấp. Nếu phạm vi trống, thì mục của bạn không có trong vectơ và độ dài của phạm vi cho bạn biết số lần mục của bạn xuất hiện trong vectơ.

Dưới đây là một ví dụ sử dụng ints thay vì struct Node:

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <string> 

int main(int argc, const char * argv[]) 
{ 
    std::vector<int> sorted = { 1, 2, 2, 5, 10 }; 

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20); 
    // Outputs "5 5" 
    std::cout << std::distance(sorted.begin(), range.first) << ' ' 
       << std::distance(sorted.begin(), range.second) << '\n'; 

    range = std::equal_range(sorted.begin(), sorted.end(), 5); 
    // Outputs "3 4" 
    std::cout << std::distance(sorted.begin(), range.first) << ' ' 
       << std::distance(sorted.begin(), range.second) << '\n'; 

    range = std::equal_range(sorted.begin(), sorted.end(), -1); 
    // Outputs "0 0" 
    std::cout << std::distance(sorted.begin(), range.first) << ' ' 
       << std::distance(sorted.begin(), range.second) << '\n'; 

    return 0; 
} 

Để làm công việc này với struct Node bạn hoặc sẽ phải cung cấp một operator < cho struct Node hoặc vượt qua trong một so sánh để std::equal_range. Bạn có thể làm điều đó bằng cách cung cấp lambda làm đối số cho std::equal_range để so sánh cấu trúc của bạn.

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} }; 
Node searchForMe { "goodbye", 6 }; 
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe, 
           [](Node lhs, Node rhs) { return lhs.id < rhs.id; });