which container should i use for this

Question

Let's say I want to have a container of Apples that have different prices. I want them sorted by their price always (highest price first), but I also want to quickly retrieve them by their id. What I have so far is the following

struct AppleClass
{
    string id;
    int price;

    bool operator<(const AppleClass& o) const 
    {
        return price > o.price; 
    }
};

int main() 
{
    set<AppleClass> myapples;
    myapples.insert({"apple1", 500});
    myapples.insert({"apple2", 600});
    myapples.insert({"apple3", 400});

    for (auto& apple : myapples)
    {
        cout << apple.id << "," << apple.price << endl;         
    }
}

http://ideone.com/NcjWDZ

My app will spend 20% of it's time removing entries, 20% inserting entries, 25% retrieving them (retrieving the whole list), and 35% updating them (their price will increase or decrease) often.

The container will have a maximum of 450 entries.

My code only solves the sort problem. Find is useless since I want to find by their id (so I need to iterate trough all of them). Removing and inserting would be slow for the same reason.

It feels like the wrong choice.

But If I have a map then it would be ordered based on the id. And every time I retrieve the list I would have to copy it to some container for example, order it, and then send it to the user, which also feels slow.

Help!

Answer 1

You can do it with two containers, one that's kept sorted by price (priority queue or linked list), and one that indexes your ids (a hash map). In order to save space, you can have both structures keep only pointers to your Apple instances, you'll need to write a custom sort functor for that though.

This way, your entry removal is O(1), insertion is O(log n), retrieval is also O(1), and updating is O(log n). I think that should be good, especially when you're dealing with such a small number of items (450).

EDIT:

Elaborating on operation costs:

All these operations are constant time for the hash map, so this is about the priority queue:

• Removal: you can get an amortized cost of O(1) with the priority queue if you defer that cost to inserts. There are lots of clever implementations out there that will show you how to do this.
• Insertion: Any basic priority queue implementation will do this in O(log n), it gets a little tricky to keep it that way if you want constant time removal.
• Retrieval: You use the map for this, no need to look through the priority queue.
• Updating: I don't think there's a (easy) way to get better complexity than O(log n) for updating, even amortized, you'll probably have to shuffle things around in the priority queue for the average case.