Unit Data Structures
Once you have the map structure determined, you can move on to your unit data structures. There are 2 primary types of unit: mobile and stationary. Mobile units are the warriors, tanks, aircraft, and so on, that actually move around the map. The stationary units, on the other hand, are the buildings or building segments that do not move.
The common elements of mobile and stationary units include an identifier, a map location, an owner, and so on. These common elements may allow you to use object-oriented techniques and create a common ancestor class for both kind of units, but that depends on the game and game logic needs.
Stationary units generally do not move around the map. Once a stationary unit is placed on the map, it stays there until the player removes it or an enemy unit destroys it. This can simplify how you handle stationary units. Since there can only be one stationary unit per map cell, the map cell needs only to have a pointer to such a unit. If the pointer is nil (or null), then there is no stationary unit occupying that map cell.
Mobile units, unlike stationary units, can move from one map location to another. They also have another significant difference from stationary units: there is technically no limit to how many mobile units can be in a single map location. Thus, you will need to maintain a list of all mobile units per map cell. Depending on your game, it's possible you may want to limit mobile units so that they cannot "stack" in a single location. Or you may want to allow stacking only in locations with a special stationary unit (like a barracks). In this case, the map cell no longer needs to maintain a list, though the special stationary unit would.
These lists I keep mentioning for mobile units in the same map location or "inside" the same stationary unit, do not need to be incredibly complex. A simple linked list would likely work fine, though you might want to include some form of sorting to support game logic such as determining which unit in a location takes damage first or which units can "leave" first. To further simplify the lists, you could embed the list information (usually just a simple "next" pointer) in the actual unit data structure. If the unit can simultaneously be in multiple lists, however, you may want to use an actual list "container" class.
It's important, however, no matter how many different lists a particular unit is in, that units be stored in a centralized data structure. A one-dimensional array works quite well for this and even allows for certain performance benefits when processing all units of a particular type. The unit's position in the array also provides a very handy identifier for that unit. Thus, the "57th Infantry" unit could be found in array location 57. Additionally, if you're in a crunch for RAM, a 16-bit ID/array index takes up half the space of a 32-bit pointer to a structure.
You may have noticed that the unit data structures include the map location, and that the map cells have a list of units in those cells. This may seem redundant, but is nearly always necessary. If you are processing the map cell by cell, you will need a fast way to know which units are in each cell. Conversely, if you are processing all units you will need to know their location without searching the entire map. This puts a mild burden on the programmer to make sure that the units always have the correct location and that the map cells they travel through are correctly updated.
To provide a more concrete example of a unit data structure, Figure 3 shows a cut-down version of the troop structure used in Artifact. As you can see from Figure 3, a single troop can be in more than one list at a time, with the actual list information maintained in the troop data structure. The ID of a troop is simply its position in the single-dimensioned "Troops" array. The ID is stored in the troop structure even though it equals the array index because often it's necessary to know the troop's ID and you only have a pointer to the troop.
Figure 3: Artifact's Troop Structure