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

Question

在阅读了Andrei的书"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会产生单个"两个"条目.但是,我收到此编译器错误:

./test.d(20):错误:模板std.algorithm.setIntersection(alias less ="a <b",Rs ...)if(allSatisfy!(isInputRange,Rs))与任何函数模板声明都不匹配

./test.d(20):错误:模板std.algorithm.setIntersection(alias less ="a <b",Rs ...)如果(allSatisfy!(isInputRange,Rs))不能从参数类型推导出模板函数! ()(INT [字符串],INT [字符串])

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

我错过了什么吗？做错了什么？如果没有,这是一个明显的遗漏吗？有什么理由可以解决这个问题吗？

Answer 1

用这个:

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

Answer 2

请注意,std::map在C++中是排序数据结构,而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不计入输入范围,因此所有范围算法都不适用.(我不知道如何将其作为输入范围.)