STL Containers - diffrence giữa vector, danh sách và deque

Question

Tôi có nên sử dụng deque thay vì véc tơ nếu tôi muốn đẩy các phần tử cũng vào việc bắt đầu container không? Khi nào tôi nên sử dụng danh sách và điểm của nó là gì?

Answer 1

Sử dụng deque nếu bạn cần chèn/xóa hiệu quả ở đầu và cuối chuỗi và truy cập ngẫu nhiên; sử dụng list nếu bạn cần chèn hiệu quả ở bất cứ nơi nào, tại sự hy sinh của truy cập ngẫu nhiên. Các bộ lặp và tham chiếu đến các phần tử list rất ổn định dưới bất kỳ đột biến nào của vùng chứa, trong khi deque có các biến lặp rất đặc biệt và các quy tắc không hợp lệ tham chiếu (vì vậy hãy kiểm tra cẩn thận).

Ngoài ra, list là vùng chứa dựa trên nút, trong khi deque sử dụng khối bộ nhớ liền kề, do đó vị trí bộ nhớ có thể có hiệu ứng hiệu suất không thể bị bắt bởi ước tính phức tạp tiệm cận.

deque có thể hoạt động thay thế cho vector hầu như ở mọi nơi và có lẽ đã được coi là vùng chứa "mặc định" trong C++ (dựa trên yêu cầu bộ nhớ linh hoạt hơn); lý do duy nhất để thích vector là khi bạn phải có bố trí bộ nhớ liền kề được đảm bảo của chuỗi của bạn.

Answer 2

deque và vector cung cấp quyền truy cập ngẫu nhiên, list chỉ cung cấp truy cập tuyến tính. Vì vậy, nếu bạn cần để có thể làm container [i], mà quy tắc ra list. Mặt khác, bạn có thể chèn và xóa các mục ở bất kỳ đâu trong một hiệu quả list và hoạt động ở giữa các số vector và deque chậm.

deque và vector rất giống nhau và về cơ bản có thể hoán đổi cho hầu hết các mục đích. Chỉ có hai sự khác biệt đáng nói đến. Đầu tiên, vector chỉ có thể thêm các mục mới một cách hiệu quả vào cuối, trong khi deque có thể thêm các mục ở một trong hai đầu một cách hiệu quả. Vậy tại sao bạn sẽ sử dụng vector sau đó? Không giống như deque, vector đảm bảo rằng tất cả các mục sẽ được lưu trữ trong các vị trí bộ nhớ liền kề, làm cho việc lặp lại chúng nhanh hơn trong một số trường hợp.