варьируется от ассоциативных массивов в D 2 - PullRequest
Новая
       17

варьируется от ассоциативных массивов в D 2

6 голосов
/ 08 августа 2010

Я только начал реализовывать свою первую программу среднего масштаба на D 2.0 после прочтения книги Андрея Язык программирования 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);
}

Мне показалось, что это достаточно просто, ожидая, что итерация по inter создаст одну запись "two".Однако, я получаю эту ошибку компилятора:

. / Test.d (20): Ошибка: шаблон std.algorithm.setIntersection (псевдоним less = "a . / test.d (20): Ошибка: шаблон std.algorithm.setIntersection (псевдоним less = "a

Я вижу, что встроенный-в ассоциативном массиве, похоже, нет какой-либо версии диапазона для использования с алгоритмами std.

Я что-то упустил?Делать что-то не так?Если нет, то это явное упущение?Есть ли какая-то причина, по которой это правильно недоступно?

Ответы [ 3 ]

6 голосов
/ 09 августа 2010

Используйте это: 

auto inter = setIntersection(map1.keys, map2.keys);
5 голосов
/ 09 августа 2010

Обратите внимание, что std::map в C ++ является отсортированной структурой данных, в то время как ассоциативный массив в 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 не считается входным диапазоном, все алгоритмы диапазона не будут работать с этим.(Я не знаю, как это можно сделать в диапазоне ввода.)

0 голосов
/ 09 августа 2010

Вы можете получить ключи или значения из ассоциативного массива.

Чтобы получить пересечение значений, используйте 

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

...