LINUX.ORG.RU

STL и С++


0

0

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

anonymous

Re: STL и С++

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

Legioner ★★★★★ ()
Ответ на: Re: STL и С++ от Legioner

Re: STL и С++

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

anonymous ()
Ответ на: Re: STL и С++ от anonymous

Re: STL и С++

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

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

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

Legioner ★★★★★ ()
Ответ на: Re: STL и С++ от anonymous

Re^2: STL и С++

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

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

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

gaa ★★ ()
Ответ на: Re^2: STL и С++ от gaa

Re: Re^2: STL и С++

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

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

dilmah ★★★★★ ()
Ответ на: Re: Re^2: STL и С++ от dilmah

Re: Re^2: STL и С++

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

anonymous ()
Ответ на: Re: Re^2: STL и С++ от anonymous

Re: Re^2: STL и С++

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

Reset ★★★★★ ()
Ответ на: Re: Re^2: STL и С++ от anonymous

Re: Re^2: STL и С++

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

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

Absurd ★★★ ()
Ответ на: Re: Re^2: STL и С++ от anonymous

Re: Re^2: STL и С++

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

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

Legioner ★★★★★ ()
Ответ на: Re: Re^2: STL и С++ от Reset

Re: Re^2: STL и С++

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

anonymous ()
Ответ на: Re: Re^2: STL и С++ от dilmah

Re: Re^2: STL и С++

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

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

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

gaa ★★ ()
Ответ на: Re: STL и С++ от Legioner

Re: STL и С++

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

anonymous ()

Re: STL и С++

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

jtootf ★★★★★ ()
Ответ на: Re: STL и С++ от jtootf

Re: STL и С++

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

anonymous ()

Re: STL и С++

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

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

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

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

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

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

Die-Hard ★★★★★ ()
Ответ на: Re: Re^2: STL и С++ от Legioner

Re: Re^2: STL и С++

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

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

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

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

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

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

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

Die-Hard ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.