Компиляторы C++

[Вудруф]

Код:

#include <iostream>
#include <vector>

#include <cstdlib>

#include <QVector>

int main(int argc, char *argv[])
{
	time_t t1, t2;

	std::time (&t1);
	for (int i = 0; i < 10000; ++i)
	{
		std::vector<int> stdList;
		for (int i = 0; i < 100000; i++)
			stdList.push_back(i);
	}
	std::time (&t2);

	std::cout << "STD: " << t2 - t1 << '\n';

	std::time (&t1);
	for (int i = 0; i < 10000; ++i)
	{
		QVector<int> qtList;
		for (int i = 0; i < 100000; i++)
			qtList.append(i);
	}
	std::time (&t2);

	std::cout << "Qt: " << t2 - t1 << '\n';
}

Вывод:
STD: 25
Qt: 36

Компилятор: GCC (MinGW) 3.4.5
Опции: -O3

Два цикла для того, чтобы не выделять много памяти.
Я не запускал программу в предложенном виде, а комментировал всё, относящееся к QVector или к std::vector в зависимости от теста.

По памяти:
Пик для STD - 1648 Кб
Пик для Qt - 2212 Кб

Для списка (list):
Время:
STD: 945
Qt: 38 (!)
Память:
Пик для STD - 3140 Кб
Пик для Qt - 2200 Кб

Странные результаты, такое ощущение, что QList - это не полноценный список, а дек (в том виде как он представлен в STD).
В assistant видим: "It stores a list of values and provides fast index-based access as well as fast insertions and removals.", что в какой-то мере подтверждает наши выводы.
Для дека (std::deque):
Время: 16 (!)
Память: 1192 Кб (!)

А ведь список - это контейнер, ориентированный на быструю вставку элемента в произвольное место. Проверим время вставки в произвольное место.
Вставляем в конец три элемента, запоминаем итератор, вставляем ещё один элемент, а затем вставляем много элементов перед итератором:
Время:
STD: 9
Qt: <1
std::deque: 2

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

Вывод: контейнеры STD работают не хуже контейнеров Qt. Более того, только для использования контейнеров не имеет смысл тащить за собой QtCore. STL весит значительно меньше.
С другой стороны QList работает быстрее, чем std::list...
С использованием reserve тесты для векторов становятся неинтересными. Равно как нет смысла проверять скорость обращения к элементам для тех же векторов.
По идее надо было бы тесты сделать более обширными, посмотреть также QMap и std::map, но лениво... Пока что покопаюсь в исходниках.
Возможно, падение производительности связано с гарантиями операций, можно и в эту сторону копнуть.

[pastor]

Воспользовавшись примером _govorilka, провел тесты с некоторыми контейнерами Qt - QMap, QList, QLinkedList, QVector и STL - std::map, std::list, std::vector. Результаты получиличь следующие:

               

Код:

           std::list        QList

append:      2100            330
prepend:     2100            450
insert:      47              8700 

ЗЫ: В тесте на insert вставка производилась после 1 элемента. Кол-во итераций ученьшено в 100 раз.

                 

Код:

          std::list        QLinkedList

append:      2100               1970
prepend:     2100               2000
insert:      2100               2100 

                 

Код:

            std::vector            QVector

append:        235                  330
prepend:        -                   8700
insert:         -                   8700 

ЗЫ: В тесте на insert вставка производилась после 1 элемента. В двух последних тестах кол-во итераций ученьшено в 100 раз.

                           

Код:

               std::map              QMap

add new item:    750                 550 

ЗЫ: Кол-во итераций ученьшено в 10 раз.



Qt 4.2.2, VS2005, Приложения собраны в Release

[Dendy]

Всё нужно использовать там, для чего оно предназначено.
Большинство операций со списком связаны с добавлением/удалением в начало и конец. Для этих случаев используется QList, который внутри представляет собой цепочку массивов. Результаты - сами видите. Очень нужный контейнер, со внутренней структурой, которой нет аналогов по оптимизации скорости работы.
В единицах случаев, когда нужно вставлять/удалять элементы всередине списка, причём гораздо чаще, чем простое наполнение списка - используется QLinkedList, элементы которого хранят ссылки на следующий и предыдущий. Фактически - это аналог std::list.
Ну и с вектором всё понятно. Этот класс нужен для обращения к цельному куску памяти, выделенной заранее. Если и происходит изменение его размера - то очень редко. Соответственно вышеприведённый тест не имеет смысла, разве что чтобы ещё раз убедиться в необходимости грамотного подхода к выбору контейнера.

[pastor]

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

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

[evilguard]

То есть QList - аналог std::deque, а QLinkedList - std::list?

[_govorilka]

...Если с контейнерами от тролей всё ясно, то понятие "стандартные (stl::list, stl::vector)" уж очень абстрактное. Реализаций море. Хоть бы ОС, компиллер, либы упомянули.

Вот, на чем проверял WinXPPro/MC++8.0 (либа стандартная), как проверял написано в исходнике. Если проверите под gcc, скажу вам огромное спасибо!!!
В Qt, как мне кажется, iterator'ы написаны удобнее, или просто к ним уже привык. По Qt контенерам есть справка, а по STL...

[Вудруф]

По QVector: зачем разрешать явно неэффективные операции? Если такие операции нужны, то нужно использовать другой контейнер. Вот в std::vector insert нет, и это правильно.
Да, получается, что QList - аналог std::deque.
Кстати, логично, что у меня со вставкой результаты дурные получались. У меня перемещать надо было только два элемента, а не все. Вставка после первого элемента - более правильный тест.
Для std::vector push_back имеет смысл делать. При грамотном перераспределении памяти операция получается не накладной. Тут надо смотреть асимптотическую (в пределе) сложность операции. И тут QVector проигрывает.
Шутки ради ещё надо сравнить скорость поиска в std::map и QMap, скорость обращения к элементам в векторе и деке, а также скорость выполнения std::sort для... std::list и QLinkedList.

добавлено спустя 5 минут:

 

По Qt контенерам есть справка, а по STL...

А Google не рулит? Вот сходу ссылки нашёл:

http://www.sgi.com/tech/stl/
http://solarix.ru/for_developers/cpp/stl/stl.shtml
http://en.wikipedia.org/wiki/Standard_Template_Library

И книжка хорошая есть.
Nicolai M. Josuttis "C++ Standard Library, The: A Tutorial and Reference"

[evilguard]

Я конечно точные тесты не проводил, но ради интереса модифицировал совю программу. В ней использовались объекты QPolygonF. Полигоны я заполнял точками по одной, с нуля, то есть изначально контейнер пустой и по ходу выполнения программы заполняется точками, причем как в конец - append, так и в начало - prepend. Посмотрел на здешние результаты, решил заменить QPolygon (который QVector<QPointF>) на QList<QPointF> - ожидал десятикратный прирост в операции prepend, а вместо этого общая скорость расчета увеличилась раза в 2.

добавлено спустя:

 еще раз проверил, в той част программы, где я ожидал прироста от prepend + QList, видимого прироста не обнаружил.
В другой части кода, где заметное падение производительности от использования QList - раньше я использовал конструктор QVector<QPointF> container(size). Для QList же выделение памяти блоком невозможно, поэтому наверное и такое падение скорости. Хотя точно не уверен.