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

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

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

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

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

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

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

я не про 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,
попробовал твой пример в linux - память выше 5М не растет и очищается периодически. может все же это конкретная реализация так себя ведет.
конечно вектор при таком использовании будет оч медленно заполнятся - каждый push_back - куча лишних операций по перераспределению ,выделению, копированию.

я пишу конкретно про MS STL
в линюксе проблем вообще нет. ну или редко и их быстро правят а мелкософт пока разродится с новой студией с этим патчем - сто лет пройдёт.

я чет сразу не увидел
хм...
MS STL - понятно, ну тут как говорится доверяй но проверяй. )

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

просто об этом надо заранее думать, вот и всё. Резервировать же можно кусками

Iron Bug, выполнил предложенный код. У меня на борту всего 640 метров озу, в момент начала запуска теста занято было 560 (смотрю диспетчером). Во время выполнения меняется от 560 до 562 , иногда прыгало до 568 - у меня ещё радива играет. Ничего не тормозит и память не жрётся, своп тоже молчит. Пробую в студии №6 , кстати.

Щас попробую в 2008

- во время запуска 631 , скачет 632... 635, без свопа, без тормозов

правда, это всё в дебаге было. Имеет значение ?

в релизе тоже память не жрётся

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


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

собственно, раз там всё равно баги, я планирую помаленьку перейти на опенсорцный STL и не парить себе моск. так оно надёжнее и ещё минус одна зависимость от мелкософта, который я терпеть не могу

та ну, неспортивно

шутка.

Я немного чайник в этом. Тема крайне заинтересовала (есть проект, жутко страдающий из-за низкой эффективности). Пара вопросов: как именно перейти с MS STL на Open-Source STL? Чем они в плане возможностей будут отличаться в контексте данной проблемы?

я пока не утверждала, что опенсорцный STL эффективнее (хотя скорее всего так оно и есть). но если в MS STL жёсткие баги, то использовать его просто нельзя. тут не до эффективности, когда прога валится с access violation.
сейчас вот как раз пытаюсь собрать один STL.

Блин. Где собрать? Как подключить? Внешне отличаться он не будет?

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

Ура! Я собрала STLport с бустом под студией 2005.

Пишу маленькую инструкцию:

Сборка STLport + Boost компилятором MSVC 2005

(я собирала с версиями STLport 5.2.1, Boost 1.44.0, MSVS 2005 SP1)

1. Качаем последнюю версию буста тут. Разворачиваем куда-либо. Допустим, пускай это будет папка c:/src/boost_1_44_0. Оттуда же качаем уже собранный bjam и помещаем bjam.exe в корневую папку с бустом (вообще, он поставляется прямо с бустом и можно его самостоятельно собрать, запустив bootstrap в корневом каталоге буста).

2. Качаем последнюю версию STLport тут. Разворачиваем куда-либо. Допустим, пускай это будет папка c:/src/STLport-5.2.1.

3. Собираем буст с заголовками STLPort:
3.1. В каталоге c:/src/boost_1_44_0/tools/build/v2 правим файл user-config.jam. Добавляем строку с указанием расположения заголовочных файлов STLport:

Пробел перед завершающим символом ";" обязателен! (блок code убивает пробелы - так что вставляю в quote)
(Буст добавляет букву p к именам библиотек, которая означает, что данная сборка собрала с STLport. Так что сборка безопасна, если у вас собраны другие варианты библиотеки).

3.2. Из корневого каталога буста (там уже лежит bjam.exe) запускаем bjam c нужными нам параметрами. Например, для полной сборки буста это будет такая строка:

bjam stdlib=stlport --toolset=msvc-8.0 --build-dir="папка, где будут храниться временные файлы во время сборки" --build-type=complete "путь, куда буст будет складывать готовые файлы"

Обратите внимание, добавлена опция stdlib=stlport - это и есть указание использовать наш STLport.
Запускаем bjam и идём отдыхать: собирается он долго и нудно. Чтобы было быстрее, можете добавить в строку опцию -jN, где N - количество ядер CPU у вас на компе - тогда он будет распараллеливать процесс сборки. Можете запустить bjam --help и посмотреть другие параметры: например, можно указать, куда конкретно складывать заголовки и библиотеки, и прочие такие полезные опции.

4. Собираем сам STLport:
4.1. Открываем консоль (cmd). Запускаем установку переменных окружения MSVC 2005. Если студия установлена в стандартном варианте, с 32-битной платформой, то это будет выглядеть так:

"С:\Program Files\Microsoft Visual Studio 8\VC\bin\vcvars32.bat"

4.2. Далее НЕ ВЫХОДЯ из консоли, перемещаемcя в ней к нашей папке с STL (cd c:/src/STLport-5.2.1) и в этой папке выполняем следующую команду:

configure msvc8 --with-static-rtl

Я собирала со статической линковкой стандартных библиотек. Можете использовать динамическую, заменив опцию на --with-dynamic-rtl.
4.3. НЕ ВЫХОДЯ из консоли, переходим в каталог c:/src/STLport-5.2.1/build/lib и запускаем там команду

nmake /fmsvc.mak install

Ждём, когда скомпилится. Детально про сборку и возможности проверки собранного STLport можно почитать в файле c:/src/STLport-5.2.1/doc/README.msvc (правда, там опечатка с указанием опции компилятора - он задаётся без префикса -c).

5. Открываем студию и прописываем в студии пути для нашего STL: меню Tools->Options. Настройка VC++ Directories:
Platform: Win32, Show directories for: Include files - добавить ПЕРЕД всеми стандартными путями путь c:/src/STLport-5.2.1/stlport
Platform: Win32, Show directories for: Library files - добавить ПЕРЕД всеми стандартными путями путь c:/src/STLport-5.2.1/lib

Собственно, всё.

Код править не нужно, насколько я понимаю. У меня deque заработал без проблем. Просто перекомпиляция.

P.S. Теоретически, можно собирать и без буста.

P.P.S. Если вдруг кто-то захочет собрать и что-то вдруг не будет собираться - сообщайте. Я могла что-то упустить, хотя вроде бы всё написала и порядок не перепутала.

Чуть поторопилась я с вариантом сборки STLport c бустом: он не собирается с ходу с новыми бустами. Однако, это не мешает собирать буст с самим STLport и писать проги с использованием STLport и boost.
Сам STLport из буста юзает только type_traits, это не критичная фича. Так, сбоку бантик. В новых бустах там не много изменилось: пару заголовков переместили. Может, попозже напишу патч для STL, чтобы он собирался с новым бустом, если будет время.
Инструкцию чуть подправила по этому поводу, в остальном вроде всё правильно. Только что собрала другую версию буста с STL. Сейчас буду пересобирать и проверять свои глобальные проекты, которые активно юзают разные фичи STL.

А я тем временем собрала то же самое под линём, с gcc. Скорее из любопытства, чем по необходимости. Пока ещё не проверяла компиляцию с проектами, но буст уже собрался. Надо сказать, что в венде эту связку собрать - это ещё цветочки! Под линём косяков с нестковкой буста и STLport было больше, а документации практически нет. Если эта химия заработает и кому-то понадобится вдруг - могу накатать аналогичную телегу и для линя. Хотя это геморно весьма: там стопицот мелких настроек там и тут. Но если заработает - я погоняю тесты на скорость. Про венду в инете пишут, что с STLPort проги быстрее робят. Надо проверить и под линюксом, ради интереса.

В общем, под вендой у меня всё заработало.
Есть некоторые тонкости, которые сразу просечь трудновато.
Во-первых, практически вся конфигурация STLport фактически задаётся в файле STLport-x.x.x/stlport/stl/config/user_condig.h.
Во-вторых, чтобы эта настройка через файл подействовала, надо обязательно пересобрать STLport с опцией clean:

Без clean он тупо переименовывает библиотеки и в итоге получается бардак.
Со статической/динамической линковкой я разобралась, но это дофига информации. Вроде там всё логично, но весьма трудно для изложения в единой связке и долго. Поэтому если будут какие вопросы - пишите сюда, попробую ответить.

Аццкая жесть или как под вендой заставить STLport выводить в консоль русские буквы (ну или какие-либо, которые в коде присустствуют) в UTF-8 (убила целый день, чтобы просечь, как это сделать!). Суть была в том, чтобы не переписывать кучу проектов под STLport iostreams.

Частично стащено отсюда, поправлены ошибки и выдернута часть только для венды (для линя и так всё работает, без особого выпендрёжа). Честно говоря, вдаваться в тонкости и разбираться во всех хитросплетениях локалей (а это самое моё ненавистное место в программах!) мне не хотелось. Это решение маленькое, возможно, не самое оптимальное, но оно РАБОТАЕТ.


Используется просто вызовом

_wsetlocale(LC_ALL,L"russian");
configure_locale();

перед началом работы. Собирается с опциями использования юникода.
Вывод стандартный:

wcout << L"Русский текст";