Which container should I use for this

Question

Let's say I want to have a container with apples that has different prices. I want them to be sorted by their price always (first the highest price), but I also want to quickly get them by their identifier. So far, I have been next

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 application will spend 20% of time deleting records, 20% inserting records, 25% getting them (getting 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 solves the sorting problem. It is useless to find, since I want to find by their identifier (so I need to repeat all of them). For the same reason, deletion and insertion will be slow.

This seems like the wrong choice.

But if I have a card, then it will be ordered based on the identifier. 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 will also be slow.

Help!

Answer 1

You can do this with two containers that are sorted by price (priority queue or linked list), and one that indexes your identifiers (hash map). To save space, you can have both structures that contain only pointers to your Apple instances, you need to write a special sorting method for them.

Thus, deleting your O(1) record, inserting O(log n) , searching also O(1) , and updating O(log n) . I think this should be good, especially when you are dealing with so few items (450).

EDIT:

Development of operating costs:

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

• Removal : you can get the depreciated cost O(1) with a priority queue if you defer that cost to inserts. There are many smart implementations that will show you how to do this.
• Insertion . Any queue implementation with the usual priority will do this in O(log n) , just hold on a little if you want to constantly take time.
• Extraction . A map is used for this; there is no need to view the priority queue.
• Update . I don’t think there is a (simple) way to get better complexity than O(log n) for updating, even amortized, you probably have to mix things up in the priority queue for the middle case.