What data structure to choose for counting elements?

Question

C++ / C#

Hello! Given - an array of structures responsible for information about transport stops - type of transport, route of transport, etc. It is necessary for a specific transport to display the number of the route with the largest stops. I understand roughly how to do this (take each route and go through the array looking for matches and incrementing the match count for each route), but I can’t figure out which SD to use for this - there are thoughts about a binary search tree, or a table hash (I tend to first). Can you suggest what structure would be the most optimal for this task? Thanks

Answer 1

You need std::map or std::unordered_map. You don't have to write the data structure yourself.
The first will be the search tree, the second will be the hashtable.
The search tree is guaranteed to run consistently fast. The hash table will run faster, but if you're not lucky, it can take a very long time. But it is preferable, in my opinion, the table.
As a key, use the pair {Transport type, route number}. The value is the stop counter.
You also need another map of transport type-> std::set or std::unordered_set of route numbers.
To build structures, hit all stops once and increment the counter in the first structure. Add a route to the transport in the second structure.
To find the answer, loop through all the set elements from the second map - these are all routes. See in the first map how many stops this route has and choose the maximum.