STL list vs multi set

[minkowski]

Hi, I was wondering if you could give me an example of when you would want to store objects in a list and when would you want to store them in a multi set. The multi set of course having the ability to store multiple values of the same object. Thanks

[73Zeppelin]

You could use a multi set to store the factors of a prime number, say, 120: {2, 2, 2, 3, 5} Using a list this would be {2,3,5} if you just wanted to identify the factors themselves. Using the multi set, you could recontruct the prime (by multiplication of the contents of the multi set). The list would just give you the factors.

---

[minkowski]

Hey thanks for your input. I thought Lists can store duplicates ? So it could store {2,2,2,3,5} ?

[73Zeppelin]

I think the difference is that multiple identical elements in a multi set can serve as their own sort keys, so the keys are not unique.

---

[Shog9 0]

List gives you fast insertion (O(1)), potentially slow lookup (O(n)). Multiset gives you sorted insertion, and reasonably fast lookup (both O(log n)).

But who is the king of all of these folks?