Why have a multiset container?

I was wondering about a plausible scenario where people would need to use the STL multiset associative container. On a different note, I am still puzzled as to why set and multiset are even called associative containers considering that they don’t associate their keys with any data like map and multimap do. In fact I was talking to Jambo and Mike and was telling them how people could always use a vector or a deque instead of a multiset (set had its use in the sense it ensured that you had no duplicates in a collection). I tried out some code (shown below) and found that multiset has one advantage over a vector collection – multiset collections were sorted and so when you iterated through them, you got them back in some specialized order – which could be handy in some situations. BTW, note how I’ve used for each to iterate through native STL collections (it’s a non-standard feature added to Unmanaged VC++ 2005).

Using a multiset<int>

multiset<int> s;
s.insert(12);
s.insert(24);
s.insert(12);
s.insert(3);
s.insert(24);
cout << "multiset listing" << endl;
for each(int i in s)
    cout << i << endl;

Output :-

multiset listing
3
12
12
24
24

Using a vector<int>

vector<int> v;
v.push_back(12);
v.push_back(24);
v.push_back(12);
v.push_back(3);
v.push_back(24);
cout << "vector listing" << endl;
for each(int i in v)
    cout << i << endl;

Output :-

vector listing
12
24
12
3
24

Notice that the vector does not return the collection in a sorted manner. BTW, instead of a multiset, you can also use a priority_queue container adaptor (code shown below), though it may not be as efficient.

Using a priority_queue

priority_queue< int, vector<int>, greater<int> > pq;
pq.push(12);
pq.push(24);
pq.push(12);
pq.push(3);
pq.push(24);
cout << "priority_queue (using vector) listing" << endl;
while(!pq.empty())
{
    cout << pq.top() << endl;
    pq.pop();
}

Output :-

priority_queue (using vector) listing
3
12
12
24
24
Advertisements
Posted in C++

2 thoughts on “Why have a multiset container?

  1. Another advantage is in searching. Multisets use a tree data structure internally (as do sets and maps/multimaps). So the find algorithm is fast, where as it can’t make ordering assumptions in a vector, and has to go through everything. The performance is O(Log(n)) for sets, and O(n) for vectors, if I’m not mistaken, so in a lookup/search heavy situation, the multiset will win out.

  2. I don’t have the standard nearby, but I’m 99.9% sure that the sorting in multiset is implementation dependent and not by standard (even if probably all implementations do have it sorted). The sorting is infact a side effect of using a RB-tree (or whatever other binary tree) for fast searches..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s