C++ trouble sorting a vector of custom objects

Question

Edit, Update: Great answers thank you all. I've written operator overloading for < and == operators. I am no longer receiving the error. I also correctly passed the vector by reference instead of by value into my removeDup(vector<Graph::Vertex>&); function.

I have a vector of objects that I need to remove duplicates from, but I am receiving an error that I am unfamiliar with (the error is below). It's a very simple object publicly contained within a class called Graph:

struct Vertex
    {
        string name;
        int num;
    public:
        Vertex();
        Vertex(string, int);
        void printVertex();
    };

I have read through a few threads regarding this (This one in particular) but I am getting a very strange error when I try to sort my vector using unique.

I add to the vector using push_back:

vector<Graph::Vertex> v;
Graph::Vertex first(string1, count);
v.push_back(first);

and attempt to sort using this code that I found in another thread:

void removeDup(vector<Graph::Vertex> v)
{
    sort( v.begin(), v.end());
    v.erase( unique( v.begin(), v.end() ), v.end() );
}

However, when I use this function, I get an error:

error C2678: binary '==' : no operator found which takes a left-hand operand of type 'Graph::Vertex' (or there is no acceptable conversion)

I am slightly new to programming in C++ and have no idea why this error is happening, or what it means. Could someone explain why I am getting this error? Do I need to write an operator overload function to take care of it?

Tried very hard to google (and use this website) for the solution to this error, but in the end had to make my first post here for help. A heads up: this is for a homework assignment, so I decided not to include the rest of my code to avoid being spoon fed the answers, but if I haven't given enough information, please let me know.

score 0 · Answer 1 · answered Apr 28 '14 at 00:38

The compiler has no idea which Vertex is placed before another Vertex when it needs to be sorted. You need to tell the compiler this information. Therefore use the 3 argument std::sort() function, or write an overloaded operator < for your Vertex class.
The compiler has no idea what makes a Vertex equal to another Vertex. You need to tell the compiler this information. Therefore use the 3 argument std::unique() function, or write an overloaded operator == for your Vertex class.
Pass objects such as vector by reference, not by value:

void removeDup(vector<Graph::Vertex>& v)

Note the &.

score 0 · Answer 2 · answered Apr 28 '14 at 00:40

Two recognize unique objects, you need to be able to test for equality (after all, how else would you recognize to objects that are the same).

Assume two objects a and b. The canonical way to test for equality is a == b. If you operate on ints the compiler knows how to deal with this expression (e.g. emit a CMP instruction).

However, since you defined Vertex yourself, the compiler must be told how to consider two Verteces to be equal. The easiest way to define arithmetic operators is like this:

struct Vertex
{
    string name;
    int num;
public:
    Vertex();
    Vertex(string, int);
    void printVertex();

    friend bool operator==(Vertex const& lhs, Vertex const& rhs)
    { return lhs.num == rhs.num; } // or whatever you wish to do here
};

Just a heads up: When defining == you may wish to also define != to be consistent. You also may wish to define all the <, <=, >, >= so that comparision is possible...

Jerry Coffin · Accepted Answer · 2014-04-28T00:51:15.463

std::sort and std::unique both need to compare items to do their jobs. They have somewhat different requirements though: std::unique compares for equality and std::sort compares for ordering. One obvious possibility for your case would be code on this general order:

bool operator==(Vertex const &other) const {
    return num == other.num;
}

bool operator<(Vertex const &other) const {
    return num < other.num;
}

[Note: these would be member functions of your Vertex class.]

It's possible to implement the required functionality in other ways, especially if (for example) you might want to sort objects based on one field sometimes, and by another field at other times (e.g., sort by number and sort by name, in the case of your Vertex class).

You can do that by passing a third parameter to sort and/or unique to tell it what to use to do the comparison. At least in current C++, if I'm going to do this, I generally use a lambda expression to specify the comparison:

std::sort(v.begin(), v.end(),
    [](Vertex const &a, Vertex const &b) { return a.name < b.name; });

This puts the comparison code right next to the sort, so it's easy to see how you're doing the sorting. You can use a separate function or function object instead, but doing so means you need to be careful with the name to ensure it describes the sort order:

struct by_name {
    bool operator()(Vertex const &a, Vertex const &b) const {
        return a.name < b.name;
    }
};

// ...
std:sort(v.begin(), v.end(), by_name());

score 0 · Answer 4 · answered Apr 28 '14 at 00:43

The compiler does not know how to compare one vertex object with another when it tries to sort. you can do it by overloading < operator in your Vertex class. This operator will be used to compare tow vertices and place one before another. and you need to overload operator == to be used in unique, since it will use operator == to check if one vertex is equal to another and hence find duplicates.

C++ trouble sorting a vector of custom objects

4 Answers4