Сохранение пары индексов в списке

Как я могу хранить пары целых чисел в списке? Я знаю, что могу сделать для них класс, например:

class Pair  
{
    int i1,i2;
}

Но если я это сделаю, я не смогу использовать функцию Contains, чтобы проверить, указана ли данная пара в списке. Как я могу это сделать, чтобы я мог легко хранить целые числа в списке и проверить, существует ли пара целых чисел? Я не могу использовать таблицу, потому что неизвестно, сколько пар будет.

EDIT:
Забыл добавить: В моей программе пары (x, y) и (y, x) должны рассматриваться как равные.

EDIT:
(x, y) и (y, x) равны, проверяя, есть ли Point в списке, но x и y не могут быть заменены, поскольку x и y представляют собой связь между двумя точками (целое число равно id, и я не могу использовать ссылку и т.д.). Когда я проверяю, содержит ли List соединение, это не важно, если это (x, y) или (y, x), но позже мне понадобится эта информация.

Ответ 1

Если вы используете .NET 4.0, вы можете использовать класс Tuple, как в

var tuple = new Tuple<int, int>(17, 42);
var otherTuple = Tuple.Create(17, 42);

и

var list = new List<Tuple<int, int>>();

Обратите внимание, что если вы пройдете маршрут использования Tuple<int, int>, вам нужно будет создать пользовательскую реализацию IEqualityComparer<Tuple<TFirst, TSecond>>, чтобы отразить ваши правила равенства, которые (x, y) считаются равными (y, x). Затем вам нужно передать экземпляр этого компаратора в List<T>.Contains(T, IEqualityComparer<T>) (здесь T есть Tuple<int, int> для вас).

class TupleAsUnorderedPairComparer : IEqualityComparer<Tuple<TFirst, TSecond>> {
    public bool Equals(Tuple<TFirst, TSecond> x, Tuple<TFirst, TSecond> y) {
        if(Object.ReferenceEquals(x, y)) {
            return true;
        }
        if(x == null || y == null) {
            return false;
        }
        return x.Item1 == y.Item1 && x.Item2 == y.Item2 ||
               x.Item1 == y.Item2 && x.Item2 == y.Item1;
    }

    public int GetHashCode(Tuple<TFirst, TSecond> x) {
        if(x == null) {
            return 0;
        }
        return x.Item1.GetHashCode() ^ x.Item2.GetHashCode();
    }
}

В противном случае, если вы не можете или не хотите использовать Tuple, вам нужно будет реализовать IEqualityComparer<Pair> для вашего класса Pair или переопределить Object.Equals и Object.GetHashCode.

class Pair {
    public int First { get; private set; }
    public int Second { get; private set; }
    public Pair(int first, int second) {
        this.First = first;
        this.Second = second;
    }

    public override bool Equals(object obj) {
        if(Object.ReferenceEquals(this, obj)) {
            return true;
        }
        Pair instance = obj as Pair;
        if(instance == null) {
            return false;
        }
        return this.First == instance.First && this.Second == instance.Second ||
               this.First == instance.Second && this.Second == instance.First;
    }

    public override int GetHashCode() {
        return this.First.GetHashCode() ^ this.Second.GetHashCode();
    }
}

и

class PairEqualityComparer : IEqualityComparer<Pair> {
    // details elided 
}

Если вы используете

list.Contains(pair);

то он будет использовать Equals и GetHashCode, но если вы используете

list.Contains(pair, new PairEqualityComparer);

то он будет использовать PairEqualityComparer.Equals и PairEqualityComparer.GetHashCode. Обратите внимание, что они могут отличаться от ваших реализаций Object.Equals и Object.GetHashCode.

Наконец, если тестирование для сдерживания - это то, что вы часто будете делать, то List не лучший выбор; вы должны использовать класс, предназначенный для этой цели, например, HashSet.

Ответ 2

Класс - ваш лучший выбор. Если вы устарели, используя метод Contains, вам нужно реализовать интерфейс IComparable в вашем классе Pair. Это позволит вам установить, что означает "равенство" для этой пары целых чисел.

Самый простой способ - создать класс, как есть, а затем создать и расширить метод для объекта List<T>.

public static bool ContainsIntegers(this List<Pair> targetList, Pair comparer) {
    foreach(Pair pair in targetList)
    {
        if(pair.i1 == comparer.i1 && pair.i2 == comparer.i2) return true;
    }
    return false;
}

Ответ 3

Другой способ сделать это - использовать List<ulong>, заполнив его, поставив наибольшее число в верхние 32 бита, а другое число в младших 32 битах:

ulong MakeEntry(int i1, int i2)
{
    ulong hi = (ulong)Math.Max(i1, i2);
    ulong lo = (ulong)Math.Min(i1, i2);
    return (hi << 32) | lo;
}

List<ulong> items = new List<ulong>();

void DoSomething()
{
    // get numbers i1 and i2
    // and add to the list
    items.Add(MakeEntry(i1, i2));

    // test to see if the pair is in the list
    if (items.Contains(MakeEntry(i1, i2)))
    {
        // do whatever
    }
}