Skip to main content

Multiset (Bag)

Overview​

A Multiset, also known as a Bag, is an abstract data type that allows duplicate elements while still treating the collection as unordered. Unlike sets, a multiset tracks how many times each element appears.

What Is a Multiset?​

A multiset:

  • Allows duplicate elements
  • Associates each element with a count
  • Does not rely on positional ordering

Conceptually:

{ a×2, b×1, c×3 }

How It Works​

Multisets are often implemented as:

Map<Element, Count>

Each element maps to the number of occurrences.

Example​

Pseudocode​

bag.add("apple")
bag.add("apple")
bag.add("orange")

count("apple")   // 2

Real-world Analogy​

A multiset is like a shopping basket. Two apples are two apples, not one 🍎🍎.

Core Operations​

OperationDescription
AddIncrease count
RemoveDecrease count
CountGet frequency
ContainsCheck existence
UnionCombine counts
IntersectionMinimum counts

Time Complexity​

Depends on implementation:

  • Access: O(1) or O(log n)
  • Update: O(1) amortized

Use Cases​

  • Frequency counting
  • Inventory systems
  • Word occurrence analysis
  • Multigraph edges

Advantages​

  • Preserves multiplicity
  • Efficient counting
  • Simple conceptual model

Limitations​

  • More memory than sets
  • No ordering guarantees
  • Slightly more complex operations