Цитата(mes @ 26.2.2011, 17:41  ) |
| если заранее зарезервировать нужный объем, то никакого лишнего расхода не будет.. |
Как же я могу знать объем памяти для резервирования? Если бы я знал, то использовал бы простой массив... а коэффициент 1.6 великоват
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C++ Builder > Насколько расточителен vector вплане памяти |
| Автор: Нитонисе 26.2.2011, 17:35 |
| Насколько я понимаю, данный контейнер STL всегда выделяет памяти больше, чем нужно для хранения фактических данных. То есть заготавлевает места для будущих элементов контейнера. А много ли вектор резервирует места для будущих своих элементов? Понятно, что если у меня пару векторов в программе используется, то затраты памяти по хранению этих векторов будут невелики. А если этих векторов будет тысяча? Насколько большие объемы памяти будут зарезервированы под будущие элементы контейнеров, но фактически которых еще нет и по идее такие затраты памяти излишни? |
| Автор: mes 26.2.2011, 17:41 |
| при переполнении он увеличивает память в N раз, где N коэффициент зависящий от реализатора.. условно равный где то 1,6.. если заранее зарезервировать нужный объем, то никакого лишнего расхода не будет.. т.е. все в руках пользователя. |
| Автор: Нитонисе 26.2.2011, 17:45 | ||
Как же я могу знать объем памяти для резервирования? Если бы я знал, то использовал бы простой массив... а коэффициент 1.6 великоват |
| Автор: mes 26.2.2011, 17:58 | ||
ну так надо проявить смекалку при решении задачи, а не пытаться решать в лоб.. 1. можно перед добавлением самостоятельно резервировать память (к примеру на один элемент больше) 2. вначале заполнить вектор автоматически, а после перенести его в подготовленное место.. 3. можно разделить задачу на две считывание и доступ : для первой использовать очередь (список) а после перенести в вектор.. (разновидность 2го варианта) и т.д. |
| Автор: Нитонисе 26.2.2011, 19:24 | ||
Проявить-то смекалку сложно, потому что вектор по определению является контейнером для заранее неизвестного количества элементов. По поводу явного указания вектору сколько памяти выделять я не знаю, но если такое есть, то мне кажется это малоэффиктивным. Дело в том, что ведь не зря вектор заранее резервирует довольно большой объем памяти. Вероятно операции расширения его емкости затратны по времени. Если этим заниматься всякий раз при добавлении/удалении, то можно получить очень низкую скорость. Наверняка этого не знаю, это в порядке предположения. Впрочем наверное тут можно найти оптимальное решение, с тем чтобы не потерять в скорости и занимать столько памяти, сколько нужно в данный момент, но для меня пока (в силу моих знаний) это решение не очевидно, да и задачи сейчас конкретно такой нет. Вектора использую, но пока не в таких больших количествах и потери памяти впустую не критичны. Поинтересовался из любопытства  |
| Автор: mes 26.2.2011, 19:43 | ||||
использовать контейнеры по назначению.. для вставки в конец наиболее оптимально подходит стек на основе очереди.. после того как заполнили, можете узнать размер данных, и перенести вектор, чтоб получить прямой доступ к нужному элементу.. если быстрый прямой доступ не обязателен, можно в очереди и оставить.. если все ж нужно одновременно и доступ и заполнение, то можно просто освободить лишнюю память, когда больше заполнение долго не предвидется.. вобщем
|
| Автор: Usper 26.2.2011, 21:55 |
| Недавно на хабре про это писали http://habrahabr.ru/blogs/cpp/113324/ там реализовали собственный вектор для экономии памяти (правда исходников нет). А reserve выделяет памяти не меньше чем нужно для заданного количества элементов, но может выделить и больше. |
| Автор: mes 26.2.2011, 23:06 | ||
я б посоветовал поосторожней относится к статьям подобного уровня.. можно подцепить много чего нехорошего.. |
| Автор: volatile 26.2.2011, 23:47 |
| По поводу статьи на хабре, я бы посоветовал автору статьи использовать дек. Он кстати примерно так и организован (в плане выделения памяти), как они это сделали. По поводу быстродействия, дек, по крайней мере на VC почти не уступает вектору. (удивительно!) так что я вектором пользуюсь очень редко. провда для случая много мелких векторов, как у ТС, дек не самое лучшее средство. так как он тоже резервирует блоками. если добавить один элемент в пустой дек, там резервируется память под 32 элемента. (я говорю о реализации на VC). На других системах реализация примерно такая-же. каждый раз при заполнении очередного блока, выделяется новый, размером N элементов. Никакого N * K ( как у вектора ) нету. При больших массивах, становится выгодно использовать именно дек. |
| Автор: Нитонисе 1.3.2011, 18:07 |
| Начал тут немного просвящаться по поводу векторов, обнаружил новые возможности. Например - принудительное резервирование нужного объема памяти под определенное количество элементов. Вокруг этого обстоятельства шли еще некоторые рассуждения о скорости работы вектора, но простого ответа на свой вопрос не обнаружил. При удалении элементов вектора скорости тратится тем больше, чем глубже эти элементы расположены. Максимально быстро удаляется последний элемент. Однако эту скорость некоторым образом можно регулировать, станавливая определенную емкость вектора. Так ли это? Кто нибудь пояснит простым языком, можно ли добиться относительно быстрого удаления элемента из позиции с индексом ноль при общем количестве элементов равном тысяче?  |
| Автор: mes 1.3.2011, 18:23 | ||
нет.. потому что все остальные нужно сдвинуть на его место. |
| Автор: Dem_max 1.3.2011, 18:42 |
| нет просто нужно сдвинуть указатель на первый элемент |
| Автор: Нитонисе 1.3.2011, 18:44 | ||
Здесь "нет" - это ответ на мой вопрос или возражение реплике mes? |
| Автор: volatile 1.3.2011, 23:29 |
| Нитонисе, попробуй дек (deque). Я писал о нём чуть выше. 1. Удаляет элементы гораздо быстрее чем вектор, из любого места. 2. Не удваивает свой размер по заполнении. 3. Не перемещает элементы при расширении. 4. Имеет произвольный доступ, так-же как вектор: name[index] 5. Быстродействие не намного уступает вектору. пятый пункт по крайней мере на VC, на других системах нужно пробовать. Добавлено через 1 минуту и 54 секунды но элементы расположены не рядом все подряд. это надо учитывать. |
| Автор: mes 1.3.2011, 23:35 | ||
уточню : имелся ввиду произвольный доступ к элементу. |
| Автор: volatile 1.3.2011, 23:59 | ||
да, именно произвольный доступ. по всем другим параметрам (добавление, удаление, вставка), быстродействие опережает вектор. |