Đối với một danh sách được liên kết đơn giản trong đó truy cập ngẫu nhiên vào các phần tử danh sách không phải là yêu cầu, có bất kỳ lợi thế đáng kể nào (hiệu suất hay cách khác) để sử dụng std::list thay vì std::vector? Nếu yêu cầu truyền tải ngược, có hiệu quả hơn khi sử dụng std::slist và reverse() danh sách trước khi lặp qua các thành phần của nó không?Hiệu suất tương đối của std :: vector so với std :: list so với std :: slist?
Như thường lệ, câu trả lời hay nhất cho câu hỏi hiệu suất là profile cả hai cách triển khai cho trường hợp sử dụng của bạn và xem nhanh hơn.
Nói chung nếu bạn có chèn vào dữ liệu cấu trúc (trừ ở cuối) sau đó vector có thể chậm hơn, nếu không trong hầu hết các trường hợp vector dự kiến sẽ hoạt động tốt hơn list nếu chỉ cho data locality issues, điều này có nghĩa rằng nếu hai các phần tử liền kề trong tập dữ liệu nằm liền kề trong bộ nhớ thì phần tử tiếp theo sẽ nằm trong bộ đệm của bộ xử lý và sẽ không phải trang lỗi bộ nhớ vào bộ đệm.
Cũng lưu ý rằng khoảng trống trên vector là hằng số (3 con trỏ) trong khi chi phí trên không gian cho mỗi phần tử là, điều này cũng làm giảm số lượng phần tử đầy đủ (dữ liệu cộng với phí) trong bộ nhớ cache cùng một lúc.
Hãy nhớ rằng thậm chí chèn nhanh hơn trong một véc tơ hơn trong một danh sách liên kết nếu vị trí chèn vào phải được tìm kiếm.Ví dụ, lấy một loạt các số nguyên ngẫu nhiên và chèn chúng vào thứ tự sắp xếp thành một véc tơ hoặc một danh sách liên kết - vector sẽ luôn nhanh hơn, bất kể tổng số mục, do bộ nhớ cache bị mất khi tìm kiếm điểm chèn vào danh sách được liên kết. – Collin
Khá nhiều nơi duy nhất mà danh sách liên kết nhanh hơn khi bạn làm nhiều nối, vì nó không liên quan đến số lượng lớn bộ nhớ cache, và mỗi mối nối là hoạt động liên tục (có thể di chuyển một số lớn các mục từ một danh sách được liên kết đến một danh sách khác). – Collin
"Cũng nên nhớ rằng chi phí không gian cho véc tơ là không đổi" Chỉ khi bạn rất cẩn thận. Để sử dụng bình thường, nó có chi phí không gian tuyến tính, giống như một 'danh sách'. Xem: push_back tuyến tính phân bổ. –
Đơn giản là không. Danh sách có lợi thế hơn Vector, nhưng truy cập tuần tự không phải là một trong số chúng - nếu đó là tất cả những gì bạn đang làm, thì một vectơ tốt hơn.
Tuy nhiên .. một véc tơ là tốn kém hơn để thêm các yếu tố bổ sung hơn một danh sách, đặc biệt là nếu bạn đang chèn ở giữa.
Hiểu cách các bộ sưu tập này được triển khai: một vectơ là một mảng dữ liệu tuần tự, một danh sách là một phần tử chứa dữ liệu và con trỏ đến các phần tử tiếp theo. Khi bạn hiểu điều đó, bạn sẽ hiểu lý do tại sao danh sách phù hợp để chèn và không phù hợp để truy cập ngẫu nhiên.
(vì vậy, phép lặp ngược lại của vectơ hoàn toàn giống với lặp lại chuyển tiếp - trình lặp chỉ trừ kích thước của các mục dữ liệu mỗi lần, danh sách vẫn phải nhảy tới mục tiếp theo qua con trỏ)
Đây là điều hiển nhiên và 99% thời gian, câu trả lời đúng. Nếu bạn cần truyền tải ngược, hãy chạy vòng lặp for backwards. Mảng/Vectơ cung cấp truy cập ngẫu nhiên, truy cập tuần tự rất nhanh và truy cập tuần tự nhanh như nhau từ bất kỳ điểm bắt đầu ngẫu nhiên nào trong vectơ. Danh sách được yêu thích chỉ có một nội dung '' và đó là xóa thành viên hoặc chèn thành viên vào một thời điểm nào đó dọc theo danh sách. Họ khá nhiều hút mọi thứ khác. Chậm, chậm, chậm. Trồng một mảng/vector dễ dàng như một malloc() và memmove() mới. Sử dụng Vprime, Vgrow, bạn chỉ có thể phát hành lại và sao chép qua lại. – RocketRoy
Nếu bạn cần truyền tải ngược, một đường trượt không thể là cơ sở hạ tầng cho bạn.
Danh sách liên kết thông thường (gấp đôi) cung cấp cho bạn thời gian chèn và xóa liên tục ở bất kỳ đâu trong danh sách; một vectơ chỉ cho phép chèn và xóa thời gian liên tục được phân bổ ở cuối danh sách. Đối với một chèn vector và thời gian xóa là tuyến tính bất cứ nơi nào khác hơn là kết thúc. Đây không phải là toàn bộ câu chuyện; cũng có những yếu tố không đổi. Một vectơ là một cơ sở hạ tầng đơn giản hơn, có những ưu điểm và nhược điểm tùy thuộc vào ngữ cảnh.
Cách tốt nhất để hiểu điều này là hiểu cách chúng được triển khai. Một danh sách liên kết có một con trỏ tiếp theo và con trỏ trước đó cho mỗi phần tử. Một vectơ có một mảng các phần tử được giải quyết bằng chỉ mục. Từ điều này, bạn có thể thấy rằng cả hai có thể thực hiện chuyển tiếp hiệu quả và ngược lại, trong khi chỉ một véc tơ có thể cung cấp truy cập ngẫu nhiên hiệu quả. Bạn cũng có thể thấy rằng chi phí bộ nhớ của một danh sách được liên kết là mỗi phần tử trong khi đối với vectơ đó là hằng số. Và bạn cũng có thể thấy lý do tại sao thời gian chèn khác nhau giữa hai cấu trúc.
Một điểm quan trọng là danh sách có thêm con trỏ cho mỗi phần tử trong khi một vectơ chỉ có ba con trỏ cho toàn bộ cấu trúc dữ liệu. – Motti
Vâng, đó là sự thật: Câu trả lời của tôi cho biết: "Danh sách liên kết có con trỏ tiếp theo cho mỗi phần tử. Một vectơ có một mảng các phần tử được chỉ mục theo chỉ mục". Rõ ràng từ "và" bị thiếu (!) Và tôi sẽ làm cho các con trỏ thêm rõ ràng. – janm
Xem câu hỏi này để biết chi tiết về các chi phí:
What are the complexity Guarantees of the standard containers
Nếu bạn có một slist và bây giờ bạn muốn đi qua nó theo thứ tự ngược lại tại sao không thay đổi kiểu liệt kê ở khắp mọi nơi?
Cấu trúc dữ liệu mặc định để nghĩ đến trong C++ là Vector.
Hãy xem xét những điểm sau đây ...
1] Traversal:
Danh sách các nút nằm rải rác ở khắp mọi nơi trong bộ nhớ và do đó danh sách traversal dẫn đến bộ nhớ cache nhớ. Nhưng sự truyền tải của vec-tơ rất trơn tru.
2] Chèn và xóa trang:
trung bình 50% của các yếu tố phải được chuyển khi bạn làm điều đó với một Vector nhưng cache rất giỏi mà! Tuy nhiên, với danh sách, bạn cần phải di chuyển đến điểm chèn/xóa ... vì vậy một lần nữa ... bộ nhớ cache bị mất! Và các vectơ bất ngờ cũng giành được trường hợp này!
3] Bảo quản:
Khi bạn sử dụng danh sách, có 2 con trỏ mỗi yếu tố (phía trước & lạc hậu) nên một danh sách lớn hơn nhiều so với một Vector! Vectơ cần bộ nhớ nhiều hơn một chút so với các thành phần thực tế cần.
Yout phải có lý do để không sử dụng vectơ.
Tôi nghĩ rằng bạn có nghĩa là bộ nhớ cache bỏ lỡ, nhưng như là một nhà phát triển trò chơi độc lập mã tôi viết cũng đã có một số tiền mặt nhớ quá. –
http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs Kindof giống như Bjarne nói, nhưng với số lượng tốt hơn và mã nguồn cho các bài kiểm tra. – gulgi
@gulgi, liên kết đó xứng đáng là một câu trả lời riêng biệt, không chỉ là một nhận xét. Nó sẽ là tốt đẹp để có đồ thị và giải thích ngắn ở đây trên Stackoverflow. –
Một số tiêu chuẩn khắt khe về vấn đề này: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
Như đã đề cập bởi những người khác, bộ nhớ lưu trữ tiếp giáp nghĩa std: : vector là tốt hơn cho hầu hết mọi thứ. Hầu như không có lý do chính đáng để sử dụng std :: list ngoại trừ một lượng nhỏ dữ liệu (nơi mà tất cả có thể phù hợp trong bộ đệm) và/hoặc nơi xóa và reinsertion thường xuyên. Đảm bảo phức tạp không liên quan đến hiệu suất thực tế vì sự khác biệt giữa bộ nhớ cache và tốc độ bộ nhớ chính (200x) và cách truy cập bộ nhớ tiếp giáp ảnh hưởng đến việc sử dụng bộ nhớ cache. Xem Chandler Carruth (google) nói về những vấn đề ở đây: https://www.youtube.com/watch?v=fHNmRkzxHWs
Và Thiết Kế Oriented liệu Mike Acton nói chuyện ở đây: https://www.youtube.com/watch?v=rX0ItVEVjHc
(Late bình luận, chỉ cho các hồ sơ): Liên kết đến một bài giảng của Bjarne Stroustrup: "Tại sao bạn nên tránh Danh sách liên kết", nơi ông tuyên bố vectơ luôn tốt hơn danh sách. Lý do ông đưa ra là trung bình việc tìm kiếm điểm chèn chiếm ưu thế trong nỗ lực, và việc dịch chuyển các phần tử (trong vectơ) là không đáng kể * so với *. Ngoài ra: cache nhớ, nhưng điều đó được đề cập trong câu trả lời dưới đây. Video: http://www.youtube.com/watch?v=YQs6IC-vgmo –
Mặc dù danh sách gần như luôn luôn chậm hơn so với véc tơ (ngoại trừ khi thực hiện cấp độ nối cao) có một lần bạn hoàn toàn CẦN danh sách: ổn định vòng lặp. Nếu bạn cần giữ bản sao của các trình vòng lặp sẽ luôn trỏ đến cùng một phần tử (trừ khi bị xóa), đây không phải là một vectơ đảm bảo có thể cung cấp (ví dụ: lệnh gọi tới push_back có thể làm mất hiệu lực tất cả các trình vòng lặp). Sử dụng các vùng nhớ bộ nhớ có thể nhận được tốc độ của một danh sách gần giống với một vectơ hơn. – coderforlife