Russian Qt Forum

Добрый день

Есть такая структурка

C++ (Qt)
struct CMatrix {
 double m[16];
 
 bool operator == ( const CMatrix & sec ) const
 {
   for (size_t i = 0; i < 16; ++i)
    if (fabs(m[i] - sec.m[i]) > epsilon) 
     return false;
 
  return true;
 }
};

Как теперь определить оператор < для использования напр в std::map ?

Спасибо

А как он должен действовать? Может суммы сравнивать?
тогда примерно так:

Оператор < для для использования в std::map никак не связан с оператором ==, поэтому можно как угодно определить, удовлетворяя StrictWeakOrdering (http://www.sgi.com/tech/stl/StrictWeakOrdering.html). Например, сравнивая лексикографически.

А если же вдруг появится дополнительное требование, чтобы отношение эквивалентности из оператора <, определяемое как !(x < y) && !(y < x), совпадало с отношением, определяемым оператором ==, то это невозможно, т.к. приведенный выше оператор == не транзитивный, а StrictWeakOrdering требует транзитивности.

по-моему это абсолютно естественный вариант

Мне хотелось бы побыть в роли незнающего, которому вумные люди покажут "как правильно" - а Вы сразу встречный вопрос(ы), типа творческая дискуссия - я на это не подписывался  :)

Я понял все что Вы сказали - ну а делать-то что?  :)  Кстати мое первое впечатление было подобным - недостижимо именно из-за требований транзитивности

Но не дающий разумных результатов

только вот матрицы, для которых operator==() будет возвращать труъ, будут добавляться по нескольку раз...

Совершенно верно, матрицы могут быть реально равны/идентичны но из-за неизбежной погрешности double "точное" сравнение вернет false

[/offtop]
У меня одного впечатление что форум как-то приуныл, много дней "нiчого цiкавого"?
Well, "Good Times Bad Times"  :)

Использовать другие структуры данных, т.к. std::map здесь явно не подходит.

может через std::unordered_map сделать?
hash примерно такая будет:

Вариант, но дороговато выходит (напр свое дерево), "при прочих равных условиях" std предпочтительнее (как справедливо рекомендует наш модератор). Нет ли ходов попрактичнее?

В std нет контейнеров для spatial indexing, поэтому или самому реализовывать или брать какие-то готовые реализации.

Не будет корректно работать, т.к. найдутся два элемента a==b, для которых будут разные значения функции hash.

Уже сам факт того, что Вас совершенно не смущает (или судя по постановки вопроса, для Вас это совершенно естественно) определять для такой структуры как матрица (похоже матрица 4x4) оператор <, вызывает как минимум сомнения в адекватности подхода к проблеме..
Может стоит отмотать несколько шагов назад и задаться вопросом что привело к такой безапелляционной мысли писать этот совершенно не свойственной для матриц оператор?

И потом, для матриц нет однозначного оператора < ... Их можно придумать бесконечное множество реализаций (в зависимости от Вашего настроения или положения звёзд и т.д.)...
А теперь подумайте о том, кто будет использовать Ваш код..

В общем это очень, подчёркиваю, очень плохая идея(
    

Реализация оператора это уже последствия, мне интересней для чего может понадобиться использовать матрицы в качестве ключа коллекции?
Что-то мне подсказывает, что лучше изменить архитектуру, что бы не приходилось так делать.

Да отчего же "несвойственной", друг мой? Напр я получаю кучу трансфомеров в виде матриц по каждому полигону - неужели это неестественно проверить и сохранить только уникальные их них? 

Ага, а вот и "тип из второго батальона", рад его видеть  :) Ну ладно m_ax - молодой, увлекается "синтаксическим сахаром", это пройдет. Но Вы-то - человек с немалым опытом - как насчет упереться рогом и подумать - или четко доказать что это невозможно. А то сразу в кусты, мол, меняем архитектуру  :)

Для меня, так же как и для m_ax, не понятен смысл оператора < для матриц, точек, цветов, виджетов и других подобных структур. :)
Что я тут могу подтверждать и опровергать?
И правда, очень интересно, для чего может понадобиться использовать матрицы в качестве ключей коллекций. Что используется в качестве значения? Расскажите без стеснений. :)

Вот я, собственно, о том же.. Мне не понятна такая категоричная исходная позиция "как реализовать оператор <". Почему всё, что привело к этой точке не может подлежать сомнению? Диктаторство какое то, ей богу)

 

Хорошо, тогда, чтоб направить обсуждение в "конструктивное русло" может стоить внести некую предысторию, которая бы воссоздавала корень самой проблемы?  

нет... для любых матриц a==b сиё должно выдавать одинаковый хеш... возможно надо будет ещё epc округлить в большую сторону до следующего двоичного разряда ...
дык kamre уже объяснил, что это не возможно и почему...

Есть N полигонных объектов каждый из которых может иметь до 8 текстур. Каждая текстура имеет матрицу. Если у каких-то объектов все текстуры равны (с заданной точностью) то они используют/шарят одни и те же данные (UV координаты), иначе разные. Как видите, дело совершенно рядовое.

Функция round разрывная, поэтому всегда можно найти два элемента a==b, для которых будет разное значение. Просто сами представьте: все пространство разбивается на области с одинаковыми значениями hash функции, всегда есть граница между областями, можно взять сколь угодно близкие элементы находящиеся по разные стороны от границы.

да... правда...

Однако же - "углубление в корень/первоосновы" никакого прогресса пока не принесло  :)

И это всем понятно? Или не очень - но лучше промолчать? :)  Почему напр не просто так

C++ (Qt)
bool CMatrix::operator < ( const CMatrix & sec ) const
{
 for (size_t i = 0; i < 16; ++i) {
  double delta = m[i] - sec.m[i];
  if (delta < -epsilon) return true;
  if (delta > epsilon) return false;
 }
 
 return false;
}

2kamre А Вас, Штирлиц, я попрошу пока воздержаться  :)

Только отсюда не следует, что для реализации этого, необходимо обязательно использовать map. ;)
Если отказаться от него, то хватит операторов равенства/не равенства.

На крайний случай можно написать свой специфичный  предикат и передать его map.
В смысле примерно так:

C++ (Qt)
struct unusual_pred {
    bool operator()(const CMatrix & m1, const CMatrix &m2) const {
        for (size_t i = 0; i < 16; ++i) {
            double delta = m1[i] - m2[i];
            if (delta < -epsilon) return true;
            if (delta > epsilon) return false;
        }
     return false;
    }
};
 
...
 
std::map<CMatrix, Data, unusual_pred> my_strange_map;
 

Но писать в самом CMatrix этот оператор< идея бредовая.
 

Ну использование прямого перебора, мягко говоря, не украшает программиста - этим он расписывается в своей беспомощности.

А почему оператор < для структуры кажется Вам бредовым? Ну есть какое-то отношение упорядочивания. Если их много - может и лучше подсовывать той или иной функтор, а если 1 и др не видно - так чего в структуре не объявить? Впрочем это дело вкуса. Главное - а корректен ли предложенный оператор/функтор?

Да? Не знал. :)
Т.е. придумать невозможный оператор для структуры, что бы ее можно было использовать  в map для вас показатель класса? :)

Да как уже неоднократно говорили: введение такого оператора нарушает свойства транзитивности для объектов матриц. Этого одного факта уже вполне достаточно чтоб хотя бы призадуматься (а может есть решение более логичное)..

Я на map не настаиваю - предлагайте др решения, только без "пускания пузырей" с прямым перебором  :)

А что это за свойства такие? И как мы их нарушаем? Можно объяснить попроще, а то у Вас все так "официально"  :)

Да очень просто: У Вас нет никаких гарантий что если a < b и b < c, то и a < c.
И как следствие, если у Вас, например, имеется некая последовательность: a1, a2, a3, a4, .. an, то отсортированная последовательность (с помощью этого оператора<) будет зависеть от исходной. Это плохо, я бы сказал - это костыль..

Во-вторых это плохо ещё и от того, что у Вас реализация класса CMatrix начинает обрастать зависимостями от способа реализации каких то частных задач.. Такие зависимости - это практически всегда следствие корявой архитектуры..

Ну и в-третьих: Вы уверены, что Вас правильно поймут те, кто, возможно будет в будущем работать с Вашим кодом?
   

про то, что транзитивность ( a<b & b<c => a<c ) не выполняется уже сказали.
с такой штукой std::map просто будет не корректно работать... в частности может добавлять одинаковые элементы или не находить уже имеющиеся. может будут и другие глюки при повороте дерева например...

одним словом тут точно придётся воять какой-то особый контейнет... есть одна идея, правда, быть может, бредовая, основанная на том, что для скалярного double аналогичный отношение с epsilon будет задавать строгий порядок... потом, может быть, расскажу, когда и если оно более детально обрисуется в голове...

Да как-то сказали - повторили написанное  :) Лучше на живом примере. Пусть epsilon = 1 и матрицы отличаются только первыми 2-мя числами. Имеем 2 ключа

(0.9, 10) (0.1, 30)

Поскольку разница по первому ключу < epsilon, используем второй. Теперь появляется 3-й ключ, напр

(1.5, 20)

Выясняется что как бы мы не крутили, расставить ключи по возрастанию (a < b < c), не удается. Мапа не будет работать правильно, а для некоторых реализаций имеет право даже рухнуть. Это популярная ошибка, поэтому лучше разжевать. 

Простое и хорошее решение было предложено в первом же ответе, оформим

C++ (Qt)
typedef std::map <double, CMatrix> TMap;
 
const CMatrix * Lookup( TMap & theMap, const CMatrix & m )
{
 double key = m.Sum();  // сумма всех 16 значений
 
 TMap::iterator it = theMap.lower_bound(key - epsilon * 16);
 if (it == theMap.end()) 
  it = theMap.begin();
 
 while (it != theMap.end()) {
  if (it.first > key + epsilon * 16) break;
  if (m == it->second) return &it->second;
 }  
 return &theMap.insert(std::make_pair(key, m)).first->second;
}
 

Писал прямо здесь, возможны погрешности. Критикуем, опровергаем  :)

Тогда уж в качестве ключа лучше брать Sp (шпур) (он же Tr (трэйс), он же след), поскольку он инвариантен по отношению к вращениям..
Да и считается быстрей)
 

Не подойдет?
Естественно, что никакого "физического" или "математического" смысла в этом операторе нет.

Гениальный!!! ответ.  Без сарказма.

Конечно этот оператор будет работать корректно, но полученный отсортированный контейнер (напр std::map) оказывается бесполезным - ведь "близкие" элементы (для которых == вернет true) окажутся где угодно, а совсем не рядом друг с другом. А задача добавлять в мапу только те матрицы для которых нет близких имеющихся

Забацайте там 20% погрешности.

:) Что-то у Вас с фундаментальными вещами совсем неважно

Умейте отличать сарказм от серьёзных ответов. :)

У Вас ни то ни другое, так, скажу что-нибудь, авось попаду в тему :)

Спасибо за лестные слова. Я их ждал.

Ну тогда, я считаю, что operator== следует модифицировать следующим образом

Это опять-таки "нетранзитивно" - найдутся такие 3 ключа которые невозможно выстроить в порядке a < b < c