Russian Qt Forum

Добрый день

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

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

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ну и т.п.

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

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

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

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

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

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

я так понимаю 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). Осталось прикрутить ортогональные хэши к группам типов, я не прав?

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