В связи с обнаружившейся страшной багой ищу какую-нибудь опенсорцную реализацию дека (ну или хотя бы очереди с итератором или оператором []).

Поиск по гуглу пока не дал ничего вразумительного (слишком распространённое название - deque), а свой огород городить банально не хватает времени... Конечно, если не найду, то придётся возиться с динамическими массивами, а у меня ещё дофига другой работы, причём довольно срочной.
Может, кто подскажет такую готовую библиотечку на С++ или С?

а какие основные плюсы использования дека ? (не довелось пользоваться ни разу - всегда вектора указателей хватало на всё)

Сообщение отредактировал Алексей1153 - 6.10.2010, 13:52

push/pop с двух сторон, итераторы. дек пошустрее вектора и лучше работает с памятью(это эмпирическое наблюдение, как они реализованы, я не смотрела).
не хочу переходить на вектор, он не чистит пространство, которое сожрал, пока не наступит нехватка памяти. а у меня объём данных может накапливаться весьма нехилый и скорость критична. а дек вроде получше себя ведёт. не замечала за ним жрачки памяти и тормозов особых.
конечно, в крайнем случае можно влепить вектор, но не радует такая перспектива. да и не везде можно перейти - у меня часто используется push/pop c головы.


Сообщение отредактировал Iron Bug - 6.10.2010, 14:03

ну, периодически можно совершать принудительную очистку. Например, если был поюзан объём данных больше заданной величины. Заодно и дефрагментация озу меньше будет.

За скорость не знаю. Но временно в обёртке можно класс-замену сделать и на векторе

Сообщение отредактировал Алексей1153 - 6.10.2010, 14:04

проблема заполнения памяти не в том, что много юзерских данных. а в том, что STL почему-то не освобождает её сразу даже когда вектор был очищен явным вызовом clear() и даже когда вектор вообще уже вышел из области видимости и теоретически должен быть удалён деструктором. выглядит это так: программа растёт в памяти пока не наступит какой-то неясный предел, после которого она разом всё очищает и начинает расти снова. это нехорошее поведение. про это я где-то читала статью, это непобедимо.
STL не предоставляет глобальные функции управления памятью. конечно, можно городить собственные аллокаторы или какие-то пулы, но это изврат и лишние затраты времени.
а проблема объёма и скорости доступа - это отдельный вопрос. ибо данные у меня сливаются не по накопленному объёму, а по загруженности процессора, ибо иначе теряется общая скорость, которая крайне критична (потеря даже одной миллисекунды может оказаться катастрофичной и дорого обойдётся). поэтому спящий в бэкграунде поток просыпается, когда проц не занят, и неторопясь сливает накопившиеся данные, пока его не прервёт система.

Сообщение отредактировал Iron Bug - 6.10.2010, 14:34

я не про clear, а про явную очистку объекта
m_vec=std::vector();
А clear() - он тем и удобен (в некоторых случаях), что не вызывает реаллокацию.

Нашла кое-какие опенсорцные STL библиотеки:
http://www.thefreecountry.com/sourcecode/cpp.shtml#stl
Сейчас буду смотреть, что они предоставляют.


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

да блин фантастика какая то ) Надо будет поэкспериментировать на досуге

Iron Bug,
есть еще реализация stl на сайте sgi и stlPort погугли на эту тему.
теоретически очередь от вектора отличается лишь началом идентичным концу вектора. т.е. быстрая вставка изЪятие и в начале и в конце. память выделяется страницами, и очереди нужен дополнительный указатель на страницу. еще двусторонняя очередь deque - единственные стандартный контейнер STL в котором итераторы могут стать недействительными при действительных указателях и ссылках, об этом Меерс пишет немного.

почему ты решила что очередь пошустрее вектора не пойму (

Вот простой код. Понаблюдай за распределением памяти при работе. (Естественно, речь про MS STL, чтобы никто не понял неправильно).



И можешь туда хоть clear вставлять, хоть любую "очистку". Не канает!
А если убрать слип (он вставлен для наглядности) и добавить объёма - то будет расти метров до 500 в памяти свободно. И потом разом чиститься, по неизвестно каким соображениям. Я же не просто так утверждаю, что такая "фича" существует, а потому что напоролась на неё при работе и ушла от активного использования векторов. плюс тормоза. это тоже при работе на больших объёмах было выявлено экспериментально.

Сообщение отредактировал Iron Bug - 6.10.2010, 15:06