Suy nghĩ về cách triển khai?

Question

Tôi đang chuyển một số c-code rất cũ vào C++ và tôi đã chạy qua một danh sách liên kết được triển khai trong một mảng. Phần tử là cấu trúc đơn giản:

struct element 
{ 
    void *m_ptrData; 
    short m_nextEntry; 
    short m_prevEntry; 
}; 

Là một mảng, có thể truy cập nhanh vào dữ liệu, nếu bạn biết chỉ mục. Các khía cạnh danh sách liên kết cho phép các yếu tố được di chuyển xung quanh, và "xóa" từ danh sách. Các yếu tố có thể được di chuyển trong danh sách, dựa trên tần suất sử dụng (cho MRU và xuống cho LRU).

Tôi thích tìm cách tốt hơn để triển khai điều này hơn là sử dụng mảng khác. Tôi muốn sử dụng STL, nhưng tôi không chắc chắn container nào là tốt nhất để sử dụng.

Bất kỳ ai có bất kỳ suy nghĩ nào?

Answer 1

Do đây là một danh sách liên kết, có lẽ bạn nên sử dụng std::list ...

Nguyên tắc hàng đầu là bạn muốn sử dụng một danh sách liên kết khi bạn cần chèn các phần tử vào các vị trí ngẫu nhiên trong danh sách, hoặc xóa các phần tử ngẫu nhiên khỏi danh sách. Nếu bạn chủ yếu cần thêm/xóa các phần tử vào/từ cuối danh sách, thì bạn nên sử dụng std::vector. Nếu bạn cần thêm/xóa các phần tử vào/từ đầu hoặc cuối danh sách, thì bạn nên sử dụng std::deque.

Hãy nhớ, chúng tôi đang nói về xác suất ở đây. Nếu bạn cần phải chèn một phần tử vào giữa một std::vector một lần trong một mặt trăng màu xanh, điều đó có thể sẽ ổn. Nhưng nếu bạn cần phải làm điều này tất cả các thời gian, nó sẽ có tác động lớn đến hiệu suất, bởi vì các vector sẽ cần phải liên tục di chuyển các yếu tố của nó, và có thể tái phân bổ bộ nhớ của nó quá. Mặt khác, lợi thế của việc sử dụng một véc tơ là các phần tử của nó tiếp giáp trong bộ nhớ, giúp cải thiện đáng kể hiệu suất nếu bạn chỉ cần duyệt qua chúng theo thứ tự do bộ nhớ đệm.

Answer 2

Xem ở đây:

http://linuxsoftware.co.nz/cppcontainers.html

Có một biểu đồ dòng chảy để giúp bạn chọn container ngay ở phía dưới.

Answer 3

Vì dữ liệu trong danh sách này là con trỏ, tại sao lại bận tâm với danh sách liên kết? Đối với POD nhỏ, std::vector thường là đặt cược đầu tiên tốt nhất và do vị trí tốt hơn dữ liệu của nó phát độc đáo với bộ xử lý lưu trữ, nó thường thực hiện danh sách được liên kết ngay cả ở đâu, về lý thuyết, danh sách được liên kết nên tốt hơn. Tôi muốn chọn std::vector cho đến khi một số tiểu sử cho thấy rằng có sự cố về hiệu suất và std::list hoạt động tốt hơn.