CODEWITHSUNDEEP
c++performancesortingvector
confusedCoder
confusedCoder

Reputation: 223

C++ sort vector<double> vs vector<Object> keyed on double member variable

I have a vector of custom objects I'm sorting and noticed that the sort took a bit longer than expected. I decided to look further into it and adapted the code from this sort benchmark where instead of vector<double>, I'm sorting a vector<Foo>. The result is that it takes about 2.5 times longer to sort the vector of custom objects, measured using boost::chrono::steady_clock as in the original benchmark code. This doesn't really make sense to me since the key is the same and the memory is already allocated by the time sorting starts. Why is that and does this affect other operations on such a vector, for example binary_search?

class Foo {
public:
  double _barKey;
  string _barStr1;
  string _barStr2;
  string _barStr3;
  int _barInt;

  Foo(double bk, string bs1, string bs2, string bs3);
};

  Foo::Foo(double bk, string bs1 = "", string bs2 = "", string bs3 = "") {
    _barKey = bk;
    _barStr1 = bs1;
    _barStr2 = bs2;
    _barStr3 = bs3;
    _barInt = 0;
}

struct less_than_key {
    inline bool operator() (const Foo& lhs, const Foo& rhs)
    {
        return (lhs._barKey < rhs._barKey);
    }
};

....

std::sort(std::begin(V), std::end(V), less_than_key());

Compiled using:

g++ -O2 -std=c++11 sort_object_bench.cpp -lboost_chrono -lboost_system -o gcc_test

Upvotes: 0

Views: 119

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122228

This doesn't really make sense to me since the key is the same and the memory is already allocated by the time sorting starts.

The difference is not due to allocations taking place. The size of the vector doesnt change while sorting, so there are no allocations. However, sort has to copy the elements around to put them in the right place. And it shouldnt be too surprising that copying a double, 3 strings and an int takes more time than copying a single double.

Upvotes: 3

Related Questions