Использование уникального по STL вектора со структурой - PullRequest
Новая
       25

Использование уникального по STL вектора со структурой

2 голосов
/ 24 января 2010

В задаче программирования я стараюсь обеспечить, чтобы определенный вектор содержал только уникальные элементы. С примитивными типами операция так же проста, как: 

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

Однако проблема в том, что я не использую int. Но: 

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

На самом деле не работает. Что я сделал не так?

EDIT:

По совету sth я реализовал два предиката сортировки для 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;
}

Но я обнаружил, что он имеет такой же эффект, как: 

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

если документация SGI может быть найдена. Более короткий и простой предикат сортировки также должен работать. Мой тест подтвердил это (хотя я не пробовал все возможные комбинации).

Ответы [ 5 ]

5 голосов
/ 24 января 2010

Вы также должны определить функцию сравнения, которая должна использоваться sort() для сортировки Rects. Эта функция сравнения должна реализовывать строгий слабый порядок , чтобы равные элементы оказывались рядом друг с другом в векторе.

Если вектор не отсортирован, unique() не найдет несортированные повторяющиеся элементы.

4 голосов
/ 24 января 2010

Почему бы вам не использовать std::set в первую очередь? Его содержимое гарантированно будет уникальным.

Sidenotes:
Вам не нужно typedef структур в C ++, достаточно просто struct Rect {};.
Ваша функция сравнения должна принимать свои параметры по const-reference (то есть const Rect&), поскольку ей не нужно изменять их и не нужно копировать.

1 голос
/ 24 января 2010

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

Как бы std::sort узнал, как отсортировать ваши Rect с? должным образом? Определите функцию сравнения и передайте ее в качестве третьего параметра, как вы это делали для std::unique. Он должен принимать два Rect s в качестве параметров и возвращает true, если первое <второе. </p>

Например: 

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

Обратите внимание, что я передаю Rect как константные ссылки, вы, кажется, забыли об этом в своем примере.

0 голосов
/ 24 января 2010

Я не уверен, что вы пытаетесь реализовать, но в целом, как было указано, вам нужно спроектировать, как вы сравниваете свои прямоугольники. Что делает один прямоугольник упорядоченным перед другим в последовательности.

Одним из самых простых вариантов является сравнение по x-координате. Более сложным вариантом является сортировка в соответствии со значением Гильберта, рассчитанным для прямоугольника. См. Вопрос Рассчитать значение Гильберта точки для использования в R-дереве Гильберта?

Возможно, вы работаете с каким-то пространственным индексом, а затем изучите R-дерево

0 голосов
/ 24 января 2010

Вот что я придумала:

Я добавил предикат в функцию сортировки: 

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;
}

Но я обнаружил, что он имеет такой же эффект, как: 

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

Итак, как сказал sth, мне просто нужно отсортировать только первый элемент (чтобы уникальная функция работала правильно)?

...