sortingpointersstruct

Sorting a Vector Containing Pointer to Struct VS Struct


I am sorting a large vector containing structs using heapsort and the runtime of my code is quite slow. Instead of storing a struct in the vector, I want to store a pointer to the struct now.

My question is, under the hood, what is actually happening when I sort things and would it be faster if I store a pointer to a struct as opposed to storing the struct itself?


Solution

  • This is answer is outdated by C++11 move semantics

    Certainly yes. Storing objects as values in stl containers will result in running copy constructor of the stored object.

    In general, for performance, it is better to store pointers instead. However you will need to be more carefull about leaks and exception safety once you are using pointers instead.

    Anyway, the simplest thing happening on sorting is the swap algorithm. Which involves copy constructing:

    void swap(T & a, T & b)
    {
        T c = a; // copy constructing
        a = b; // copy constructing
        b = c; // copy constructing
    }
    

    It is definitelly much more faster to copy pointer instead of bigger objects.