cấu trúc dữ liệu cơ bản của danh sách, vector và thiết lập STL là gì?cấu trúc dữ liệu cơ bản của danh sách STL, vector và thiết lập là gì?
Giải pháp của tôi:
Phải không?
Dựa trên ý kiến, làm rõ, đó là những lựa chọn phổ biến nhất, nhưng dựa vào độ phức tạp mong muốn và các yếu tố khác, sự ủng hộ của những hiện thực có thể thay đổi:
Vector = tự động thay đổi kích thước mảng
Danh sách = Doubly Linked List
Set = Red/Black Tree (cân bằng Binary Search Tree)
tôi nghĩ rằng bạn có thể có thể được trộn lên Heaps và BSTs. Một đống được hiển thị dưới dạng cây, nhưng nó thực sự được xây dựng trên cấu trúc danh sách có thể lập chỉ mục (ví dụ: mảng hoặc vectơ). C++ cung cấp chức năng heap thông qua algorithm header trong STL. BST có nhiều cấu trúc dựa trên khóa/giá trị được sử dụng để tra cứu hiệu quả (đó là những gì bạn thường muốn cho một bộ).
danh sách là một danh sách liên kết gấp đôi – Praetorian
Điều này thường đúng, nhưng lưu ý rằng đây không phải là lựa chọn duy nhất (nó phụ thuộc vào việc triển khai thực hiện). – avakar
@sgusc, bản đồ là cây đỏ-đen, bộ không phải vì các phần tử trên đó không được sắp xếp. Khác biệt giữa danh sách và danh sách liên kết là gì? cấu trúc dữ liệu của "danh sách liên kết" là gì? một danh sách? – user1002288
Tiêu chuẩn không đảm bảo về cấu trúc dữ liệu nào được sử dụng, chỉ có đảm bảo phức tạp, do đó việc triển khai có thể chọn bất kỳ cấu trúc nào đáp ứng được chúng.
Điều đó nói rằng, std::vector thường là một dynamic array, std::list có lẽ là một doubly-linked list và std::set là thường xuyên nhất một số loại self-balancing binary tree.
Thực hiện được xác định, nhưng nói chung, 'std :: vector' là mảng được phân bổ động. 'std :: list' là một danh sách được liên kết kép (C++ 11 giới thiệu' std :: forward_list' là một danh sách liên kết đơn), và 'bộ' thường dựa trên [cây đỏ đen] (http://en.wikipedia.org/wiki/Red%E2%80%93black_tree), mặc dù bất cứ điều gì phù hợp với các yêu cầu phức tạp và hành vi phân bổ của các giao diện được xác định trong tiêu chuẩn là các triển khai có thể chấp nhận được. – birryree