C++ HashMap or Map in terms of time complexity and memory space

I've to store a sparse matrix in which the elements are just '1' or '2' (represent BlueCar and RedCar). I know the size of the matrix only at runtime after reading a .csv with comma separated values. I have to implement an algorithm to move cars:

• blue ones move downward;
• red ones move rightward;
• there is a turn in which all the blue ones move and a turn to move all the red ones (move of a car can happen only if the destination is empty).

So the algorithm must:

• cycle over the data structure (to select red cars or blue cars to move)
• must find if the destination position is free. Free means 'position does not exist', because I want to save only the existing cars associated with their coordinates.
• must update coordinates of moving cars or delete the old position and insert the new one.

I have to choose the best data structure to save cars and coordinates that is efficient in terms of time complexity and memory usage.

To be detailed, in the next steps of the implementation I have to deal with openMP and MPI.

It's better to use a single structure with key-value pair (1) or one structure per car type (2) in which I need only to save coordinates?

(1) I thought to a std::map<std::pair<row,column>,value> or std::unordered_map. I don't know what to choose, but I know that map access is O(logN) and unordered is O(1). I think that the elements in the unordered map can be easily ordered because I insert them in a ordered way when the file is read. When the car moves I have to change its coordinates that are the key of the map/unordered_map. But now the question is: it's better the change the key (if it's possible) or to delete and insert a new key-value pair?

(2) If in this situation the 2nd case is better for me than the 1st one, which data structure can I implement?