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

[kamre]

Похоже, что нужен аналог Java-класса LinkedHashMap.

Можно сразу взять готовый и навороченный boost::multi_index. Там можно у контейнера сразу несколько индексов иметь: по ключу id и по порядку добавления.

Или что-то свое сделать. Вроде бы вот так вполне должно работать:

Код:

template <typename K, typename V>
class Storage {
...
private:
    typedef std::list<V> List;
    typedef std::map<K, List::iterator> Map;
    Map m_map;
    List m_list;
};

Итераторы у std::list не инвалидируются при добавлении/удалении элементов. Поиск итератора по ключу делается за O(log n), а по итератору можно и значение вернуть, и удалить элемент из std::list за константное время.

[Igors]

Итераторы у std::list не инвалидируются при добавлении/удалении элементов. Поиск итератора по ключу делается за O(log n), а по итератору можно и значение вернуть, и удалить элемент из std::list за константное время.

Да, все четко. Вот как бы еще индекс элемента иметь (да, это др задача, просто у меня она есть  )

[unkeep]

в общем пока имею:

1) Qlist с указателями и QHash c [ид,указатель];

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

3) пробегаться по Qlist для поиска по значению(в данном случае это указатель) нужно только в одном случае, когда элемент сначала добавили, а потом удалили. Из хеша удаляется по ключу.

4) После того как делаем Sumbit и  по очереди из списка все элементы занеслись\изменились\удалились в базу, список чистится. Из хэша указатели удаляются во время прохода. Если на каком-то шаге возникла ошибка то выход из цикла и удаление из списка всех элементов до косячного.

работает нормально, скорость адекватная. Всем спасибо за советы.

[Alexandr Az]

Может тема уже для автора не актуальна, но для меня интересна.
Мозг сломал, как скрестить QLIst c QHash. Вообще не возможно. Нет, если задаста целью, то у меня есть пару вариантов, но это крик души, КРИК!

Столкнулся с проблемой автора.
Точно также думал реализовывать через дельту (историю изменений).

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

Во первых, для линейного поиска, не QList, однозначно не QList. Добавлю - не QList. Привыкли к нему, да уж. QVector вам в помощь. Да уж. Какой бы хреновый не был. Но он быстрее гораздо.

Дельту держать бессмысленно, проще держать два списка - один оригинальный, второй клиентский.
При обновлении чего либо, проще пробежаться по 100 тыс. записям и построить новый. Благо пробегание по 100 тыс. записей в QVecore (да даже в QLIst) детский лепет по сравнению с прорисовкой окна. Я повторюсь - НИЧЕГО НЕ СТОИТ! Вообще. Также вы должны понимать, что пробег по этим записям - это либо запись в БД, либо отмена - редкие операции, которые по времени не сопоставимы (с записью в БД и придумайте сами).

Я к чему это? Да я точно также, зная, что неправильно оптимизировать по производительности заранее (пусть сначала заработает, потом будем оптимизировать), не мог допустить простой вещи - как же это я буду перебирать записи для определения чего-то. Та это фигня. Нужно оптимальность, нужна производительность.
Автор, я за, меня тоже прёт от хорошего, красивого кода, который ещё к тому же и быстрый. Но перебор быстрей.

Анализ держания дельты - при любой операции (вставке, удалении) -  нужна её сортировка.

А идею автора не понял - перестройка всего и вся (всех листов и хешей)
Если автор простой код создал, хочу чтобы поделился как.

Цена Хеша и Листа, его заполнения, кол-во к нему обращений не стОит цене линейного перебора записей.

Замете, я беру граничные значение 100 тыч. записей. Граничней некуда. Вьюха  загнётся на 10 тыс.

[Igors]

При обновлении чего либо, проще пробежаться по 100 тыс. записям и построить новый. Благо пробегание по 100 тыс. записей в QVecore (да даже в QLIst) детский лепет по сравнению с прорисовкой окна. Я повторюсь - НИЧЕГО НЕ СТОИТ! Вообще. Также вы должны понимать, что пробег ...

Это легко проверить задав приличное N пробегов. Поэтому не стоит вводить людей в заблуждение. Вероятно Вы имели ввиду что такой пробег - операция разовая (или достаточно редкая). Тогда можно действовать "брутой форсой", с этим никто не спорит

[Alexandr Az]

Это легко проверить задав приличное N пробегов. Поэтому не стоит вводить людей в заблуждение. Вероятно Вы имели ввиду что такой пробег - операция разовая (или достаточно редкая). Тогда можно действовать "брутой форсой", с этим никто не спорит

Вы правы конечно, просто очень хотел усилить. Иногда незаметны другие ресурсоемкие операции, а свои видно на лицо, поэтому иногда акцент делается не на тех оптимизациях. Это как знаете - утверждение, которое я никогда не понимал: "Скриптовые языки программирования догнали по производительности нативные приложения". Как, как это может быть, любому готов был доказать, что это бред (благо, не пришлось). Пока не пришло прозрение - 1 мс на Си, или 30 мс на скрипте - для пользователя не важно. Они одинаково быстры. Он глазом дольше моргает. Он быстрее не среагирует. Так и тут, модель - это не та вещь, которая минует участие человека, она только для взаимодействия с пользователем и создана. Именно в этом контексте, операция перебора 100 тыс. записей ничего не стоит. Да и вообще, 100 тыс. Кому скажи, открой ексель со 100 тыс. записями, он у виска покрутит (если не ошибаюсь, там макс 65 тыс.). Но модель со 100 тыс. имеет почему то право на жизнь.

[unkeep]

В общем для этой ситуации может и действительно лучше использовать вектор, но вот другая ситуация из того же проекта:
поиск по дереву. Надо сохранять куда-то индексы и при каждом вызове вьюхой Data(index, Qt::BackgroundRole) проверять лежит ли он в результатах (кроме того надо оставить порядок, чтобы можно было двигаться по результатам вверх-вниз) А это операция повторяется куда чаще чем выборочное изменение модели в предыдущем примере. Записей где-то около 5тыс. В результах поиска допустим будет 3тыс индексов. Таким образом грубо говоря 5*3тыс проходов. Тут бы я не рискнул список использовать.
вот собственно тема http://www.prog.org.ru/index.php?topic=25659.msg183709#msg183709