Varies from associative arrays in D 2

Question

I just started to implement my first middle-class program in D 2.0 after reading Andrei’s book D programming language . One of the first issues I came up with 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 to me that this was quite simple, expecting that iterating over inter would result in a single record of two. However, I get this compiler error:

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

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

I see that the built-in associative array does not seem to provide any version of the range for use with std algorithms.

Am I missing something? Something is wrong? If not, is this a blatant omission? Is there a reason this is not possible?

Answer 1

Use this:

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

Answer 2

Note that std::map in C ++ is a sorted data structure, and the associative array in D is unordered. std.algorithm.setIntersection accepts a sorted range, so you cannot use this function until you convert an associative array to a sorted range, for example. ( 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 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 - O (N log N) is required to sort the range.

A more efficient method is to write your own intersection procedure, which only accepts 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, since opApply is not considered an input range, all range algorithms will not work with this. (I do not know how this can be done in the input range.)

Answer 3

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

To get the intersection of 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 do not think that you can access a range containing key pairs, values, for example, with C ++ std :: map.

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