2012-06-24 17 views
11

Tôi luôn luôn tự hỏi tại sao không cótại sao không sắp xếp (v) trong C++?

sort(v);// same as std::sort(v.begin(),v.end()) 

Nếu tôi nhớ lại thời gian một cách chính xác lâu rồi tôi thấy một clip boostcon nơi loa nói rằng khái niệm được yêu cầu cho điều này, nhưng tôi không hiểu tại sao. BTW Tôi đã thử này (trong VS 11) và nó hoạt động niceli từ những gì tôi có thể nhìn thấy.

template <typename Container> 
void sortfx(Container& c) 
{ 
    std::sort(c.begin(),c.end()); 
} 
int main() 
{ 

    std::vector<double> v; 
    //std::list<double> v; this causes compile errors 
    v.push_back(1701); 
    v.push_back(1729); 
    v.push_back(74656); 
    v.push_back(2063); 
    sortfx(v); 
    assert(std::is_sorted(begin(v),end(v))); 

} 

EDIT: Bjarne mình giải thích các khái niệm, với loại làm ví dụ :) https://www.informit.com/articles/article.aspx?p=2080042&WT.rss_f=Article&WT.rss_a=An%20Interview%20with%20Bjarne%20Stroustrup&WT.rss_ev=a

+0

Đoán rằng họ chỉ đoán rằng nó không đáng để thêm khi bạn chỉ có thể dành thời gian để viết hai đối số, hoặc của riêng bạn, hoặc rằng công chúng sẽ không nhận được rất nhiều sử dụng trong số đó. Đó là một trong những bổ sung thư viện cá nhân có thể hoạt động tốt cho một số người. Bên cạnh đó, nếu họ thêm 'sắp xếp' cho toàn bộ thùng chứa, họ có thể sẽ phải thêm những người khác nữa. – chris

+3

Bạn có thể thực hiện nó. Nhưng nếu bạn muốn sắp xếp một mảng tích hợp thì sao? Bạn nên sử dụng SFINAE hoặc một số cơ chế khác để đạt được điều tương tự. Nó chỉ là nhiều mã mà không có lý do. 'std :: sort (c.begin(), c.end());' là đủ ngắn. – mfontanini

+2

@mfontanini Và những người khác sẽ nghĩ rằng luôn luôn chỉ rõ bộ so sánh được sử dụng cũng là "đủ ngắn", nhưng chúng tôi vẫn không phải làm vậy. Tôi đồng ý rằng đó là một thiếu sót gây phiền nhiễu, bởi vì thực sự 99% thời gian chúng tôi muốn sắp xếp toàn bộ container. – Voo

Trả lời

10

Không phải là mở rộng std::sort(v) ->std::sort(v.begin(), v.end()) cần khái niệm, nhưng hàm sắp xếp thay thế lấy thông số bổ sung cho so sánh - std::sort(v.begin(), v.end(), compare).

Nếu bạn có một cuộc gọi std::sort(v, compare), việc triển khai sẽ cần các khái niệm để phân biệt với std::sort(start, end) đối với loại không chứa.

Đầu đề <algorithm> có đầy đủ các mẫu với loại sự cố này.

+0

Trên thực tế có cả 'sắp xếp (v, so sánh)' và 'sắp xếp (bắt đầu, kết thúc)' sẽ hoạt động tốt trong hầu hết các trường hợp ([ví dụ] (http://ideone.com/7QTf44)). Như đã bình luận [ở đây] (http://herbsutter.com/2011/10/07/why-no-container-based-algorithms/#comment-3622), một vấn đề sẽ chỉ nảy sinh nếu bản thân container được sử dụng như một bộ so sánh , trong trường hợp này, bạn sẽ nhận được một thông báo lỗi nhiều báo lỗi chỉ đến việc triển khai thực hiện quá tải của quá trình thực hiện hai lần lặp ([ví dụ đơn giản] (http://ideone.com/DR5JN5), được so sánh với [cùng mã dòng cuối cùng đã nhận xét] (http://ideone.com/N4TfMa)). –

3

<algorithm> chức năng không làm việc trên container trực tiếp. Chúng chỉ tương tác với các trình vòng lặp, mà không có bất kỳ kiến ​​thức ngữ cảnh nào của vùng chứa. Tôi thấy không có hại nếu bạn sử dụng một ký hiệu sắp xếp phạm vi đầy đủ ngắn cho mục đích của riêng bạn, nhưng bạn phải giả định đối tượng có giao diện bắt đầu/kết thúc, cũng xảy ra là các trình vòng lặp hai chiều.

1

Không có gì về điều này đòi hỏi khái niệm. Các phạm vi không phức tạp hơn các trình lặp thực sự.

1

Điều gì sẽ xảy ra nếu bạn chỉ muốn sắp xếp một tập con của vùng chứa?

Gần đây tôi đã đăng câu hỏi tương tự về lý do tại sao for_each không phải là chức năng thành viên của Container thay vì là độc lập. tức là v.for_each([&sum] (int i) { sum += i; });

+1

Tôi không nghĩ rằng có một thời gian mà tôi chỉ muốn sắp xếp * một phần * của một container. – cHao

+0

Tôi cũng vậy, nhưng có lẽ ai đó ở đâu đó có – James

+0

Tôi đã sử dụng một phần sắp xếp để tìm trung vị cho một số bài tập về nhà thống kê ngớ ngẩn. – EvilTeach

5

Từ Learning Standard C++ as a New Language (PDF) Stroustrup, C/C++ Journal Journal. trang 43-54. Tháng 5 năm 1999:

Loại đồng bằng (v) sẽ đơn giản hơn trong trường hợp này, nhưng đôi khi chúng tôi muốn sắp xếp một phần của hộp chứa để xác định đầu và cuối của thứ chúng tôi muốn sắp xếp.

Điều đó hợp lý với tôi. Nó là tầm thường để tạo ra một wrapper, như bạn đã chứng minh, và nó không terribly cồng kềnh để sử dụng mà không có một wrapper. Có một thứ hai sort() mà lấy Container chỉ có vẻ không có giá trị nó.

0

Các khái niệm không phải là yêu cầu cho điều này - nhưng (khi chúng được đề xuất trong khi chuẩn hóa C++ 11), chúng sẽ làm cho việc triển khai này trở nên khá dễ dàng.

Vì nó đứng ngay bây giờ, bạn có thể thực hiện việc này bằng cách cung cấp thêm một số quá tải (hoặc có thể là chuyên môn rõ ràng) cho std::sort. Vấn đề, tất nhiên, là std::sort không phải là thuật toán duy nhất, vì vậy bạn chắc chắn muốn làm tương tự cho rất nhiều thuật toán khác cũng (gần như tất cả trong số họ, rất có thể).

Các khái niệm (cụ thể là bản đồ khái niệm, nếu bộ nhớ phục vụ) sẽ cung cấp một cách khá sạch sẽ để cung cấp (tương đương) tất cả các quá tải đó theo cách tương đối tập trung, vì vậy bạn sẽ có tất cả các bộ điều hợp đó ở một nơi thay vì N vị trí (một cho mỗi thuật toán). Vẫn còn tốt hơn, miễn là chúng tuân theo các quy ước bình thường, nó sẽ làm việc cho các thuật toán khác nữa.

Khá nhiều người tin rằng phạm vi là cách điều này sẽ được xử lý - thuật toán nên hoạt động trên phạm vi và bất kỳ vùng chứa nào nên xác định phạm vi (nhưng cũng phải có các cách khác để xác định phạm vi). Mặc dù điều này có thể là một ý tưởng chung nhưng dường như có một số bất đồng chính xác về chi tiết chính xác về những gì cần phải xác định phạm vi, cách xác định chúng, v.v.

Nếu bạn thực sự muốn khám phá điều này, Boost đã có range library bao gồm các phiên bản dựa trên phạm vi của hầu hết các thuật toán chuẩn (và một số các thuật toán khác). Ít nhất nếu bộ nhớ phục vụ, điều này bao gồm một số bộ điều hợp để tạo ra một phạm vi từ một container, vì vậy những thứ như sort(c) sẽ hoạt động mà không cần phải chỉ định rõ một dải hoặc các trình lặp.

Các vấn đề liên quan