I have an array of map tiles (Tile.h). Each tile used to have a
Terrain object and also a pointer to a Creature* object. However, I've
realised a lot of properties of both terrain, creatures and later
items are the same so I've created an Entity object to be the parent
class of both my Terrain, Creature and Item classes.

Now in my Tile class I have a vector<Entity*> entities that holds a
vector of all the things that inhabit that particular tile. This means
I can have terrain, a creature and multiple items inhabiting the one
tile. I intend to use a flag (isPassable) to ensure there's only one
creature on it at a time. In my Creature.move() method I erase the
creatures pointer from the current tile's vector and add it to the
vector of the tile I'm moving to. All good.

Now, my problem is I don't know quite how to extract this data from
the Tile class from elsewhere in my progam when I need it. At times I
need to be able to pull the pointer to the occupying Creature if one
exists in the vector. I looked at the STL find() algo but have no idea
what to make the "value" field. If I go this route I need to find a
Creature object in a vector of pointers to Entities. Same with terrain
and other Entity subclasses.

Basically. If I make a vector of pointers to Entity classes (of which
may differ due to subclassing) how do I differentiate between them?

(1) Test all the entities pointed to to see if one is a Creature

(2) Keep a certain vector element for Creatures (perhaps the first or
second, you could do this for Terrain also assuming there is only one
Terrain per tile.  If there is no Creature you can put in a null
pointer, or a pointer to a null Creature.

It seems like it would be simpler to keep them separate always, for
example making a Tile class like the following.  I imagine something
like this is commonly used in roguelikes:

class Tile
{
        Terrain * m_pTerrain;
        Creature* m_pCreature;
        vector< Item* > m_Items;

Slightly more complex is that you can adopt an invariant that, if there
is a creature on the tile, it is referenced by cell 0 of the vector.
That way you only ever have to check cell 0.  The additional cost is
in the code that adds something to a tile; if it's a creature, you
check cell 0 for another creature (and yell about the one-creature-
per-tile rule if you find one), then move whatever's in cell 0 to
the end of the vector and replace it with the creature.

No problem so far.  But if you suspect there's a real design
problem here, I think I may have spotted it.

Simply put, what data structure "owns" the pointers to your
creatures?  Putting direct pointers to your creatures in the map
sounds like the map owns 'em.  That's reasonable, because you have
to be able to find the creature on a particular tile when the @
next to that tile attacks in its direction or when an area effect
somethingorother affects that tile.  

But you also have to be able to find that creature when it's that
creature's turn to act, so the schedule wants a pointer to the
creatures too.  And that creates a problem when it's time to
deallocate the creature, because if you drop it from the map and
the schedule still has a dangling pointer to it, then when its turn
comes up the schedule dereferences a dangling pointer - and gets
either the wrong object or a protection fault.

Anyway, the design question is this:  Do you have multiple
different data structures that all have pointers to creatures?  
And if so, how do you keep them synchronized to avoid segfaults
when you deallocate one?

Note this does not address your real question.  But your original
wording suggests you would look at the raw entity list anywhere in the
program you want to get a creature.  This is very bad practice.

Your decision to collapse all your entities into one vector<> should
not be readily apparent in the rest of your code (excluding any place
you genuinely want all Entities!)

foreach entity in list:
  Creature *foo = dynamic_cast<Creature *> entity;
  if (foo)
    return foo;

Monsters are, IMHO, logically held by the *map*.  Rather than
Tile *tile = map->getTile(x, y);
Creature *creature = tile->getCreature();
I prefer
Creature *creature = map->getCreature(x, y);

Now, you can always implement Map::getCreature(x, y) by passing down
to Tile::getCreature(), but in practice I find I usually have a
location which I want to query and a map, and not yet the Tile.

My first approximation of a roguelike (before premature optimization)
thus consists of the Map which contains a list of Creatures and Items
that lie on that map.  The Creatures and Items contain their x/y
cooridinates on the map.  This is surprisingly efficient for most
operations since total number of creatures and items is usually much
less than the number of map cells.  When you are iterating over all
map cells, such as for display, you don't look up items and creatures
once per cell, but do it as a second pass.
1) Draw all terrain cells
2) For each creature/item, draw it on top of the cell
This avoids the O(n^3) of the naive approach

The big problem with storing pointers on your Tiles is that you now
have redundant information about where your creatures are.  Your
creature's location is defined by which Tile points to them and also
by their (x,y) value.  This is just asking for synchronization issues
and lots of pain and suffering.

Particularly bad, IMHO, is that when you move a creature you have to
take it off the map or duplicate it on the map during the move.
Movement is so very common (teleportation, spawning, etc) I get very
worried if it is possible to screw it up.

My second approximation of a roguelike is usually to build a cache of
Creature * for each cell to speed up getCreature(x, y) calls.
Inevitably this results in ghost creatures or other peculiarities as
one screws up the programming.

In Jacob's Matrix I took all this a bit farther as I replaced all my
(x, y) cooridinates with a POS class.  This position class is where I
could then add getCreature(), etc.  So, if I had a creature "rat" and
wanted to get the creature one step up from him...
Creature *mobtonorth = rat->getPos().delta(0, 1).getCreature();

POS::delta(dx, dy) does the logical equivalent of (x+dx, y+dy) and
returns the result.  Note that these positions aren't Tile types, they
don't actually contain any data about the tile, they just hold the
(map, roomid, x, y, orient) tuple.

I'm now removing creatures and items from the tiles and using my map
"overlay" to display them. I'll also be expanding use of my Position()
class which I didn't realise was such a good idea when I created it.

The solution is to create a small set of functions which maintain the
data structure, and go through those for all cases when monsters move,
or are created or destroyed.  I did that for my game Lair of the Demon
Ape and had no problems from this source.

Of course we all know about the pitfalls of premature optimisation. but
having to search the list of monsters to determine what if any monster
is on a given tile would just cause me so much mental pain that I just
could not implement them that way, even knowing it would work fine!  
This is despite the fact that I had very little interest overall in
optimisation and efficiency when coding Lair...

Going aside into optimization: It seems to me that the best option in
terms of speed and simplicity would be a bijective hash-map. That way:

Using a monster* as a key, if the monster is on a tile, return a
pointer to that tile; otherwise return NULL.
Using a tile* as a key, if the tile has a monster, return a pointer to
that monster; otherwise return NULL.
Invariant: If monster* and tile* are in the BiMap, then BiMap.keyTile
(BiMap.keyMonster(monster*)) == monster*, and BiMap.keyMonster
(BiMap.keyTile(tile*)) == tile*.

Unfortunately as far as I am aware bijective maps aren't available in
most language's standard library, although Boost has a C++
implementation called Boost.Bimap, and Apache Commons provides Java
implementations for BidiMap, OrderedBidiMap and SortedBidiMap
interfaces, including one called a DualHashBidiMap.

In fact, I'm bored.  Here, I'll bang out some C code for it. If
you want to use it you get to debug it.

                                Bear

Note: beware bugs in the code below; I have not tested it.

-------------------------------------------------------

define ERASED -1  /* signal value */

typedef struct {
   void *key;
   int assoc;

   for (rehash = 0; rehash < map.keycount; rehash++){

      /* note the hash function needs to have the property
         that it never repeats a number on rehashes until
         it has tried 'em all from 0 to tablesize. Consult
         Knuth v3 if uncertain how to implement. */
      index = hash(key, rehash, map->tablesize);

      /* an unused, unerased entry means the key isn't stored. */
      if (map->table[index].key == NULL &&
          map->table[index].assoc != ERASED) return(NULL);
      else if (map->table[index].key == key){
         assert(map->table[map->table[index].assoc].assoc == index);
         return(map->table[map->table[index].assoc].key);
      }
      /* The other possible cases are erased entries and non-key
         entries. In both cases we do nothing and fall through
         to the next for-loop iteration. */
   } /* end for. */
   /* we get here only if the table is completely full,
      and we searched the whole thing and didn't find it. */
   return(NULL);

/* no public interface, only for internal use. */
void resizetable(bimap *map){
   int size = map->tablesize;
   int newsize = size;
   int index;
   bimapentry *newtable;
   bimap newmap;
   void *key1;
   void *key2;

   /* guarantees no "sensitive" sizes at which adding and deleting a
      single association can cause consecutive resizings. */
   while ((newsize > 8 * map->keycount) && newsize > 16) newsize /= 2;
   while ((newsize < 2 * map->keycount) || newsize < 16) newsize *= 2;

   if (newsize == size) return;

   newtable = (bimapentry*)calloc(newsize, sizeof(bimapentry));
   assert(newtable != NULL);
   newmap.keycount = 0;
   newmap.tablesize = newsize;
   newmap.table = newtable;
   for (index = 0; index < size; index++){      
      key1 = map->table[index].key;
      if (key1 != NULL){
         assert(map->table[index].assoc != ERASED);
         key2 = map->table[map->table[index].assoc].key;
         assert (map->table[map->table[index].assoc].assoc != ERASED;
         bimapinsert(key1, key2, &newmap);
      }
   }
   map->tablesize = newsize;
   map->keycount = newmap.keycount;
   free(map->table);
   map->table = newtable;

   do { index1 = hash(key1, rehash++, map->tablesize);
      } until (map->table[index1].key == NULL);
   rehash = 0;        
   do { index2 = hash(key2, rehash++, map->tablesize);
      } until (map->table[index2].key == NULL && index2 != index1);
   map->table[index1].key = key1;
   map->table[index2].key = key2;
   map->table[index1].assoc = key2;
   map->table[index2].assoc = key1;
   map->keycount += 2;

   rehash = 0;
   do { index2 = hash(key2, rehash++, map->tablesize);
      } until (map->table[index2].key == key2 ||
        map->table[index2].assoc == ERASED);

   /* key2 unindexed, hence no such association, cannot delete. */
   if (map->table[index2].assoc == ERASED) return;

   /* both indexed - check to make sure they're associated,
      and if so delete. */
   if (map->table[index1].assoc == index2 &&
       map->table[index2].assoc == index1){
      map->table[index1].assoc = ERASED;
      map->table[index2].assoc = ERASED;
      map->table[index1].key = NULL;
      map->table[index2].key = NULL;
      map->keycount -= 2;
      resizetable(map);
   }

void addmonstertotile(creature *monster, tile* tile, bimap *map){
   tile *checktile = tilelookup(monster, map);
   creature *checkmonster = creaturelookup(tile, map);

   /* monster and tile already associated - can't stand on the
      same square twice */
   if (checktile == tile) return;

   /* something else is standing there - fail. */
   if (checkmonster != NULL) return;

   /* monster and tile are unassociated - make association */
   else if (checktile == NULL)
      bimapinsert((void *)monster, (void *)tile, map);

   else { /* monster associated with different tile.
             remove from there and make new assoc. */
      bimapdelete((void *)monster, (void *)checktile, map);
      bimapinsert((void *)monster, (void *)tile, map);
   }

That's the simplest concept, but since Monster and Character were
separate classes, I couldn't make it quite so simple.  

So the reality ws the same idea but slightly more complex, because I
used two vectors, one for monsters and another one for character(s) and
pets, which were a subclass of Monster.  The ID was, IIRC, (index+1)
for monsters, and -(index+1) for characters/pets, leaving 0 for an
unoccupied square.  But it may have been some other encoding, I don't
recall exactly.

Obviously there are numerous ways to deal with this complication, none
obviously better than any other.

At the end of the day, though, when this was all wrapped up in a few
standard function calls, I had no need to think any more about any of
it.  And that's the important thing, whatever your solution.

Note: using a vector of monsters did introduce one interesting
'premature optimisation' bug - in some functions (always within a
single character or monster move) I passed a pointer to a Monster
instance, rather than an index.  This worked perfectly well right until
I implememted summoning, and my vector started getting reallocated from
time to time!  My clunky fix was to ensure that the capacity of the
vector before every turn exceeded its size by more than the maximum
number of monsters that might be summoned on a turn.

Another clunky choice was to mark dead monsters and leave them on the
vector.  Since the game had no going back and not a huge amount of
summons, the vector would not grow too much, and would be cleared and
generated from scratch at the start of each new level.

I'm not sure it's wrong to do things like this.  On one basis it may be
a positive indicator in that it means you know the general shape of
your final roguelike and don't have an open-ended project where you
write lots of code to cater for stuff that may never matter.  On the
downside, it reduces your options for re-use, though of course in a
roguelike it would be okay to occasionally call a clean-up function to
garbage-collect any dead monsters, so the above wouldn't really be a
roadblock.  

As monsters move around and become associated with new tiles, ERASED
entities build up in the table.  In fact, after every monster has
taken just eight steps, your table that's 30% occupied will have
only about 4% of its space both free and unerased.  After every
monster has taken 16 steps,  only 0.233% of the entries will be
free and unerased.  In practical terms, this means that shortly
after you start the level,  odds are there will be ZERO cells
both free and unerased.

This doesn't slow down insertions, successful lookups, or
successful deletions.

But because a lookup can only stop on an unerased empty node or a
match, the case where there is no match becomes expensive as
unerased empty nodes become scarce. Unsuccessful lookups once
the table is packed with erased entities take time linear in
the size of the table.

That means every time you check and find that a tile is empty (such
as right before moving a monster onto it, or to determine whether @
attacks or moves when the player mashes an arrow key) you're doing
an expensive operation.

For a better match between problem and data structure, this approach
should use open hashing rather than closed hashing.

Anyway I've got it planned out for the eventuality of needing to speed
it up; I'll just switch from a list to a dictionary (a.k.a. hash map).
The keys will be the objects' positions (a tuple with (x,y), but you
could just as easily use x*map_width+y). Then retrieving an object by
position will be trivial and blazing fast. But for now I don't need
it!