ranges from associative arrays in D 2

Question

I've just started implementing my first medium scale program in D 2.0 after reading Andrei's book The D Programming Language. One of the first problems I came to was using the std.algorithm library with a built-in associative array. For example:

#!/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);
}

It seemed a simple enough thing to me, expecting that iterating over the inter would produce the single "two" entry. However, I get this compiler error:

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

I can see that the built-in associative array doesn't seem to provide any version of the range to use with the std algorithms.

Am I missing something? Doing something wrong? If not, is this a glaring omission? Is there some reason why this is properly unavailable?

Answer 1

Use this:

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

Answer 2

You can get either the keys or the values from an associative array.

To get the intersection on the values, use

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

To get the intersection on the keys, use

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

I don't think you can get access to a range containing the key, value pairs like with a C++ std::map.

See http://www.digitalmars.com/d/2.0/hash-map.html

Answer 3

Note that std::map in C++ is a sorted data structure, while an associative array in D is unordered. std.algorithm.setIntersection assumes a sorted range, so you can't use this function until you've converted the associative array into a sorted range, e.g. (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)));
}

But this method is inefficient — it takes O(N log N) to sort a range.

A more efficient method is like to write your own intersection routine, which only takes O(N) (result):

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, " ");

}

However, because opApply doesn't count as an input range, all range algorithms won't work with this. (I don't know how this can be made into an input range.)