V: Keep map in defined order

[chr-stoev]

Is it possible to get a map implementation where the order keys are defined in will be kept when you loop over them?

What did you do?

m := {
    'foo': 1
    'bar': 2
    'tar': 3
    'baz': 4
}

for key, val in m {
    println(key + ': ' + val.str())
}

What happened?

foo: 1
bar: 2
baz: 4
tar: 3

What did you expect?

foo: 1
bar: 2
tar: 3
baz: 4

[radare]

define "order". hashtables by itself dont have any order, they are optimized for accessing the keys not for iterating them. you may sort the keys before iterating them. or create a map that does that, but it is not the default/standard thing

On 16 Oct 2019, at 16:27, chr-stoev [e-mail] wrote:

Is it possible to get a map implementation where the order keys are defined in will be kept when you loop over them?

What did you do?

m := {
'foo': 1
'bar': 2
'tar': 3
'baz': 4
}

for key, val in m {
println(key + ': ' + val.str())
}
What happened?

foo: 1
bar: 2
baz: 4
tar: 3
What did you expect?

foo: 1
bar: 2
tar: 3
baz: 4
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub https://github.com/vlang/v/issues/2376?email_source=notifications&email_token=AAG75FQLWJX5TJIFGGPS6YLQO4QDJA5CNFSM4JBMKW42YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HSFYNEQ, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAG75FXMXTADTB74ATDOAXTQO4QDJANCNFSM4JBMKW4Q.

[chr-stoev]

define "order"

As I try to show with the example, the order should be the order I add the entries. If I add tar to the map before baz then I would expect to get tar before baz when I iterate over the map.

hashtables by itself dont have any order, they are optimized for accessing the keys not for iterating them. you may sort the keys before iterating them. or create a map that does that, but it is not the default/standard thing

I know. That is why I am requesting an implementation that has that feature. E.g. look at arrays in PHP.

Also as far as I can tell, map in V is currently implemented as a tree structure, not a hash map. But I might be wrong

[medvednikov]

Indeed, they are trees right now.

A separate ordered map type will be available, like in C++.

[nedpals]

Maps are now ordered. Should we close this?

foo: 1
bar: 2
tar: 3
baz: 4

Playground: https://devbits.app/play/1Nmf2DTIPGzN

[radare]

Why’s that do we have unordered maps somewhere? Performance wise unordered maps are important in many situations

On 26 Apr 2020, at 11:35, Ned Palacios [e-mail] wrote:


Maps are now ordered. Should we close this?

foo: 1
bar: 2
tar: 3
baz: 4
Playground: https://devbits.app/play/1Nmf2DTIPGzN

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or unsubscribe.

[ka-weihe]

@radare We do not have an unordered map, but the map is still a hashmap (O(1) get, set, and delete). The map was changed to be ordered for the same reason python dictionaries are now ordered. TLDR: it is faster and more memory efficient. But... this is only an implementation detail for now @nedpals, no one should rely on the order of the map. We will, as @medvednikov said, have a "separate ordered map type" or at some point make the map officially "ordered". For now, it is best to not make any restrictions to the implementation of map, it should just be whatever is fastest.

[radare]

Ok sgtm

On 4 May 2020, at 15:27, ka-weihe [e-mail] wrote:


@radare We do not have an unordered map, but the map is still a hashmap (O(1) get, set and delete). The map was changed to be ordered for the same reason python dictionaries are now ordered. TLDR: it is faster and more memory efficent. But... this is only an implementation detail for now, no one should rely on the order of the map.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or unsubscribe.