shared_ptr doesn't seem to work because that is reference counted.

Or of course simply a weak_ptr.

shared_ptr and weak_ptr are entirely the wrong mechanisms here -- both express a particular flavor of ownership (potential ownership, in the case of weak_ptr), but the marines discussed here don't 'own' their target. Any pointer they do hold to their current target should be raw (raw pointers are the preferred mechanism for non-owning semantics) and probably const-appropriate; above all, it should be viewed not even as an implementation detail of the AI, but an implementation detail of a particular optimization (e.g. "its likely that the thing I was interested in last frame still interests me.")

It sounds to me that the root of OPs problem here is that entities effectively become tightly-coupled when they interact. It sounds like there's direct-dealing between the sides, mediated by some AI/logic processes that are coupled to one or both of the participants. A solution is to move towards having more autonomous agents who make observations about their environment, and then perform some action as a result (possibly spawning a new autonomous agent) that achieves what they want ("fire my gun at my enemy"), but its hands off between the marine and his target.

@Ravyne

You mean the target-pointer shouldn't persist between frames, but the unit should decide every frame which one is the current target?

It depends -- if you engineer your system to support it, then you can keep it around between frames and possibly use it as an avenue to short-circuit the AI routine ("If my target hasn't been destroyed, just keep attacking it, don't consider other options"). But you're right that you can't keep it if there's no mechanism to identify when an object has been removed from play, and simply deleting that object from memory doesn't cut it. Using weak_ptr would work, but its not a good solution for reasons I'll get into below. Another solution would be for destroyed objects to post a message, and that game entities would subscribe to that message, whereupon they could clear the pointer. Another solution would be to have a system of entity 'slots' that persistently occupy the same memory location, combined with an enemy ID -- you could keep the pointer around between frames, along with its ID, and check whether the slot still corresponds to that ID. Yet another would be to temporarily exist in a destroyed state for some extra frames, so that everyone has a chance to notice its been destroyed (in practice, this can work well as there's often an animation cycle associated with the object or entity being destroyed/killed).

Also, although I'm using the word 'pointer' I don't strictly mean a memory address; It could be any kind of handle that resolves to a specific object reliably.

The trouble OP has is that things become tightly coupled when they interact. The result of this is that it creates this false appearance of ownership semantics -- to be clear, the need for shared ownership semantics in the system OP describes is real, but the ownership is necessitated by the implementation rather than the requirements. Ultimately this is a code-smell.

shared_ptr and weak_ptr are quite thin -- thin enough that you should instinctively reach for them when they fulfill your requirements -- but they are not so thin that one should consider using them to compensate for design flaws. Its implementation dependent, but if you ever look into the guts of how share_ptr and make_shared work, you can get yourself into situations in which just one extant weak_ptr (and no extant shared_ptr) disallows a significant block of memory from being freed because the control block is not deallocated until there is no extant weak_ptr (as when make_shared decides to embed the allocation block into the control block for objects up to an implementation-defined size) -- its always the case that the object is deconstructed and that the resources it holds are released when the shared count reaches 0, but its not always the case that the memory for the object itself is freed. I believe its common that this kind of combined control/allocation block can be as large as 32 or 64 bytes, which can add up quickly. Furthermore, use of make_shared (but not share_ptr) necessarily implies that the objects are non-contiguous and can't be used with pooled allocation (because you can't use a custom deleter) which could disallow significant optimizations in other parts of the code.

I would go with an event approach.

I like this approach too - usually if you want to perform a specific reaction to something happening (like the target dying) then event based solutions are hard to beat. Your original brute force search approach is akin to polling for a certain state to occur, while if your units register with the target when they acquire it, then they can get easily notified when the target gets deleted. You could make this part of the units themselves, or have a mediated subsystem in between that would manage the monitoring of the objects and perform the notifications - either way, you just want to be notified when the event occurs, not poll the status to see if something already happened!

shared_ptr doesn't seem to work because that is reference counted.
The other option I thought of was creating a new pointer type (unless one exists), where anytime I deconstruct a copy of the pointer, it has maintainted a list of people pointing to it and sets all pointers in the list to NULL.

Or of course simply a weak_ptr.

shared_ptr and weak_ptr are entirely the wrong mechanisms here -- both express a particular flavor of ownership (potential ownership, in the case of weak_ptr), but the marines discussed here don't 'own' their target. Any pointer they do hold to their current target should be raw (raw pointers are the preferred mechanism for non-owning semantics) and probably const-appropriate.

A weak_ptr expresses no ownership at all; it expresses using an object that may have a shorter lifetime than you.
It's also the exact "unless one exists" class that the OP was about to reinvent.

A raw-pointer expresses that the used-object's lifetime is longer than the user-object's lifetime. In this case, if the building can be deleted before the marines, then a raw-pointer isn't valid (without reinventing some kind of notification system, a la weak_ptr). Yeah, maybe the building/marines shouldn't be getting deleted at all, but that's another kettle of fish!