Can the order in associative array change when keys are not midified?

[H. S. Teoh via Digitalmars-d-learn]

On Thu, Jan 01, 2015 at 04:17:39PM +0000, Idan Arye via Digitalmars-d-learn wrote:
[...]
> My use case is that I have a large AA where the values are numbers and
> the keys are strings, and I need to send it over network again and
> again. The values constantly change but the keys should remain the
> same(after an initial initialization process), so I don't want to
> always have to send the keys, which compose the larger part of the
> AA's size. If the order is fixed as long as the keys are fixed I can
> cache the keys order and send only the values(without having to sort
> them each time).

It's risky to rely on the order of values returned by an AA. It's
implementation-dependent. Although currently we don't see any reason for
ever changing the order, that doesn't guarantee that a future
implementation with a new, innovative lookup algorithm, won't change it,
since the spec says that AA's are inherently unordered.

If you need consistent ordering of values, you probably want a different
data structure, like an ordered map, instead of an AA. Alternatively,
you can implement your own wrapper around the built-in AA's that keeps
track of insertion order, something like this:

	struct MyAA(K,V) {
		static struct WrappedValue {
			WrappedValue* next;
			V value;
			alias value this;
		}
		private WrappedValue[K] impl;
		WrappedValue* first;

		void opIndexAssign(V value, K key) {
			auto val = WrappedValue(value);
			val.next = first;
			impl[key] = val;
			first = &impl[key];
		}

		ref V opIndex(K key) {
			return impl[key].value;
		}

		@property auto byValue() {
			static struct Range {
				WrappedValue* current;
				@property bool empty() {
					return current is null;
				}
				@property auto front() {
					return current.value;
				}
				void popFront() {
					current = current.next;
				}
			}
			return Range(first);
		}

		... // other AA methods here
	}

Some care would have to be taken care of if you need to support deleting
AA keys (you have to relink stuff, so potentially you want a
doubly-linked list instead of a singly-linked list here). But basically,
something along these lines should give you an AA-like container that
guarantees iteration order no matter what the underlying AA
implementation is.


T

-- 
"No, John.  I want formats that are actually useful, rather than over-featured megaliths that address all questions by piling on ridiculous internal links in forms which are hideously over-complex." -- Simon St. Laurent on xml-dev