3D Tilebased engine problem

I''ve been working on a 3d tile based engine (looking for sort of a 3D X-com look and feel). I have the basic tile rendering all up and running and that''s fine. I''m running into some speed issues, though. I''m thinking I need to change the collection of items to be drawn. Basically, every tile is made up of 4 wall objects, a floor and a ceiling object. Any of these can, of course be NULL (meaning they don''t exist for the given tile). Previously, I simply looped through all my tiles and rendered whatever elements were present in a given tile (i.e., if there was a floor, I rendered it). Obviously, this begs for optimization, but it was a good starting point and worked fine when my wirld was 10x10x10 tiles (1000 tiles). The problem was, expanding to 100x100x10 slowed the engine down to about 3 FPS...for obvious reasons! For my test, the actual number of squares with elements was roughly 20,000 (so the other 80,000 squares were being checked for no reason). So I though I would optimize by creating a STL vector of only those elements that needed to be drawn. For example, the vector would contain not the squares, but pointers to the floor, the wall, etc. This means that instead of looping through 80,000 squares needlessly, I loop only through the 20,000 elements I know I want to draw. The problem is that, using this STL vector of pointers to my elements, performance is completely dead. The machine just seems to hang. Is 20,000 elements too many for a STL vector? I''m on VC++ 5.0 and know that STL compile times aren''t supposed to be great, but is there an actual performance issue as well?? I cannot imagine how looping through 20,000 elements can be slower than looping through 100,000. Would I be better off not using the STL vector and instead implementing the items as a linked list or something similar? I know that the push_back onto the vector will be slow, but this is only done once when loading all the elements. To actually access them, I use a for loop < vector.size and use at(count). Is there a problem with this? What I need is a fast method for mainly looping through them with the ability (not often used) to add or subtract items from the collection. Any ideas? Note: in my final version, maps probably won''t be that big (more like 50x50x5 or so), but I''d like to be able to tackle the bigger maps with the engine. All help appreciated! Best, Onnel