Re: [devel] [JT] std::sort

["Alex V. Myltsev" <avm@altlinux.ru>]

On Sun, 17 Dec 2006 20:15:15 +0300
Alexey Tourbin wrote:
> Что такое "strict weak ordering" по-русски?
Не знаю.
> Антирефлексивное неполное отношение порядка? То есть некоторые
> элементы несравнимы и неравны, а те которые сравнимы обязательно
> неравны.
Этого мало. Это у вас вроде строгий частичный порядок получается, но он
допускает такую ситуацию: a<b<c<e, a<d<e, пары (b,d) и (c,d) несравнимы.
То есть несравнимость может быть нетранзитивной, а это плохо: например,
подают нам на вход последовательность {a,c,d,b,e}; она неупорядочена, а
сравнением соседних элементов мы этого обнаружить не можем. И
сортировка вся идёт лесом.

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

> Да я Страуса листал а у него книжка толстая и наполовину бестолковая.
Google лучше.