Cấu trúc dữ liệu cơ bản của một bộ STL trong C++ là gì?

Question

Tôi muốn biết cách cài đặt được thực hiện trong C++. Nếu tôi đã triển khai vùng chứa đã đặt của riêng mình mà không sử dụng vùng chứa được cung cấp STL, thì cách tốt nhất để thực hiện nhiệm vụ này là gì?

Tôi hiểu tập hợp STL dựa trên cấu trúc dữ liệu trừu tượng của cây tìm kiếm nhị phân. Vậy cấu trúc dữ liệu cơ bản là gì? Một mảng?

Ngoài ra, cách insert() hoạt động cho một bộ? Làm thế nào để thiết lập kiểm tra xem một phần tử đã tồn tại trong nó chưa?

Tôi đọc trên wikipedia rằng một cách khác để triển khai tập hợp là với bảng băm. Làm thế nào điều này sẽ làm việc?

Answer 1

Bạn có thể thực hiện một cây tìm kiếm nhị phân bằng cách đầu tiên xác định một struct Node:

struct Node 
{ 
    void *nodeData; 
    Node *leftChild; 
    Node *rightChild; 
} 

Sau đó, bạn có thể xác định một thư mục gốc của cây với một Node *rootNode;

Mục Wikipedia trên Binary Search Tree có khá ví dụ tốt về cách triển khai phương thức chèn, vì vậy tôi cũng khuyên bạn nên kiểm tra điều đó.

Về mặt trùng lặp, chúng thường không được cho phép trong tập hợp, vì vậy bạn có thể loại bỏ đầu vào đó, ném ngoại lệ, v.v., tùy thuộc vào đặc điểm kỹ thuật của bạn.

Answer 2

Cách một vùng chứa cụ thể được triển khai trong C++ hoàn toàn phụ thuộc vào việc triển khai thực hiện. Tất cả những gì được yêu cầu là kết quả để đáp ứng các yêu cầu được nêu trong tiêu chuẩn, chẳng hạn như yêu cầu phức tạp đối với các phương pháp khác nhau, yêu cầu về trình vòng lặp, v.v.

Answer 3

Như KTC đã nói, cách thực hiện std::set có thể khác nhau - chuẩn C++ chỉ cần chỉ định một kiểu dữ liệu trừu tượng. Nói cách khác, tiêu chuẩn không chỉ rõ cách một container nên được thực hiện, chỉ cần những hoạt động nào cần thiết để hỗ trợ. Tuy nhiên, hầu hết các hiện thực của STL làm, theo như tôi biết, hãy sử dụng red-black trees hoặc các cây tìm kiếm nhị phân cân bằng khác của một số loại (ví dụ GNU libstdC++, sử dụng các cây đỏ-đen). Trong khi bạn về mặt lý thuyết có thể thực hiện một bộ như một bảng băm và nhận được hiệu suất tiệm cận nhanh hơn (phân bổ O (chiều dài khóa) so với O (log n) để tra cứu và chèn), điều đó sẽ yêu cầu người dùng phải cung cấp hàm băm cho bất kỳ loại nào họ muốn lưu trữ (xem Wikipedia's entry on hash tables để có giải thích tốt về cách chúng hoạt động). Đối với việc thực hiện một cây tìm kiếm nhị phân, bạn sẽ không muốn sử dụng một mảng - như Raul đã đề cập, bạn sẽ muốn một số loại cấu trúc dữ liệu Node.

Answer 4

Tôi hiểu tập hợp STL dựa trên cấu trúc dữ liệu trừu tượng của cây tìm kiếm nhị phân. Vậy cấu trúc dữ liệu cơ bản là gì? Một mảng?

Như những người khác đã chỉ ra, nó thay đổi. Một tập hợp thường được thực hiện như một cây (cây đỏ đen, cây cân bằng, vv) mặc dù nhưng có thể có các triển khai khác tồn tại.

Ngoài ra, cách insert() hoạt động đối với được đặt?

Nó phụ thuộc vào việc triển khai cơ bản của tập hợp của bạn.Nếu nó được thực hiện như một cây nhị phân, Wikipedia có triển khai đệ quy mẫu cho hàm insert(). Bạn có thể muốn kiểm tra xem nó ra.

Bộ kiểm tra xem phần tử đã tồn tại trong đó chưa?

Nếu nó được triển khai dưới dạng cây, nó sẽ đi qua cây và kiểm tra từng phần tử. Tuy nhiên, bộ không cho phép lưu trữ các phần tử trùng lặp. Nếu bạn muốn một tập hợp cho phép các phần tử trùng lặp, thì bạn cần một multiset.

Tôi đọc trên wikipedia theo cách khác để triển khai bộ có bảng băm . Làm thế nào điều này sẽ làm việc?

Bạn có thể tham chiếu đến hash_set, nơi tập hợp được triển khai bằng bảng băm. Bạn cần cung cấp hàm băm để biết vị trí nào lưu trữ phần tử của bạn. Triển khai này lý tưởng khi bạn muốn có thể tìm kiếm phần tử nhanh chóng. Tuy nhiên, nếu điều quan trọng đối với các yếu tố của bạn được lưu trữ theo thứ tự cụ thể, thì việc triển khai cây phù hợp hơn vì bạn có thể duyệt qua các đơn đặt hàng trước, inorder hoặc postorder.