C++, декрементирование multimap::end(), ошибка в коде

> this->_timestamps.insert(/*--_timestamps.end(),*/ std::pair<time_t, unsigned int>(current_time, key_hash));

А самый первый элемент _timestamps случайно не в этом месте вставляется? Если до втсавки первого элемента котейнера сделать --_timestamps.end(), получится невалидный итератор, что и может привести к segmentation fault. Или же память ранее попорчена, утилита valgrind в помощь.

А вообще судя по приведённому коду у меня возникло подозрение, что вместо multimap здесь можно импользовать vector или deque - насколько я понимаю вставка происходит исключительно в конец. А для выбора элемента использовать бинарный поиск std::lower_bound & Co. Средняя алгоритмическая сложность будет не хуже чем у multimap, (правда в случае vector иногда может происходить переаллокация буфера, но суммарные затраты на все переаллокации будут O(числа элементов)).

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

Если же последовательное итерирование не нужно, то можно вообще воспользоваться де-факто стандартным __gnu_cxx::hash_map (или std::unordered_multimap в режиме С++0x) тогда и выборка элемента будет происходить за O(1) (на практике)

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

По поводу остального - нужно последовательное итерирование, а multimap я выбрал именно изза того что новый элемент всегда вставляеться упорядоченным, он не всегда идет именно в конец(в 10-15% случаев не в конец), в будущем я его переделаю на односвязный список без всякого stl, пока это beta версия софта для которой не особо важно быстродействие.

Если не сложно поясните пожалуйста еще один момент, при детальном рассмотрении map'а/multimap'а, обнаружил что занесение элемета с помощью m.insert(pair<type,type>(key, value) приводит к 3м(!) копированиям value, почему это не оптимизировано в libstd++? Имхо, в идеале должно быть одно копирование, непосредственно в узел дерева. Допустим 2е - изза отсутствия оптимизации копирования временной переменной pair<...>, а 3е то откуда? Пытался найти код в /usr/include/c++/4.1.2/bits/stl_map.h, но там insert перевызывает метод insert у внутренней переменной _M_t_ типа __Rep_type определение которого я не нашел...

Забыл указать C++09 и класса не описанные в C++03 стандарте не рассматриваются по причине необходимости маскимальной переносимости

Про вставку с подсказкой я почитал http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html и видимо таки если вставка веротянее всего произойдёт в конец, следует в качестве подсказки указывать прямо end(), не умеьшая его на единицу.

И хотя здесь (стандрата под рукой нет сейчас) http://www.sgi.com/tech/stl/MultipleSortedAssociativeContainer.html написано что hint должен быть "nonsingular iterator", вероятно под nonsingular имеется ввиду не то что end() передавать нельзя, а то что итератор просто должен быть корректным и по тому же контейнеру, в который происходит вставка. Вообще возможность передачи end() в качетсве подсказки мне представляется логичной - для контейнера с N элементами есть N+1 возможная позиция для вставки, что как раз соотвествует N+1 корректному итератору, поэтому пердача итератора i соответсвует предполагаемой позиции вставки _перед_ i, и для всавки в конец следует передавать именно end().

Относительно копирований. _M_insert для типа _Rb_tree (=_Rep_type) можно изучить в stl_tree.h, там создаётся узел дерева и вызывается _Rb_tree_insert_and_rebalance для него, посмотреть на который можно только в исходниках библиотеки libstdс++, но не в хедерах. Я уже было стал грешить на него, но отладчик показал, что подстава оказалась в совершенно неожиданном месте:

in std::pair<int, MyC>::pair

in std::pair<int const, MyC>::pair<int, MyC>

и 3-е копирование непосредственно в узел.

то есть вначале создатся пара <int, MyC>, которая потом преобразуется в тип значения контейнера <int const, MyC>. Отличие только в const. Явное указание этого const в коде как m.insert(pair<const int, MyC>(1,MyC())) уменьшило число копирований до ожидаемых 2х.

У меня были похожие проблемы с лишними копированиями при использованиии ассоциативных контейнеров. Если для value копирование дважды вместо одного раза неприемлемо (но для умолчального значения value() копирование всё же тривиально), а key - легковесный, то можно написать m[key]=wanted_value, что эклвивальентно добавлению пары (wanted_key, value()) с последующей заменой второго члена пары с помощью полученного итератора на wanted_value. Сложность при этом не ухудшится. Если же копирование нетривиально для key или для умолчального value(), то приходится просто хранить key или value отдельно, а в контейнер засовывать лишь указатели на них (с переопределённыим операторами сравнения в случае key). В общем криво очень всё тут, в интерфейсе этих контейнеров явно не хватает insert(key&, value&).

По поводу односвязного списка. Односвязный сортированный список - вещь довольно странная имхо, ибо по ассимтотическим характеристикам не лучше сортированного массива. Вставка и там и там O(n), точнее даже O(расстояние от конца до места вставки) (ибо в списке придётся искать место для вставки, а в массиве сдвигать элементы). А поиск элемента за O(log N) список при этом не обеспечивает. Да, сдвиг массива работает дольше чем поиск элемента, но и список не безгрешен - выделение/освобождение памяти из кучи под каждый элемент довольно сильно загрузит менеджер. И итерирование по массиву эффективней оказывается. Так что тут сравнивать надо, что будет эффективней в конкретном случае.