Java có một số LinkedHashSet, là tập hợp có thứ tự lặp lại có thể dự đoán được. Cấu trúc dữ liệu sẵn có gần nhất trong C++ là gì?Có tập hợp băm được liên kết trong C++ không?
Hiện tại tôi đang sao chép dữ liệu của mình bằng cách sử dụng cả tập hợp và vectơ. Tôi chèn dữ liệu của tôi vào tập hợp. Nếu dữ liệu được chèn thành công (nghĩa là dữ liệu chưa có trong tập hợp), thì tôi push_back vào vectơ. Khi tôi lặp qua dữ liệu, tôi sử dụng vectơ.
Nếu bạn có thể sử dụng, thì Boost.MultiIndex với các chỉ mục sequenced và hashed_unique có cùng cấu trúc dữ liệu là LinkedHashSet.
Nếu không, hãy giữ unordered_set (hoặc hash_set, nếu đó là những gì triển khai của bạn cung cấp) của một số loại có nút danh sách trong đó và tự xử lý thứ tự tuần tự bằng nút danh sách đó.
Những vấn đề với những gì bạn đang làm việc nữa (set và vector) là:
mutable thành viên dữ liệu bị bỏ qua bởi so sánh đơn đặt hàng và ai đó viết mã dự kiến sẽ tắt tiếng e qua tra cứu và xem các thay đổi khi lặp theo trình tự).LinkedHashSet, không có cách nào nhanh chóng để xóa phần tử ở giữa chuỗi. Và nếu bạn muốn xóa theo giá trị thay vì theo vị trí, thì bạn phải tìm kiếm vectơ để xóa giá trị.set có các đặc tính hiệu suất khác nhau từ bộ băm.Nếu bạn không quan tâm đến bất kỳ điều nào trong số đó, thì những gì bạn có là có thể ổn. Nếu trùng lặp là vấn đề duy nhất thì bạn có thể xem xét việc giữ một vectơ con trỏ tới các phần tử trong tập hợp, thay vì một vectơ trùng lặp.
Bạn có thể muốn biết rằng std :: bản đồ không cung cấp cho bạn bất kỳ loại (log n) nào trong thời gian tra cứu "null". Và bằng cách sử dụng std :: tr1 :: unordered là rủi ro kinh doanh vì nó phá hủy bất kỳ thứ tự để có được thời gian tra cứu liên tục.
Cố gắng bash một thùng chứa chỉ mục đa tăng để tự do hơn về nó.
Cách bạn mô tả kết hợp lại std::set và std::vector vẻ như những gì bạn cần phải làm, ngoại trừ bằng cách sử dụng std::unordered_set (tương đương với HashSet Java) và std::list (danh sách gấp đôi liên kết). Bạn cũng có thể sử dụng std::unordered_map để lưu khóa (để tra cứu) cùng với một trình vòng lặp vào danh sách để tìm các đối tượng thực mà bạn lưu trữ (nếu các phím khác với các đối tượng (hoặc chỉ một phần của chúng)).
Thư viện tăng cường cung cấp một số loại kết hợp các vùng chứa và chỉ mục tra cứu này. Ví dụ: this bidirectional list with fast look-ups example.
Để sao chép LinkedHashSet từ JAVA trong C++, tôi nghĩ bạn sẽ cần hai vanilla std::map (xin lưu ý rằng bạn sẽ nhận được LinkedTreeSet thay vì LinkedHashSet thực thay vào đó sẽ nhận được O (log n) để chèn và xóa) công việc.
Khi bạn đang đi để chèn, bạn sử dụng std::map::find trong std::map đầu tiên để đảm bảo rằng không có đối tượng giống hệt nhau tồn tại trong đó.
std::map Tôi đã đề cập trước đây.Khi bạn đang đi để lặp qua chuyện này theo lệnh của chèn, bạn lặp qua thứ hai std::map vì nó sẽ được sắp xếp theo thứ tự chèn (bất cứ thứ gì rơi vào std::map hoặc std::set sẽ được sắp xếp tự động).
Khi bạn sắp xóa phần tử khỏi nó, bạn sử dụng std::map::find để nhận thứ tự chèn. Sử dụng thứ tự chèn này để xóa phần tử khỏi số std::map thứ hai và xóa đối tượng khỏi đối tượng đầu tiên. Vui lòng lưu ý rằng giải pháp này không hoàn hảo, nếu bạn dự định sử dụng trên cơ sở dài hạn, bạn sẽ cần phải "nhỏ gọn" thứ tự chèn sau một số lần xóa nhất định kể từ khi bạn cuối cùng sẽ chạy ra khỏi thứ tự chèn (2^32 chỉ mục cho unsigned int hoặc 2^64 chỉ mục cho unsigned dài dài int). Để làm điều này, bạn sẽ cần phải đặt tất cả các đối tượng "giá trị" vào một vectơ, xóa tất cả các giá trị từ cả hai bản đồ và sau đó chèn lại các giá trị từ vectơ trở lại vào cả hai bản đồ. Thủ tục này mất thời gian O (nlogn).
Nếu bạn đang sử dụng C++ 11, bạn có thể thay thế std::map đầu tiên bằng std::unordered_map để cải thiện hiệu quả, bạn sẽ không thể thay thế hiệu quả thứ hai bằng nó. Lý do là std::unordered map sử dụng mã băm để lập chỉ mục sao cho chỉ mục không thể được sắp xếp một cách đáng tin cậy trong tình huống này.
'std :: set' được đặt hàng. Bạn có nghĩa là bạn muốn nó được theo thứ tự bạn đã chèn nó? –
@sftrabbit, Có, tôi muốn nó theo thứ tự chèn. –
Để thực sự bắt chước LinkedHashSet này, bạn nên sử dụng std :: unordered_set + std :: list, thay vì std :: set + std :: vector. –