Testing STL container performance

[Lowest0ne]

I'm trying to figure out a good container for my needs. I wont have many insertions, but look up needs to be as fast as possible. I figure then to sequence container and then sort it after insertion. I'm second guessing myself as I right this, hmm...

Anyway, right now I am trying to figure out what container sorts the fastest. I have this Windows dependent code, which basically says:

Create an array of random numbers,
copy the array into a vector using push_back (no reserved space)
sort the vector
copy the array into a forward_list
sort the forward_list

The Windows dependency is for counting milliseconds of the program.

#include <Windows.h>
#include <iostream>
#include <forward_list>
#include <vector>
#include <algorithm>
#include <random>

#define AMT 500000
#define MSEC GetTickCount()
typedef DWORD timeType;

void testVector(int *arr)
{
	std::vector<int> v;
	
	std::cout << "Vector Insertion: ";
	timeType start = MSEC;
	for (int i = 0; i < AMT; i++)
		v.push_back(arr[i]);
	timeType end = MSEC;
	timeType total = end - start;
	std::cout << total << std::endl;

	std::cout << "Vector Sort: ";
	start = MSEC;
	std::sort(v.begin(), v.end());
	end = MSEC;
	total += end - start;
	std::cout << end - start << std::endl;


	std::cout << "Vector Total: " << total << std::endl;
}
void testList(int *arr)
{
	std::forward_list<int> l;
	
	std::cout << "List Insertion: ";
	timeType start = MSEC;
	for (int i = 0; i < AMT; i++)
		l.push_front(arr[i]);
	timeType end = MSEC;
	timeType total = end - start;
	std::cout << total << std::endl;

	std::cout << "List Sort: ";
	start = MSEC;
	l.sort();
	end = MSEC;
	total += end - start;
	std::cout << end - start << std::endl;


	std::cout << "List Total: " << total << std::endl;

}
int main(void)
{
	std::random_device rand;
	int *arr;
	arr = new int[AMT];
	for (int i = 0; i < AMT; i++)
		arr[i] = rand() % (AMT);

	testVector(arr);
	testList(arr);

	std::cin.get();
	delete [] arr;
	return 0;
}

The output being:

Vector Insertion: 218
Vector Sort: 1079
Vector Total: 1297
List Insertion: 1531
List Sort: 84282
List Total: 85813

How in the world is the forward_list so bad? I thought this was something it would out perform the vector in.

Edit: Do I need a more complex data type to sort? Or perhaps a class with complicated constructors?

[ne555]

http://en.wikipedia.org/wiki/Locality_of_reference
(on a related note, check out `data-driven programming')

Use a profiler.

>Do I need a more complex data type to sort? Or perhaps a class with complicated constructors?
Test it with data type that you expect to use.

[Lowest0ne]

Thanks for the links. I made my data type more complex and the vector started to be slower.

Test it with data type that you expect to use.

Thanks for that, honestly. There is a lot for me to do now, I don't even know if this is going to be a bottleneck for the program.

[htirwin]

Make sure you compile with optimizations.

[ne555]

> I made my data type more complex and the vector started to be slower.
If with more complex you mean bigger, consider storing pointers in the vector.
Then the containers would be equivalent (one pointer and one value for every element) and you'll be comparing the algorithms.