Menu
Firstly, finding an item in a very small vector can easily be faster than the same thing in a map, because all the memory in a vector is always contiguous (and so plays more nicely with computers' caches and such things), and the number of comparisons needed to find something in a vector might be about the same as for ...
The map solution results in "Time Limit Exceeded on Test 3", whereas the set solution results in "Time Limit Exceeded on Test 2", which means that Test 2 is such that the map solution works faster on it than the set solution.
A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.
Maps are 'fast enough' but not brilliant for some cases. Try to analyze what is the structure of objects you need to store. If the fields are fixed I'd recommend not to use nested maps. At all.
In the interpreter for my experimental programming language I have a symbol table. Each symbol consists of a name and a value (the value can be e.g.: of type string, int, function, etc.).
At first I represented the table with a vector and iterated through the symbols checking if the given symbol name fitted.
Then I though using a map, in my case map<string,symbol>, would be better than iterating through the vector all the time but:
It's a bit hard to explain this part but I'll try.
If a variable is retrieved the first time in a program in my language, of course its position in the symbol table has to be found (using vector now). If I would iterate through the vector every time the line gets executed (think of a loop), it would be terribly slow (as it currently is, nearly as slow as microsoft's batch).
So I could use a map to retrieve the variable: SymbolTable[ myVar.Name ]
But think of the following: If the variable, still using vector, is found the first time, I can store its exact integer position in the vector with it. That means: The next time it is needed, my interpreter knows that it has been "cached" and doesn't search the symbol table for it but does something like SymbolTable.at( myVar.CachedPosition ).
Now my (rather hard?) question:
Should I use a vector for the symbol table together with caching the position of the variable in the vector?
Should I rather use a map? Why? How fast is the [] operator?
Should I use something completely different?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With