pointer delegate in STL set.

Question

I'm kinda stuck with using a set with a pointer delegate. My code is as follows:

void Graph::addNodes (NodeSet& nodes)
{ 
  for (NodeSet::iterator pos = nodes.begin(); pos != nodes.end(); ++pos)
  { 
    addNode(*pos);
  }
}

Here NodeSet is defined as:

typedef std::set<Node_ptr, Node_ptr_Sorting_Predicate> NodeSet;

The above piece of code works perfectly on my windows machine, but when I run the same piece of code on a MAC, it gives me the following error:

no matching function for call to 'Graph::addNode(const boost::shared_ptr<Node>&)'

FYI, Node_ptr is of type: typedef boost::shared_ptr<Node> Node_ptr;

Can somebody please tell me why this is happening?

Answer 1

Ok, from your added information, the problem seems to be that addNode takes a Node_ptr per non-const reference, while what the compiler has to call the function is a const boost::shared_ptr<Node>& (note the const). Let me explain:

std::set is an associative container. Associative containers store their elements in some order, using the key element to define the ordering. If you would be allowed to change the key without the container knowing, you would invalidate the container's internal order. That's why I believe dereferencing a std::set<T>::iterator does not return an modifiable lvalue. (Which means you cannot alter the reference returned. For example, if you have an iterator pos into a std::set<int>, *pos=42 should not compile.)
The catch with this is that only modifiable lvalues will bind to a non-const reference. But what *pos returns isn't a modifiable lvalue and thus won't. (So, in my example, int& r = *pos; won't compile.) The reason is that, if this was allowed, you could change the sorting key through that non-const reference behind the container's back and mess up the container's internal ordering.
That is why the result of your *pos won't bind to a Node_ptr&. And that in turn is why the compiler cannot call your function.

Does your addNode() member function really alter the Node it's given? If not, it should take a const Node_ptr&.
If it does, you have a design problem. You cannot alter an element that's in a set. The only thing you can do is to remove it from the set, change it, and add it back in.

On a side note: VC9 indeed compiles the following piece of code:

#include <iostream>
#include <set>
#include <typeinfo>
#include <iterator>

int main()
{
    std::set<int> set;
    set.insert(5);
    std::cout << *set.begin() << '\n';
    *set.begin() = 3; // this is an error!
    std::cout << *set.begin() << '\n';
    return (0);
}

I believe this is an error in VC9. Comeau rejects it.

---

Here's how to solve riddles with a compiler not calling a function you think it should call or calling the wrong function from a set of overloads.
The function you thought it should call is Graph::addNode(Node_ptr&). The code that you thought should call it is

addNode(*pos);

Change that code so that it provides the exact parameter(s) required:

Node_ptr& tmp = *pos;
addNode(tmp);

Now the call should definitely compile (or call the right overload), and the compiler should bark if it thinks *pos cannot be assigned to to a Node_ptr&.
Usually this tactic helps me to find out what's wrong in such situations.

Answer 2

If memory serves, the original C++ spec (1998) permits std::set to return modifiable iterators. This carries with it a risk--the iterator might be used to modify the stored value, such that the ordering of the set is now broken. I believe subsequent versions of the spec have changed this, and now all set iterators are non-modifiable.

VC++ 2010 respects the new behaviour, and has non-modifiable set iterators (which is annoying, as it prevents making changes that don't change the ordering and which ought to be legal).

Prior versions, however, did not. This means that you can create functions that are not suitably annotated with const, which will cause problems on switching to different compilers. The solution is to add the necessary const changes. VC++ will still work (since non-const values can be implicitly made const anyway), and so will everything else.