Sorting vector of pointers

Question

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

Solution 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)

Solution 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.

Solution 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.

Comments

[Kerrek SB]

Arguably, PointerCompare could just be a static function.

[boycy]

The result of using operator<() to compare pointers is generally unspecified as per [expr.rel/2]: "If two pointers p and q of the same type point to different objects that are not members of the same object or elements of the same array or to different functions, or if only one of them is null, the results of p<q, p>q, p<=q, and p>=q are unspecified." You may use std::less<const Node*>() instead of PointerCompare to achieve this.

[matth]

@boycy - 1) My example never compares pointers. 2) std::less<const Node*>() does compare pointers, and thus invokes undefined behavior.

[boycy]

@Robᵩ Erk sorry, my bad - being too hasty. FWIW std::less<T*> doesn't invoke UB as it has a partial specialization that provides well-defined total order for pointers regardless of operator<() (ditto the other 3 comparators) [N3337 20.8.6/8]

[matth]

@boycy - Thanks! I didn't know that std::less was defined for pointer types.

[boycy]

No worries, I thought a freebie was in order since you refrained from calling me a muppet ;-)