Здравствуйте, SchweinDeBurg, Вы писали:
S> Требуется контейнер, максимально быстрый по совокупности двух операций:
S> 1) поэлементное добавление в конец;
std::deque
std::vector
S> 2) единовременный убой всех элементов.
Требуется контейнер, максимально быстрый по совокупности двух операций:
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 производят плачевное впечатление.
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
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Я думаю, что реализация самого вектора не обязана быть такой, чтобы выделять один длинный буфер на все элементы.
Можно сделать свой гибрид, скажем, список векторов фиксированной длины. Т.е. выделение (и уничтожение) памяти будет происходить сегментами. Главное, хорошо подобрать размер сегмента.
Здравствуйте, superuriy, Вы писали:
s> Я думаю, что реализация самого вектора не обязана быть такой, чтобы s> выделять один длинный буфер на все элементы.
Обязана.
s> Можно сделать свой гибрид, скажем, список векторов фиксированной длины. s> Т.е. выделение (и уничтожение) памяти будет происходить сегментами.
Это std::deque.
Posted via RSDN NNTP Server 1.6 RC1
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Это std::deque.
Понятно.
Усё уже украдено — до нас...
Re[3]: STL - самый быстрый контейнер
От:
Аноним
Дата:
22.08.03 14:35
Оценка:
Здравствуйте, Павел Кузнецов, Вы писали:
s>> Можно сделать свой гибрид, скажем, список векторов фиксированной длины. s>> Т.е. выделение (и уничтожение) памяти будет происходить сегментами.
ПК>Это std::deque.
Подожди, а тогда какими же кусками (размеры) ввыделяются сегменты?
, то выходит вот что:
), то std::list, иначе std::vector.
