GCC Tree STL data containers

Question

Possible Duplicate:
remove_if equivalent for std::map

Yesterday i wrote a program, which use multiset for storing elements like this:

std::multiset < boost::shared_ptr < CEntity > > m_Entities;

Then i try to use standard algorithm remove_if like this:

std::remove_if(m_Entities.begin, m_Entities.end(), MarkedForDestroy);

BUT compilation failed, because if we see in GCC 4.4 implementaion of set and multiset we see that:

typedef typename _Rep_type::const_iterator            iterator;
typedef typename _Rep_type::const_iterator            const_iterator;

I was shocked. I google this moment and better that i found that this does not contradict the standard. The same for set.

How this cannot contradict if standart algorithms doesnt work? How i can better change container?

Answer 1

Because multiset (and also set) are immutable containers, i.e. elements in the container cannot be changed modified in-place, they can be removed, modified, and (re-)inserted.

See, for example:

• a different set related answer
• section 27.3.2.1 in this tutorial

In simple associative containers, where the elements are the keys, the elements are completely immutable; the nested types iterator and const_iterator are therefore the same.

Answer 2

You can not use std::remove_if algorithm on an associative container. You need to a write a for loop and use the erase method to remove the elements. See this similar question remove_if equivalent for std::map for more details.

Answer 3

All standard ordered/associative containers (map, set, multimap, multiset) have immutable keys (just the keys not the entire container).

As to why just look at what would need to happen every time you would change the value of the key: the key type would need somehow to notify it's container that it got changed (which would introduce a very tight and unnecessary coupling between the container & it's key type - not to mention being impossible to do for fundamental types) because the container would need to be resorted so to keep it's ordering property (which is a pretty big overhead).