Does "erase" function from "set/map" STL container rebalance the tree after calling?

[starquest1000]

Hello,

I have a "set" or "map" container and it contains many elements.

Please see following code:

 std::set<int>::iterator it = myset.begin();
 std::set<int>::iterator itEnd = myset.end();
 std::set<int>::iterator itNext;

 while (it != itEnd)
 {
    itNext = it;
    itNext++;                 // Advance pointer to next element
    if (it->number == 100)
    {
       myset.erase (it);
       it = itNext;           // Continue with next element in the container
       continue;
    }  
    
    it++; 
 }    

My questions is:

By calling the "erase()" function, will elements from the container be "re-balanced"?


Perhaps I may need to elaborate my concerns/questions a little here ...

After the "erase()" is called ...

1) Will "itNext" still be pointing the correct next element?
2) Will the ACTUAL "itEnd" changed so I may never get out of the "while" loop?

3) If above are correct? Is there any workaround to the problem?

Thanks in advance.

[mik2718]

Should work, the erase operator only invalidates the iterator used for erasing.

I think this summary is correct, r.e. containers and erase()

vector - all iterators greater than and including the erased element are invalidated
map/set - only the iterator pointing to the erased element is invalidated
list - only the iterator to the erased element is invalidated, you can get the next element as a return values from the erase method

[kbw]

The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis gives this example for map and multimap.

   //remove all elements having a certain value
   for (pos = coll.begin(); pos != coll.end(); ) {
       if (pos->second == value) {
           coll.erase(pos++);
       }
       else {
           ++pos;
       }
   }

In coll.erase(pos++);, pos++ increments pos, but returns the old iterator. This very useful side effect does the erase and increment in one line. It's a very useful pattern.

[Peter87]

coll.erase(pos++);, you can also do pos = coll.erase(pos);

[vlad from moscow]

kbw Mar 3, 2012 at 3:37pm
The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis gives this example for map and multimap.

    //remove all elements having a certain value
   for (pos = coll.begin(); pos != coll.end(); ) {
       if (pos->second == value) {
           coll.erase(pos++);
       }
       else {
           ++pos;
       }
   }

In coll.erase(pos++);, pos++ increments pos, but returns the old iterator. This very useful side effect does the erase and increment in one line. It's a very useful pattern.

it is very and very bad practice That shows only that the programmer is low qualified. Never use this approach. Consider for example if your collection is of type std::vector. What you will get as result of execution this code?!

Member function erase for all standard containers returns valid iterator which points to the next element . And you should use this interface provided by the function. So the correct code wiil look like

    //remove all elements having a certain value
   for (pos = coll.begin(); pos != coll.end(); ) {
       if (pos->second == value) {
           pos = coll.erase(pos);
       }
       else {
           ++pos;
       }
   }

In this case you can use this code either with sets or with vectors.

[kbw]

it is very and very bad practice That shows only that the programmer is low qualified.

I love it, maybe Josotis should get some qualifiations! And what if your implementation's map erase return type is void (as in gcc 4.5 and VC10.0)?

[vlad from moscow]

You can write any bad code if you have so low qualification. But the C++ Standard lists requirements for iterators and containers. And a qualified programmer writes code that satisfies these requirements. So a qualified programmer will write erase function that similar to other erase functions of standard containers and returns next iterator. So it will not break common interface. An unqualified programmer will write erase which returns void. As in Russia people says the law is not writtten for stupids.

[vlad from moscow]

kbw.

by the way it is interesting what standard container does define erase which returns void? For example, in Sequence container requirements is written that erase shall return iterator. The same is written in Associative container requirements with some additions. Also basic_string class satisfies these requirements.

[Peter87]

In C++03 erase did not return an iterator for all containers. std::set was one of them so I don't really see a better way than doing coll.erase(pos++); if you are writing C++03 code. It is safe and it is guaranteed to work even in C++11 for std::set, std::map, and a few other containers.

[vlad from moscow]

It was obvious bug of C++03 and it was updated in C++11.
I'd like to say that even C++11 contains many bugs. For example there are absent global functions cbegin, cend, rbegin, rend, crbegin, and crend in the Standard. I sent already my proposals to the Committee to include these functions in the Standard.

Or another example with container adapters. They had no such useful function as swap and only now this function was included in the Standard. But what about max_size and clear fro container adapters?!

Well I have already pointed out what will be the result of your code if your collection is of type std::vector? It is obvious that you will get a bug.

So if there is a possibility to use the interface the function provides it is much better to use it.

I think that it is the bad code that Josotis demonstrates (with Herb Sutter) results to adoption of common requirements to containers. Because it is in general very bad when functions with the same name that perform the same task have different interfaces. This make life of programmers harder.

As now the C++ 11 Standard is adopted it is better to follow its recomendations.

[kbw]

I really don't see the point of bashing C++03 compilers as there are no commercial grade or mainstream C++11 compliant compiler available.

If you want to live in a bubble and talk about tomorrows products that's fine, but some of us have to use todays tools today.

The post was about a map. I mentioned map and multimap in my post. As these don't return iterators, there isn't a general case that covers all containers.

[vlad from moscow]

kbw,

I have checked MS VC++ 10 now and have seen that erase returns iterator.The old version of the function is commented in header file <set>.
And Microsoft is going to release VC 11 this year.

[starquest1000]

Guys, thanks for all the inputs, but I am not sure if my questions are answered.

So, what I am getting from you guys are:

1) The "set" tree is NOT re-balanced after the "erase()"?
2) Though even if the tree is rebalanced, this should be transparent to the user by calling

pos = coll.erase(pos);

, it should be correctly advance to the next correct element from the container.
3) When I checked the description of the return value of the (set) erase() function (

http://www.cplusplus.com/reference/stl/set/erase/

), it stated:

Only for the second version, the function returns the number of elements erased,

The second version, I am assuming it is the C++11 that you mentioned, it does not say the return value of the "erase()" function points to the next element in the container. Am I missing something here?

Thanks.

[JLBorges]

> The "set" tree is NOT re-balanced after the "erase()"?

It may be. However, there is a guarantee that iterators (and references) to other elements are not invalidated.



> Though even if the tree is rebalanced, this should be transparent to the user by calling
pos = coll.erase(pos);

It will be transparent to the user. However, pos = coll.erase(pos); is not valid C++98.



> When I checked the description of the return value of the (set) erase() function
> http://www.cplusplus.com/reference/stl/set/erase/ ...
> ... it does not say the return value of the "erase()" function points to the next element in the container.
> Am I missing something here?

Yes. Up to date documentation. There is a change from C++98 to C++11.
See: http://en.cppreference.com/w/cpp/container/set/erase

In practice, right from 1998, Dinkumware (and by extension Microsoft) implementations have always returned an iterator to the next element.

[starquest1000]

Thanks JLBorges.

there is a guarantee that iterators (and references) to other elements are not invalidated.

With balanced tree, when an element is removed, the tree will be rebalanced. How can we guarantee that iterators (and references) to other elements are not invalidated? Perhaps I am still missing something here.

Just a stupid question:

How do I find out what version of C++ I am using?

Thanks.

[JLBorges]

> With balanced tree, when an element is removed, the tree will be rebalanced.
> How can we guarantee that iterators (and references) to other elements are not invalidated?

I presume the 'we' in 'How can we guarantee' refers to the implementation - how can can an implementation guarantee that iterators (and references) to other elements are not invalidated?

By not moving the nodes of the tree to a different location in storage.


> How do I find out what version of C++ I am using?

See: http://cplusplus.com/forum/beginner/62482/