Sorting vector of pointers

问题:

I'm having a little trouble trying to sort a vector of pointers.

This is what I have done so far:

class Node
{
    private:
    vector <Node*> _children;
    string _data;
    ...
    public:
    void Node::add_child(Node* child)
    {
        ...
        sort(_children.begin(), _children.end());
    }

    bool Node::operator<(const Node& node)
    {
        return (this->_data.compare(node._data) == -1);
    }
};

My less-than operator works, if I write like this:

Node* root = new Node("abc");
Node* n = new Node("def");
cout << (*root<*n) << endl;

Why does sort never call the operator?? Any help would be appreciated! Thanks.

madshov

回答1:

Because you sort the pointer values, not the Nodes they point to.

You can use the third argument of the std::sort algorithm to specify a custom comparator.

For example :

bool comparePtrToNode(Node* a, Node* b) { return (*a < *b); }

std::sort(_children.begin(), _children.end(), comparePtrToNode);

(note that this code is just an indication - you'll have to add extra safety checks where needed)

回答2:

Your less-than operator takes const Node& arguments, but your vector is sorting Node*s. You need to specify a comparison function as the third parameter to std::sort.

class Node
{
    private:
    vector <Node*> _children;
    string _data;
    struct PointerCompare {
      bool operator()(const Node* l, const Node* r) {
        return *l < *r;
      }
    };
    public:
    void add_child(Node* child)
    {
        sort(_children.begin(), _children.end(), PointerCompare());
    }

    bool operator<(const Node& node) const
    {
        return (this->_data.compare(node._data) == -1);
    }
};

Also, your operator< needs to be declared const.

回答3:

Your operator<() operates on references to Node objects; but the vector contains pointers to Node objects, which can't be compared with that function. You'll have to explicitly supply a proper function (one that accepts pointers as arguments) to the sort() algorithm.