Any suggestions for a sorted set where uniqueness and order are predicated on different values?

1

Hey guys. I'm looking for a collection that can order of elements by weight, however maintain uniqueness by id. Somewhat like a BTreeSet where for the following struct:

pub struct Item {
    id: usize,
    weight: i32
}

I can, perhaps, implement ordering on the weight variable, however inserting into the set will make comparisons on the id field. Does such a collection exist? Ideally I would calling pop() on the set which would return the item with the highest weight, and inserting other Item structs where if the item already exists in the set, it would modify the weight with the larger of the two. Similar to using entry, and_modify and such in relevant collections. Does anyone have a suggestion for something suitable in the rust?

2

This might be what you are looking for:

3

Like in databases you need two indexes, one for the id (could be an HashMap/HashSet) and one for the sorted weight (this could be the BTreeMap/BTreeSet you mentioned), and then glue them together.

2 Likes
4

Providing the caller knows the weight for an id at all times, you can use a BTreeSet keyed with the weight and then the id. This is a simple solution. Updating the weight requires removal then re-insertion with the new weight.

The heap solution I suggested is more complex, but can be much more efficient in terms of the number of comparisons needed, especially if the weights typically change by a small amount. The caller does need to retain a "handle" ( actually an index into a Vec ) returned by the insert operation which is used to update the weight.

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.