Re: STL и С++

В идеале аналогично C-шным конструкциям. Обобщённые алгоритмы могут быть даже быстрее. Только нужно хорошо представлять, что происходит под капотом.

Re: STL и С++

А я не хорошо представляю, сколько я заплачу используя vector или list вместо голого массива. Ну скажем vector с 100000000 элементов типа double сколько лишнего Г в памяти оставит???

Re: STL и С++

Ну пару десятков байтов (всего). Вряд ли больше. vector<double> это обёртка над double[].

list конечно больше, это double-linked list, с указателями вперёд и назад на каждом элементе, со всеми вытекающими.

Есть хорошая книга Йосаттиса (Josuttis) про STL.

Re: STL и С++

А как она полностью называется если не секрет?

Re: STL и С++

http://anatolix.naumen.ru/Books/CPPSTL?v=dbl

Re^2: STL и С++

> А я не хорошо представляю, сколько я заплачу используя vector или list вместо голого массива. Ну скажем vector с 100000000 элементов типа double сколько лишнего Г в памяти оставит???

Количество этого г -- константа у листа, но линейно пропорционально у вектора.

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

Re: Re^2: STL и С++

> Количество этого г -- константа у листа, но линейно пропорционально у вектора.

что ты тут перепутал..

Re: Re^2: STL и С++

мне более интересны затраты в map<My_type,My_type1> по памяти и скорость поиска по ключу в дико большом массиве (по макимуму миллиард элементов)?

Re: Re^2: STL и С++

Книжку по STL почитать слабо? По памяти надо смотреть исходники тут может сильно зависеть от реализации, а по скорости будет гарантированно log(1000000000). Если хочешь быстрее, то надо использовать unordered_map и подбирать функцию хеширования.

Re: Re^2: STL и С++

>мне более интересны затраты в map<My_type,My_type1> по памяти и скорость поиска по ключу в дико большом массиве (по макимуму миллиард элементов)?

А оно в память вообще влезет? map это красно-черное сбалансированное дерево. В каждом узле три указателя (родитель, левый бранч и правый бранч) + булеан (цвет узла) + выравнивание. Не считая собственно ключа и данных.

Re: Re^2: STL и С++

Обычно чёрно-красное дерево используют. Поиск в среднем O(ln), т.е. довольно быстро. Правда миллиард элементов это гигабайты памяти. Я бы рассмотрел возможность хранения данных в чём то вроде B-дерева на диске, и подгружать нужное. Ну или обычная RDBMS.

И вообще, моё имхо — для экстремальных случаев лучше самому писать код, оптимизированный под конкретный случай, или, по крайней мере, писать код так, чтобы замена контейнера на самописный была как можно мене болезненной.

Re: Re^2: STL и С++

Нет не слабо? только пока я её читаю много времени пройдет а ТЗ родить надо в ближайшие дни... Спасибо за советы.

Re: Re^2: STL и С++

>> Количество этого г -- константа у листа, но линейно пропорционально у вектора.

> что ты тут перепутал..

Ну да, всё наоборот. Спать надо больше :)

Re: STL и С++

s/Йосаттис/Джосьютис/

Re: STL и С++

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

Re: STL и С++

Скоко несостоявшихся програмеров за живое-то задело...

Re: STL и С++

> Стоитли пользовать STL еслои нужно хранить и иметь быстрый достум к большому количеству (100000 и более) одинаковых объектов?

ИМХО как раз сотня тысяч -- барьер. Ниже STL пользоваться можно (и нужно), выше -- стОит подумать о рукоблудной оптимизации.

Начиная с миллионов главной проблемой будет фрагментация памяти либсишным умолчательным аллокатором. Использование кастомного аллокатора с STL контейнерами -- глупость (аллокатор должен быть привязан к алгоритму).

> Или лучше писать собственные контейнеры руководсьвуясь требованиями жесткой оптимизации?

Очевидно, да.

Если это -- боттлнек, то надо писАть самому. STL, как и всякая "серебряная пуля", не достаточно оптимальна в каждом конкретном случае.

Re: Re^2: STL и С++

> Обычно чёрно-красное дерево используют.

Вроде, теперь АВЛ?

Я вообще не понимаю области приложения чёрно-красных деревьев. Везде, где употребление балансировки на каждый чих оправдано, АВЛ деревья имеют преимущество.

> Я бы рассмотрел возможность хранения данных в чём то вроде B-дерева на диске, и подгружать нужное.

В таком случае нет нужды велосипед изобретать. Есть Берклиевские хэши, есть qdbm ( http://qdbm.sourceforge.net/ ) и есть Бернштейновские константные хэши ( http://www.corpit.ru/mjt/tinycdb.html )

> Ну или обычная RDBMS

Вот это ИМХО совершенно мимо -- типа, из пушки по воробьям.