1

I'm using a std::multiset of pointers to objects to implement Z-ordering in my game, so I don't need to sort the structure on each insertion. I use a comparator for insertion by the object's depth: 

struct rendererComparator
{
    bool operator ()(const Renderable* r1, const Renderable* r2) const
    {
        return r1->depth < r2->depth;
    }
};

std::multiset<Renderable*, rendererComparator> m_Renderables;

However when it comes to erasing an element in the multiset, the call to erase removes all elements which have the same depth which is undesirable. I tried the suggestions in this question: In std::multiset is there a function or algorithm to erase just one sample (unicate or duplicate) if an element is found but 

auto iterator = m_Renderables.find(renderable);
if (iterator != m_Renderables.end())
{
    m_Renderables.erase(renderable);
}

Still erases all the elements with the same depth because of the comparator.

Is it possible to define 2 comparators for std::multiset without boost? (How can I set two kind of comparator (one for insert, one for find) on this multiset?) One for insertion and one for comparison?

Thanks

Edit: Jignatious pointed out that I wasn't erasing the iterator (typo by me). I solved it by using std::find_if

auto iterator = std::find_if(m_Renderables.begin(), m_Renderables.end(), [renderable](const Renderable* r1) { return r1 == renderable; });
if (iterator != m_Renderables.end())
{
    m_Renderables.erase(iterator);
}
Nubcake
  • 449
  • 1
  • 8
  • 21

2 Answers2

2

The problem is on this line:

m_Renderables.erase(renderable);

which erases all elements with the same value.

You need to erase with the iterator from the find() function call instead. That will erase the single element that the iterator points to:

m_Renderables.erase(iterator);

Note that std::multiset::find() returns an iterator pointing to the lower bound (or first) of the elements which is searched in the multiset if it exists, otherwise the one past the end element iterator.

jignatius
  • 6,304
  • 2
  • 15
  • 30
  • Thanks, that was a typo by me. I've edited my answer to show my solution. – Nubcake Apr 25 '20 at 21:26
  • @Nubcake Although `std::find_if` works the `find()` of the multiset will be faster. As a general rule you should prefer the `find()` functions of containers than using `std::find()` or `std:find_if()` because they are optimised for their containers. – jignatius Apr 25 '20 at 21:33
  • The reason I used `std::find_if` is that `find()` returned an iterator to the first value it found (in this case there were 3 elements with the same depth) but it was not always the correct object so I had to check if the next element with the same depth was the object I was looking for. Is there a better solution to this? – Nubcake Apr 25 '20 at 21:54
  • @Nubcake You could use [std::multiset::equal_range](http://www.cplusplus.com/reference/set/multiset/equal_range/) to return a pair of iterators representing the first and last iterator for elements with a particular value. Then you can do a loop using those iterators, checking the element first before erasing the right one. – jignatius Apr 26 '20 at 03:40
0

Instead of multiset, you can use std::set with comparer like this:

struct Element
{
    int value;

    Element(int v)
    {
        value = v;
    }

    bool operator() (Element* const& left, Element* const& right) const
    {
        if (left->value == right->value)
            return (left < right);

        return left->value < right->value;
    }
};

It will store multiple values like multimap, but without 'erase all' on erase, without replace same values on insert and with proper find by reference.


std::set<Element*, Element> set;
set.insert(new Element(10));
auto last = new Element(10);
set.insert(last); // 10 10 like in multiset
set.erase(last); // will delete proper references
Vitalik Beloded
  • 1