On 3/23/12, Andrej Mitrovic <andrej.mitrov...@gmail.com> wrote: > Does someone have a map implementation that maintains the insertion > order of the keys?
Here's a sloppy implementation: module test; import std.stdio; import std.traits; template KeyType(V : V[K], K) if (isAssociativeArray!(V[K])) { alias K KeyType; } template ValueType(V : V[K], K) if (isAssociativeArray!(V[K])) { alias V ValueType; } template BaseElement(T : U[], U) { alias U BaseElement; } struct LinkedHash(T) if (isAssociativeArray!T) { alias KeyType!T Key; alias ValueType!T Value; static if (isArray!Value) template isValue(T) { enum bool isValue = (is(T == Value) || is(BaseElement!Value == T)); } else template isValue(T) { enum bool isValue = is(T == Value); } Value[] payload; size_t[Key] keyToIndex; Key[size_t] indexToKey; size_t lastIndex; size_t getNewIndex() { payload.length = payload.length + 1; return lastIndex++; } size_t* getKeyIndex(string key) { if (auto index = key in keyToIndex) return index; else return null; } Value opIndex(in Key key) { if (auto index = getKeyIndex(key)) return payload[*index]; else assert(0, "Key '" ~ key ~ "' not found."); } void opIndexAssign(V)(V value, Key key) if (isValue!V) { if (auto index = getKeyIndex(key)) payload[*index] = value; else { auto index = getNewIndex(); payload[index] = value; keyToIndex[key] = index; indexToKey[index] = key; } } void opIndexOpAssign(string op, V)(V value, Key key) if (isValue!V) { if (auto index = getKeyIndex(key)) mixin("payload[*index] " ~ op ~ "= value;"); else { auto index = getNewIndex(); mixin("payload[index] " ~ op ~ "= value;"); keyToIndex[key] = index; indexToKey[index] = key; } } int opApply(scope int delegate(ref Key, ref Value) dg) { foreach (index; 0 .. lastIndex) { auto result = dg(indexToKey[index], payload[index]); if (result) return result; } return 0; } } void main() { auto names = ["1", "2", "3", "4", "5", "6", "7", "8"]; LinkedHash!(string[string]) stringMap; foreach (name; names) stringMap[name] ~= "test"; foreach (key, val; stringMap) writefln("%s: %s", key, val); LinkedHash!(string[][string]) stringArrMap; stringArrMap["100"] = ["foo"]; stringArrMap["101"] ~= "bar"; foreach (name; names) stringArrMap[name] ~= "test"; foreach (key, val; stringArrMap) writefln("%s: %s", key, val); }