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.

Arne Mertz · Accepted Answer · 2014-04-07T07:02:44.050

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()
);

Would it still be possible to compare references in the == operator function? Right now I added a friend bool operator(Node x, Node y) function to my Node class, which returns &x == &y. It compiles, but I haven't gotten to the point where I can debug it. Could you sanity check this? Edit: The reason I ask is because the id field is likely to be removed, and Nodes may have the same position, so I feel the most reliable way to ensure the node I want to remove is the same one found in the vector is to compare references. — Mel, Mar 31 '14 at 07:26
@Mel Yes, it is possible and advisable for the `operator==` to take its parameters by reference. Taking them by value and then comparing the addresses of these values does not make any sense. Call-by-value means that `x` and `y` are always two distinct (but not necessarily different) variables. And the adresses of those two distinct variables can never be the same. Comparing the adresses is not necessarily the right thing to do even if you call by reference, because it is the content that matters, not if it is the very same variable that you compare. See my example `operator==`. — Arne Mertz, Mar 31 '14 at 07:37

score 0 · Answer 2 · answered Mar 31 '14 at 06:45

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());

score 0 · Answer 3 · answered Mar 31 '14 at 06:45

0

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.

answered Mar 31 '14 at 06:45

Andrei

4,880
23
30

Removing a Node by reference from std::vector

3 Answers3