1

When we insert elements in a multiset are they inserted in a sorted order .

How can i find the smallest elements of a mutiset ?

And how can i access ith element in a mutiset ?

Can some one please explain how multiset works and how it store elements in it ?

Thanks in advance .

Andrey Chernukha
  • 21,488
  • 17
  • 97
  • 161
dhruvsharma
  • 125
  • 1
  • 13

2 Answers2

3

Here is one solution that always works (regardless of the ordering scheme):

   std::multiset<int> m;
   //do something with m
   std::cout<<*std::min_element(m.begin(),m.end())<<std::endl;

That should be O(n), so it takes no advantages of the already sorted nature of the storage scheme of a multiset.

Access "i-th" element:

std::cout<<*std::next(m.begin(),i-1)<<std::endl;

But again, what is meant by "i-th element" is determined by your ordering scheme.

Ok, and when your ordering scheme is given by std::less -- the standard case -- then indeed 

m.begin();

gives you the minimal element. You can read it up here.

davidhigh
  • 14,652
  • 2
  • 44
  • 75
0

Multiset works by maintaining a red-black balanced binary tree.

Generally the meaning of a balanced tree (and red-black specifically) is that you can add/search/delete/get the min/get the max (and more) in O(logk) operations where k is the size of the tree (that is, the number of elements in the multiset). Specifically in c++'s multiset the complexity might change a bit, depends on the action.

If your set is s then:

  • You can get the min element in the set by using s.begin();
  • You can get the i'th element in the set by using *next(s.begin(),i-1) (as next(it, d) gives you the pointer to the element in position it + d). The complexity of this is linear as stated here.
Lukarish
  • 1