структура для хранения истории изменений (hash, map, list, ...)

[unkeep]

Здравствуйте. В моей модели данных есть _history  (ключ-элемент) в которую заносятся новые элементы. В  Submit  пробегаемся по истории и сохраняем элементы в базу В ТОМ ПОРЯДКЕ В КОТОРОМ ОНИ БЫЛИ ДОБАВЛЕНЫ В ИСТОРИЮ.
вопрос: в чём хранить _history?
1) изначально был QHash - но он я так понимаю не упорядочивает данные.
2) QMap сортирует по ключу. А надо тупо оставить тот порядок, в котором вставлялись элементы
3) QList порядок - ок, но нельзя достать нужный элемент по ключу, не пробегаясь по всему списку

Ещё варианты?
пока склоняюсь к Qlist+QHash. (в списке лежат id, QHash - хранит эл-ты c ключом id)

[Old]

пока склоняюсь к Qlist+QHash. (в списке лежат id, QHash - хранит эл-ты c ключом id)

Если нужен порядок и быстрый поиск, то вполне нормальное решение.
Правда я бы элементы хранил в QList (указатели на них), а в хеше хранил пару [id : указатель на элемент].

[unkeep]

Правда я бы элементы хранил в QList (указатели на них), а в хеше хранил пару [id : указатель на элемент].

да, пожалуй так будет лучше. спасибо.

жду ещё варианты, если не будет, завра закрою тему

[unkeep]

всё-таки всё-равно пробегаться нужно по списку.
когда из истории надо удалить, нужно и из QHash удалить и из Qlist. Не зная номера в списке, удалить по элементу можно только пробегаясь по списку. Ну или removeAll(указатель на эл-т), но тоже не быстро.

[Igors]

Правда я бы элементы хранил в QList (указатели на них), а в хеше хранил пару [id : указатель на элемент].

Адреса элементов в QList могут "уплыть"

- при удалении/вставке если sizeof(element) <= sizeof(void) (маловероятно но все же - напр QString)
- при std::sort/qSort
- при std::remove_if

Почти наверняка этого не будет, но заботиться об этом напрягает. Если связываться с хранением адресов то лучше std::map. Первоначальный вариант неплох, но для удаления придется использовать линейный поиск по id. Можно сделать одним QHash, только

- запоминать id первого элемента в переменной
- в элементе хранить id следующего (или адрес - по вкусу)

если не будет, завра закрою тему

Ваше право, но зачем? Разве тема кому-то мешает?  

[unkeep]

Можно сделать одним QHash, только

- запоминать id первого элемента в переменной
- в элементе хранить id следующего (или адрес - по вкусу)

1)при удалении тогда надо будет лезть в предыдущий элемент и задавать новый id следующего
2)в случаях хранения элементов не как истории, указатель на следующий элемент не нужен

а что насчёт QCache? в описании ничего не написано про порядок в нём, но думаю что как и QHash(

[Old]

Адреса элементов в QList могут "уплыть"

Придумываете.
В QList храним указатели на элементы, специально для вас в скобках написал.

[Fregloin]

QList+QHash часто использую,и да, указатели - тогда все быстро и компактно

[unkeep]

QList+QHash часто использую,и да, указатели - тогда все быстро и компактно

хорошо, есть список и хеш.

Код

C++ (Qt)
		QHash<IdType, TreeNode*> _history;
        QList <TreeNode*> _historyOrder;

1)получить эл-т

Код

C++ (Qt)
TreeNode* nodePtr = _history[id];

2)добавить

Код

C++ (Qt)
        _history.insert(newId, newNodePtr );
        _historyOrder.append(newNode);

3)удалить

Код

C++ (Qt)
            _history.remove(nodePtr->id);
            _historyOrder.removeOne(nodePtr);

removeOne(nodePtr) будет работать?

[Igors]

1)при удалении тогда надо будет лезть в предыдущий элемент и задавать новый id следующего
2)в случаях хранения элементов не как истории, указатель на следующий элемент не нужен

Да, ну и слазите в следующий/предыдущий - зато один контейнер на все-про все

Придумываете.
В QList храним указатели на элементы, специально для вас в скобках написал.

Здесь указатели, во втором тоже, где ж тогда сами тела? 

removeOne(nodePtr) будет работать?

Будет, но все равно это поиск перебором

[Old]

Здесь указатели, во втором тоже, где ж тогда сами тела?  

Внимание! В куче.
И владеть элементами должен QList.

[Igors]

Внимание! В куче.
И владеть элементами должен QList.

Не то чтобы "ошибка" или "плохо", но как-то слишком развесисто, кучеряво 

[Old]

Не то чтобы "ошибка" или "плохо"

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

как-то слишком развесисто, кучеряво  

Почему?
QList и так и так будет все хранить в куче развесисто и кучеряво.

[Old]

removeOne(nodePtr) будет работать?

Смотрите, при добавлении в хеш элемента с ключем, который уже есть в хеше, приведет к замене элемента для этого ключа. Т.е. ключ-значение будет по прежнему одно.
А вот в QList вы добавите еще один элемент.

[Old]

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