Simple solution is to use a free list and, of course, remove all components when requesting to remove an entity. Reuse the memory of an entity as an index to the next free entity when it is removed from the list (without actually removing it from the array or shuffling it around). This diagram should clarify the idea:

Code example:

struct Entity
{
    union Data
    {
         ...
         int next_free;
    };
    Data data;
};

struct Ecs
{
    ...
    vector<Entity> entities;
    int free_entity; // set to -1 initially
};   

int Ecs::insert_entity(const Entity& entity)
{
     if (free_entity != -1)
     {
          // If there's a free entity index available,
          // pop it from the free list and overwrite the
          // entity at that index.
          const int index = free_entity;
          free_entity = entities[free_entity].data.next_free;
          entities[index] = entity;
     }
     else
     {
          // Otherwise insert a new entity.
          entities.push_back(entity);
     }
}

void Ecs::erase(int entity_index)
{
     // Push the entity index to the free list.
     entities[entity_index].data.next_free = free_entity;
     free_entity = entity_index;
}

This will keep your indices from becoming invalidated, allow rapid reclaiming of vacant spaces, and keep your insertion and removal dirt cheap constant-time operations, and all without creating any new data structure or anything like that.

Simple solution is to use a free list and, of course, remove all components when requesting to remove an entity. Reuse the memory of an entity as an index to the next free entity when it is removed from the list (without actually removing it from the array or shuffling it around). This diagram should clarify the idea:

Code example:

struct Entity
{
    union Data
    {
         ...
         int next_free;
    };
    Data data;
};

struct Ecs
{
    ...
    vector<Entity> entities;
    int free_entity; // set to -1 initially
};   

int Ecs::insert_entity(const Entity& entity)
{
     if (free_entity != -1)
     {
          // If there's a free entity index available,
          // pop it from the free list and overwrite the
          // entity at that index.
          const int index = free_entity;
          free_entity = entities[free_entity].data.next_free;
          entities[index] = entity;
          return index;
     }
     else
     {
          // Otherwise insert a new entity.
          entities.push_back(entity);
          return entities.size() - 1;
     }
}

void Ecs::erase_entity(int entity_index)
{
     // Push the entity index to the free list.
     entities[entity_index].data.next_free = free_entity;
     free_entity = entity_index;
}

This will keep your indices from becoming invalidated, allow rapid reclaiming of vacant spaces, and keep your insertion and removal dirt cheap constant-time operations, and all without creating any new data structure or anything like that.

Of course whenever you have an array with "holes", it can start wasting memory if there's lot of vacant spaces where the client removed a whole bunch of things and never bothered to insert anything new. A way to mitigate that is to use a random-access sequence composed of blocks containing, say, 16 entities each. If a block becomes entirely empty, you can free its memory and replace it with a null pointer, to be reallocated later on if the client ever wants to reclaim the range of indices the block previously represented. That has the downside of slower random-access (a little more arithmetic to access the nth element), but does a better job of freeing memory as people remove elements from it. It's also compatible with the free list approach.