StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Note that <code>std::map</code> in C++ is a <em>sorted</em> data structure, while an associative array in D is <em>unordered</em>. <code>std.algorithm.setIntersection</code> assumes a <em>sorted</em> range, so you can't use this function until you've converted the associative array into a sorted range, e.g. (<a href="http://www.ideone.com/be76N" rel="noreferrer">result</a>)</p> <pre><code>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))); } </code></pre> <p>But this method is inefficient — it takes O(N log N) to sort a range.</p> <p>A more efficient method is like to write your own intersection routine, which only takes O(N) (<a href="http://www.ideone.com/3qaSt" rel="noreferrer">result</a>):</p> <pre><code>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, " "); } </code></pre> <p>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.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload