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.

  • $\begingroup$ 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? $\endgroup$ – Raphael Jun 29 '15 at 20:51
  • $\begingroup$ @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. $\endgroup$ – Steve Moser Jun 29 '15 at 20:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jun 29 '15 at 20:59
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

If you want to search the literature, some sources (e.g. Algorithms by R. Sedgewick and K. Wayne (2011, 4th ed)) call the abstract data structure for multi sets a bag. This notion seems to be used in practice as well.

Note that some implementations will assume that you assign data to keys, and that the same key can occur multiple times with different data. In this case, using a counter is not enough, so these may not directly do what you want (since they may not even bother to detect duplicate keys).

  • $\begingroup$ But conceptually a dictionary doesn't guarantee order correct? $\endgroup$ – Steve Moser Jun 29 '15 at 20:55
  • 1
    $\begingroup$ Not per se, but there are ordered dictionaries; (balanced) search trees, for instance. Java calls it TreeSet<T> iirc. $\endgroup$ – Raphael Jun 29 '15 at 20:58
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – babou Jul 1 '15 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.