một số thùng chứa trong stl không có chức năng tìm kiếm

Question

Một số vùng chứa STL như std::list và std::vector không có phương thức find() làm hàm thành viên. Tại sao vậy? Tôi biết rằng có thay thế bằng cách sử dụng std::find từ <algorithm> nhưng vẫn sử dụng này không phải là 100% tự nhiên.

Answer 1

Vì có chức năng std::find từ algorithm áp dụng cho chúng.

Nói chung, các vùng chứa như std::vector và std::list có độ phức tạp về thời gian tìm kiếm tuyến tính. Như vậy gắn với họ một thành viên find chức năng là một sự thừa vì đã có std::find. Đối với các vùng chứa khác (ví dụ: std::set hoặc std::map v.v.) có cách tốt hơn (tức là, nhanh hơn độ phức tạp tuyến tính) để triển khai tìm kiếm. Như vậy những người triển khai thực hiện thuật toán tìm kiếm nhanh hơn này như các hàm thành viên.

Answer 2

Vùng chứa có tính năng tìm kiếm bằng khóa sẽ được tích hợp phương pháp tìm kiếm (ví dụ: map được triển khai bên trong bằng cây nhị phân có thể tra cứu hiệu quả).

Những người khác, như những người bạn trích dẫn, sẽ cho phép một phạm vi tìm kiếm với std::find nhưng không có một chức năng tìm đặc trưng vì nó sẽ có không có lợi thế so với thuật toán std :: tìm (trừ được sắp xếp/đặc biệt trường hợp)

Answer 3

Nguyên tắc thiết kế chung là sử dụng std::find nếu có thể và thực hiện các chức năng thành viên find khi hiệu quả hơn.

Các container mà làm có thành viên find là container trong đó có một yếu tố nhìn lên cơ chế hiệu quả hơn thì việc tìm kiếm tuyến tính thực hiện trong std::find. Ví dụ: cây tìm kiếm nhị phân chẳng hạn như std::set và std::map hoặc bảng băm như đối tác unordered của chúng.

Answer 4

Sử dụng cùng chức năng cho các vùng chứa khác nhau làm cho API rõ ràng hơn, bạn không phải tìm hiểu tính đặc thù của mỗi vùng chứa, chỉ cách áp dụng một hàm mà bạn sử dụng cho tất cả.

Nó cũng cho sử dụng lại mã - bạn sử dụng các thuật toán mà có lặp từ bất kỳ container mà cung cấp cho họ, vì vậy các thuật toán không phải dựa trên thùng sơn là một std::vector, std::list, vv

Answer 5

như vậy các vùng chứa là std::vector, std::list, std::forward_list và một số khác là các vùng chứa tuần tự. Không có gì tốt hơn so với tìm kiếm tuần tự có thể được áp dụng cho các thùng chứa này. Vì vậy, không cần phải viết lại tìm kiếm tuần tự cho mỗi vùng chứa tuần tự nếu nó giống nhau cho tất cả các vùng chứa này.

Ngoại lệ là lớp std::basic_string ban đầu mô phỏng các chuỗi C đã có các chức năng tìm kiếm đặc biệt như strchr, strstr và các chức năng khác.

Answer 6

find, lower_bound và upper_bound chức năng thành viên chỉ được cung cấp khi hiệu quả hơn hơn bằng cách sử dụng tương đương phi thành viên, hoặc khi không phải là thành viên không thể hoạt động cho API công cộng của container

Lưu ý rằng std::string có chức năng find cung cấp std::find() giống như các cơ sở tìm kiếm tuyến tính cho tìm kiếm ký tự và std::search() các cơ sở giống như dành cho chuỗi con arches: trong khi các phiên bản không phải là thành viên có thể có hiệu quả lớn-O, chúng cũng có thể kém hiệu quả hơn với các hướng dẫn mã máy chuyên dụng thường có sẵn cho tìm kiếm "chuỗi". Ngoài ra còn có các yếu tố lịch sử, tiện lợi và dễ dàng chuyển đổi.

Khá ngoài các vấn đề về hiệu quả, đó là cần lưu ý rằng một số container:

• vốn đã hoặc sắp xếp (multi-set, map) hoặc không được phân loại (unordered_map, unordered_set), thường không được phân loại (ví dụ std::string) hoặc dễ dàng hoặc là (std::vector)

• hỗ trợ công khai chuyển tiếp lặp lại và/hoặc truy cập ngẫu nhiên

• thể tư nhân hỗ trợ tìm kiếm nhị phân

• có một API công cộng chuyên ngành để truy cập yếu tố đó tái sử dụng tiềm năng của thuật toán là tương đối giới hạn (ví dụ unordered_map::bucket/::begin(n) et al)

Nó cũng quan tâm rằng tìm kiếm trong một vector thể được thực hiện bằng cách sử dụng nhiều thuật toán lớn:

• std::find hiện một brute force tuyến tính O (n) tìm kiếm mà trước tiên sẽ "tìm" các phần tử chỉ mục thấp hơn,

• std::binary_search yêu cầu phải có một vector được sắp xếp nhưng nhảy xung quanh để đạt được độ phức tạp O (log2n).

• tùy chọn khác như tìm kiếm ngoại suy và băm có thể được áp dụng

Làm thế nào bạn sẽ chọn để thực hiện và bổ sung làm thành viên? Có vẻ hơi tùy ý. Tuy nhiên, lựa chọn sử dụng có thể là yếu tố quan trọng về hiệu năng: đối với hàng triệu yếu tố, trung bình một nửa triệu so sánh phần tử trước một trận đấu và toàn bộ triệu khi phần tử không có, trong khi đó, binary_search thường mất ~ 20 so sánh đường.

Các container với find thường không cung cấp sự linh hoạt như vậy, và find và/hoặc lower_bound/upper_bound họ cung cấp có thể được xem như thay thế cho các khoản tương đương phi thành viên, và có khả năng cách hợp lý duy nhất để tìm kiếm các container.

Answer 7

Như đã đề cập trong các nhận xét khác, lý do thiết kế là vector::find() có thể được triển khai hiệu quả như chức năng không phải là thành viên std::find(). Lợi ích của việc sử dụng thứ hai là nó tách rời các cấu trúc dữ liệu và các toán tử hoạt động trên cấu trúc dữ liệu, làm tăng khả năng bảo trì (điều này thuận lợi cho các nhà phát triển của thư viện).

Tuy nhiên, lợi ích của trước đây là nó sẽ làm cho API giữa tất cả các vùng chứa nhất quán và làm cho mã khách hàng ít tiết hơn. Điều này sẽ làm tăng khả năng học và dễ đọc (điều này thuận lợi cho người dùng thư viện). Ngoài ra, API nhất quán sẽ cho phép viết mã chung. Xem xét việc này:

template <typename Container, typename T> 
void foo(const Container& c, const T& x) { 
    if (std::find(c.begin(), c.end(), x) != c.end()) { 
     // ... 
    } 
} 

Trên đây là không hiệu quả khi Container là một std::map hoặc std::set. Để làm cho nó hiệu quả, chúng ta cần phải làm:

template <typename Container, typename T> 
void foo(const Container& c, const T& x) { 
    if (c.find(x) != c.end()) { 
     // ... 
    } 
} 

Nhưng sau đó nó không biên dịch cho std::vector và std::list. Điều này đặt ra gánh nặng cho người sử dụng thư viện để viết hàm tổng quát của mình bằng tay chuyên/quá tải đối với từng loại họ muốn hỗ trợ:

template <typename T> 
bool contains(const std::vector<T>& c, const T& x) { 
    return std::find(c.begin(), c.end(), x) != c.end(); 
} 

template <typename T> 
bool contains(const std::set<T>& c, const T& x) { 
    return c.find(x) != c.end(); 
} 

template <typename Container, typename T> 
void foo(const Container& c, const T& x) { 
    if (contains(c, x)) { 
     // ... 
    } 
} 

Tôi xác nhận rằng thực hiện các loại quyết định thiết kế là khó khăn, nhưng quan điểm của tôi là các nhà thiết kế của STL đã phạm sai lầm ở đây. Các gánh nặng bảo trì rất nhỏ có vẻ khá phần lớn đáng giá hơn API và nhất quán cho người dùng. Tóm lại, vì find phải là một hàm thành viên cho một số vùng chứa (để thực hiện), sau đó find phải là một hàm thành viên cho tất cả các vùng chứa (để nhất quán). Lưu ý rằng tôi hoàn toàn ổn với các thuật toán khác là các hàm không phải là thành viên.

_{(Ý tôi là, thôi nào, một thùng chứa theo định nghĩa một cái gì đó có chứa nội dung. Sẽ không quan trọng để người dùng viết một hàm "chứa" chung và hiệu quả. Thực tế, tôi cho rằng nó nên được thêm vào}