2

Кто-нибудь может объяснить, почему фейлится assert в конце TestSortedSet()?

using System.Collections.Generic;
using System.Diagnostics;

public static class Test
{
    private sealed class FooComparer : IComparer<Foo>
    {
        public int Compare(Foo x, Foo y)
        {
            if (x.Id > y.Id)
            {
                return 1;
            }
            if (x.Id < y.Id)
            {
                return -1;
            }
            if (x != y)
            {
                return 1;
            }
            return 0;
        }
    }

    private class Foo
    {
        public int Id;
    }

    public static void TestSortedSet()
    {
        var comparer = new FooComparer();
        var set = new SortedSet<Foo>(comparer);

        set.Add(new Foo {Id = 1});
        set.Add(new Foo {Id = 1});
        set.Add(new Foo {Id = 1});

        set.RemoveWhere(obj => obj.Id == 1);

        Debug.Assert(set.Count == 0);
    }
}

P.S.: Компаратор кривой, да. Но ответа на вопрос это не дает.

1
  • +1 за SSCCE.
    – VladD
    Commented 11 февр. 2013 в 18:35

2 ответа 2

3

Проблема, очевидно, в этом коде:

if (x != y)
{
    return 1;
}

Дело в том, что компаратор обязан быть антисиметричным. (То есть если Compare(x, y) == 1, то обязательно Compare(y, x) == -1.) Ваш компаратор не антисиметричен. Вы нарушили контракт, поведение непредсказуемо.

Уберите проблемный код, должно работать. Или скажите, для чего он нужен, попробуем решить проблему по-другому.


Давайте разберёмся, как работает RemoveWhere. Если верить декомпиляции с ILSpy (.NET 4.0), код такой:

public int RemoveWhere(Predicate<T> match)
{
    if (match == null)
        throw new ArgumentNullException("match");
    List<T> matches = new List<T>(this.Count);
    // получаем список всех элементовпроходящих через предикат
    BreadthFirstTreeWalk(delegate(SortedSet<T>.Node n)
        {
            if (match(n.Item)) { matches.Add(n.Item); }
            return true;
        });
    int num = 0;
    for (int i = matches.Count - 1; i >= 0; i--)
    {
        if (Remove(matches[i])) num++;
    }
    return num;
}

Тут вроде ничего подозрительного.

Функция BreadthFirstTreeWalk для TreeWalkPredicate, возвращающего только true, обходит всё дерево:

internal virtual bool BreadthFirstTreeWalk(TreeWalkPredicate<T> action)
{
    if (this.root == null) return true;
    List<SortedSet<T>.Node> list = new List<SortedSet<T>.Node>();
    list.Add(this.root);
    while (list.Count != 0)
    {
        SortedSet<T>.Node node = list[0];
        list.RemoveAt(0);
        if (!action(node)) // тут у нас всегда true
            return false;
        if (node.Left != null) list.Add(node.Left);
        if (node.Right != null) list.Add(node.Right);
    }
    return true;
}

Так мы должны получить список всех элементов, если, конечно, добавление в дерево не зафейлилось из-за компаратора. Так что проблема должна быть в функции Remove. (Ну или Add.)

Код функции DoRemove (к которой сводится функция Remove) слишком большой, положил тут: http://pastebin.com/MQ87EtQv. Интересен вот этот фрагмент:

int num = flag ? -1 : this.comparer.Compare(item, node.Item);
if (num == 0)
{
    flag = true;
    node4 = node;
    parentOfMatch = node2;
}
node3 = node2;
node2 = node;
if (num < 0)
    node = node.Left;
else
    node = node.Right;

Здесь видно, что результат сравнения управляет тем, куда пойдёт алгоритм искать дальше узел, если он не совпадает с node. В нашем случае будет всегда num > 0, поэтому алгоритм всегда пойдёт вправо, несмотря на то, что искомый узел может находится и слева.

6
  • Понятно, что обязан. Но это не объясняет того, что удаляется ровно N/2 из N удовлетворяющих предикату объектов. Commented 11 февр. 2013 в 18:20
  • 2
    @Flammable: если контракт нарушен, поведение имеет право быть любым. Такое оно сейчас из-за конкретной реализации внутренних методов, это не должно быть нам интересным. В C++ вон вообще программа с undefined behaviour имеет право отформатировать винчестер и застрелить вашего кота.
    – VladD
    Commented 11 февр. 2013 в 18:21
  • @Flammable: по поводу данного поведения, может, алгоритм ищет позицию, начиная с которой удалять, двоичным поиском, начиная с середины. Если завтра выйдет сервис-пак, в котором проверка if (comparator.Compare(x, middle) < 0) поменяется на if (comparator.Compare(middle, х) > 0), будет работать по-другому.
    – VladD
    Commented 11 февр. 2013 в 18:26
  • Это интересные особенности красно-черного дерева (на его основе реализован SortedSet) при сравнении нодов кривым компаратором. Хотя, честно говоря, я не понял до конца, как именно такое происходит. Commented 11 февр. 2013 в 19:05
  • @Flammable: ну как, получилось? Проблема, наверное, была нетривиальная.
    – VladD
    Commented 20 февр. 2013 в 18:00
0

Потому что

if (x != y)
{
    return 1;
}

здесь не в кассу

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.