Spec-Zone.ru › Nim 1

множества

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

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

Общие способы использования множеств:

  • удаление дубликатов из контейнера путем преобразования его с помощью процедурой toHashSet (см. также процедуру sequtils.deduplicate)
  • проверка принадлежности
  • математические операции над двумя множествами, такие как объединение, пересечение, разность и симметричная разность 
echo toHashSet([9, 5, 1])     # {9, 1, 5}
echo toOrderedSet([9, 5, 1])  # {9, 5, 1}

let
  s1 = toHashSet([9, 5, 1])
  s2 = toHashSet([3, 5, 7])

echo s1 + s2    # {9, 1, 3, 5, 7}
echo s1 - s2    # {1, 9}
echo s1 * s2    # {5}
echo s1 -+- s2  # {9, 1, 3, 7}

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

См. также:

  • модуль intsets для эффективных множеств целых чисел
  • модуль tables для хэш-таблиц

Импорты

hashes, math

Типы

HashSet[A] {...}{..} = object
  data: KeyValuePairSeq[A]
  counter: int

Универсальное множество хэш.

Используйте процедуру init или процедуру initHashSet перед вызовом других процедур.

Исходный код Редактировать 
OrderedSet[A] {...}{..} = object
  data: OrderedKeyValuePairSeq[A]
  counter, first, last: int

Универсальное множество хэш, которое запоминает порядок вставки.

Используйте процедуру init или процедуру initOrderedSet перед вызовом других процедур.

Исходный код Редактировать 
SomeSet[A] = HashSet[A] | OrderedSet[A]
Объединение типов, представляющее HashSet или OrderedSet. Исходный код Редактировать

Константы

defaultInitialSize = 64
Исходный код Редактировать

Процедуры

proc rightSize(count: Natural): int {...}{.inline,
                                      deprecated: "Deprecated since 1.4.0",
                                      raises: [], tags: [].}
Устаревший: Устаревший начиная с версии 1.4.0

Устаревший начиная с Nim v1.4.0, больше не нужен, так как выбор правильного размера выполняется внутри.

Возвращает значение initialSize для поддержки элементов count.

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

Исходный код Изменить 
proc init[A](s: var HashSet[A]; initialSize = defaultInitialSize)

Инициализирует множество хеш.

Начиная с Nim v0.20, множества инициализируются по умолчанию, и вызов этой функции явно не нужен.

Вы можете вызвать эту процедуру для ранее инициализированного множества хеш, которое отбросит все его значения. Это может быть удобнее, чем итерация по существующим значениям и вызов excl() для них.

См. также:

  • процедура initHashSet
  • процедура toHashSet

Пример:

var a: HashSet[int]
init(a)
Исходный код Изменить 
proc initHashSet[A](initialSize = defaultInitialSize): HashSet[A]

Обёртка над процедурой init для инициализации множеств хеш.

Возвращает пустое множество хеш, которое можно напрямую присвоить в блоках var в одной строке.

Начиная с Nim v0.20, множества инициализируются по умолчанию, и вызов этой функции явно не нужен.

См. также:

  • процедура toHashSet

Пример:

var a = initHashSet[int]()
a.incl(3)
assert len(a) == 1
Исходный код Изменить 
proc `[]`[A](s: var HashSet[A]; key: A): var A

Возвращает элемент, который фактически хранится в s, имеющий такое же значение, как key, или возбуждает исключение KeyError.

Это полезно, когда перегружены hash и ==, но всё ещё требуется семантика ссылок для совместного использования.

Исходный код Изменить 
proc contains[A](s: HashSet[A]; key: A): bool

Возвращает true, если key содержится в s.

Это позволяет использовать оператор in.

См. также:

  • процедура incl
  • процедура containsOrIncl

Пример:

var values = initHashSet[int]()
assert(not values.contains(2))
assert 2 notin values

values.incl(2)
assert values.contains(2)
assert 2 in values
Исходный код Изменить 
proc incl[A](s: var HashSet[A]; key: A)

Включает элемент key в s.

Не выполняет никаких действий, если key уже содержится в s.

См. также:

  • процедура excl для исключения элемента
  • процедура incl для включения другого множества
  • процедура containsOrIncl

Пример:

var values = initHashSet[int]()
values.incl(2)
values.incl(2)
assert values.len == 1
Исходный код Изменить 
proc incl[A](s: var HashSet[A]; other: HashSet[A])

Включает все элементы из множества other в множество s (должно быть объявлено как var).

Это версия в месте s + other.

См. также:

  • процедура excl для исключения другого множества
  • процедура incl для включения элемента
  • процедура containsOrIncl

Пример:

var
  values = toHashSet([1, 2, 3])
  others = toHashSet([3, 4, 5])
values.incl(others)
assert values.len == 5
Исходный код Изменить 
proc toHashSet[A](keys: openArray[A]): HashSet[A]

Создаёт новое множество хеш, содержащее элементы из заданной коллекции (seq, array или строка) keys.

Дубликаты удаляются.

См. также:

  • процедура initHashSet

Пример:

let
  a = toHashSet([5, 3, 2])
  b = toHashSet("abracadabra")
assert len(a) == 3
## a == {2, 3, 5}
assert len(b) == 5
## b == {'a', 'b', 'c', 'd', 'r'}
Исходный код Изменить 
proc containsOrIncl[A](s: var HashSet[A]; key: A): bool

Включает key в множество s и сообщает, было ли key уже в s.

Разница по сравнению с процедурой incl заключается в том, что эта процедура возвращает true, если s уже содержал key . Процедура вернёт false, если key был добавлен как новое значение в s во время этого вызова.

См. также:

  • процедура incl для включения элемента
  • процедура incl для включения другого множества
  • процедура missingOrExcl

Пример:

var values = initHashSet[int]()
assert values.containsOrIncl(2) == false
assert values.containsOrIncl(2) == true
assert values.containsOrIncl(3) == false
Исходный код Изменить 
proc excl[A](s: var HashSet[A]; key: A)

Исключает key из множества s.

Не выполняет никаких действий, если key не найден в s.

См. также:

  • процедура incl для включения элемента
  • процедура excl для исключения другого множества
  • процедура missingOrExcl

Пример:

var s = toHashSet([2, 3, 6, 7])
s.excl(2)
s.excl(2)
assert s.len == 3
Исходный код Изменить 
proc excl[A](s: var HashSet[A]; other: HashSet[A])

Исключает все элементы множества other из множества s.

Это версия в месте s - other.

См. также:

  • процедура incl для включения другого множества
  • процедура excl для исключения элемента
  • процедура missingOrExcl

Пример:

var
  numbers = toHashSet([1, 2, 3, 4, 5])
  even = toHashSet([2, 4, 6, 8])
numbers.excl(even)
assert len(numbers) == 3
## numbers == {1, 3, 5}
Исходный код Изменить 
proc missingOrExcl[A](s: var HashSet[A]; key: A): bool

Исключает key из множества s и сообщает, было ли key отсутствовало в s.

Разница по сравнению с процедурой excl заключается в том, что эта процедура возвращает true, если key отсутствовало в s . Процедура вернёт false, если key присутствовало в s и было удалено во время этого вызова.

См. также:

  • процедура excl для исключения элемента
  • процедура excl для исключения другого множества
  • процедура containsOrIncl

Пример:

var s = toHashSet([2, 3, 6, 7])
assert s.missingOrExcl(4) == true
assert s.missingOrExcl(6) == false
assert s.missingOrExcl(6) == true
Исходный код Изменить 
proc pop[A](s: var HashSet[A]): A

Удаляет и возвращает произвольный элемент из множества s.

Возбуждает исключение KeyError, если множество s пустое.

См. также:

  • процедура clear

Пример:

var s = toHashSet([2, 1])
assert [s.pop, s.pop] in [[1, 2], [2,1]] # order unspecified
doAssertRaises(KeyError, echo s.pop)
Исходный код Изменить 
proc clear[A](s: var HashSet[A])

Очищает множество хеш до пустого состояния, не уменьшая существующее хранилище.

O(n) операция, где n — размер корзины хеш.

См. также:

  • процедура pop

Пример:

var s = toHashSet([3, 5, 7])
clear(s)
assert len(s) == 0
Исходный код Изменить 
proc len[A](s: HashSet[A]): int

Возвращает количество элементов в s.

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

Пример:

var a: HashSet[string]
assert len(a) == 0
let s = toHashSet([3, 5, 7])
assert len(s) == 3
Исходный код Редактировать 
proc card[A](s: HashSet[A]): int

Псевдоним для len().

Card означает мощность множества.

Исходный код Редактировать 
proc union[A](s1, s2: HashSet[A]): HashSet[A]

Возвращает объединение множеств s1 и s2.

То же самое, что и s1 + s2.

Объединение двух множеств математически представляется как A ∪ B и является множеством всех объектов, которые являются членами s1, s2 или обоих.

См. также:

  • функция intersection
  • функция difference
  • функция symmetricDifference

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
  c = union(a, b)
assert c == toHashSet(["a", "b", "c"])
Исходный код Редактировать 
proc intersection[A](s1, s2: HashSet[A]): HashSet[A]

Возвращает пересечение множеств s1 и s2.

То же самое, что и s1 * s2.

Пересечение двух множеств математически представляется как A ∩ B и является множеством всех объектов, которые являются членами s1 и s2 одновременно.

См. также:

  • функция union
  • функция difference
  • функция symmetricDifference

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
  c = intersection(a, b)
assert c == toHashSet(["b"])
Исходный код Редактировать 
proc difference[A](s1, s2: HashSet[A]): HashSet[A]

Возвращает разность множеств s1 и s2.

То же самое, что и s1 - s2.

Разность двух множеств математически представляется как A ∖ B и является множеством всех объектов, которые являются членами s1 и не являются членами s2.

См. также:

  • функция union
  • функция intersection
  • функция symmetricDifference

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
  c = difference(a, b)
assert c == toHashSet(["a"])
Исходный код Редактировать 
proc symmetricDifference[A](s1, s2: HashSet[A]): HashSet[A]

Возвращает симметрическую разность множеств s1 и s2.

То же самое, что и s1 -+- s2.

Симметрическая разность двух множеств математически представляется как A △ B или A ⊖ B и является множеством всех объектов, которые являются членами s1 или s2 , но не обоих одновременно.

См. также:

  • функция union
  • функция intersection
  • функция difference

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
  c = symmetricDifference(a, b)
assert c == toHashSet(["a", "c"])
Исходный код Редактировать 
proc `+`[A](s1, s2: HashSet[A]): HashSet[A] {...}{.inline.}
Псевдоним для union(s1, s2). Исходный код Редактировать 
proc `*`[A](s1, s2: HashSet[A]): HashSet[A] {...}{.inline.}
Псевдоним для intersection(s1, s2). Исходный код Редактировать 
proc `-`[A](s1, s2: HashSet[A]): HashSet[A] {...}{.inline.}
Псевдоним для difference(s1, s2). Исходный код Редактировать 
proc `-+-`[A](s1, s2: HashSet[A]): HashSet[A] {...}{.inline.}
Псевдоним для symmetricDifference(s1, s2). Исходный код Редактировать 
proc disjoint[A](s1, s2: HashSet[A]): bool
Возвращает true, если множества s1 и s2 не имеют общих элементов.

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
assert disjoint(a, b) == false
assert disjoint(a, b - a) == true
Исходный код Редактировать 
proc `<`[A](s, t: HashSet[A]): bool

Возвращает true, если s является строгим подмножеством t.

Строгое подмножество s содержит все свои элементы в t, но t содержит больше элементов, чем s.

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
  c = intersection(a, b)
assert c < a and c < b
assert(not (a < a))
Исходный код Редактировать 
proc `<=`[A](s, t: HashSet[A]): bool

Возвращает true, если s является подмножеством t.

Подмножество s содержит все свои элементы в t, и t не обязательно содержит больше элементов, чем s. То есть, s может быть равно t.

Пример:

let
  a = toHashSet(["a", "b"])
  b = toHashSet(["b", "c"])
  c = intersection(a, b)
assert c <= a and c <= b
assert a <= a
Исходный код Редактировать 
proc `==`[A](s, t: HashSet[A]): bool
Возвращает true, если оба s и t имеют одинаковые элементы и размер множества.

Пример:

var
  a = toHashSet([1, 2])
  b = toHashSet([2, 1])
assert a == b
Исходный код Редактировать 
proc map[A, B](data: HashSet[A]; op: proc (x: A): B {...}{.closure.}): HashSet[B]

Возвращает новое множество после применения функции op к каждому элементу множества data.

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

Пример:

let
  a = toHashSet([1, 2, 3])
  b = a.map(proc (x: int): string = $x)
assert b == toHashSet(["1", "2", "3"])
Исходный код Редактировать 
proc hash[A](s: HashSet[A]): Hash
Хеширование HashSet. Исходный код Редактировать 
proc `$`[A](s: HashSet[A]): string

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

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

Примеры:

echo toHashSet([2, 4, 5])
# --> {2, 4, 5}
echo toHashSet(["no", "esc'aping", "is \" provided"])
# --> {no, esc'aping, is " provided}
Исходный код Редактировать 
proc initSet[A](initialSize = defaultInitialSize): HashSet[A] {...}{.
    deprecated: "Deprecated since v0.20, use \'initHashSet\'".}
Устаревшее: Устарело начиная с версии v0.20, используйте 'initHashSet'
Исходный код Редактировать 
proc toSet[A](keys: openArray[A]): HashSet[A] {...}{.
    deprecated: "Deprecated since v0.20, use \'toHashSet\'".}
Устаревшее: Устарело начиная с версии v0.20, используйте 'toHashSet'
Исходный код Редактировать 
proc isValid[A](s: HashSet[A]): bool {...}{.deprecated: "Deprecated since v0.20; sets are initialized by default".}
Устаревшее: Устарело начиная с версии v0.20; множества инициализируются по умолчанию

Возвращает true если множество было инициализировано (с помощью функции initHashSet или init).

Примеры:

proc savePreferences(options: HashSet[string]) =
  assert options.isValid, "Pass an initialized set!"
  # Do stuff here, may crash in release builds!
Исходный код Редактировать 
proc init[A](s: var OrderedSet[A]; initialSize = defaultInitialSize)

Инициализирует упорядоченное хеш-множество.

Начиная с Nim v0.20, множества инициализируются по умолчанию, и вызывать эту функцию явно не требуется.

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

См. также:

  • процедуру initOrderedSet
  • процедуру toOrderedSet

Пример:

var a: OrderedSet[int]
init(a)
Исходный код Редактировать 
proc initOrderedSet[A](initialSize = defaultInitialSize): OrderedSet[A]

Обёртка над процедурой init для инициализации упорядоченных хеш-множеств.

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

Начиная с Nim v0.20, множества инициализируются по умолчанию, и вызывать эту функцию явно не требуется.

См. также:

  • процедуру toOrderedSet

Пример:

var a = initOrderedSet[int]()
a.incl(3)
assert len(a) == 1
Исходный код Редактировать 
proc toOrderedSet[A](keys: openArray[A]): OrderedSet[A]

Создаёт новое хеш-множество, содержащее элементы заданной коллекции (seq, массив или строка) keys.

Дубликаты удаляются.

См. также:

  • процедуру initOrderedSet

Пример:

let
  a = toOrderedSet([5, 3, 2])
  b = toOrderedSet("abracadabra")
assert len(a) == 3
## a == {5, 3, 2} # different than in HashSet
assert len(b) == 5
## b == {'a', 'b', 'r', 'c', 'd'} # different than in HashSet
Исходный код Редактировать 
proc contains[A](s: OrderedSet[A]; key: A): bool

Возвращает true, если key содержится в s.

Это позволяет использовать оператор in.

См. также:

  • процедуру incl
  • процедуру containsOrIncl

Пример:

var values = initOrderedSet[int]()
assert(not values.contains(2))
assert 2 notin values

values.incl(2)
assert values.contains(2)
assert 2 in values
Исходный код Редактировать 
proc incl[A](s: var OrderedSet[A]; key: A)

Включает элемент key в s.

Это не делает ничего, если key уже содержится в s.

См. также:

  • процедуру excl для исключения элемента
  • процедуру incl для включения другого множества
  • процедуру containsOrIncl

Пример:

var values = initOrderedSet[int]()
values.incl(2)
values.incl(2)
assert values.len == 1
Исходный код Редактировать 
proc incl[A](s: var HashSet[A]; other: OrderedSet[A])

Включает все элементы из OrderedSet other в HashSet s (должен быть объявлен как var).

См. также:

  • процедуру incl для включения элемента
  • процедуру containsOrIncl

Пример:

var
  values = toHashSet([1, 2, 3])
  others = toOrderedSet([3, 4, 5])
values.incl(others)
assert values.len == 5
Исходный код Редактировать 
proc containsOrIncl[A](s: var OrderedSet[A]; key: A): bool

Включает key в множество s и сообщает, если key уже находилось в s.

Различие по сравнению с процедурой incl заключается в том, что эта процедура возвращает true если s уже содержало key. Процедура вернёт false, если key было добавлено как новое значение в s во время этого вызова.

См. также:

  • процедуру incl для включения элемента
  • процедуру missingOrExcl

Пример:

var values = initOrderedSet[int]()
assert values.containsOrIncl(2) == false
assert values.containsOrIncl(2) == true
assert values.containsOrIncl(3) == false
Исходный код Редактировать 
proc excl[A](s: var OrderedSet[A]; key: A)

Исключает key из множества s.

Это ничего не делает, если key не найдено в s.

См. также:

  • процедуру incl для включения элемента
  • процедуру missingOrExcl

Пример:

var s = toOrderedSet([2, 3, 6, 7])
s.excl(2)
s.excl(2)
assert s.len == 3
Исходный код Редактировать 
proc missingOrExcl[A](s: var OrderedSet[A]; key: A): bool

Исключает key из множества s и сообщает, если key уже отсутствовало в s.

Различие по сравнению с процедурой excl заключается в том, что эта процедура возвращает true если key отсутствовало в s.

Процедура вернёт false если key находилось в s и было удалено во время этого вызова.

См. также:

  • процедуру excl
  • процедуру containsOrIncl

Пример:

var s = toOrderedSet([2, 3, 6, 7])
assert s.missingOrExcl(4) == true
assert s.missingOrExcl(6) == false
assert s.missingOrExcl(6) == true
Исходный код Редактировать 
proc clear[A](s: var OrderedSet[A])

Очищает упорядоченное множество до пустого состояния, не уменьшая размер хранилища.

O(n) операция, где n — размер хеш-корзины.

Пример:

var s = toOrderedSet([3, 5, 7])
clear(s)
assert len(s) == 0
Исходный код Редактировать 
proc len[A](s: OrderedSet[A]): int {...}{.inline.}

Возвращает количество элементов в s.

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

Пример:

var a: OrderedSet[string]
assert len(a) == 0
let s = toHashSet([3, 5, 7])
assert len(s) == 3
Исходный код Редактировать 
proc card[A](s: OrderedSet[A]): int {...}{.inline.}

Псевдоним для len().

Card означает мощность множества.

Исходный код Редактировать 
proc `==`[A](s, t: OrderedSet[A]): bool
Равенство для упорядоченных множеств.

Пример:

let
  a = toOrderedSet([1, 2])
  b = toOrderedSet([2, 1])
assert(not (a == b))
Исходный код Редактировать 
proc hash[A](s: OrderedSet[A]): Hash
Хеширование OrderedSet. Исходный код Редактировать 
proc `$`[A](s: OrderedSet[A]): string

Преобразует упорядоченное хеш-множество s в строку, в основном для целей протоколирования и вывода.

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

Примеры:

echo toOrderedSet([2, 4, 5])
# --> {2, 4, 5}
echo toOrderedSet(["no", "esc'aping", "is \" provided"])
# --> {no, esc'aping, is " provided}
Исходный код Редактировать
END_OF_DOCUMENT_MARKER

Итераторы

iterator items[A](s: HashSet[A]): A

Итерируется по элементам множества s.

Если вам нужна последовательность с элементами, вы можете использовать шаблон sequtils.toSeq.

type
  pair = tuple[a, b: int]
var
  a, b = initHashSet[pair]()
a.incl((2, 3))
a.incl((3, 2))
a.incl((2, 3))
for x, y in a.items:
  b.incl((x - 2, y + 1))
assert a.len == 2
echo b
# --> {(a: 1, b: 3), (a: 0, b: 4)}
Исходный код Редактировать 
iterator items[A](s: OrderedSet[A]): A

Итерируется по ключам в упорядоченном множестве s в порядке вставки.

Если вам нужна последовательность с элементами, вы можете использовать шаблон sequtils.toSeq.

var a = initOrderedSet[int]()
for value in [9, 2, 1, 5, 1, 8, 4, 2]:
  a.incl(value)
for value in a.items:
  echo "Got ", value
# --> Got 9
# --> Got 2
# --> Got 1
# --> Got 5
# --> Got 8
# --> Got 4
Исходный код Редактировать 
iterator pairs[A](s: OrderedSet[A]): tuple[a: int, b: A]
Итерируется по кортежам (позиция, значение) упорядоченного множества s.

Пример:

let a = toOrderedSet("abracadabra")
var p = newSeq[(int, char)]()
for x in pairs(a):
  p.add(x)
assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')]
Исходный код Редактировать

© 2006–2021 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/sets.html

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API