Thread: Best ADT to use?

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    1,619

    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.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    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:
    Code:
    // For example, a map
    typedef map<string, long>              DataMap;
    typedef map<string, DataMap::iterator> StringKeyMap;
    typedef map<long, DataMap::iterator>   CostKeyMap;
    
    DataMap      Primary;
    StringKeyMap StringSecondary;
    CostKeyMap   CostSecondary;
    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).
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    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.

  4. #4
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  2. Array-based ADT list
    By campermama in forum C++ Programming
    Replies: 0
    Last Post: 06-14-2004, 01:32 PM
  3. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM
  4. Problem with My Sets ADT
    By jawwadalam in forum C++ Programming
    Replies: 2
    Last Post: 10-04-2002, 06:36 AM
  5. ADT Initialization/Passing of Array from Friended ADT
    By Wiggin in forum C++ Programming
    Replies: 1
    Last Post: 04-27-2002, 12:45 AM