Comments 48
Было бы интересно посмотреть как вы это реализовали.
UFO just landed and posted this here
А итераторы тоже реализовали?
идиоты, про std::deque никогда не слышали
Ну deque тут не поможет. Обычно у STL-ного deque тоже переаллокация с копированием элементов происходит. Например в gcc используется реализация с вектором и циклической индексацией. Т.е. когда место в векторе закончится, то будет все то же самое.
у std::deque push_back имеет O(1) скорость выполнения, топикреатер просто нешарит в языке на котором пишет- вот и высирает вылосипеды, ну высирыает и высирает, это ещё полбеды- но когда свой высер на обозрение общественности выставляет- это уже плохо.
Не будет.
«A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle. „
«A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle. „
Отчего же сразу идиоты, они просто еще не Senior и не читали Кнута и Мейерса, либо пролистали просто.
Кроме того, не сильно ясно какие у них задачи, может им только вектор и подходит. Посему не стоит так критично, каждый контейнер на свою задачу, к тому же если бы deque равнозначно заменял vector, он был бы не нужен, посему тут нужно просто полистать Мёртвого Страуса и Мейерса, выбрать контейнер. Если выбор не определился, то полистать более серьёзную литературу и выбрать правильный аллокатор.
Они по сути простенький хэш сделали своим «ветором векторов», может им бы банальное дерево подошло, кто знает, что у них там за потребности.
Кроме того, не сильно ясно какие у них задачи, может им только вектор и подходит. Посему не стоит так критично, каждый контейнер на свою задачу, к тому же если бы deque равнозначно заменял vector, он был бы не нужен, посему тут нужно просто полистать Мёртвого Страуса и Мейерса, выбрать контейнер. Если выбор не определился, то полистать более серьёзную литературу и выбрать правильный аллокатор.
Они по сути простенький хэш сделали своим «ветором векторов», может им бы банальное дерево подошло, кто знает, что у них там за потребности.
UFO just landed and posted this here
Беда, инструментом пользуетесь, а как он работает не знаете. Скажите честно, сколько рабочих часов потратили на то, чтобы выявить ошибку и выяснить как работает банальный std::vector?
Вы знаете как работает АБС в машине, к-рую водите? Или гидроусилитель?
Что удерживает мотоцикл от падения на скорости?
Как данные обрабатываются на видеокарте прежде, чем попасть на экран?
Я пользуюсь Хабром (что тоже инструмент), но не вникаю во внутренний механизм его работы (даже если б имел такую возможность) — потому, что не вижу в этом потребности.
У автора до некоторого момента не возникала потребность в знании реализации контейнера. Появилась — выяснил.
Что удерживает мотоцикл от падения на скорости?
Как данные обрабатываются на видеокарте прежде, чем попасть на экран?
Я пользуюсь Хабром (что тоже инструмент), но не вникаю во внутренний механизм его работы (даже если б имел такую возможность) — потому, что не вижу в этом потребности.
У автора до некоторого момента не возникала потребность в знании реализации контейнера. Появилась — выяснил.
использование того или иного контейнера основывается как раз таки на его преимуществах\недостатках, надо знать сильные и слабые стороны, дабы для конкретной задачи подбирать более подходящее решение. именно такие вещи и надо знать.
В большинстве случаей не правильный выбор контейнера не проявит себя на скорости выполнения никак.
Ну считываете вы параметры программы из ini файла. Ну пусть вы использовали vector/deque/list вместо map? Если в программе менее сотни конфигурационных параметров, каждый из к-рых считывается скажем раз в пару секунд — на современной машине вы даже с секундомером не увидите разницы, несмотря на линейную скорость поиска против логарифмической
Ну считываете вы параметры программы из ini файла. Ну пусть вы использовали vector/deque/list вместо map? Если в программе менее сотни конфигурационных параметров, каждый из к-рых считывается скажем раз в пару секунд — на современной машине вы даже с секундомером не увидите разницы, несмотря на линейную скорость поиска против логарифмической
UFO just landed and posted this here
Интересно, а реализация Vector в AS3 это тупое зеркало? Плеер то на плюсах, наверно, написан. Мне бы большим подспорьем стало. Массивы хоть не такие большие (до 1000), но думается, если элемент вектора весит по 50кб, то оптимизация будет ощутима.
Вообще-то vector изначально не оптимален для частого добавления элементов. И доролнительная проблема с часто растущими векторами, как и в предыдущей статье — фрагментация памяти. Был кусок size, стал size + K*size, потом оригинальную size освободили, но не факт что оптимально удастся ее использовать.
Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.
RTFM.
реализация вектора и логарифмическое выделение памяти соответсвует все академическим каннонам. именно так нас учили в универе пистать динамические массивы. вывод — общий случай не работает везде
Ну не знаю, часто бывает, что использование вектора для частых добавлений это просто ошибка проектирования, мне приходилось работать со списками данных с 2 и более миллионами записей, использовал list, проблем не обнаруживал вообще. Нормально и добавлял и бегал и получал доступ к нужным элементам, делал частичный индекс и многое другое и прожил без vector.
Если бы вы сначала описали, зачем вам понадобился именно vector. Было бы интереснее, да и может быть предложили бы другой вариант. А стандартный контейнер я переписывал только 1 раз, мне нужна была репликация данных на диск при изменении.
Если бы вы сначала описали, зачем вам понадобился именно vector. Было бы интереснее, да и может быть предложили бы другой вариант. А стандартный контейнер я переписывал только 1 раз, мне нужна была репликация данных на диск при изменении.
Целая статья из проблемы, которая решается за пару минут, комментарии «используй list/deque», от людей, не знающих, что у list/deeque среднее время доступа O(N), а у вектора O(1)…
«бида-бида, грусть — пичаль»
авторы, почитайте про stlxxl
«бида-бида, грусть — пичаль»
авторы, почитайте про stlxxl
Выделение памяти прежде всего зависит от условий задачи, и лишь уж потом — от используемых в ней инструментов (алгоритмов, библиотек и прочего). Данная задача выбивается из ряда обычных, поэтому и недовольство аллокатором или наслоенным поверх него темплейтом становится более вероятным. Серебряной пули нет. Правила русской рулетки того и не требуют.
Звучит как реализация sparce array (разреженный массив)
«STL для самых маленьких» на Хабре :)
А им, знаете ли, тоже нужно учиться. И, честно говоря, не всегда хорошо учиться на своих ошибках.
Ясно что и нам нужно было учиться раньше и нужно было обращать внимание на «мелочи» ( специально взял в кавычки чтобы избежать очередного холливара о мелочах в программировании ), но ведь всегда есть достаточно веские причины вроде специфики проекта, особенностей реализации под конкретную платформу и просто человеческого фактора.
К слову, когда-то, много лет назад, мне приходилось писать нативную либу для работы с COM-портом в Java просто потому как таковая хоть и существовала, но была в настолько непотребном состоянии, что использовать ее не представлялось возможным. И там уже не стоял вопрос о знании языка, радиусе кривизны рук и длине костылей — нужно было просто быстро найти выход из сложившейся ситуации иначе финиш.
Собственно такая ситуация описана была и здесь. И, глядишь, кто-нибудь из этих «самых маленьких» благодаря умению читать и любви к хабру обойдет такие грабли стороной и скажет спасибо хабру или, чем черт не шутит, мне.
Ясно что и нам нужно было учиться раньше и нужно было обращать внимание на «мелочи» ( специально взял в кавычки чтобы избежать очередного холливара о мелочах в программировании ), но ведь всегда есть достаточно веские причины вроде специфики проекта, особенностей реализации под конкретную платформу и просто человеческого фактора.
К слову, когда-то, много лет назад, мне приходилось писать нативную либу для работы с COM-портом в Java просто потому как таковая хоть и существовала, но была в настолько непотребном состоянии, что использовать ее не представлялось возможным. И там уже не стоял вопрос о знании языка, радиусе кривизны рук и длине костылей — нужно было просто быстро найти выход из сложившейся ситуации иначе финиш.
Собственно такая ситуация описана была и здесь. И, глядишь, кто-нибудь из этих «самых маленьких» благодаря умению читать и любви к хабру обойдет такие грабли стороной и скажет спасибо хабру или, чем черт не шутит, мне.
> «STL для самых маленьких» на Хабре :)
Поправочка:
«STL для самых маленьких» из песочницы.
Поправочка:
«STL для самых маленьких» из песочницы.
Sign up to leave a comment.
Доработка контейнера vector для работы с большими объемами данных