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

Question

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

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

Вы можете использовать хеш, в котором членами являются ключи, которые отображаются на «1» или «true», но в большинстве языков существуют ограничения на типы данных, которыми может быть хеш-ключ.

Какой стандартный способ сделать это на современных языках (PHP, Perl, Ruby, Python и т. Д.)?

Answer 1

Большинство современных языков будут иметь некоторую форму структуры данных Set. Java имеет HashSet , который реализует интерфейс Set .

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

Answer 2

C # имеет общую коллекцию HashSet .

public class EmailAddress  // probably needs to override GetHashCode()
{
   ...
}

var addresses = new HashSet<EmailAddress>();

Answer 3

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

Answer 4

В Perl я бы определенно использовал хеш. На других языках я бы посетовал на отсутствие хеша.

Answer 5

и Array - это обычно самый простой способ хранения данных без каких-либо других требований. Обычно другие типы данных используются по разным причинам (вы хотите добавить данные, вы хотите искать данные в постоянном времени, вам нужно быстро установить соединение / пересечение и т. Д.) Если вас беспокоит только абстракция, вы можете обернуть ее в какой-то вид неупорядоченный фасад.

Answer 6

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

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

Это действительно зависит от того, как вы хотите получить доступ и использовать данные.

Answer 7

В качестве замены для непосредственного понимания машины:

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

Написание функций для реализации добавления и удаления элементов, тестирования на наличие или отсутствие, тестирования на подмножества и т. Д. По мере необходимости.

---

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