Cấu trúc dữ liệu tương đương của các thùng chứa STL

Question

Tôi nghiên cứu cấu trúc dữ liệu và tôi muốn hỏi những gì tương đương với các container STL.

ví dụ

• vector = array động
• queue = đợi
• chồng = chồng
• priority_queue = đống
• list = danh sách liên kết
• set = cây
• slist = danh sách được liên kết đơn lẻ
• bit_vector = vector bool
• map = pair
• deque =?
• multiset =?
• multimap =?
• hash_set =?
• hash_map =?
• hash_multiset =?
• hash_multimap =?
• hash =?
• bit_set =?

Answer 1

Làm nổi bật các thùng chứa thư viện chuẩn C++, bản thân tiêu chuẩn cố gắng không nói quá nhiều về việc triển khai. Tuy nhiên, các ràng buộc rất cụ thể về độ phức tạp của việc chèn, loại bỏ, tra cứu, chèn phạm vi và như vậy, có nghĩa là hầu hết các triển khai sử dụng cùng một loại cấu trúc dữ liệu cho các thùng chứa.Liên quan đến một số ví dụ của bạn:

• std :: Danh mục: gấp đôi danh sách liên kết
• std :: set, std :: MultiSet, std :: bản đồ, std :: Multimap: tự cân đối nhị phân cây, thường là màu đen-đen.
• hash_ *: C++ 11 cung cấp unordered_set, unordered_map và multi anh chị em. Đây là những bảng băm.
• bitset: mảng có kích thước cố định

Tôi tin rằng STL tuân theo các triển khai này.

Answer 2

bộ và multiset- cây tìm kiếm nhị phân

bản đồ và Multimap - cây tìm kiếm nhị phân

deque - deque

các hash* container được băm container kết hợp thực hiện như bảng băm. ví dụ: hash_map chứa pair<key,value> được tra cứu bằng bảng băm.

trong bitset

the individual elements are accessed as special references which mimic bool elements

Answer 3

Tôi không nghĩ rằng đủ điều kiện std :: map <> như chỉ là một "cặp" sẽ là chính xác. Trên thực tế, có một tiện ích có tên std :: pair <> thực sự chỉ là một cặp. std :: map <> lưu trữ các khóa duy nhất và các giá trị không phải duy nhất theo cách mà có thể sử dụng cú pháp tương tự như của một mảng với các chỉ mục thuộc loại có thể là số hay không.

Chỉnh sửa: "Vùng chứa" được sửa thành "tiện ích" nhờ juanchopanza.

Answer 4

vector = dynamic array 

queue = queue 

stack = stack 

priority_queue = priority queue based on binary heap 
       priority_queue can be implemented using 
       1. sorted array 
       2. sorted list (unrolled list, skip list etc) 
       3. any other heap like Fibonacci heap, binomial heap 

list = doubly linked list 

set = set based on AVL Tree (usually) 
     can implemented using any other binary balancing tree like 
     1. Binary Search Tree 
     2. Red black Tree 
     3. Splay Tree 

slist = single linked list 

map = map based on Red Black Tree (usually) 
     where every node is 'pair' structure 
     can implemented using any other binary balancing tree like 
     1. Binary Search Tree 
     2. AVL Tree 
     3. Splay Tree 

deque = deque 

hash_set = set implemented using hash 

hash_map = hash table 

hash = 'Not Available', used as functor