Có thư viện nào cung cấp cấu trúc dữ liệu để giữ thứ tự các mục và không chứa bất kỳ bản sao nào không? Và không tồn tại một tên thích hợp cho một cấu trúc dữ liệu như vậy?Danh sách không có bản sao hoặc bộ được đặt hàng
Tôi mong nó hoạt động như một danh sách với nub được áp dụng sau mỗi thao tác trên đó. Tất nhiên tôi không mong đợi nó được thực hiện như là không hiệu quả.
Dưới đây là một giải pháp:
Sử dụng một fingertree với monoid Set như biện pháp của bạn. Sau đó, trên chèn, kiểm tra thành viên đầu tiên, bằng cách sử dụng measure của toàn bộ ngón tay của bạn. Điều này cung cấp cho bạn O(log(n)) khuyết điểm và snoc, O(1) xóa.
Đây là một giải pháp:
Pair một danh sách bình thường với một bình thường Set và nhận được về cơ bản tác dụng tương tự. Bạn nhận được các yếu tố không đổi tốt hơn, nhưng xóa O(log(n)).
Đây là câu hỏi: Bạn muốn điều gì xảy ra khi chèn một bản sao? Nếu vị trí hiện tại được bảo tồn? Vị trí mới? Hàng đợi ưu tiên có thể gần với thứ bạn muốn, tùy thuộc.
Nó nhắc tôi về [LinkedHashSet] của Java (http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html). Vì vậy, tôi cho rằng một phương pháp tương tự có thể được sử dụng cho một cấu trúc dữ liệu chức năng bất biến. –
Nếu loại của bạn thuộc về 'Ord', bạn có thể sử dụng' Data.Set' để viết và 'ordNub' lấy' O (n * log m) ', trong đó' n' là số mục và 'm 'số lượng các mục duy nhất. Nếu 'Hashable' và không phải' Ord', bạn có thể làm tương tự với 'Data.HashSet'. Điều đó có đủ không hiệu quả không? –
Xin chào 2013, bạn đã đến một giải pháp chưa? – akst