Bạn có thể chia sẻ suy nghĩ của mình về cấu trúc dữ liệu STL tốt nhất để lưu trữ danh sách tên lớn và thực hiện tìm kiếm trên những tên này không?Cấu trúc dữ liệu C++ sẽ tốt nhất để giữ một danh sách lớn các tên
Chỉnh sửa: Tên không phải là duy nhất và danh sách có thể phát triển khi tên mới có thể được thêm liên tục vào tên. Và nói chung tôi đang nói từ 1 triệu đến 10 triệu tên.
Vì bạn muốn tìm kiếm tên, bạn muốn có cấu trúc hỗ trợ truy cập ngẫu nhiên nhanh. Điều đó có nghĩa là véc tơ, deque và danh sách là tất cả ra khỏi câu hỏi. Ngoài ra, vector/mảng là chậm trên ngẫu nhiên thêm/chèn cho các bộ được sắp xếp bởi vì họ phải thay đổi các mục để nhường chỗ cho mỗi mục được chèn vào. Tuy nhiên, việc thêm vào kết thúc rất nhanh.
Cân nhắc std::map, std::unordered_map hoặc std::unordered_multimap (hoặc anh chị em ruột của họ std::set, std::unordered_set và std::unordered_multiset nếu bạn chỉ lưu trữ các phím).
Nếu bạn hoàn toàn sẽ thực hiện truy cập ngẫu nhiên, độc đáo, tôi sẽ bắt đầu với một trong các vùng chứa unordered_ *.
Nếu bạn cần lưu trữ một danh sách có thứ tự các tên, và cần phải thực hiện tìm kiếm phạm vi/lặp và các hoạt động sắp xếp, một cây dựa container như std::map hoặc std::set nên làm tốt hơn với những hoạt động lặp đi lặp lại hơn một container dựa băm vì cựu sẽ lưu trữ các vật phẩm liền kề với những người tiền nhiệm và người thừa kế hợp lý của chúng. Đối với truy cập ngẫu nhiên, nó là O (log N) mà vẫn còn phong nha.
Trước khi std :: unordered_ *, tôi đã sử dụng std::map để giữ số lượng lớn đối tượng cho bộ nhớ cache đối tượng và mặc dù có các thùng chứa truy cập ngẫu nhiên nhanh hơn, nó đủ rộng để sử dụng. Unordered_map mới hơn có thời gian truy cập O (1), do đó nó là một cấu trúc băm và sẽ cho bạn thời gian truy cập gần nhất.
Nếu tất cả những gì anh ta có là một danh sách các chuỗi và không có gì để ánh xạ chúng vào thì các tập hợp khác nhau 'container là một lựa chọn tốt hơn. –
Nhưng anh ta sẽ lập bản đồ tên cho những gì? – 0x499602D2
Tôi không chắc liệu anh ta có cần lưu giữ một bản ghi hay không, hoặc nếu tên đó là bản ghi. Tôi chắc chắn anh ta có thể thay thế các thiết lập tương ứng thay thế khi cần thiết. Trong mọi trường hợp, nếu bạn cảm thấy câu trả lời sẽ được cải thiện bởi tôi tham khảo các anh chị em *, tôi sẽ chỉnh sửa nó. – codenheim
Bạn có thể xem xét khả năng sử dụng nối các tên đó bằng dấu phân tách nhưng tìm kiếm có thể bị ảnh hưởng. Bạn sẽ cần phải tìm ra một tìm kiếm nhị phân được điều chỉnh.
Nhưng bạn nên thử giải pháp rõ ràng trước tiên là một hashmap được gọi là unordered_map trong stl. Xem nếu đáp ứng nhu cầu của bạn. Tìm kiếm sẽ nhanh chóng ở đó nhưng với chi phí bộ nhớ.
Tên có độc đáo không? Bạn đang tạo vùng chứa này một lần và sau đó tìm kiếm nhiều lần hoặc có một số lượng thêm/xóa các mục cũng như các tìm kiếm không? Bạn có cần lặp qua vùng chứa theo thứ tự bảng chữ cái không? –
Mảng động hoặc tiêu chuẩn :: vectơ (vật lý giống nhau). bộ và danh sách liên kết không phù hợp với số lượng lớn các phần tử vì thời gian thêm quá dài. – texasbruce
Ngoài ra, lớn cỡ nào? Nếu nó chỉ là một vài triệu tên dài 10 ký tự, std :: bản đồ có lẽ là tốt trên một máy tính xách tay được cung cấp hợp lý. Nếu bạn cần vài tỷ tên, mỗi tên dài 100 ký tự hoặc nếu bạn có hệ thống bị hạn chế về bộ nhớ, bạn có thể cần một giải pháp ngoài lõi, có thể loại trừ STL (mặc dù Google tìm thấy http: //stxxl.sourceforge .net /, yêu cầu xử lý trường hợp đó). – wrdieter