范围从D语言中的关联数组开始。

Question

我在阅读Andrei的书《D编程语言》后，开始着手实施我的第一个中型程序。我遇到的第一个问题之一是如何使用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);
}

对我来说，似乎这是一个简单的事情，期望在迭代过程中产生单个的“two”条目。然而，我得到了这个编译器错误：

./test.d(20): Error: template std.algorithm.setIntersection(alias less = "a < b",Rs...) if (allSatisfy!(isInputRange,Rs)) does not match any function template declaration

./test.d(20): Error: template std.algorithm.setIntersection(alias less = "a < b",Rs...) if (allSatisfy!(isInputRange,Rs)) cannot deduce template function from argument types !()(int[string],int[string])

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

我是否漏掉了什么？做错了什么？如果没有，这是一个明显的遗漏吗？为什么这样做是正确不可用的？

- aligature

---

两个关联数组的交集是什么意思？如果 map1 = ["red":4, "blue":6] 和 map2 = ["blue":2, "green":1]，会怎样？ - kennytm

在C++中，一个类似的例子是std::map<std::string, int>。在这种情况下，std::set_intersection使用迭代器类型，它基本上引用了std::pair<const std::string, int>的value_type。std::set_intersection在value_type上使用<来比较键和值。因此，在您的示例中，我预计交集将为空。 - aligature

Answer 1

请使用以下内容：

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

- Andrei Alexandrescu

---

需要对范围进行排序吗？ - dsimcha

文档明确表示，传递给 setIntersection() 的范围需要按照其给定的谓词（默认为 "a < b"）先进行排序。因此，我期望您需要先对键进行排序。 - Jonathan M Davis

Answer 2

请注意，C++中的std::map是一种有序数据结构，而D语言中的关联数组是无序的。因此，std.algorithm.setIntersection函数假定输入的区间是有序的，所以在使用该函数之前，您需要将关联数组转换为有序区间，例如（result）。

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不被视为输入范围，因此所有的范围算法都无法与之配合使用。（我不知道如何将其转换为输入范围。）

- kennytm

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

- JRM