Если я передам пользовательский IComparer экземпляру метода Sort() списка, будет ли когда-либо вызываться метод компаратора Compare(x,y) с одним и тем же элементом?
т.е. Возможно ли, что Compare(x,x) может быть вызван.
Изменить: больше интересует случай, когда элементы списка различны.
Я написал тестовую программу, чтобы проверить это. Похоже, что на самом деле выполняет Compare() один и тот же элемент с самим собой (по крайней мере, Compare() вызывается для одного и того же элемента дважды). В этой программе Compare() вызывается с аргументами (2, 2).
using System;
using System.Collections.Generic;
static class Program
{
class MyComparer : Comparer<int>
{
public override int Compare(int x, int y)
{
Console.WriteLine("Compare(" + x + ", " + y + ")");
if (x < y) return -1;
if (x > y) return 1;
return 0;
}
}
static void Main()
{
MyComparer comparer = new MyComparer();
List<int> list = new List<int> { 1, 2, 3 };
list.Sort(comparer);
return;
}
}
И вывод:
Compare(1, 2)
Compare(1, 3)
Compare(2, 3)
Compare(1, 2)
Compare(2, 2)
Compare(2, 3)
Compare(2, 2)
using и оператор WriteLine, чтобы людям было проще попробовать самостоятельно.)
- person Thomas; 11.09.2011
Compare(1, 2) Compare(1, 3) Compare(2, 3) Эффективный.
- person Jeppe Stig Nielsen; 29.08.2017
Из документов:
Этот метод использует Array.Sort, который использует алгоритм QuickSort.
Быстрая сортировка никогда не сравнивает элемент сам с собой. Некоторые реализации быстрой сортировки сравнивают элементы сами с собой. Это также может произойти, если этот элемент встречается в вашем списке более одного раза.
В любом случае, для того, чтобы ваша функция сравнения была правильной, корректной функцией сравнения, вам необходимо обработать случай, когда элементы сравниваются сами с собой.
Другой ответ, основанный на части XML ECMA-335, спецификация BCL (библиотека базовых классов). Хотя это не гарантирует связи с тем, что делают фактические реализации, это настолько авторитетно, насколько это возможно. И спецификация не говорит ничего, кроме:
В худшем случае эта операция выполняется за O(n^2), где n — количество элементов для сортировки. В среднем это O (n log n).
Хотя это наводит на мысль о QuickSort, это абсолютно не гарантирует. Спецификация также не требует реализации с точки зрения Array.Sort.
Итог: что касается спецификации, для реализации совершенно нормально сравнивать элементы с самими собой.
Хотя это не является строго гарантированным, я почти уверен, что метод List Sort никогда не вызовет ваш метод сравнения для сравнения объекта с самим собой, если только этот объект не появится в списке несколько раз. Я основываю этот вывод на том, что List.Sort реализован с использованием алгоритма QuickSort (согласно MSDN), который никогда не сравнивает обычно не предполагает сравнения одного и того же элемента с самим собой (и ни один из других задокументированных алгоритмов сортировки, о которых я могу думать). (Редактировать: кажется, что реализация Microsoft действительно сравнивает элемент с самим собой. См. Принятый ответ выше.)
Однако в соответствии с хорошей практикой кодирования ваша реализация IComparer должна иметь возможность обрабатывать передачу одного и того же объекта в обоих параметрах, поскольку в противном случае ваша реализация не выполняет контракт, определенный IComparer. Это, вероятно, сработает для вашего сценария, но вы будете полагаться на детали реализации метода сортировки (которые могут измениться в будущем), и вы не сможете использовать свою реализацию IComparer в других сценариях, где такого нет. гарантия (или, что еще хуже, вы или кто-то другой ДЕЙСТВИТЕЛЬНО используете его и, возможно, создает трудно обнаруживаемую ошибку).
