6

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?

2
  • 1
    What do you mean by the intersection of two associative arrays? What if map1 = ["red":4, "blue":6] and map2 = ["blue":2, "green":1]?
    – kennytm
    Aug 8, 2010 at 19:07
  • In C++ a close example would be std::map<std::string, int>. In this case std::set_intersection takes the iterator type which essentially references the value_type of std::pair<const std::string, int>. The std::set_intersection uses < on the value_type which compares both the key and value. So, in your example, I would expect the intersection to be empty.
    – aligature
    Aug 8, 2010 at 22:46

3 Answers 3

6

Use this:

auto inter = setIntersection(map1.keys, map2.keys);
2
  • 3
    Don't the ranges need to be sorted, though?
    – dsimcha
    Aug 9, 2010 at 4:41
  • 1
    The docs certainly say that the ranges that you pass to setIntersection() need to be sorted first by whatever predicate is given to it (which happens to be "a < b" by default). So, I'd expect you to have to sort the keys first. Aug 9, 2010 at 7:00
5

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

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.