TStringList. Неустойчивость сортировки

Delphi , Компоненты и Классы , Списки

Автор: Илья Илларионов

Метод Sort класса TStringList является НЕУСТОЙЧИВЫМ. Это критично при работе со свойством Objects. Например, при использовании в качестве строкового индекса для добавляемых объектов. После вызова Sort объекты с одинаковым именем в списке располагаются в порядке, обратном тому, в котором были добавлены.

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

КОММЕНТАРИЙ

Этот камень перенесен из категории БИБЛИОТЕКА.

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

Метод Sort класса TStringList является неустойчивым и может привести к неправильному порядку объектов с одинаковыми значениями свойства Objects после вызова этого метода.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Списки ::