[РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка

[G-virus]

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

Суть проблемы: Нужно удалить дубликаты из QList<QVector3D>, решил делать так: копирую лист в множество, возвращаю множество как лист и готово, но вот компилятор со мной не согласен.

Код

C++ (Qt)
QList<QVector3D> Menu::calcNewVector3D(const QList<QVector3D> &list)
{
    return list.toSet().toList();
}
 

Попробовал исполнить подобный код для проверки, выскакивает такая же ошибка:

Код

C++ (Qt)
QVector3D vec; 
QSet<QVector3D> set;
set.insert(vec);
 

Подскажите, пожалуйста, где не прав.
Спасибо

[kambala]

#include <QSet> не забыл?

если размер списка большой, то такое преобразование может быть довольно дорогой операцией.

[G-virus]

#include <QSet> не забыл?
если размер списка большой, то такое преобразование может быть довольно дорогой операцией.

Заинклудить не забыл. Да, списки большие, около 30 000 элементов.

[Kurles]

Он для проверки на уникальные значения генерирует для каждого значения списка хеш с помощью функции uint qHash(...),а ее, принимающей QVector3D нет. Собственно если ее реализовать - то все заработает.

Код

C++ (Qt)
uint qHash(const QVector3D &val)
{
    qreal x = val.x();
    qreal y = val.y();
    qreal z = val.z();
    QString temp = QString("%0%1%2").arg(x, 0).arg(y).arg(x).arg(z);
    return ::qHash(temp);
}

[G-virus]

Спасибо большое, Kurles, все заработало

[Igors]

Конечно 30k точек - пионерский размер, пройдет все что угодно. Но все-таки ресурсы Вы разбазариваете по-черному, машину совсем не бережете 

[kostya2vntu]

Нормальное решение. Алгоритмическая сложность оптимальная - nlogn. Можно оптимизировать только константу, применив другое решение - отсортировав список и затем за один проход выбрав уникальные значения. Но выиграш на таких размерах данных будет незаметным. И то не факт что он будет.
И да, замечание - предложенная выше хеш функция просто отвратна, самое что ни есть разбазаривание ресурсов

[Bepec]

Щепановский - можешь только оценивать других? Видишь как сделать лучше - напиши. А не разводи тут фигню на постном масле

[DmitryM]

отсортировав список и затем за один проход выбрав уникальные значения.

У QVector3D нет оператора operator<, потому тебе придется придумать компаратор, что бы отсортировать.
Но если есть компаратор, то его можно передать std::set

[Igors]

Код

C++ (Qt)
QList<QVector3D> Menu::calcNewVector3D(const QList<QVector3D> &list)
{
    return list.toSet().toList();
}
 

Надо понимать что "просто так" (бесплатно) ничего не бывает. Выигрывая в простоте и легкости написания мы проигрываем в скорости и расходах памяти, часто во много раз. Человеку с небольшим опытом возможно покажется такой текст очень крутым (вот, одной строкой все сделал), но когда-то он будет удивлен узнав что, оказывается, возможно сделать в 5-10 раз быстрее. И будет не очень приятно осознать что "простая реализация" оказывается "лоховская реализация". Поэтому лучше к таким "уж очень удобным" ф-циям не привыкать. 

Использование QList (вместо QVector) в данном случае уже увеличивает расход памяти более чем в полтора раза. Создание нового контейнера и возврат его по значению также операция недешевая и никакой необходимостью не вызывается. Заметим что эти, довольно грубые, ляпы не вызывают никаких замечаний    Конвертация в QString для получения ключа - ну хоть это осуждается.

[kostya2vntu]

Щепановский - можешь только оценивать других? Видишь как сделать лучше - напиши. А не разводи тут фигню на постном масле

Код:

uint qHash(const QVector3D &val)
{
    qreal x = val.x();
    qreal y = val.y();
    qreal z = val.z();
    return ::qHash(uint(x)) ^ ::qHash(uint(y)) ^ ::qHash(uint(z));
}

Быстро, но далеко от идеала - будут проблемы с коллизиями для определенных наборов данных. В общем случае хеш от даблов сложно брать. Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.

[Igors]

Быстро, но далеко от идеала - будут проблемы с коллизиями для определенных наборов данных. В общем случае хеш от даблов сложно брать. Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.

Не вижу коллизий, все очень прилично. Но это "в теории". Автор темы сильно упростил себе жизнь, удаляя "совпадающие", а реально это такая задача: дан контейнер QPoint3D. Нужно:

- слить точки стоящие друг от друга на расстоянии меньше критического, которое принимается равным достаточно малому epsilon, часто 1.0e-5

- изменять исходный порядок точек не разрешается

Есть желающие блеснуть техникой? Верес, не надо говорить что Вы "не сильны в графике" (ее здесь нет). Покажите себя вместо того чтобы клевать новичков 

[Bepec]

Я очень не силён в графике ) И даже не представляю что это за контейнер и что себе представляет

Igors - думаете порог вхождения в ваши чертоги так низок?

[kostya2vntu]

Быстро, но далеко от идеала - будут проблемы с коллизиями для определенных наборов данных. В общем случае хеш от даблов сложно брать. Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.

Не вижу коллизий, все очень прилично.

Из-за приведения double к int, которое по сути сохраняет только целую часть значения отбрасывая дробную. Из-за этого, например, если у множества точек координаты будут в диапазоне [0,1) - хеш код их всех будет одинаковым, и хеш-таблица превратится в одну большую коллизию.

[Igors]

И даже не представляю что это за контейнер и что себе представляет

QVector <QPoint3D>

Igors - думаете порог вхождения в ваши чертоги так низок?

Да какие там чертоги? "Хижина дяди Тома". Работа с контейнерами и структурами данных, хотите в терминах Qt, хотите std. Никто не подавляет, не тыкает в нос Вындоуз хуками, прОтокалами и прочей лабудой. Так, небольшой кроссворд/пузл после трудового дня.

Из-за приведения double к int, которое по сути сохраняет только целую часть значения отбрасывая дробную. Из-за этого, например, если у множества точек координаты будут в диапазоне [0,1) - хеш код их всех будет одинаковым, и хеш-таблица превратится в одну большую коллизию.

Не думаю что мантиссы так интенсивно совпадут - файл в котором записаны флоты практически не сжимается. А еще лучше так

Код

C++ (Qt)
uint qHash(const QVector3D &val)
{
    float f[3] = { val.x(), val.y(), val.z() };
    uint32 * dummy = (uint32 *) f;
    return dummy[0] ^ dummy[1] ^ dummy[2];
}