Структура данных указателей, которые могут удалять (T*), добавлять (T*) и выполнять итерацию очень быстро (хэш не достаточно быстр)

Question

Я хочу структуру, которая может:-

1. быстро добавить новый элемент (элемент всегда указатель, а не данные)
2. быстро удалить существующий элемент, используя только ту информацию, на которую указывает указатель.
   (B * b1, B * b2, тест b1==b2 напрямую)
   Удаление имеет тенденцию происходить в случайном порядке (повсюду).
   Пользовательские звонки remove(T*),
3. итерация быстро

Структура данных, которая соответствует критериям, кажется, HashSet,
Тем не мение, Hashset страдает эти недостатки:

1. Для добавления элемента требуется хеш-функция, которая работает медленно.
2. Добавление элемента: необходим доступ к какому-то управлению корзиной, еще более медленному.
3. Удаление элемента страдает тем же симптомом, что и добавление.
4. Итерация страдает от доступа к корзине O(size of basket)и нужно проехать пройти пустую корзину.

Я проверил это (n = от 500 до 1000), это очень медленно, чем массив.

Вопрос

Какая структура данных может поддерживать это требование?

Мое плохое решение

Единственное решение, которое я нашел, - хранить индекс непосредственно в элементе.
Это быстро и соответствует всем критериям, но, похоже, взломать.

С этим взломом есть еще одно странное ограничение.
-> Определенный элемент может содержаться только в одной DataStructure.

Если я хочу больше, взлом становится более сложным.

class B{
    int indexSlot1_;
    public: static int& indexSlot1(B* b){ return b->indexSlot1_; }
    //... provide additional slots if required ....
}
Datastructure<B*,&B::indexSlot1> database1;
Datastructure<B*,&B::indexSlot2> database2;