3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Jun 29, 2015 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
    Commented Jun 29, 2015 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
    Commented Jun 29, 2015 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
    Commented Jun 29, 2015 at 23:43

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ But conceptually a dictionary doesn't guarantee order correct? $\endgroup$
    – Steve Moser
    Commented Jun 29, 2015 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
    Commented Jun 29, 2015 at 20:58
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – babou
    Commented Jul 1, 2015 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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