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 