Требуется контейнер, максимально быстрый по совокупности двух операций:
1) поэлементное добавление в конец;
2) единовременный убой всех элементов.
Число элементов может достигать десятков тысяч, но заранее оно неизвестно.
Что посоветуете? Программа на MFC, но CArray и CList производят плачевное впечатление.
Здравствуйте, SchweinDeBurg, Вы писали:
SDB>Здравствуйте, Анатолий Широков, Вы писали:
АШ>>std::vector
SDB>Спасибо за оперативный ответ. Завтра я, конечно, и сам это потрогаю, но насколько он быстрее CArray Вы не навскидку сказать не можете?
Не проводил замеры, но точно могу сказать, что при правильном прогнозе (std::vector::reserve) вы получаете оптимильное быстродействие.
Здравствуйте, Анатолий Широков, Вы писали:
АШ>Здравствуйте, SchweinDeBurg, Вы писали:
SDB>>Здравствуйте, Анатолий Широков, Вы писали:
АШ>>>std::vector
SDB>>Спасибо за оперативный ответ. Завтра я, конечно, и сам это потрогаю, но насколько он быстрее CArray Вы не навскидку сказать не можете?
АШ>Не проводил замеры, но точно могу сказать, что при правильном прогнозе (std::vector::reserve) вы получаете оптимильное быстродействие.
Эх, если бы я знал, сколько надо reserv'нуть, я бы и с CArray'ем это сделал...
Здравствуйте, SchweinDeBurg, Вы писали:
SDB>Доброго времени суток всем нам!
SDB>Требуется контейнер, максимально быстрый по совокупности двух операций: SDB>1) поэлементное добавление в конец; SDB>2) единовременный убой всех элементов. SDB>Число элементов может достигать десятков тысяч, но заранее оно неизвестно.
SDB>Что посоветуете? Программа на MFC, но CArray и CList производят плачевное впечатление.
Здравствуйте, SchweinDeBurg, Вы писали:
S> Требуется контейнер, максимально быстрый по совокупности двух операций:
S> 1) поэлементное добавление в конец;
std::deque
std::vector
S> 2) единовременный убой всех элементов.
SDB>Эх, если бы я знал, сколько надо reserv'нуть, я бы и с CArray'ем это сделал...
Ну, хорошо, можно и без прогноза, только важно понимать, что для последовательного размещения худшее из зол наличие нетривиального конструктора копирования. А так, врядли быстродействие одного будет значительно отличаться от другого.
Здравствуйте, SchweinDeBurg, Вы писали:
SDB>Требуется контейнер, максимально быстрый по совокупности двух операций: SDB>1) поэлементное добавление в конец; SDB>2) единовременный убой всех элементов. SDB>Число элементов может достигать десятков тысяч, но заранее оно неизвестно.
Если требуется быстрое добавление/удаление с конца/начала то std::deque.
Но если в цикле происходит заполнение, очистка или есть возможность отправить контейнер на долговременное хранение то лучше std::vector ибо после того как он раздуется перестанет переалоцировать память.
Также в случае использования вектора можно слелать reserve на некое магическое число я бы поставил примерно в 1.5 раза больше среднего. Если не хватит то вектор удвоит размер буфера.
... << RSDN@Home 1.1 alpha 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, SchweinDeBurg, Вы писали:
SDB>Требуется контейнер, максимально быстрый по совокупности двух операций: SDB>1) поэлементное добавление в конец; SDB>2) единовременный убой всех элементов. SDB>Число элементов может достигать десятков тысяч, но заранее оно неизвестно. SDB>Что посоветуете? Программа на MFC, но CArray и CList производят плачевное впечатление.
Если не известно сколько надо зарезервировать, то оптимальным вариантом, наверное, будет std::deque.Он всё таки "быстрее" растёт чем std::vector
Здравствуйте, Mechanicus, Вы писали:
M> Если не известно сколько надо зарезервировать, то оптимальным M> вариантом, наверное, будет std::deque.Он всё таки "быстрее" растёт M> чем std::vector
Очень сильно зависит от характеристик и количества элементов.
Зачастую std::vector оказывается быстрее, чем std::deque.
Posted via RSDN NNTP Server 1.6 RC1
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, SchweinDeBurg, Вы писали:
SDB>Требуется контейнер, максимально быстрый по совокупности двух операций: SDB>1) поэлементное добавление в конец; SDB>2) единовременный убой всех элементов. SDB>Число элементов может достигать десятков тысяч, но заранее оно неизвестно.
Слова про то, что количество заранее не известно, тут выжны. Если не принимать в расчет возможность "застолбить" террабайт памяти, чтобы уж наверняка хватило , то выходит вот что:
Если конструктор копирования у элемента тормозной (например требует выделения относительно больших кусков памяти, соединения с БД, форматирования диска ), то std::list, иначе std::vector.
Здравствуйте, plads_project, Вы писали:
_>Здравствуйте, SchweinDeBurg, Вы писали:
SDB>>Требуется контейнер, максимально быстрый по совокупности двух операций: SDB>>1) поэлементное добавление в конец; SDB>>2) единовременный убой всех элементов. SDB>>Число элементов может достигать десятков тысяч, но заранее оно неизвестно.
_>Слова про то, что количество заранее не известно, тут выжны. Если не принимать в расчет возможность "застолбить" террабайт памяти, чтобы уж наверняка хватило , то выходит вот что: _>Если конструктор копирования у элемента тормозной (например требует выделения относительно больших кусков памяти, соединения с БД, форматирования диска ), то std::list, иначе std::vector.
Дополнение:
Еще есть std::deque, но в данном случае он должен быть близок по показателям к std::list (по крайней мере его реализация в VS 7.1).
std::list не проходит из-за требования быстрого удаления всех эелементов сразу. А скорость конструктора копирования тут не при чем, он вызывается при вставке в любой контейнер.
Здравствуйте, plads_project, Вы писали:
pp> Еще есть std::deque, но в данном случае он должен быть близок по pp> показателям к std::list (по крайней мере его реализация в VS 7.1).
У Dinkumware (то, что используется в VS 7.1) std::deque на подобных задачах обычно дает
показатели раза в два получше, чем std::list, и раза в четыре побыстрее на итерации.
Posted via RSDN NNTP Server 1.6 RC1
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Павел Кузнецов ПК>Зачастую std::vector оказывается быстрее, чем std::deque.
А где это наблюдается?
Вроде бы deque шустрее на больших объёмах данных, чем vector, так как память ему не обязательно выделять единым блоком, что опять таки ведёт к увеличению скорости.
If the milk turns out to be sour,
I ain't the kind of pussy to drink it
Здравствуйте, skyline, Вы писали:
ПК>> Зачастую std::vector оказывается быстрее, чем std::deque.
s> А где это наблюдается?
Простой тест по добавлению элементов в конец последовательности.
s> Вроде бы deque шустрее на больших объёмах данных, чем vector, так как s> память ему не обязательно выделять единым блоком, что опять таки s> ведёт к увеличению скорости.
Зато "обслуга" у std::deque тяжелее... Т.е., конечно, в пределе, на достаточно больших объемах,
std::deque таки обгонит std::vector. Вопрос в том, что является "достаточно большими объемами".
Например, у Dinkumware на простых структурах (два int) на моих тестах std::vector оказывался
быстрее вплоть до 10 000 элементов.
Posted via RSDN NNTP Server 1.6 RC1
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
, то выходит вот что:
), то std::list, иначе std::vector.
