C++ Vector Sorting – Is std::vector Making Struct Sort Slow?

c++sortingstructvector

I have a list of structs that I am sorting by one of the members. I am using std::sort with my own comparison function, that part is fine. However, I notice a (very) large performance gap when I change the struct from:

struct square
{
    float x;
    float y;
    float z;

    float scale;
    float angle;

    GLuint texture;
};

to

struct square
{
    float x;
    float y;
    float z;

    float scale;
    float angle;

    GLuint texture;
    std::vector <float> color;
};

I have since used an entirely different method, and I realize that using a vector like this is a bad idea (I know the size of array – rgb) but I was wondering why I got the performance hit. I was comparing the z values to sort.

Here is my sorting function and struct list:

std::vector <square> square_list;
//Then add a bunch of squares

bool sort (square a,square b)
{
   return a.z < b.z;
}

//Here is the sort that is slow
std::sort (square_list.begin(),square_list.end(),sort);

I wonder if it has anything to do with re-ordering the list of structs as their size is significantly bigger in the second case?

Thanks for any responses.

Best Answer

bool sort (square a,square b)

This copies the structs each time, including the vectors. Vectors are slower to copy than normal arrays. You should use this instead.

bool sort (const square& a, const square& b)

If you are using C++11, you can replace the vector with std::array as the size is constant.

Related Question