If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?

On 1/1/15, Idan Arye via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:
> If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?

Associative arrays are not ordered at all.

See the first note here: http://dlang.org/hash-map.html

On Thursday, 1 January 2015 at 13:13:10 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:
> On 1/1/15, Idan Arye via Digitalmars-d-learn
> <digitalmars-d-learn@puremagic.com> wrote:
>> If I have an associative array and I only modify it's values,
>> without changing the keys, can I assume that the order won't
>> change?
>
> Associative arrays are not ordered at all.
>
> See the first note here: http://dlang.org/hash-map.html

The order is unspecified, but an iteration must iterate in *some* order. The question (if I've understood it correctly), is whether that order of iteration changes when the keys aren't changed.

The spec doesn't say anything about this, although I would expect in practice that the order will not change.

I've added a bug to track this omission from the spec: https://issues.dlang.org/show_bug.cgi?id=13923

On Thursday, 1 January 2015 at 13:39:57 UTC, Peter Alexander wrote:
> On Thursday, 1 January 2015 at 13:13:10 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:
>> On 1/1/15, Idan Arye via Digitalmars-d-learn
>> <digitalmars-d-learn@puremagic.com> wrote:
>>> If I have an associative array and I only modify it's values,
>>> without changing the keys, can I assume that the order won't
>>> change?
>>
>> Associative arrays are not ordered at all.
>>
>> See the first note here: http://dlang.org/hash-map.html
>
> The order is unspecified, but an iteration must iterate in *some* order. The question (if I've understood it correctly), is whether that order of iteration changes when the keys aren't changed.
>
> The spec doesn't say anything about this, although I would expect in practice that the order will not change.
>
> I've added a bug to track this omission from the spec: https://issues.dlang.org/show_bug.cgi?id=13923

That's right.

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

On 1/1/15, Peter Alexander via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:
> The order is unspecified, but an iteration must iterate in *some* order. The question (if I've understood it correctly), is whether that order of iteration changes when the keys aren't changed.

Hmm yeah, that definitely wasn't ever specified. But remember that there is also a .rehash() method. It's a bit tricky to work with AAs for sure..

> The spec doesn't say anything about this, although I would expect in practice that the order will not change.
>
> I've added a bug to track this omission from the spec: https://issues.dlang.org/show_bug.cgi?id=13923

Thanks.

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

On 1/1/15, H. S. Teoh via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:
> If you need consistent ordering of values, you probably want a different data structure, like an ordered map

This one works nicely on D1, I'd imagine the D2 port works just the same:

https://github.com/SiegeLord/Tango-D2/blob/d2port/tango/util/container/SortedMap.d

On Thursday, 1 January 2015 at 18:08:52 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:
> On 1/1/15, H. S. Teoh via Digitalmars-d-learn
> <digitalmars-d-learn@puremagic.com> wrote:
>> If you need consistent ordering of values, you probably want a different
>> data structure, like an ordered map
>
> This one works nicely on D1, I'd imagine the D2 port works just the same:
>
> https://github.com/SiegeLord/Tango-D2/blob/d2port/tango/util/container/SortedMap.d

You could implement an OrderedMap!(Key, Value) via RedBlackTree!(Tuple!(Key, Value), (a,b) => a[0] < b[0]).

On 1/1/15, Tobias Pankrath via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:
> You could implement an OrderedMap!(Key, Value) via
> RedBlackTree!(Tuple!(Key, Value), (a,b) => a[0] < b[0]).

We could add this as an alias into Phobos or perhaps as just a documentation line on the website.

On Thu, 01 Jan 2015 12:32:33 +0000
Idan Arye via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com>
wrote:

> If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?
please, don't: this is implementation-specific. druntime code can change (for example, by tracking access frequency and regrouping frequently accesed keys into clusters for better cache utilising), and your finely crafted code will start to fail mysteriously.

it is safe to assume that after ANY change in AA *everything* is changed there. you'd better augment AA with some "change buffer" or use different data structure for your task.