Dennis Hedegaard's Blog

Here are some test results from a simple benchmark using vector, list, queue and stack in the c++ stl:

The benchmarks are done on 40.000.000 structs with a string and an int.

With aggressive optimizations (-march=native -funroll-all-loops -fomit-frame-pointer -finline -O9 -ffast-math):

$ ./stacktest
5.59 seconds
$ ./linkedtest
8.05 seconds
$ ./queuetest
5.51 seconds
$ ./vectortest
10 seconds

Without aggressive optimizations:

$ ./stacktest
8.3 seconds
$ ./linkedtest
12.84 seconds
$ ./queuetest
7.82 seconds
$ ./vectortest
12.89 seconds

What’s noteworthy is that a queue and a stack is pretty close in performance, compared to a vector and list.

The code for the project is on git for now:

http://git.neo2k.dk/?p=sum_benchmark.git;a=summary

I’m using cmake for makefiles :>

c++ is partly an extension on the c language, it introduces things like exceptions, classes and more.

Amongst these things are the c++ standard library, which consists of already implemented generic datastructures. I’m mostly used to java, so it’s nice to see vectors, lists, sets, queues and stacks implemented in a generic way.

For now I’ve found no smart way to use this new knowledge, for now one of the new things is the whole namespace system, which looks alot like packages in java. For instance, std is the standard package, you can the “import” methods and classes after including in the following matter:

using std::cout;

That includes the cout, which is the standard output stream, this is usefull for keeping repetitive code to a minimum, but one should of course consider the impacts of putting too many things in the namespace.

For instance, the vector is in std, so it’s called std::vector. A vector of course has an iterator, which is below vector as: std::vector::iterator.

For sorting, binary searches and so on, there’s the algorithm header, the funny thing is, the sort algorithm can only be used on a vector. Lists for instance, have their own sort as a static method in the list class, list is ofcourse std::list. A list is sorted like this:

list.sort();

For vectors, it’s a bit different, you use the algorithms header, and use the sort method in there, that sorting method uses an iterator for the start, and one for the end.

sort(v.begin(), c.end());

this seems to work like this, because you cannot take an object in the middle on a vector, thereby the vector datastructure is like an array in the memory, and the iterator is a pointer being pushed. begin() and end() are “locations” as well, for instance you start at begin() and then you push the iterator like you push a pointer, with: iterator++ until it is == end().

The list class in c++, has erase methods (which removes a “spot” in the list) and a remove method (which removes an “object” from the list). In java we have method overloading, so both methods are called remove. I am not sure wether c++ has this or not, and if it does, I’m not currently sure of the policy of why the 2 methods could not have the same names here as well.

For now, it seems very easy to use the c++ standard library, when you have some background knowledge from another language, much like it.

Here’s some example code with a list of ints, I push 3 items in the back of the list, print them with an iterator. I then sort the list and print with the iterator from the same position as the first time:

#include <iostream>
#include <list>
#include <iterator>

using std::cout;
using std::list;
using std::endl;

int main() {
 list<int> test;
 list<int>::iterator ite;
 test.push_back(10);
 test.push_back(5);
 test.push_back(2);
 cout << "pre sort:" << endl;
 ite = test.begin();
 while (ite != test.end())
 cout << *(ite++) << endl;
 test.sort();
 cout << "post sort:" << endl;
 ite = test.begin();
 while (ite != test.end())
 cout << *(ite++) << endl;
 return 0;
}