Use of unique on STL vector with a structure

Question

In a programming task, I'm trying to ensure a particular vector contains only unique items. With primitive types, the operation is as simple as:

vector<int> lala;
lala.push_back(1);
lala.push_back(99);
lala.push_back(3);
lala.push_back(99);

sort(lala.begin(), lala.end()); // lala: 1, 3, 99, 99
lala.erase(unique(lala.begin(), lala.end()), lala.end()); // lala: 1, 3, 99

However, the problem is I'm not using int. But:

typedef struct
{
    int x;
    int y;
    int maxX;
    int maxY;
    int width;
    int height;
    int id;
} Rect;

bool SameRect(Rect first, Rect second)
{
    return first.x      == second.x &&
           first.y      == second.y &&
           first.width  == second.width &&
           first.height == second.height &&
           first.maxX   == second.maxX &&
           first.maxY   == second.maxY;
}

//...
vector<Rect> lala;
//...
sort(lala.begin(), lala.end());
lala.erase(unique(lala.begin(), lala.end(), SameRect), lala.end());
//...

Doesn't really work. What did I done wrong?

EDIT:

With sth's advice, I implemented two sorting predicate for std::sort():

bool SortRect(const Rect &first, const Rect &second)
{
    if (first.x < second.x) return true;
    if (first.x > second.x) return false;

    if (first.y < second.y) return true;
    if (first.y > second.y) return false;

    if (first.maxX < second.maxX) return true;
    if (first.maxX > second.maxX) return false;

    if (first.maxY < second.maxY) return true;
    if (first.maxY > second.maxY) return false;

    if (first.width < second.width) return true;
    if (first.width > second.width) return false;

    if (first.height < second.height) return true;
    if (first.height > second.height) return false;

    if (first.id < second.id) return true;
    if (first.id > second.id) return false;

    return false;
}

But I found that it has the same effect as:

bool SortRect(const Rect &first, const Rect &second)
{
    return first.x < second.x;
}

if SGI's documentation is anything to come by. The shorter, simple sorting predicate should work as well. My test has confirmed this (Although I have not try all possible combinations).

Answer 1

Why don't you use std::set in the first place? Its contents are guaranteed to be unique.

Sidenotes:
You don't need to typedef structs in C++, just struct Rect {}; is sufficient.
Your comparison function should take its parameters by const-reference (i.e. const Rect&) as it doesn't need to modify them and doesn't need copies.

Answer 2

You also have to define a comparison function that should be used by sort() to sort the Rects. This comparison function should implement a strict weak ordering so that equal elements end up next to each other in the vector.

If the vector is not sorted, unique() will not find the unsorted duplicate elements.

Answer 3

sort(lala.begin(), lala.end());

How would std::sort know how to sort your Rects? properly? Define a comparison function and pass it as third parameter, as you did for std::unique. It must take two Rects as parameters and returns true if the first is < the second.

For example:

bool CompareRect(const Rect& first, const Rect& second) {
    return first.id<second.id;
}

Note that I'm passing the Rect's as const references, you seem to have forgotten this in your sample.

Answer 4

This is what I come up with:

I added a predicate to the sorting function:

bool SortRect(const Rect &first, const Rect &second)
{
    if (first.x < second.x) return true;
    if (first.x > second.x) return false;

    if (first.y < second.y) return true;
    if (first.y > second.y) return false;

    if (first.maxX < second.maxX) return true;
    if (first.maxX > second.maxX) return false;

    if (first.maxY < second.maxY) return true;
    if (first.maxY > second.maxY) return false;

    if (first.width < second.width) return true;
    if (first.width > second.width) return false;

    if (first.height < second.height) return true;
    if (first.height > second.height) return false;

    if (first.id < second.id) return true;
    if (first.id > second.id) return false;

    return false;
}

But I found that it has the same effect as:

bool SortRect(const Rect &first, const Rect &second)
{
    return first.x < second.x;
}

So is it like sth said, I just need to sort only the first element (for the unique function to work properly)?

Answer 5

I'm not sure what you are trying to implement, but generally as it's been pointed, you need to design what's your comparison of your rectangles. What makes one rectangle ordered before another one in a sequence.

One of the simplest variant is to compare on the x-coordinate. More sophisticated option is to sort according to Hilbert value calculated for rectangle. See question Calculate the Hilbert value of a point for use in a Hilbert R-Tree?

Perhaps you're working on some sort of spatial index, then learn about R-tree