www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Can the order in associative array change when keys are not midified?

reply "Idan Arye" <GenericNPC gmail.com> writes:
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?
Jan 01 2015
next sibling parent reply Andrej Mitrovic via Digitalmars-d-learn writes:
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
Jan 01 2015
parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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
Jan 01 2015
next sibling parent reply "Idan Arye" <GenericNPC gmail.com> writes:
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).
Jan 01 2015
next sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
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
Jan 01 2015
prev sibling parent reply Andrej Mitrovic via Digitalmars-d-learn writes:
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
Jan 01 2015
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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]).
Jan 01 2015
parent reply Andrej Mitrovic via Digitalmars-d-learn writes:
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.
Jan 01 2015
next sibling parent "Laeeth Isharc" <Laeeth.nospam nospam-laeeth.com> writes:
On Thursday, 1 January 2015 at 18:58:04 UTC, Andrej Mitrovic via 
Digitalmars-d-learn wrote:

 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.


V good point.

This is one of those small frictions that cumulatively raises the 
cost of adoption for newcomers who are not by nature hackers but 
want to get stuff done, and yet could be valuable members of the 
D community over time.  For whatever reason, there is some 
resistance for many people to ask for help in a forum and it is 
easy to be overwhelmed and give up.  Modern people don't have 
much tolerance for pain, even though that's an essential part of 
learning and being a developer.   And compare python where you 
have OrderedDict and a search will find many examples of how to 
use it.

I agree with comments about readability of library functions, but 
maybe also worth extending hints and tips for common patterns / 
code fragments.

What is the protocol for contributing to the wiki?  Can one just 
edit it ?
Jan 01 2015
prev sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
On Thursday, 1 January 2015 at 18:58:04 UTC, Andrej Mitrovic via 
Digitalmars-d-learn wrote:

 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.


Will do. Going to submit some documentation PRs anyway.
Jan 02 2015
prev sibling parent Andrej Mitrovic via Digitalmars-d-learn writes:
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.
Jan 01 2015
prev sibling next sibling parent ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
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,=20
 without changing the keys, can I assume that the order won't=20
 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.
Jan 01 2015
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/1/15 7:32 AM, Idan Arye 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?


I would never make that assumption. An AA is free to rehash at any time, 
for whatever reason.

What I would say is that you can probably safely assume an AA will 
iterate in the same order as long as it hasn't been changed.

If you need guaranteed ordering, use an array or a RedBlackTree.

-Steve
Jan 02 2015