compiling error when erasing a STL std::set element by key

Question

I have the following code, in which I hold a std::set of iterators to a STL container of ints, and erase an element by key (where the key is an iterator to the STL container). The code compiles and runs as expected (compiler is VC 2008) if the container is std::vector, but fails to compile if the container is a std::list

using namespace std;

typedef vector< int > Container;     //--> fails to compile if 'vector' is changed to 'list'
typedef Container::iterator IntIt;

set< IntIt > itSet;
Container c;
c.push_back (1);
c.push_back (2);
c.push_back (3);

IntIt it = c.begin ();
itSet.insert (it++);
itSet.insert (it++);
itSet.erase (c.begin ()); //--> The problematic line

The compile error is:

c:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\include\functional(143) : error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const IntIt'

So it seems to me the error is because the compiler interprets one of the template's < as smaller than operator - but I can't really understand why, or how to fix it.

It fails on VS2008, I guess it depends upon list::iterator implementation. — Naveen
In my opinion, its really bad idea to have a std::set of iterator (of vector), because once the vector resizes itself, all the iterators in the set would be invalidated, and you never know when the vector resizes itself. I'm not saying that its impossible to know when it happens, but it wouldn't be elegant to have such design that requires this knowledge. If you tell us the goal as to what exactly you're trying to do, maybe we could suggest some better solutions. — Nawaz
What are you really trying to do? A set of iterators into a vector will just contain what you get when incrementing from c.begin() to c.end(). — Bo Persson

Björn Pollex Björn Pollex · Accepted Answer · 2011-05-26T10:37:44

The problem is caused by the fact list::iterator does not have a comparison defined. The value type of an std::set requires a strict weak ordering.

A vector supports random access iterators, which have an ordering. A list is only required to support bidirectional iterators, which do not have an ordering (of course, an implementation is free to support random access iterators for lists as well, so on some compilers it might work).

In order to fix it, you would have to write a comparison function yourself. The problem is that the only way to detect the order of two iterators in a list would be to walk from one to the other, which requires linear time.

compiling error when erasing a STL std::set element by key

1 Answers