代码之家 › 专栏 › 技术社区 › v.oddou

设置哈希表和哈希集键之间的差异

nim-lang adapter set

v.oddou · 技术社区 · 8 年前

如何在nim中的“哈希表中的键视图”和哈希集之间执行集差异操作?

概念上:

import tables, sets, sequtils

var a = initTable[int, string]()
var b: HashSet[int]
b.init(4)

a[0] = "a"
a[1] = "b"

b.incl(0)
b.incl(1)
b.incl(2)
b.incl(3)

var diff = b - toset(toseq(a.keys))
echo diff # {2, 3}

这很有效( 而且很难工作,编译器给出了误导性的信息。e、 g.尝试删除 toseq 上面写着“未声明字段:'键'”,哇。 )
但当然,这是没有用的,我会在这种情况下循环并改变自己。
我们需要的是一种直接与哈希集/哈希表一起工作的无分配方法。例如:

var diff = b - a.keys

或者最坏的情况是:

var diff = b - HashSetView(a.keys)

它将从键迭代器创建一个适配器对象,以适应 - 可能只接受集合的过程。

可能的

编辑: 事实上,我刚刚想起了我脑海中一直浮现的是 boost::transform_iterator 概念
Initialize a container with iterator range of container with different type
这就是为什么在C++的设计中,每个算法/stdlib函数都有一个范围(2 iter),而不是尽可能多地引用容器本身。这是鸭子打字的一种形式。
再想一想,我这里的问题似乎是集合差分过程不适用于迭代器。

1 回复 | 直到 8 年前

Ryan Stein 8 年前

Nim的元编程和UFCS设施似乎很好地解决了您需要的问题:

proc `-`[K, V](a: HashSet[K], b: Table[K, V]): HashSet[K] =
  result = a

  for k in b.keys:
    result.excl k


var diff = b - a

正如您所怀疑的,这将比只为一个集合分配一个全新的序列来丢弃它更有效。然而,似乎没有一种内在的方式来完成你想要完成的事情。

这个 undeclared field: "keys" 在以下情况下,错误是有意义的 keys 是 an inline iterator 而不是字段,但是此错误消息肯定会提供更多信息。如果希望使用任意迭代器,似乎必须 wrap it in a closure ,尽管这可能会导致一些开销。

具有 toClosure 从 nim-iterutils 包装:

template toClosure*(i): auto =
  ## Wrap an inline iterator in a first-class closure iterator.
  iterator j: type(i) {.closure.} =
    for x in i:
      yield x
  j

proc `-`[K](a: HashSet[K], b: iterator): HashSet[K] =
  result = a

  for k in b():
    result.excl k


var diff = b - toClosure(a.keys)

如果不需要完整的结果,那么产生差异可能会有更大的性能。

iterator without_keys[K, V](a: HashSet[K], b: Table[K, V]): K =
  for k in a.items:
    if not b.has_key(k):
      yield k

for k in b.without_keys(a):
  echo k

推荐文章