# sets

- マニュアル
- 標準ライブラリ
- 索引

検索
分類:

The `sets` module implements an efficient hash set and ordered hash set.

Hash sets are different from the built in set type. Sets allow you to store any value that can be hashed and they don't contain duplicate entries.

Common usages of sets:

- removing duplicates from a container by converting it with toHashSet proc (see also sequtils.deduplicate proc)
- membership testing
- mathematical operations on two sets, such as union, intersection, difference, and symmetric difference

    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}

Note: The data types declared here have value semantics: This means that `=` performs a copy of the set.

関連:

- intsets module for efficient int sets
- tables module for hash tables

# インポート

hashes, math

# 型

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

  A generic hash set.

  Use init proc or initHashSet proc before calling other procs on it.

  ソース 編集

    OrderedSet[A] {...}{..} = object
      data: OrderedKeyValuePairSeq[A]
      counter, first, last: int

  A generic hash set that remembers insertion order.

  Use init proc or initOrderedSet proc before calling other procs on it.

  ソース 編集

# 定数

    defaultInitialSize = 64

  ソース 編集

# プロシージャ

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

  Initializes a hash set.

  The `initialSize` parameter needs to be a power of two (default: 64). If you need to accept runtime values for this, you can use math.nextPowerOfTwo proc or rightSize proc from this module.

  Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

  You can call this proc on a previously initialized hash set, which will discard all its values. This might be more convenient than iterating over existing values and calling excl() on them.

  関連:

  - initHashSet proc
  - toHashSet proc

  用例:

      var a: HashSet[int]
      assert(not a.isValid)
      init(a)
      assert a.isValid

  ソース 編集

    proc initHashSet[A](initialSize = defaultInitialSize): HashSet[A]

  Wrapper around init proc for initialization of hash sets.

  Returns an empty hash set you can assign directly in `var` blocks in a single line.

  Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

  関連:

  - toHashSet proc

  用例:

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

  ソース 編集

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

  Returns the element that is actually stored in `s` which has the same value as `key` or raises the `KeyError` exception.

  This is useful when one overloaded `hash` and `==` but still needs reference semantics for sharing.

  ソース 編集

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

  Returns true if `key` is in `s`.

  This allows the usage of `in` operator.

  関連:

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

  Includes an element `key` in `s`.

  This doesn't do anything if `key` is already in `s`.

  関連:

  - excl proc for excluding an element
  - incl proc for including other set
  - containsOrIncl proc

  用例:

      var values = initHashSet[int]()
      values.incl(2)
      values.incl(2)
      assert values.len == 1

  ソース 編集

    proc incl[A](s: var HashSet[A]; other: HashSet[A])

  Includes all elements from `other` set into `s` (must be declared as `var`).

  This is the in-place version of s + other.

  関連:

  - excl proc for excluding other set
  - incl proc for including an element
  - containsOrIncl proc

  用例:

      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]

  Creates a new hash set that contains the members of the given collection (seq, array, or string) `keys`.

  Duplicates are removed.

  関連:

  - initHashSet proc

  用例:

      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

  Includes `key` in the set `s` and tells if `key` was already in `s`.

  The difference with regards to the incl proc is that this proc returns `true` if `s` already contained `key`. The proc will return `false` if `key` was added as a new value to `s` during this call.

  関連:

  - incl proc for including an element
  - incl proc for including other set
  - missingOrExcl proc

  用例:

      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)

  Excludes `key` from the set `s`.

  This doesn't do anything if `key` is not found in `s`.

  関連:

  - incl proc for including an element
  - excl proc for excluding other set
  - missingOrExcl proc

  用例:

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

  Excludes all elements of `other` set from `s`.

  This is the in-place version of s - other.

  関連:

  - incl proc for including other set
  - excl proc for excluding an element
  - missingOrExcl proc

  用例:

      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

  Excludes `key` in the set `s` and tells if `key` was already missing from `s`.

  The difference with regards to the excl proc is that this proc returns `true` if `key` was missing from `s`. The proc will return `false` if `key` was in `s` and it was removed during this call.

  関連:

  - excl proc for excluding an element
  - excl proc for excluding other set
  - containsOrIncl proc

  用例:

      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

  Remove and return an arbitrary element from the set `s`.

  Raises KeyError if the set `s` is empty.

  関連:

  - clear proc

  用例:

      var s = toHashSet([2, 1])
      assert s.pop == 1
      assert s.pop == 2
      doAssertRaises(KeyError, echo s.pop)

  ソース 編集

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

  Clears the HashSet back to an empty state, without shrinking any of the existing storage.

  `O(n)` operation, where `n` is the size of the hash bucket.

  関連:

  - pop proc

  用例:

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

  ソース 編集

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

  Returns the number of elements in `s`.

  Due to an implementation detail you can call this proc on variables which have not been initialized yet. The proc will return zero as the length then.

  用例:

      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

  Alias for len().

  Card stands for the cardinality of a set.

  ソース 編集

    proc union[A](s1, s2: HashSet[A]): HashSet[A]

  Returns the union of the sets `s1` and `s2`.

  The same as s1 + s2.

  The union of two sets is represented mathematically as A ∪ B and is the set of all objects that are members of `s1`, `s2` or both.

  関連:

  - intersection proc
  - difference proc
  - symmetricDifference proc

  用例:

      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]

  Returns the intersection of the sets `s1` and `s2`.

  The same as s1 * s2.

  The intersection of two sets is represented mathematically as A ∩ B and is the set of all objects that are members of `s1` and `s2` at the same time.

  関連:

  - union proc
  - difference proc
  - symmetricDifference proc

  用例:

      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]

  Returns the difference of the sets `s1` and `s2`.

  The same as s1 - s2.

  The difference of two sets is represented mathematically as A ∖ B and is the set of all objects that are members of `s1` and not members of `s2`.

  関連:

  - union proc
  - intersection proc
  - symmetricDifference proc

  用例:

      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]

  Returns the symmetric difference of the sets `s1` and `s2`.

  The same as s1 -+- s2.

  The symmetric difference of two sets is represented mathematically as A △ B or A ⊖ B and is the set of all objects that are members of `s1` or `s2` but not both at the same time.

  関連:

  - union proc
  - intersection proc
  - difference proc

  用例:

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

  Alias for union(s1, s2). ソース 編集

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

  Alias for intersection(s1, s2). ソース 編集

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

  Alias for difference(s1, s2). ソース 編集

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

  Alias for symmetricDifference(s1, s2). ソース 編集

    proc disjoint[A](s1, s2: HashSet[A]): bool

  Returns `true` if the sets `s1` and `s2` have no items in common.

  用例:

      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

  Returns true if `s` is a strict or proper subset of `t`.

  A strict or proper subset `s` has all of its members in `t` but `t` has more elements than `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

  Returns true if `s` is a subset of `t`.

  A subset `s` has all of its members in `t` and `t` doesn't necessarily have more members than `s`. That is, `s` can be equal to `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

  Returns true if both `s` and `t` have the same members and set size.

  用例:

      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]

  Returns a new set after applying `op` proc on each of the elements of `data` set.

  You can use this proc to transform the elements from a set.

  用例:

      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

  Hashing of HashSet. ソース 編集

    proc `$`[A](s: HashSet[A]): string

  Converts the set `s` to a string, mostly for logging and printing purposes.

  Don't use this proc for serialization, the representation may change at any moment and values are not escaped.

  用例:

      echo toHashSet([2, 4, 5])
      # --> {2, 4, 5}
      echo toHashSet(["no", "esc'aping", "is \" provided"])
      # --> {no, esc'aping, is " provided}

  ソース 編集

    proc rightSize(count: Natural): int {...}{.inline, raises: [], tags: [].}

  Return the value of `initialSize` to support `count` items.

  If more items are expected to be added, simply add that expected extra amount to the parameter before calling this.

  Internally, we want `mustRehash(rightSize(x), x) == false`.

  ソース 編集

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

  Deprecated: Deprecated since v0.20, use 'initHashSet'
  ソース 編集

    proc toSet[A](keys: openArray[A]): HashSet[A] {...}{.
        deprecated: "Deprecated since v0.20, use \'toHashSet\'".}

  Deprecated: Deprecated since v0.20, use 'toHashSet'
  ソース 編集

    proc isValid[A](s: HashSet[A]): bool {...}{.deprecated: "Deprecated since v0.20; sets are initialized by default".}

  Deprecated: Deprecated since v0.20; sets are initialized by default

  Returns `true` if the set has been initialized (with initHashSet proc or init proc).

  用例:

      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)

  Initializes an ordered hash set.

  The `initialSize` parameter needs to be a power of two (default: 64). If you need to accept runtime values for this, you can use math.nextPowerOfTwo proc or rightSize proc from this module.

  Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

  You can call this proc on a previously initialized hash set, which will discard all its values. This might be more convenient than iterating over existing values and calling excl() on them.

  関連:

  - initOrderedSet proc
  - toOrderedSet proc

  用例:

      var a: OrderedSet[int]
      assert(not a.isValid)
      init(a)
      assert a.isValid

  ソース 編集

    proc initOrderedSet[A](initialSize = defaultInitialSize): OrderedSet[A]

  Wrapper around init proc for initialization of ordered hash sets.

  Returns an empty ordered hash set you can assign directly in `var` blocks in a single line.

  Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

  関連:

  - toOrderedSet proc

  用例:

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

  ソース 編集

    proc toOrderedSet[A](keys: openArray[A]): OrderedSet[A]

  Creates a new hash set that contains the members of the given collection (seq, array, or string) `keys`.

  Duplicates are removed.

  関連:

  - initOrderedSet proc

  用例:

      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

  Returns true if `key` is in `s`.

  This allows the usage of `in` operator.

  関連:

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

  Includes an element `key` in `s`.

  This doesn't do anything if `key` is already in `s`.

  関連:

  - excl proc for excluding an element
  - incl proc for including other set
  - containsOrIncl proc

  用例:

      var values = initOrderedSet[int]()
      values.incl(2)
      values.incl(2)
      assert values.len == 1

  ソース 編集

    proc incl[A](s: var HashSet[A]; other: OrderedSet[A])

  Includes all elements from the OrderedSet `other` into HashSet `s` (must be declared as `var`).

  関連:

  - incl proc for including an element
  - containsOrIncl proc

  用例:

      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

  Includes `key` in the set `s` and tells if `key` was already in `s`.

  The difference with regards to the incl proc is that this proc returns `true` if `s` already contained `key`. The proc will return false if `key` was added as a new value to `s` during this call.

  関連:

  - incl proc for including an element
  - missingOrExcl proc

  用例:

      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)

  Excludes `key` from the set `s`. Efficiency: `O(n)`.

  This doesn't do anything if `key` is not found in `s`.

  関連:

  - incl proc for including an element
  - missingOrExcl proc

  用例:

      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

  Excludes `key` in the set `s` and tells if `key` was already missing from `s`. Efficiency: O(n).

  The difference with regards to the excl proc is that this proc returns `true` if `key` was missing from `s`. The proc will return `false` if `key` was in `s` and it was removed during this call.

  関連:

  - excl proc
  - containsOrIncl proc

  用例:

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

  Clears the OrderedSet back to an empty state, without shrinking any of the existing storage.

  `O(n)` operation where `n` is the size of the hash bucket.

  用例:

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

  ソース 編集

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

  Returns the number of elements in `s`.

  Due to an implementation detail you can call this proc on variables which have not been initialized yet. The proc will return zero as the length then.

  用例:

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

  Alias for len().

  Card stands for the cardinality of a set.

  ソース 編集

    proc `==`[A](s, t: OrderedSet[A]): bool

  Equality for ordered sets.

  用例:

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

  ソース 編集

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

  Hashing of OrderedSet. ソース 編集

    proc `$`[A](s: OrderedSet[A]): string

  Converts the ordered hash set `s` to a string, mostly for logging and printing purposes.

  Don't use this proc for serialization, the representation may change at any moment and values are not escaped.

  用例:

      echo toOrderedSet([2, 4, 5])
      # --> {2, 4, 5}
      echo toOrderedSet(["no", "esc'aping", "is \" provided"])
      # --> {no, esc'aping, is " provided}

  ソース 編集

    proc isValid[A](s: OrderedSet[A]): bool {...}{.deprecated: "Deprecated since v0.20; sets are initialized by default".}

  Deprecated: Deprecated since v0.20; sets are initialized by default

  > Returns `true` if the set has been initialized (with initHashSet proc or init proc).

  > 用例:

  >     proc savePreferences(options: OrderedSet[string]) =
  >       assert options.isValid, "Pass an initialized set!"
  >       # Do stuff here, may crash in release builds!

  ソース 編集

# イテレータ

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

  Iterates over elements of the set `s`.

  If you need a sequence with the elements you can use sequtils.toSeq template.

      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

  Iterates over keys in the ordered set `s` in insertion order.

  If you need a sequence with the elements you can use sequtils.toSeq template.

      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]

  Iterates through (position, value) tuples of OrderedSet `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')]

  ソース 編集