Вариант 1:
Статический приватный QMap/QHash< long, CBase* > в который объект записывается в конструкторе и удаляется в деструкторе. Если возможна многопоточность, то статический же QReadWriteLock для защиты.

Вариант 2:
Если тип и генерация id не важны, то можно как mObjectID использовать сам указатель, т.е. size_t(this).

Почему б этот map и не считать глобальным списком объектов.

Про то, что объекты могут и не попадать в список вы не говорили в первом посте и это совершенно не очевидно.

map.value( mObjectID );
Доступ через функцию, а не на прямую, что бы локером защитить при надобности.

Вариантов много, один из - что-то вроде ещё одной коллекции QMap< type, list >.

type - здесь идентификатор типа. Им может служить type_info* (у классов должны быть виртуальные методы, например деструктор) или MetaTypeId или ещё что-то что придумаете и что сумете для нужного класса получать.

list - собственно список нужного типа. Если нужен и с известным классом доступ по индексу можно тот же QMap/QHash< long, CBase* > использовать. Если не нужно можно QList< CBase * > (или другую коллекцию смотря какие действия критичны по времени выполнения).

P.S. Вынужден признать, что не помню, должно ли type_info правильно работать в конструкторе базового класса. Надо смотреть по стандарту, где заполняется виртуальная таблица.

QMap< type, QList< CBase* > >;

C++ (Qt)
static QMap< type, QList< CBase* > > typedMap 
 
QList< CBase* >* list = GetTypeList( typeID )
{
    if ( !typedMap.contains( typeID ) )
    {
         typedMap.insert( typeID, QList< CBase* >() );
    }
    return &typedMap.value( typeID );
}
 
CBase* GetFirstTypedObject( type typeID )
{
    QList< CBase* >* list = GetTypeList( typeID );
    return list.first();
}
 
CBase* GetNextTypedObject( CBase* obj )
{
    if ( obj == 0 )
    {
        return 0;
    }
    QList< CBase* >* list = GetTypeList( typeOf( obj ) );
    int index = list.indexOf( obj );
    if ( ( index == -1 ) || ( ( index+1 ) == list.length() ) )
    {
         return 0;
    }
    else
    {
        return list.at( index + 1 );
    }
}

ну и т.п.

Я и не говорю, что надо делать так, я лишь предлагаю тему для размышления.
Знаете проект только вы и никто другой дать вам готовый ответ не сможет.

Зато GetNthTypedObject будет выполняться за O(1) (ну точнее O(log(type))*O(1)).
А в той реализации с указателями наверняка за O(n).
Next() и Prev() напротив выполняться за O(n) вместо O(1) в старой реализации. То есть в одном выигрываем, в другом проигрываем.
Вы же так и не сказали какие из функций более критичны по времени.

Потому что так всё устроенно. Нельзя все 3: последовательный доступ (prev-next), произвольный доступ (по индексу) и добавление/удаление сделать очень быстро (за O(1)). Ну и как четвёртый параметр можно взять простоту реализации.
Поэтому надо посмотреть на имеющуюся программу и оценить, что же приоритетно.
При этом надо учесть, что скажем цикл по всему множеству легко реализуется как через последовательный доступ, так и через индексный, поэтому такие циклы можно переписать на более  быстрый вариант в данной реализации.

Ну и в итоге:
1) если у нас важен индексный доступ: самое простое - List, Vector или банальный массив.
O(1)      O(n)      O(n)      элементарно в реализации
2) если важен последовательный доступ и удаление: двунаправленный список, как уже и реализованно.
O(n)      O(1)      O(1)      элементарно в реализации
3) если важен и последовательный и индексный доступ - комбинируем первый и второй вариант:
O(1)      O(1)      O(n)      чуть сложнее в реализации
4) если одинаково важна скорость по всем параметрам - список из 2 + дерево
O(log(n))   O(1)      O(log(n))   сложно в реализации
Деревьев много различных видов. Для гарантированной логорифмичности подойдут, скажем, RB- и AVL- деревья.

Никогда не понимал всех этих "O" Требования к скорости невысоки, логарифм прекрасно устраивает - не было бы перебора. Приоритеты надежность и удобство использования

А кто такие "ортогональные хэши" ?
Наверное лучше прикидывать структуры напр в std::. Посмотрим простой вариант

C++ (Qt)
typedef long TID;
std::map <TID, CBase *> theMapID;  // поиск объекта по ID
 
typedef std::vector <TID> TVecID;
TVecID theVecAllID;  // вектор всех объектов
 
std::map <type, TVecID *>  theMapTypeID;  // поиск по типу объекта
 

Так нет проблем с прямым доступом по индексу как ко всем объектам, так и конкретного типа. А вот получить индекс объекта - увы, перебором. Также теперешний код  содержит много сотен вызовов GetNextObject(obj) и, конечно, хотелось бы их не трогать - но так не получается и придется менять на итератор.

Изменения затеяны для развязки зависимостей между объектами. Пример

C++ (Qt)
class MyObj {
  ...
  MyTarget * mTarget;
};
 

Это вызывает массу проблем с delete/undo и load/save. Задумка сделать так

C++ (Qt)
MyTarget * GetDependentObject(ID(), DEPENDENCY_TYPE_1);
size_t NumDependentObjects(ID(), DEPENDENCY_TYPE_1);
 

ID объектов неуклонно растут. delete реально удаляет объект, но не вычеркивает его из theMapID, а просто устванавливает value() = NULL. Undo создает новый объект (со старым ID) и устанавливает value() на него. Ну это пока "так хочется"