std::map

[Alezis]

Мне нужно было создать ас. контейнер в котором ключом есть int а самим значением какой-то объект, котрый представляет собой структуру с некоторыми данными параметрами. Объектов в среднем что то вроде 1млн. , затраты памяти пока ужасные но этого пока не касаемся. map сортирует всё по убыванию моего ключа, это меня устраивает. Вопрос вот в чем. Когда я начинаю обработку этих объектов , то уж больно "долго" идёт эта обработка. Счас уточню. Долго относительно того же алгоритма только на CSharp где место map используется Hashtable. Она тоже сортирует по убыванию ключа что мне и надо. Так вот CSharp работает допустим 8 сек. ТО С++ около 25. Ошибки в алгоритме нет. просто мот сам цикл долго ходит. он типа такой.

Код: Выделить всё

Obj* o; 
for(iterator = _map.begin();!(iterator == _map.end());iterator++)
{
 std::pair<int,Obj*> s = *iterator;
 o = s.second;
....
}

Как мот лучше огранизовать перебор.

Далее.Если я ставлю hash_map
Всё не отсортировано, но это меня тоже устраивает.
Но теперь как организовать перебор потому что насколько я понимаю
через iterator не покатит.

[Kolinus]

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

[Absurd]

Если добавления происходят редко, то можно использовать std::vector< std: air<int, ValType> > , затем поддерживать все это дело в отсортированном состоянии и искать бинарным поиском. Можешь взять из Loki класс Loki::AssocVector, он все это делает автоматически.

[Eugie]

Относительно hash_map. Он а) хранит элементы в отсортированном виде (один из параметров конструктора включает предикат сортировки) и б) содержит внутренний тип iterator, аналогично другим контейнерам STL. Надо только иметь в виду, что в разных версиях STL hash-контейнеры могут и не включаться в std namespace, например, в Visual C++ .NET 2003 требуется указывать дополнительно using namespace <stdext>

[Alezis]

мда... чёто тут попробовал и list и hash и map. Всё как то медленно пашет. Просто когда загоняю в контейнер значения (1000000 штук) они только могут удалятся, но не добавляться. Т.е. после обработки всего контейнера, оттуда например надо удалить 300000 штук. т.е. остаётся 700000. Ну и так далее в итоге должно оставаться около 5000 сиз 1 миллиона. я вот думаю забить на stl и сделать с помощью обычных массивов. Хотя мот просто алгоритм жрёт много.

[WinMain]

Если массив отсортирован по какому-то ключевому параметру, то поиск в нём осуществляется не последовательным перебором, а методом деления пополам (т.н. бинарный поиск). Для поиска значения в массиве из 1.000.000 элементов потребуется не более 20 итераций. Ещё для организации большого массива данных и поиска значений по индексу используют бинарное дерево сортировки. Об этом отдельный разговор. Контейнеры STL свми по себе довольно медленные, поэтому неудивительно, что у тебя программа тормозит и большой расход памяти наблюдается.

[Absurd]

А нафиг тебе в память такие большие объемы загружать? Используй B* деревья и грузи их по кусочкам