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

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

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

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

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

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

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

Re^2: STL и С++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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