varie de tableaux associatifs en D 2

Question

Je viens de commencer à implémenter mon premier programme de taille moyenne en D 2.0 après avoir lu le livre de Andrei Le langage de programmation D. L'un des premiers problèmes que j'ai rencontré était l'utilisation de la bibliothèque std.algorithm avec un tableau associatif intégré. Par exemple:

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

Il semblait assez simple chose à moi, attendant que itérer sur l'inter produirait la seule entrée « deux ». Cependant, je reçois cette erreur du compilateur:

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

je peux voir que le haut-tableau associatif ne semble pas fournir une version de la gamme à utiliser avec les algorithmes de std.

Ai-je raté quelque chose? Faire quelque chose de mal? Sinon, est-ce une omission flagrante? Y a-t-il une raison pour laquelle cela est indisponible?

Answer 1

Utilisez ceci:

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

Answer 2

Vous pouvez obtenir soit les touches ou les valeurs d'un tableau associatif.

Pour obtenir l'intersection des valeurs, utilisez

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

Pour obtenir l'intersection sur les touches, utilisez

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

Je ne pense pas que vous pouvez avoir accès à une plage contenant la key, paires de valeurs comme avec un C++ std :: map.

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

Answer 3

Notez que std::map en C++ est une structure de données triées, tandis qu'un tableau associatif en D est non ordonnée. std.algorithm.setIntersection suppose une plage triée, donc vous ne pouvez pas utiliser cette fonction tant que vous n'avez pas converti le tableau associatif en une plage triée, par ex. (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))); 
} 

Mais cette méthode est inefficace - il faut O (N log N) pour trier une plage.

Une méthode plus efficace est comme d'écrire votre propre routine d'intersection, qui ne prend 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, " "); 

} 

Cependant, parce que opApply ne compte pas comme une plage d'entrée, toute la gamme les algorithmes ne fonctionneront pas avec ça. (Je ne sais pas comment cela peut être fait dans une plage d'entrée.)