Best ADT to use?
Alright, I was wondering what would be the best way to do the following:
I'm trying to maintain a collection of objects, and I want to be able to quickly search on two different parameters. Quick addition and deletion is also necessary. Essentially, items have a unique string ID and a (not necessarily unique) cost associated with each. I want to be able to add/remove items by string, and also I want to be able to remove the highest-cost item, without looking at each item's cost one at a time. If multiple items tie for the highest cost, I don't care which I get.
I was thinking doing two self-balancing trees (like 2 red-black trees) where each node in the first tree had a counterpart in the other. The benefit is that I can do all operations in log time, but it's going to be a little more complicated to handle the trees themselves; I have to cause the nodes to be linked, and I have to make sure a deletion in one tree causes a deletion in the other.
Is there a simpler/more elegant way? As I can make this work in log time, any alternate would have to be at least as fast.
What you really want is a single copy of the data and multiple (optimized) search paths to that data, much like typical database systems. The common solution is to create a primary container that holds the data and then secondary containers providing iterators into the primary container:
Or without STL assistance, a single balanced tree holding the data and N trees with pointers to the data instead of copies of the data (as you seemed to want before).
// For example, a map
typedef map<string, long> DataMap;
typedef map<string, DataMap::iterator> StringKeyMap;
typedef map<long, DataMap::iterator> CostKeyMap;
Hmm, that seems like it will work OK until I want to delete an element. For example, if I want to remove the highest-cost element, then I can quickly find it via the cost map, and I can remove it easily from both cost and data maps, but this leaves an iterator in the string map, which now is an invalid iterator (the element it represented no longer exists).
I could work around by not truly deleting any nodes (flag them as deleted but not remove them anywhere), but this would mean that searches take longer (searches have to find "good" entries only).
I suppose I could have the object contain iterators into both secondary maps, which might work although it's a little complex.
Searches would only have to check after they found the unique element, not for every node in the map. One branch per search, I wouldn't worry. I would make it a reference count, rather then just a flag. In your case it's actually quite easy just make your string keyed map the "data" map. The delete min structure could be a priority_queue with iterators into the string map. Doesn't scale though.