Замена базового класса

[Igors]

Добрый день

Затеял изменения и хочу переделать базовый класс написанный (не мной) очень давно и работающий по сей день

Код

C++ (Qt)
struct CBase {
 long mObjectID:   // уникальное ID объекта
 
 CBase * mPrev;   // предыдущий объект (все объекты связаны в список)
 CBase * mNext;   // следующий объект 
 
 CBase * mPrevTyped;   // предыдущий объект того же типа (унаследованного от CBase)
 CBase * mNextTyped;   // следующий объект  того же типа
 };
 

Требуемая ф-циональность
- находить объект по ID - сейчас, увы, это решается перебором всего списка 
- находить/вставлять/удалять объект по "общему" индексу
- находить/вставлять/удалять объект по индексу объектов такого типа  (сейчас головы/хвосты этих списков собраны в отдельном векторе)

Какие есть соображения ?

Спасибо

[LisandreL]

- находить объект по ID - сейчас, увы, это решается перебором всего списка

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

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

[Igors]

Если тип и генерация id не важны..

Важны т.к. указатель не уникален для delete/undo

Статический приватный QMap/QHash< long, CBase* > в который объект записывается в конструкторе и удаляется в деструкторе.

Как говорит молодежь "решение должно быть комплексным" Пристроить map (или др. контейнер) для быстрого поиска по ID я могу и сейчас, но по существу это не пере-планирование класса а заплатка, решающая одну проблему, да и то плохо. Зарегистрировав ID в конструкторе мы еще не добавили объект в "списки" (или в то что вместо них в новом классе) и получаем "неконсистентность" организации. объектов. Заметим что для локального объекта (созданного на стеке) пока неясно - стоит ли разрешать его регистрацию или нет.

[LisandreL]

Зарегистрировав ID в конструкторе мы еще не добавили объект в "списки" (или в то что вместо них в новом классе) и получаем "неконсистентность" организации. объектов.

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

Заметим что для локального объекта (созданного на стеке) пока неясно - стоит ли разрешать его регистрацию или нет.

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

[Igors]

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

А как из нее брать по индексам ? И где взять счетчик(и) объектов нужного типа ?

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

Я этого и сейчас не утверждаю (самому неясно ). Просто здравый смысл говорит что локальному объекту там делать нечего.

Общее замечание: требуется тщательное обдумывание, т.к. класс базовый для довольно большого проекта. По-быстрому пристегнуть что-то прочитанное в Ассыстант - ну конечно хорошо если бы так получилось, но оно так получаться не обязано.

[LisandreL]

А как из нее брать по индексам ?

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

И где взять счетчик(и) объектов нужного типа ?

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

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

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

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

[Igors]

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

А как из нее брать по индексам ?

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

Так это поиск по ID, индекс здесь ни при чем. Примеры использования индексов (псевдокод)

Код

C++ (Qt)
CBase * obj = GetFirstTypedObject(TYPE_1);
while (obj) {
 // do something with obj
 obj = GetNextTypedObject(obj);
}
....
CBase * obj = GetNthTypedObject(TYPE_1);
if (obj != NULL) ..
...
InsertTypedObject(newObj, thePosition);
 

[LisandreL]

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 );
    }
}

ну и т.п.

[Igors]

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

Код

C++ (Qt)
CBase* GetNextTypedObject( CBase* obj )
{
  ...
    int index = list.indexOf( obj );
  ...
}

Согласитесь что теперешняя реализация (которая, как я вижу, была изначально написана на Pascal а потом (абы-как) переведена на С) бьет Ваш "модерн" по всем статьям - ведь перескочить на следующий элемент списка - ну максимум 4-5 машинных команд, а у Вас indexOf может съесть много тысяч. Не торопитесь.

[LisandreL]

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

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

Согласитесь что теперешняя реализация (которая, как я вижу, была изначально написана на Pascal а потом (абы-как) переведена на С) бьет Ваш "модерн" по всем статьям - ведь перескочить на следующий элемент списка - ну максимум 4-5 машинных команд, а у Вас indexOf может съесть много тысяч. Не торопитесь.

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

[Igors]

Знаете проект только вы и никто другой дать вам готовый ответ не сможет.

А я готового ответа и не прошу, интересуюсь как бы Вы решали

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

Ну а почему хоть какие-то вызовы должны выполняться "грубой силой"? Можно спорить что там лучше (типа QMap или QHash) но никак не решать линейным перебором. Так что "диалектика" здесь ни при чем.

[LisandreL]

Ну а почему хоть какие-то вызовы должны выполняться "грубой силой"?

Потому что так всё устроенно. Нельзя все 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- деревья.

[brankovic]

O(log(n))   O(1)      O(log(n))   сложно в реализации

я так понимаю boost::multi_index можно превратить в что-то такое, задав 2 ordered-индекса и один random access (этими не пользовался). Будет O(log(n)) на деревянные поиски/вставки/удаления, O(1) на индексный поиск и O(1) на итерацию.

Кстати, а почему нельзя все 3 сделать за O(1)? hash_map даёт на поиск (грубо говоря) O(1), на удаление O(1), при этом в нём есть последовательная итерация за O(1). Осталось прикрутить ортогональные хэши к группам типов, я не прав?

[Igors]

Никогда не понимал всех этих "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() на него. Ну это пока "так хочется"