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;
IntIt it = c.begin ();
itSet.erase (c.begin ()); //--> The problematic line
The compile error is:
c:\Program Files (x86)\Microsoft
9.0\VC\include\functional(143) : error C2784: 'bool std::operator <(const
std::_Tree<_Traits> &)' : could not
deduce template argument for 'const
std::_Tree<_Traits> &' from 'const
So it seems to me the error is because the compiler interprets one of the template's
smaller than operator - but I can't really understand why, or how to fix it.
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.
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.