std/sets

Модуль 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, outparams

Типы

HashSet[A] {..} = object

Общее хеш-множество.

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

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

OrderedSet[A] {..} = object

Общее хеш-множество, которое запоминает порядок вставки.

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

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

SomeSet[A] = HashSet[A] | OrderedSet[A]

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

Константы

defaultInitialSize = 64

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

Процедуры

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 `$`[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}

Исходный код Изменить

proc `*`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}

Псевдоним для intersection(s1, s2). Исходный код Изменить

proc `+`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}

Псевдоним для union(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 `<`[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 `==`[A](s, t: OrderedSet[A]): bool

Равенство для упорядоченных множеств.

Пример:

let
  a = toOrderedSet([1, 2])
  b = toOrderedSet([2, 1])
assert(not (a == b))

Исходный код Изменить

proc `[]`[A](s: var HashSet[A]; key: A): var A

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

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

Исходный код Изменить

proc card[A](s: HashSet[A]): int

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

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

Исходный код Изменить

proc card[A](s: OrderedSet[A]): int {.inline.}

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

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

Исходный код Изменить

proc clear[A](s: var HashSet[A])

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

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

См. также:

• pop proc

Пример:

var s = toHashSet([3, 5, 7])
clear(s)
assert len(s) == 0

Исходный код Изменить

proc clear[A](s: var OrderedSet[A])

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

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

Пример:

var s = toOrderedSet([3, 5, 7])
clear(s)
assert len(s) == 0

Исходный код Изменить

proc contains[A](s: HashSet[A]; key: A): bool

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

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

См. также:

• incl proc
• containsOrIncl proc

Пример:

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 contains[A](s: OrderedSet[A]; key: A): bool

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

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

См. также:

• incl proc
• containsOrIncl proc

Пример:

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 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 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 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 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 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 excl[A](s: var OrderedSet[A]; key: A)

Исключает key из множества s. Эффективность: O(n).

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

См. также:

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

Пример:

var s = toOrderedSet([2, 3, 6, 7])
s.excl(2)
s.excl(2)
assert s.len == 3

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

proc hash[A](s: HashSet[A]): Hash

Хеширование HashSet. Исходный код Редактировать

proc hash[A](s: OrderedSet[A]): Hash

Хеширование OrderedSet. Исходный код Редактировать

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 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 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 init[A](s: var HashSet[A]; initialSize = defaultInitialSize)

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

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

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

См. также:

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

Пример:

var a: HashSet[int]
init(a)

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

proc init[A](s: var OrderedSet[A]; initialSize = defaultInitialSize)

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

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

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

См. также:

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

Пример:

var a: OrderedSet[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 initOrderedSet[A](initialSize = defaultInitialSize): OrderedSet[A]

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

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

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

См. также:

• процедура toOrderedSet

Пример:

var a = initOrderedSet[int]()
a.incl(3)
assert len(a) == 1

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

proc initSet[A](initialSize = defaultInitialSize): HashSet[A] {.
    ...deprecated: "Deprecated since v0.20, use \'initHashSet\'".}

Устаревшее: Устарело с версии v0.20, используйте 'initHashSet'

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

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 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 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 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 map[A, B](data: HashSet[A]; op: proc (x: A): B {.closure.}): HashSet[B] {.
    effectsOf: op.}

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

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

Пример:

let
  a = toHashSet([1, 2, 3])
  b = a.map(proc (x: int): string = $x)
assert b == toHashSet(["1", "2", "3"])

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

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 missingOrExcl[A](s: var OrderedSet[A]; key: A): bool

Исключает key из множества s и указывает, было ли key уже отсутствовало в s . Эффективность: O(n).

Разница по сравнению с процедурой 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 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 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 toHashSet[A](keys: openArray[A]): HashSet[A]

Создаёт новое хеш-множество, содержащее элементы заданного набора (последовательности, массива или строки) 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 toOrderedSet[A](keys: openArray[A]): OrderedSet[A]

Создаёт новое упорядоченное множество, содержащее члены заданного набора (последовательности, массива или строки) 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 toSet[A](keys: openArray[A]): HashSet[A] {.
    ...deprecated: "Deprecated since v0.20, use \'toHashSet\'".}

Устаревшее: Устаревшее с версии v0.20, используйте 'toHashSet'

Исходный код Изменить

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"])

Исходный код Изменить

Итераторы

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')]

Исходный код Изменить