[devel] [JT] std::sort

Alex V. Myltsev =?iso-8859-1?q?avm_=CE=C1_altlinux=2Eru?=
Вс Дек 17 20:54:19 MSK 2006


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 лучше.



Подробная информация о списке рассылки Devel