Removing a Node by reference from std::vector

Question

I'm relatively new to C++ so please excuse any oversights.

I have a custom Node class that contains an id and a position. In the main portion of my code, I created a vector, std::vector<Node>candidateNodes, and pushed a bunch of newly created nodes in.

I have a function, expandCandidateNode, that takes in one of the nodes from the vector of candidateNodes as well as the vector itself and does some stuff with it:

expandCandidateNode(Node &candidateNode, std::vector<Node> &candidateNodes)

At the end of the function, I want to remove the candidateNode from my vector of candidateNodes. I tried using the solution from this stackoverflow question, which looks something like this:

candidateNodes.erase(std::remove(candidateNodes.begin(), candidateNodes.end(), candidateNode), candidateNodes.end());

However, when I tried building the project, I got the following error:

1>c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1815): error C2678: binary '==' : no operator found which takes a left-hand operand of type 'Node' (or there is no acceptable conversion)

I took a closer look, and found the error originated from the template function remove in the algorithm class. I'm not really sure what to do from here. My intention was to have the candidateNodes vector search for the node with the same reference as the candidateNode (basically ensuring they are the same object in memory), and removing it, but it seems like the == operator isn't able to compare their references? I may be misunderstanding something. If someone could clarify how I can properly remove a node from a vector, given its reference, it would be much appreciated. Thanks.

Answer 1

std::remove comes in two flavors:

The std::remove that you used takes a value as third parameter and compares it to the elements using the equality operator ==. Your Node class does not seem to support those comparisons, therefore you get the error somewhere deep in the guts of the standard library, where the comparison is made.

The alternative is std::remove_if. Instead of the value to compare, it takes a callable as third parameter. It passes the objects in the range to that callable and expects a result convertible to bool, to tell if the element should be removed or not.

So, if you want your Nodes to be comparable with == in general, you will have to define that operator and can then use std::remove:

bool operator== (Node const& lhs, Node const& rhs) {
  return lhs.id == rhs.id && lhs.position == rhs.position;
}

And the just call remove as you had it.

The other option is to provide a function object to std::remove_if. That could be done either via a C++11 lambda expression, or by providing a handwritten functor in C++03:

C++11:

candidateNodes.erase (
  std::remove_if (
    candidateNodes.begin(), 
    candidateNodes.end(), 
    //here comes the C++11 lambda:
    [&](Node const& node) {
      return node.id == candidateNode.id && node.position == candidateNode.position;
    }
  ), 
  candidateNodes.end()
);   

Or C++03:

struct cmpNode {
  Node const& candidateNode;

  cmpNode(Node const& cn) : candidateNode(cn) {}

  bool operator()(Node const& node) {
    return node.id == candidateNode.id && node.position == candidateNode.position;
  }
};

candidateNodes.erase(
  std::remove_if(
    candidateNodes.begin(), 
    candidateNodes.end(), 
    //here comes the C++03 functor:
    cmpNode(candidateNode);
  ), 
  candidateNodes.end()
);   

Answer 2

You can do like this,

 struct Node
    {
            int id;
            int position;
        };

        struct Node targetNode; //the node you want to move
        bool comp(const Node& element)
        {
            return ((element.id == targetNode.id) && (element.position == targetNode.position));
        }
        candidateNodes.erase(std::remove_if(candidateNodes.begin(), candidateNodes.end(), comp), candidateNodes.end());

Answer 3

std::remove uses operator== to do the check. You still need to add this operator to your Node class.

I recommend you create a good implementation of the operator, relying on the unique data of the Node, the id and/or the position.