范围来自 D 2 中的关联数组

Question

在阅读 Andrei 的《The D 编程语言》一书后，我刚刚开始在 D 2.0 中实现我的第一个中型程序。我遇到的第一个问题是使用带有内置关联数组的 std.algorithm 库。例如：

#!/usr/bin/env rdmd

import std.stdio;
import std.algorithm;

void main()
{
   alias int[string] StringHashmap;

   StringHashmap map1;
   map1["one"] = 1;
   map1["two"] = 2;
   writefln("map1: %s", map1);

   StringHashmap map2;
   map2["two"] = 2;
   map2["three"] = 3;
   writefln("map2: %s", map2);

   auto inter = setIntersection(map1, map2);
}

对我来说，这似乎是一件很简单的事情，期望迭代 inter 会产生单个“two”条目。但是，我收到此编译器错误：

./test.d(20)：错误：模板 std.algorithm.setIntersection(别名 less = "a < b",Rs...) 如果 (allSatisfy!(isInputRange,Rs)) 确实 不匹配任何函数模板 声明

./test.d(20)：错误：模板 std.algorithm.setIntersection(别名 less = "a < b",Rs...) 如果 (allSatisfy!(isInputRange,Rs)) 不能 从参数推导出模板函数 类型 !()(int[string],int[string])

我可以看到内置关联数组似乎没有提供与 std 算法一起使用的范围的任何版本。

我错过了什么吗？做错事了吗？如果不是，这是否是一个明显的遗漏？是否有某种原因导致此功能不可用？

Answer 1

使用这个：

auto inter = setIntersection(map1.keys, map2.keys);

Answer 2

请注意，C++ 中的 std::map 是排序的数据结构，而 D 中的关联数组是无序的。 std.algorithm.setIntersection 假定一个已排序范围，因此在将关联数组转换为已排序范围之前，您无法使用此函数，例如 (结果）

import std.typecons;
import std.array;
import std.algorithm;
import std.stdio;

auto byItemSorted(K,V)(V[K] dict) {
   auto app = appender!(Tuple!(K,V)[])();
   foreach (k, v; dict)
     app.put(tuple(k, v));
   auto res = app.data;    // if there's byItem() we don't need this appender stuff.
   sort(res);
   return res;
}

auto dictIntersection(K,V)(V[K] map1, V[K] map2) {
  return setIntersection(byItemSorted(map1), byItemSorted(map2));
}

void main () {
   auto map1 = ["red":4, "blue":6],
        map2 = ["blue":2, "green":1],
        map3 = ["blue":6, "purple":8];
   writeln("map1 & map2 = ", array(dictIntersection(map1, map2)));
   writeln("map1 & map3 = ", array(dictIntersection(map1, map3)));
}

但是这种方法效率很低——对一个范围进行排序需要 O(N log N) 。

更有效的方法是编写自己的交集例程，这只需要 O(N) (结果) ：

import std.stdio;

struct DictIntersection(K,V) {
  V[K] m1, m2;
  this(V[K] map1, V[K] map2) { m1 = map1; m2 = map2; }
  int opApply(int delegate(ref K, ref V) dg) {
    int res = 0;
    foreach (k, v; m1) {
      V* p = k in m2;
      if (p && v == *p) {
        res = dg(k, v);
        if (res)
          break;
      }
    }
    return res;
  }
}
DictIntersection!(K,V) dictIntersection(K,V)(V[K] map1, V[K] map2) {
  return typeof(return)(map1, map2);
}

void main () {
   auto map1 = ["red":4, "blue":6],
        map2 = ["blue":2, "green":1],
        map3 = ["blue":6, "purple":8];

   write("map1 & map2 = ");
   foreach (k, v; dictIntersection(map1, map2)) write(k, "->", v, " ");
   write("\nmap1 & map3 = ");
   foreach (k, v; dictIntersection(map1, map3)) write(k, "->", v, " ");

}

但是，由于 opApply 不算作输入范围，因此所有范围算法都不适用于此。 （我不知道如何将其变成输入范围。）

Answer 3

您可以从关联数组中获取键或值。

要获取值上的交集，请使用

auto inter = setIntersection(map1.values, map2.values);
foreach (i; inter) {
   writeln(i);
}

要获取键上的交集，请使用

auto inter = setIntersection(map1.keys, map2.keys);
foreach (i; inter) {
   writeln(i);
}

我认为您无法像使用 C++ std::map 那样访问包含键、值对的范围。

请参阅http://www.digitalmars.com/d/2.0/hash-map .html