C# как избежать дубликатов в списке?

Question

Какой способ я мог использовать, чтобы избежать дублирования в списке?

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

Еще один способ, которым я мог бы использовать хэшсет, что если я попытаюсь добавить новый элемент, сам проверить, существует ли элемент, если нет, он добавит новый элемент, если он существует, а затем ничего не делать.

Но я знаю, что хешсет менее эффективен, нужно больше ресурсов, чем список, поэтому я не знаю, использовать ли хэшсет для избежания дубликатов, это хорошее использование хешета.

Есть ли другая альтернатива?

Спасибо.

Answer 1

List является структура данных, которая может содержать дубликаты. Их повторяющиеся элементы неоднозначны.

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

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

Другой способ, которым я могу использовать хэшетт, что если я попытаюсь добавить новый элемент, сам проверить, существует ли элемент, если нет, он добавит новый элемент, если он существует, а затем ничего не делать.

Это предпочтительный способ. Лучше всего использовать стандартную библиотеку для обеспечения требуемых ограничений.

Но я знаю, что хешсет менее эффективен, нужно больше ресурсов, чем список, поэтому я не знаю, использовать ли хешсет для избежания дубликатов, это хорошее использование хешета.

Эффективность зависит от того, что вы пытаетесь сделать; см. https://stackoverflow.com/a/23949528/1256041.

Есть ли другая альтернатива?

Вы можете осуществить собственный ISet используя List. Это сделает вставку намного медленнее (вам нужно будет перебирать всю коллекцию), но вы получите O(1) случайный доступ.

Answer 2

Вы можете достичь этого в одной строке кода: -

List<long> longs = new List<long> { 1, 2, 3, 4, 3, 2, 5 }; 

List<long> unique = longs.Distinct().ToList(); 

unique будет содержит только 1,2,3,4,5

Answer 3

Хешсет - лучший способ проверить, существует ли предмет, потому что это O (1).

Таким образом, вы можете вставить элементы как в список, так и в hashset , и перед тем, как вставить новый элемент, вы проверяете, существует ли он в hashset.

Answer 4

Вы не можете избежать повтора в List. Ни в коем случае - проверка предметов не производится.

Если вы не беспокоитесь о порядке вещей - используйте HashSet.

Если вы хотите сохранить порядок предметов (на самом деле есть небольшая двусмысленность - должен появиться элемент с индексом первого сложения или по индексу последнего добавления). Но вы хотите быть уверены, что все элементы уникальны, тогда вы должны написать свой собственный класс List. То есть то, который реализует интерфейс IList<T>:

public class ListWithoutDuplicates<T> : IList<T> 

И у вас есть различные варианты здесь. Например. вы должны решить, что для вас важнее - быстрое добавление или потребление памяти. Поскольку для быстрого добавления и содержит операцию, вы должны использовать некоторую структуру данных на основе хэша. Что неупорядочено. Вот пример реализации с HashSet для хранения хэшей всех элементов, хранящихся во внутреннем списке. Вам нужно будет следующие поля:

private readonly HashSet<int> hashes = new HashSet<int>(); 
private readonly List<T> items = new List<T>(); 
private static readonly Comparer<T> comparer = Comparer<T>.Default; 

Добавление элементов просто (предупреждение: не нулевые чеки здесь и далее) - не использовать элемент хэш-код для быстрого O (1) проверить, если он уже добавлен. Используйте тот же подход для удаления элементов:

public void Add(T item) 
{ 
    var hash = item.GetHashCode(); 
    if (hashes.Contains(hash)) 
     return; 

    hashes.Add(hash); 
    items.Add(item); 
} 

public bool Remove(T item) 
{ 
    var hash = item.GetHashCode(); 
    if (!hashes.Contains(hash)) 
     return false; 

    hashes.Remove(item.GetHashCode()); 
    return items.Remove(item); 
} 

Некоторые индексные на основе операций:

public int IndexOf(T item) 
{ 
    var hash = item.GetHashCode(); 
    if (!hashes.Contains(hash)) 
     return -1; 

    return items.IndexOf(item); 
} 

public void Insert(int index, T item) 
{ 
    var itemAtIndex = items[index]; 
    if (comparer.Compare(item, itemAtIndex) == 0) 
     return; 

    var hash = item.GetHashCode(); 

    if (!hashes.Contains(hash)) 
    { 
     hashes.Remove(itemAtIndex.GetHashCode()); 
     items[index] = item; 
     hashes.Add(hash); 
     return; 
    } 

    throw new ArgumentException("Cannot add duplicate item"); 
} 

public void RemoveAt(int index) 
{ 
    var item = items[index]; 
    hashes.Remove(item.GetHashCode()); 
    items.RemoveAt(index); 
} 

И доели:

public T this[int index] 
{ 
    get { return items[index]; } 
    set { Insert(index, value); } 
} 

public int Count => items.Count; 
public bool Contains(T item) => hashes.Contains(item.GetHashCode()); 
public IEnumerator<T> GetEnumerator() => items.GetEnumerator(); 
IEnumerator IEnumerable.GetEnumerator() => items.GetEnumerator(); 

Вот и все. Теперь у вас есть реализация списка, которая будет добавлять элемент только один раз (первый раз). Например.

var list = new ListWithoutDuplicates<int> { 1, 2, 1, 3, 5, 2, 5, 3, 4 }; 

Будет ли создать список с пунктами 1, 2, 3, 5, 4. Примечание: если потребление памяти является более важным, чем производительность, то вместо того, чтобы использовать хеши использовать items.Contains операцию, которая является О (п).

КСТАТИ Что мы только что сделали это на самом деле IList Decorator