О деталях и возможностях реализации <vector>

	Комментарий модератора
	Эта тема выделена из темы: Работа с векторами без использования STL и библиотеки <vector>

Сообщение от hoggy если он не будет защищен внутренними проверками. я б такую халтуру вообще бы не принял.

Ну это уже в зависимости от зависимости. Примерно в 50% случаев внутренняя проверка только дает оверхед.
из кода AnsiString (той которая в комплекте C++ Builder)
Так и сидит в инклюде который идет в поставке с таким комментарием.
в подавляющем большинстве случаев разумно вот так:

0

Сообщение от Renji Потому что в кеше содержатся не четырехкилобайтовые страницы,

Это в L1. А кроме него есть еще L2 и L3

Добавлено через 2 минуты

Сообщение от Renji Если для вас шесть мегабайт - серьезная трата, отнесите свой ПК в музей наконец

Считаем дальше. В каждом задании ну на вскидку 1000 дверей и 1000 окон, которые имеют ручки и т.п. А так же 500 комнат. В каждой комнате еще куча мебели у которой тоже есть дверцы и т.д. и т.п. И в каждом ящике этой мебели еще может что то лежать, причем тоже составное. итого если в 16GB оверхеда из за этих 16 байт уместимся считай повезло.

Добавлено через 9 минут

Сообщение от Renji тормозит реалок списка страниц

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

Добавлено через 22 минуты

Сообщение от Renji Размер страницы большой - просто дикий оверхед по памяти

Ну надеюсь понимаете что такие массивы (со страничной организацией) они не для накопления связей между объектами используются. А к примеру для накопления буфера вертексов в редакторе. Размер вертекса по нынешним временам от 32 байт. если сделать страничку к примеру 128 вертексов то и оверхед небольшой (не более 4Kb на буффер, что для современных 3D моделей мелочи), и вставка быстрая и без протормозок на копирование самих вертексов при ресайзе. И даже при ресайзе массива страниц последовательности из 1 млн вертексов (~32МБ) скопировать нужно всего ~62 Kb указателей. Если же вертекс более тяжелый то отношение размера копирования при ресайзе массива страниц к размеру последовательности еще меньше. std::vector такая эффективность и не снилась. Ну исключительно потому что он без учета где его применять будут проектировался.


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

0

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

Стандартная библиотека проектируется так, чтобы использоваться ВСЕМИ. Без информации, в какой задаче он будет использована. Вот какие с..и её писали!!! Ату их!!! Долой стандартную библиотеку, всё напишем сами на коленке!

Поэтому и непригоден нигде кроме хеллоувердов.

Без комментариев.

0

Сообщение от Fulcrum_013 Это в L1. А кроме него есть еще L2 и L3

А там 128 байт. До страницы все равно далеко.

Сообщение от Fulcrum_013 Считаем дальше. В каждом задании ну на вскидку 1000 дверей и 1000 окон, которые имеют ручки и т.п. А так же 500 комнат. В каждой комнате еще куча мебели у которой тоже есть дверцы и т.д. и т.п. И в каждом ящике этой мебели еще может что то лежать, причем тоже составное. итого если в 16GB оверхеда из за этих 16 байт уместимся считай повезло.

Смотрим на размер списка childDoors и понимаем что на его фоне массив на 16 элементов - сущие копейки.
А если это 3D сцена, то идем сносить все комнаты по критерию "не попадают в кадр".

Сообщение от Fulcrum_013 Ну надеюсь понимаете что такие массивы (со страничной организацией) они не для накопления связей между объектами используются. А к примеру для накопления буфера вертексов в редакторе.

После чего операция "скопировать в буфер" работает аж на 0.001 секунды быстрее. А вы наверняка имеете дополнительный секс с библиотеками 3D графики, пытаясь скормить им не один большой шмат вертексов, а нарезку из страниц.
Вот потому, собственно и вектор. Доступен из коробки, дает гарантии приличной скорости работы, дает гарантии непрерывного размещения элементов. И если при его использовании не видно разницы, зачем кодить больше?

0

Сообщение от Renji После чего операция "скопировать в буфер" работает аж на 0.001 секунды быстрее.

Ну во первых операция "скопировать буфер в" таким образом ускорится врядли, потому как размер для этой операции обычно заранее известен. Во вторых если дело касается реалтаймовой графики то 0.001 это очень и даже очень много, потому как таймфрейм не более 0,032 секунды. А вот накопление вертексов в генераторе на основе параметрического проектирования ускорится, и ускорится хорошо. Потому как для того чтобы дорасти до миллиона вертексов std::vector с его стратегией роста скопируется 40 раз. А вот как раз в таких генераторах подсчет общего количества вертексов на выходе обычно очень затруднен.

Сообщение от Renji А вы наверняка имеете дополнительный секс с библиотеками 3D графики, пытаясь скормить им не один большой шмат вертексов, а нарезку из страниц.

Секс дело полезное. А тем более библиотеки свои родные (врапперы gl и dx). Да и в буфер видеокарты все равно все это копировать. А вот каким образом - страницами или отдельным куском разница небольшая.
Кстати попытки запихнуть одним шматом из того что возвращает data() почему то заканчиваются Access Violation на первом же байте. Что самое интересное после замены вектора на свои массивы никаких проблем.

Добавлено через 2 часа 24 минуты

Сообщение от DeadPenguin Долой стандартную библиотеку, всё напишем сами на коленке!

Кстати наиболее востребованной структуры данных - древьев в stl нет. Так же как и толковых списков. Имеются в виду не деки а списки указателей на объекты c произвольным доступом. Мало того нет никакой возможности организации взаимодействия контейнера с хранимым объектом и оповещений контейнером других объектов (подписчиков) об изменении состояния.
Т.е. в STL вообще ничего нужного нет.

Добавлено через 1 час 8 минут

Сообщение от Renji Смотрим на размер списка childDoors и понимаем что на его фоне массив на 16 элементов - сущие копейки.

Ага. Только вот когда у каждого из этих чилдов свой массивчик. Причем большую часть времени пустой. то таки ой-ой-ой. А он нужен. На случай добавления всяких временных приколов типа пулевых отверстий, брызгов крови, ошметков мозгов, и т.д и т.п.

Добавлено через 4 часа 15 минут
hoggy, DeadPenguin, Renji,
Вопрос знатокам STL:
Вот и скажите как называются _ptr<> которые это нормально обработают и какие контейнеры позволят этот объект из себя удалить при его удалении (объект может отправить оповещение об удалении из деструктора), и какой итератор сможет итерировать вызов Update() таких классов? Никакой? Так где место вашей STL? Правильно в хеллоувердах. Ану бегом ООП учить, двоешники.

0

То, что Вы навелосипедили, есть в STL. Называется deque.

Список указателей с произвольным доступом магически получается, если в список с произвольным доступом(например, deque) класть указатели.

Деревья в STL есть. Может быть, они не подходят к Вашей задаче, но они там есть. Set и map сделаны на деревьях.

Возможность, позволяющая организовать взаимодействие контейнера с хранимыми объектами и оповещения подписчиков, называется "наследование".

Добавлено через 22 минуты
Объект, который знает о контейнере, в котором лежит (раз уж может отправить ему уведомление), это очень, очень плохой стиль. И delete this - это тоже очень, очень плохой стиль. Хотя бы потому, что это налагает кучу ограничений на способ создания объектов.

Добавлено через 9 минут
Один из параметров любого контейнера в STL - аллокатор. Пишете аллокатор и извращаетесь как угодно.
Если очень хочется делать delete this - пишете аллокатор, который не будет вызывать для удаляемых объектов деструктор.

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

0

Сообщение от Eldies Возможность, позволяющая организовать взаимодействие контейнера с хранимыми объектами и оповещения подписчиков, называется "наследование"

Угу. Которое на переписывание с нуля тянет.

Сообщение от Eldies Set и map сделаны на деревьях

Не путайте бинарные деревья поисков и деревья объектов. К примеру наподобие борландовских TTreeNodes. Да кстати двумерных и прочих мерностей массивов в STL тоже нет.

Сообщение от Eldies То, что Вы навелосипедили, есть в STL. Называется deque.

То в STL с 16-байтными страницами навелосипедили. Типы больше 8 байт размером там будут по одному в странице.

Добавлено через 4 минуты

Сообщение от Eldies Объект, который знает о контейнере, в котором лежит (раз уж может отправить ему уведомление), это очень, очень плохой стиль

Наоборот. Потому как позволяет организовать взаимодействие снизу. Можно кстати реализовать и так чтобы вообще никаких ограничений не ставилось ни на создание ни на количество списков в которых объект присутствует. (оповещение реализуется через делегатов).

Сообщение от Eldies И delete this - это тоже очень, очень плохой стиль.

Тоже очень хороший. Потому что и то и другое избавляет от кучи внешнего геммороя.

Добавлено через 16 минут

Сообщение от Eldies пишете аллокатор, который не будет вызывать для удаляемых объектов деструктор

Ну что за бред? Если список владения грохнули он должен удалить всех кто в нем находится. Просто экземпляры настолько грамотные что сами определяют когда им пора того при живом контейнере. Да кстати представляете какой говнокод будет при объявлении экземпляров контейнеров с указанием аллокаторов и тд?

Добавлено через 13 минут

Сообщение от Eldies Если очень хочется итерироваться по контейнеру и одновременно удалять из него объекты - можно, например, отнаследоваться от контейнера и сделать удаления откладываемыми.

А можно просто правильно итерироваться. Ну со списками это вообще просто. С массивами посложнее но тоже можно. По таблицам БД как то же итерируются параллельно с удалением? И ничего, все абсолютно safe. А потому что курсоры взаимодействуют с последовательностью.

Добавлено через 10 минут
А если по человечески писать то все просто получается в результате:

0

Сообщение от Fulcrum_013 Она появилась гораздо позже чем более продвинутые средства. Зачем мне лезть в дебри малочитабельного говнокода который не имеет средств для решения необходимых мне задач?

типично неосиляторская позиция:
"не читал, но осуждаю".

и потом,
ключевым моментом в вашем отношении является "малочитабельный" фактор.

то бишь, она не нравится вам не потому,
что существуют какие то объективные причины
ущербности библиотеки.
а потому, что вам тупо сложно с нею работать.

Сообщение от Fulcrum_013 Представьте что в самолете вообще нет пилота. Но от этого абсолютно ничего не меняется.

вы не поняли.

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

что-то, что вполне реально может произойти.
при этом, программа не должна упасть.
она должна корректно обработать искл. ситуацию,
и продолжать работать дальше.

вот вам ещё пример:
нужно сохранить данные на жестком диске.
мы не можем заранее знать, получится ли это сделать.
вдруг в этот самый момент кто-то другой записал данные,
и на диске тупо не хватит места?

но если действительно возникнет проблема,
мы просто покажем пользователю окошко: "не хватает места".
и сделаем отмену.

если пользователю нужны эти данные,
он освободит место и ещё раз зделает сохранение.

Сообщение от Fulcrum_013 А вот это не очень хорошая практика. Потому как во первых ввод надо проверять, вне зависимости есть ли внутренние проверки внутри компонентов-вычислителей. Во вторых проверки для рандомного доступа дают ужасный оверхед при последовательном, при этом и рандомный в большинстве случаев имеет групповую внешнюю проверку. Пример:

вы так нефига и не поняли.
понятно, что снаружи тоже нужно выполнять проверки.
речь жеж не об этом.

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

в данном случае этой причиной является блондинка,
которая из консольки вбивает индекс.

касательно производительности:
ошибки алгоритмов валидируются ассертами.
поэтому нет никаких пенальти в релизе.

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

Сообщение от Fulcrum_013 Так или иначе аварийное завершение всей программы при ассерте, или как минимум какой либо ее ветки вычислений при екскепшине. Результат тот же - птичка на земле.

вам нужно понять одну концептуальную вещь:

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

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

мой отец - инженер, говорил так:
вероятность деффекта деталей - одна тысячная.
в обычном авто 10 000 деталей.
это значит, что как минимум 10 из них - бракованные.
но машина ездиет.

примерно точно так же дела обстоят с программами.
программа управляет полетом звездолета.
и в ней есть ошибки.
тем не менее звездолет летит.

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

Сообщение от Fulcrum_013 Если вы не умеете использовать его для отладки то это не значит что он для этого не предназначен.

а если я умею использовать его для отладки, тогда что это значит? (ц)программисткий юмор

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

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

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

и хотя их можно (и нужно) использовать в этом качестве,
нельзя забывать о настоящем их предназначении.

Сообщение от Fulcrum_013 Основа отказоустойчивости в корректности работы программ. trow это еще и инструмент который способен сообщить о некорректности программы на этапе отладки. В корректной программе возникновение таких экскепшинов исключено, в следствие невозможности срабатывания проверок их выбрасывающих. Соответсвенно в релизе все эти проверки выпиливаются.

основа отказоустойчивости - возможность создания автоматических и эвристических систем
восстановления после паники.

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

весь остальной текст - это описания ассерта, а не эксепшена.

Сообщение от Fulcrum_013 Поясните что делает ваш close, и что вы видите аморального?

это не важно.

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

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

Сообщение от Fulcrum_013 Покажет. Только этот стек нужно видеть в момент возникновения ошибки. При этом иметь возможность не только видеть стек но и перейти в место вызова и посмотреть локальные данные

я вам третий раз повторяю: в этом смысле, ассерты такие же, как и эксепшены.
вы увидите точно такой же стек вызовов, и бла бла бла.

Сообщение от Fulcrum_013 Во первых в отличии от assert это очень помагает при отладке

я ещё могу понять неосилятора stl,
но как можно было не осилить ассерт???

Сообщение от Fulcrum_013 Если заметили даже штатные либы от всех производителей идут в двух видах бинарника - debug и release. Чем они по вашему отличаются кроме выпеленной в release части проверок?

какое это имеет значение?

Сообщение от Fulcrum_013 Например CGrowableArray вместо std::vector

вы осознаете принципиальную разницу между этими двумя контейнерами?

0

Сообщение от Fulcrum_013 Ну во первых операция "скопировать буфер в" таким образом ускорится врядли, потому как размер для этой операции обычно заранее известен. Во вторых если дело касается реалтаймовой графики то 0.001 это очень и даже очень много, потому как таймфрейм не более 0,032 секунды.

Для реалтайма либо дана предельная нагрузка на буфер (и он тупо делается статическим), либо это не реалтайм (нет гарантии что не повиснет на буфере размером в десять гиг).
Для не реалтайма же известна типичная нагрузка, на которой пользователь едва ли заметит эффект от подобных шаманств. А к тормозам на сто гиговом буфере все относятся с пониманием.

Сообщение от Fulcrum_013 Ага. Только вот когда у каждого из этих чилдов свой массивчик. Причем большую часть времени пустой. то таки ой-ой-ой. А он нужен. На случай добавления всяких временных приколов типа пулевых отверстий, брызгов крови, ошметков мозгов, и т.д и т.п.

А, стрелялка обыкновенная. И 500 комнат наверняка создаются путем копирования одного заранее нарисованного образца. Так и напрашиваются shallow copy и процедурная генерация (помните как в Elite огромная галактика умещалась в четырехбайтовом семени?). После чего 100K домиков на бумаге, превращаются в максимум сотню по факту. Все остальные домики существуют лишь в форме семени генератора случайных чисел, из которого будут созданы потроха домика, когда игрок в него зайдет.

0

На переписывание с нуля не тянет.
Уведомление подписчиков: отнаследоваться, в наследнике нужно поле - контейнер для подписчиков, пара функций для подписки и отписки. И там, где Вы хотите, чтобы контейнер о чем-то уведомля, перегружаем метод, пишем в нем уведомление и пишем в ней вызов метода базового класса.

Стандарт не конкретизирует, какой величины страницы должны быть в deque. Не нравятся выбранные изготовителем Вашего компилятора (насколько мне известно, 16 байт исключительно в вижуал студии) - можно отнаследоваться и использовать какие хочется. Хотя, конечно, в случае с вижуал студией проще переписать, да. В gcc это гораздо проще.

И то и другое избавляет от кучи внешнего геморроя, зато добавляет кучу внутреннего.

Кладём в список владения shared_ptr, кладём в остальные списки weak_ptr. Когда надо удалить - удаляем из списка владения и всё. При проходе по остальным спискам одновременно вычищаем невалидные weak_ptrы. Или, когда по списку проходим, невалидное игнорируем, но время от времени вычищаем отдельным проходом. Внезапно, стандартных контейнеров для этого вполне достаточно. Писать надо гораздо меньше -> багов гораздо меньше -> гораздо более по человечески, чем писать две собственных разных реализации списков.

Добавлено через 7 минут
//Коммент для Fulcrum_013
//извиняюсь, что без цитат - с мобильного устройства адски неудобно

0

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

А при отладке вылет за границы массива ситуация очень даже ожидаемая. Поэтому и экскепшены. Когла отладили это уже невозможная ситуация. Поэтому и выпиливаем.

Добавлено через 59 секунд

Сообщение от Eldies зато добавляет кучу внутреннего

Та нет, обычно во внутренней части все просто и логично. Опять же - внутреннее делается один раз а пользуется постоянно.

0

Сообщение от Fulcrum_013 А при отладке вылет за границы массива ситуация очень даже ожидаемая. Поэтому и экскепшены. Когла отладили это уже невозможная ситуация. Поэтому и выпиливаем.

вы описываете ассерт.

0

Сообщение от Fulcrum_013 А при отладке вылет за границы массива ситуация очень даже ожидаемая. Поэтому и экскепшены. Когла отладили это уже невозможная ситуация. Поэтому и выпиливаем.

Дадут непредсказуемый эффект в nothrow функции (ибо UB), застрянут в catch(const std::exception&) секции, до отладчика в итоге не дойдут. При этом потребуют ручками обшивать их define, удаляющими throw из релиза.

0

Сообщение от Eldies При проходе по остальным спискам одновременно вычищаем невалидные weak_ptrы. Или, когда по списку проходим, невалидное игнорируем, но время от времени вычищаем отдельным проходом.

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

Добавлено через 3 минуты

Сообщение от Renji до отладчика в итоге не дойдут

Вы что отладчиком никогда не пользовались? Он останавливается в точке выброса в момент выброса а не где либо еще. Деление на ноль кстати тоже екскепшен. причем хардварный.

Добавлено через 1 минуту

Сообщение от Renji Дадут непредсказуемый эффект в nothrow функции

ну и кто назовет умным человека который выкидывает экскепшены из функции которую он же пометил nothrow?

0

Сообщение от Fulcrum_013 Вы что отладчиком никогда не пользовались? Он останавливается в точке выброса в момент выброса а не где либо еще.

Это вы отладчиком никогда не пользовались.

Сообщение от Fulcrum_013 ну и кто назовет умным человека который выкидывает экскепшены из функции которую он же пометил nothrow?

А как еще прикажете делать отдалочные проверки, если assert использовать некошерно?

0

Сообщение от Renji Это вы отладчиком никогда не пользовались.

отладчик вижуал студии умеет брякаться и на ассертах,
и на исключениях.

0

Сообщение от hoggy отладчик вижуал студии умеет брякаться и на ассертах, и на исключениях.

На исключениях, которые явно указано ловить и обрабатывать в catch секции, а не в отладчике? Ну и безобразие.

0

Сообщение от hoggy вы описываете ассерт.

А на ассерте вашем дебуггер остановится?

0

Сообщение от Renji На исключениях, которые явно указано ловить и обрабатывать в catch секции, а не в отладчике? Ну и безобразие.

можно поставить галочку "брякаться на исключениях".
после этого отладчик будет брякаться на исключениях.

Сообщение от Fulcrum_013 А на ассерте вашем дебуггер остановится?

какое именно слово в фразе:

Сообщение от hoggy я вам третий раз повторяю: в этом смысле, ассерты такие же, как и эксепшены. вы увидите точно такой же стек вызовов, и бла бла бла.

вам не понятно?

1

Сообщение от Renji Это вы отладчиком никогда не пользовались.

Не знал что e MSVC настолько тупой отладчик. Ну или std::runtime_error заранее внесен в список исключений. Нормальные отладчики останавливаются и даже если по верху cath, лишь бы екскепшен не был в списке игнорируемых. Сколько раз говорить - MSVC для лохов. А крутые пацаны пользуют Embarcodero Debug Kernel

Добавлено через 1 минуту
да точно внесен. Потому как вот так останавливается.
еще одно доказательство идиотизма STL

0

Сообщение от Fulcrum_013 еще одно доказательство идиотизма STL

казалось бы: и при чем тут stl?

0