Tại sao không có toán tử [] cho danh sách std ::?

Question

Bất cứ ai có thể giải thích tại sao không phải là toán tử [] thực hiện cho một danh sách std ::? Tôi đã tìm kiếm xung quanh một chút nhưng không tìm thấy câu trả lời. Nó sẽ không quá khó để thực hiện hoặc tôi thiếu một cái gì đó?

Answer 1

Lấy một phần tử theo chỉ mục là một hoạt động O (n) cho danh sách liên kết, đó là những gì std::list là. Vì vậy, nó đã được quyết định rằng việc cung cấp operator[] sẽ là lừa đảo, vì mọi người sẽ bị cám dỗ để chủ động sử dụng nó, và sau đó bạn sẽ thấy mã như:

std::list<int> xs; 
for (int i = 0; i < xs.size(); ++i) { 
    int x = xs[i]; 
    ... 
} 

mà là O (n^2) - rất khó chịu. Vì vậy, tiêu chuẩn ISO C++ đề cập cụ thể rằng tất cả các chuỗi STL hỗ trợ operator[] nên làm điều đó trong thời gian cố định phân bổ (23.1.1 [lib.sequence.reqmts]/12), có thể đạt được cho vector và deque, nhưng không phải list.

Đối với trường hợp bạn thực sự cần điều đó đại loại như vậy, bạn có thể sử dụng std::advance thuật toán:

int iter = xs.begin(); 
std::advance(iter, i); 
int x = *iter; 

Answer 2

Nó sẽ không quá khó (đối với người triển khai) nhưng nó sẽ là quá khó khăn trong thời gian chạy, vì hiệu suất sẽ là khủng khiếp trong hầu hết các trường hợp. Buộc người dùng đi qua từng liên kết sẽ làm cho nó rõ ràng hơn những gì đang xảy ra trong đó hơn 'myList [102452]' sẽ.

Answer 3

Tôi nghĩ rằng tôi đã tìm thấy câu trả lời trong một SO gửi Extending std::list

"nhà điều hành của bạn [] là O (N) thời gian "- điều này là chính xác lý do tại sao nó không được bao gồm trong tiêu chuẩn std :: danh sách <>. - Michael Burr ngày 14 tháng 12 tại 17:29

Tuy nhiên, đó có phải là lý do duy nhất không?

CHỈNH SỬA: Dường như mọi người đã đề cập đến nó là vấn đề nhất quán về hiệu suất sau đó thực hiện nghiêm ngặt.

Answer 4

Trên thực tế, có hoàn toàn không có lý do gì để không cung cấp operator [] hoặc ít nhất là phương pháp tại (int), vì hai lý do:

• Đây là danh sách liên kết đôi, vì vậy bạn cần phải di chuyển ở hầu hết kích thước()/2 nơi trình vòng lặp của bạn để lấy chỉ mục của bạn, và chi phí để giữ lại một vài vòng lặp cố định hơn là rất thấp. Và cuối cùng, thư viện Qt cung cấp toán tử [] và tại, và tôi không thấy chi phí hiệu năng sử dụng nó.
• buộc người khác không sử dụng là thói quen lập trình rất xấu, vì danh sách sẽ sử dụng nhiều thùng chứa, nếu bạn có quyền truy cập ngẫu nhiên gần quyền truy cập được liên kết, có nhiều ví dụ khi bạn cần cả hai quyền truy cập mà thời gian chạy.