How maps are implemented in verse ?

Development Programming & Scripting Verse
, , ,
1

I have a small question about maps: how do they work, and how are they implemented internally? I didn’t find any information anywhere.

Are they simply c++ maps? If not ..

I’m trying to understand exactly when it is more efficient to use a map versus an array, without considering the different features that each data structure provides.

For example, I’m quite sure this is more optimized:

Values : []random_object = array{}
if (Value := Values[0]):
    ...

Than:

Values : [int]random_object = map{}
if (Value := Values[0]):
    ...

But what happens if the map key is a string? How the maps access to a specific key ? And how does that compare to using an array of tuple like this:

Values : []tuple(string, random_object) : array{}
for(Value : Values, Value(0) = "MyKey"):
   ...

So, to formalize my main questions:

  • How are maps implemented internally (hash tables, trees, …) compared to arrays?
  • What is the time complexity of accessing elements in an array versus a map?
  • What is the time complexity of searching an element in each structure?
  • What is the time complexity of adding or removing elements in an array versus a map?

Thank you in advance for the answer :grinning_face:

1 Like
2

not fully sure how it is either, but might assume its a bit similar to UE’s map, with some limitations? Would think arrays be fast when used nicely, wouldn’t worry too much about maps, unless you use a lot of them. would think its nice to use for some devices and how you find the elements in the map might get wild at some point and where it has to search or so I assume.

I just think it as like 2 arrays being on either side, removing the index to be other array instead.

https://dev.epicgames.com/documentation/en-us/fortnite/map-in-verse

tutorial, UE, where some of the visual scripting can help a little.

https://youtu.be/wmY17-a9xpc?t=1068

unsure if they have added more types since the last asked threads, compared to what was in the links above.

https://forums.unrealengine.com/t/how-use-the-verse-maps-with-container-types/1176627/3

1 Like
3

I can’t speak for all the answers but in my experience you should use maps when arrays get long and you need a specific element because the lookup time is much faster with a key, and it doesn’t need to copy the entire array.

2 Likes
4

Thank you for your answer, it helps to understand :slight_smile:

So if I understand correctly your answer, when we access to one value of an array, the full array is loaded in memory? but it’s not the case for the map? or your explaination was when we iterate over an array with a for?

That mean even if the" key" is an int, in some case it’s faster to use a map?

5

If you’re accessing one value in an array I think it just copies that one value, but for example if you have an array of PlayerStats (custom class) and you are receiving info to store that comes with an agent, you would have to for loop thru the array to match the agent and thus make a copy of each value until you find it, but with maps each agent can only possibly have one match for PlayerStats so it finds the value instantly

1 Like
6

Ok, thanks, it’s working just like I thought!