Хранение пары целых в списке

Question

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

class Pair  
{
    int i1,i2;
}

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

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

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

Answer 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.

Answer 2

Другой способ сделать это - использовать 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
    }
}

Answer 3

Класс - ваша лучшая ставка.Если вы не можете использовать метод 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;
}