Insert in stl set

Question

I need to keep a collection of integers in a priority_queue. However I need to be able to remove one of these integers even if it's not the first element of my container. I couldn't use std::priority_queue. I chose to use a set which would keep the integers sorted based on a custom comparator.

class Comparator
{
    vector<double>& cmp;
    public:
    Comparator(vector<double>& a_cmp) : cmp(a_cmp) {}
    bool operator() (int i, int j) const {return cmp.at(i) < cmp.at(j);}
};

I then used the set like this :

Comparator comp = Comparator(a_cmp);
set<int, Comparator> my_set (comp);
my_set.insert(index);

However it appears that for two integers i and j such as i != j and cmp.at(i) == cmp.at(j), if I try to insert both, only one would be inserted into the set. I understand that it is the behaviour of std::set, however I would have prefered if both those integers (which are not equals) would be inserted in the set next to each other. In other words I need my custom comparator to be used when sorting the set but not to prevent insertions. I think it may work when I modify my comparison function for:

bool operator() (int i, int j) const {return cmp.at(i) =< cmp.at(j);}

However I'm not sure if it's completely correct. Should I use a std::vector with my original comparison function and sort it with std::sort instead? Thanks for your answers.

Answer 1

However it appears that for two integers i and j such as i != j and cmp.at(i) == cmp.at(j), if I try to insert both, only one would be inserted into the set. I understand that it is the behaviour of std::set, however I would have prefered if both those integers (which are not equals) would be inserted in the set next to each other.

In your operator(), you could do

return (cmp.at(i) < cmp.at(j)) || (!(cmp.at(j) < cmp.at(i)) && (i < j));

Which is basically saying that the set will be sorted in ascending order by the value at the index, then by the relative value of the index itself.

Answer 2

Boost has several heap implementations with more features than the one provided with the STL. You can use boost::heap::fibonacci_heap which has an erase() method.

You can find the complexities of each heap operations here.