# Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered?

For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the items were added to the cart unless an item of the same type was already added in which case a number associated with item is incremented.

Is this a well studied data structure or just a specialized multiset? I imagine it could be represented with an internal data structure of a dictionary and an array.

• The computer science answer seems obvious (maybe it isn't if you haven't been brainwashed) so I'm not sure what you are after. Do you want to know how to program this? – Raphael Jun 29 '15 at 20:51
• @Raphael I was just wondering if there is a better name for this so I could communicate it better to others. Also maybe find what the expectation would be for an API into this data structure. For example would asking for the last element in this structure return just an item or a tuple containing the item and its count. – Steve Moser Jun 29 '15 at 20:54
• I'm not aware of a special name in CS. In OOP, you'd just use a usual ordered Collection (maybe wrapped so you get nice methods for your purposes) and give the objects you store a counter, so nothing special there either. – Raphael Jun 29 '15 at 20:59
• The choice of the data structure is very dependent on the operations you need on that structure. In your case, you do no say how the information stored is to be used. If it is never used, you can replace your memory by a block of wood. If it is to be used, you have to say how. You call it an ordered multiset, but that could corresponds to different uses, requiring different representation. As your question stands, the right data structure could be an array of size 0. – babou Jun 29 '15 at 23:43

Just use a regular dictionary (also dynamic set) and attach a counter to each entry. The insert operation then finds already existing entries and can increase the counter; similarly for delete.
• Not per se, but there are ordered dictionaries; (balanced) search trees, for instance. Java calls it TreeSet<T> iirc. – Raphael Jun 29 '15 at 20:58