boost::spreadsort for std::pair

Question

Boost 1.58 has new library spreadsort, so I tried it out. I wrote simple sample for sorting vector of pairs of int:

#include <chrono>
#include <iomanip>
#include <boost/sort/sort.hpp>
// based on http://www.boost.org/doc/libs/develop/libs/sort/doc/html/sort/sort_hpp/string_sort.html
struct lessthan
{
 inline bool operator()(const std::pair<int, int> &x, const std::pair<int, int> &y) const
 {
 return x < y;
 }
};
struct bracket
{
 inline unsigned char operator()(const std::pair<int, int> &x, size_t offset) const
 {
 if (offset < sizeof(int))
 return get_char(x.first, offset);
 return get_char(x.second, offset - sizeof(int));
 }
private:
 inline unsigned char get_char(int x, size_t offset) const
 {
 static const boost::uint64_t base_mask = 0xff;
 const int bit_shift = 8 * (sizeof(int) - offset - 1);
 unsigned char result = (x & (base_mask << bit_shift)) >> bit_shift;
 if (offset == 0)
 return result ^ 128;
 return result;
 }
};
struct getsize
{
 inline size_t operator()(const std::pair<int, int> &) const
 {
 return 2 * sizeof(int);
 }
};
bool verify_sorted(const std::vector<std::pair<int, int>> & a)
{
 lessthan ls;
 for (size_t i = 0; i + 1 < a.size(); i++)
 {
 if (ls(a[i + 1], a[i]))
 return false;
 }
 return true;
}
int main()
{
 std::vector<std::pair<int, int>> r;
 srand(12345);
 for (size_t i = 0; i < 10000000; i++)
 r.push_back(std::make_pair(rand(), rand()));
 {
 std::vector<std::pair<int, int>> a = r;
 auto t_start = std::chrono::high_resolution_clock::now();
 std::sort(a.begin(), a.end());
 auto t_end = std::chrono::high_resolution_clock::now();
 std::cout << std::fixed << std::setprecision(2) << "CPU time used (std::sort): "
 << std::chrono::duration<double, std::milli>(t_end - t_start).count()
 << " ms\n";
 std::cout << (verify_sorted(a) ? "OK." : "FAIL!") << std::endl;
 }
 {
 std::vector<std::pair<int, int>> a = r;
 auto t_start = std::chrono::high_resolution_clock::now();
 boost::sort::spreadsort::string_sort(a.begin(), a.end(), bracket(), getsize(), lessthan());
 auto t_end = std::chrono::high_resolution_clock::now();
 std::cout << std::fixed << std::setprecision(2) << "CPU time used (boost::sort::spreadsort::string_sort): "
 << std::chrono::duration<double, std::milli>(t_end - t_start).count()
 << " ms\n";
 std::cout << (verify_sorted(a) ? "OK." : "FAIL!") << std::endl;
 }
}

It's faster then std::sort, but it's seems to me this implementation is to heavyweight and ugly for such a simple task. Can anyone propose better one?

• JaDogg: This doesn't look like you are asking for a code review !!

Answer 1

You spend a lot of lines of code trying to get the expressions lessthan(), getsize(), and bracket() to behave like plain old functions. Consider just using plain old functions, instead. For example:

static uint8_t get_char(int x, size_t offset)
{
 const int bit_shift = 8 * (sizeof(int) - offset - 1);
 uint8_t result = (x >> bit_shift) & 0xFF;
 if (offset == 0) result ^= 128;
 return result;
}
static uint8_t bracket(const std::pair<int,int>& x, size_t offset)
{
 if (offset < sizeof(int))
 return get_char(x.first, offset);
 return get_char(x.second, offset - sizeof(int));
}
...
string_sort(a.begin(), a.end(), bracket, getsize(), lessthan());

You could also productively replace the expression getsize() with

auto getsize = [](auto){ return 2*sizeof(int); };
...
string_sort(a.begin(), a.end(), bracket, getsize, lessthan());

Finally, lessthan is equivalent to std::less<std::pair<int,int>>, so you can just write

string_sort(a.begin(), a.end(), bracket, getsize, std::less<>());

That's the kind of shortening you were looking for, right? :)