2

I am interested in inserting elements in a std::multiset but I would like to keep the set fixed length. Every time an element is inserted, the last element will be removed. I came up with the following solution

int main(){
       std::multiset<std::pair<double, int>> ms;
       for (int i=0; i<10; i++){
              ms.insert(std::pair<double, int>(double(rand())/RAND_MAX, i));
      }
      ms.insert(std::pair<double, int>(0.5, 10));
      ms.erase(--ms.end());
      for(auto el : ms){std::cout<<el.first<<"\t"<<el.second<<std::endl;}
return 0;
}

I will be doing something similar to this many times in my code on sets of a size in the order of 1000 elements. Is there a more performant way of doing this? I am worried that the erase will cause memory reallocation and slow down the code.

JVn
  • 21
  • 2
  • Do you use a `std::multiset` because you need to keep the container sorted? – Christian Hackl Apr 07 '16 at 15:09
  • In other words: is it important that the *last* element is erased? Or can it be any element? – Christian Hackl Apr 07 '16 at 15:13
  • I was under the impression that std::set can't handle the case in which 2 elements are the same so to avoid this I used multisite. I will always have to remove the last element. – JVn Apr 07 '16 at 15:14
  • Yes, a `std::set`'s elements are unique, while a `std::multiset`'s elements are not. But both are sorted. – Christian Hackl Apr 07 '16 at 15:17
  • [This post](http://stackoverflow.com/a/16220234/5717589) may be of some interest to you. It's a comparison of performance of a priority queue and a multiset. – ptrj Apr 08 '16 at 02:22

0 Answers0