how remove multiple items from multimap in one step of while?

Question

I use iterator for removing items, I want to erase first item and second item from my map in each step of while.

Here is code (this code is part of Huffman code)

std::multimap<float, node *> ::iterator first, second;
first = floattnode.begin();
second = ++first;
while (floattnode.size() != 0) { //floattnode is a multimap mapping frequency to node
    root = new node((*first).first + (*second).first, '-');
    root->left = new node(((*first).second), 0);
    root->right = new node(((*second).second), 1);

    floattnode.erase(first);
    floattnode.erase(second);//here i have problem

    first = floattnode.begin(); //check
    floattnode.insert(std::pair<float, node *>(root->freq, root));
    first = floattnode.begin();
    second = ++first;
}

when iterator remove first item it can't access to second item to erase, how can I remove this two items ?

Answer 1

second=++first;

Here you are not only assigning the iterator to the second element to second, but also you are stepping the iterator in first, because ++ is the increment operator, which increments its operand. There seems not to be an addition operator for multimap iterators. So you will have to decrease the iterator after you assigned second again:

second = (++first)++;

This will first increment first and return it to second, after that it will be incremented again. Or assign to second and increment it afterwards:

second = first;
second++;

or shorter:

(second = first)++;

Anyway you should first check whether there are at least two elements in the container. If there is no element, then first == floattnode.end(), which you will try to increment, invoking undefined behaviour. (My setup actually gives me an infinite loop for trying this, see also Strange behavior with std::map::iterator's postincrement)

while (floattnode.size() != 0) {

You are creating new objects with new in each loop turn and assign their pointer to root, later you insert pointers to them into floattnode, but erase them in one of the later loop turns again. So you loose all references to the created objects at some point. Since you also never call delete on them, you are leaking memory there.

Since you add an element to floattnode at the end of each loop run, floattnode.size() can never be zero at the loop condition check. This is an infinite loop.

root=new node((*first).first+(*second).first,'-');

If floattnode.size() == 1 this will be executed and second will be dereferenced, although it points behind the last element of the map. This results in undefined behaviour.

Instead of (*first).first you should use first->first for readability. (It does the same).

floattnode.erase(first);
floattnode.erase(second);//here i have problem

You are trying to erase the same iterator twice because of the error I mentioned in the beginning. In general iterators to containers may become invalid if the container is modified, so if you want to make sure this doesn't affect you use:

floattnode.erase(floattnode.begin());
floattnode.erase(floattnode.begin()); // Notice this is now the originally second element because the first one was erased.

However for multimap it seems that only the erased iterator is invalidated by calling erase, based on the answers here: Iterator invalidation rules . Sou you should be fine with your original code in this case.

Because you only check for the container size to be greater than zero, there is again undefined behaviour if the size is exactly 1 and you try to erase the second element (that is floattnode.end(), pointing behind the last element).

second = ++first;

Same error as at the beginning.

Answer 2

I never modify sets, lists or maps in place. I always create a new one and loop through the old one adding the entries I want into the new one and omit the ones I want to delete.

I tried understanding what was happening with delete in place and iterators and decided it was too hard for me, and anyone coming after me.