CODEWITHSUNDEEP
c++sortingbooststdpreload
AntonioLimosani
AntonioLimosani

Reputation: 11

Replace std::sort with boost::sort

I would like to replace std::sort with boost::sort to compare the performance between them. A colleague recommended that I create a shared library with a re-definition of std::sort that calls boost:sort, and then simply use LD_PRELOAD to bring in the new shared library, and therefore override std:sort. Will this work? If so, can someone post an example of how to replace a stl function?

Upvotes: 1

Views: 2459

Answers (1)

user3920237
user3920237

Reputation:

To corroborate Neil Kirk's claim, we can take a look at the boost/range/algorithm/sort.hpp header. And range::sort is in fact implemented in terms of std::sort.

template<class RandomAccessRange>
inline RandomAccessRange& sort(RandomAccessRange& rng)
{
    BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
    std::sort(boost::begin(rng), boost::end(rng));
    return rng;
}

/// \overload
template<class RandomAccessRange>
inline const RandomAccessRange& sort(const RandomAccessRange& rng)
{
    BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
    std::sort(boost::begin(rng), boost::end(rng));
    return rng;
}

/// \overload
template<class RandomAccessRange, class BinaryPredicate>
inline RandomAccessRange& sort(RandomAccessRange& rng, BinaryPredicate pred)
{
    BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
    std::sort(boost::begin(rng), boost::end(rng), pred);
    return rng;
}

/// \overload
template<class RandomAccessRange, class BinaryPredicate>
inline const RandomAccessRange& sort(const RandomAccessRange& rng, BinaryPredicate pred)
{
    BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
    std::sort(boost::begin(rng), boost::end(rng), pred);
    return rng;
}

So there's no point in doing this. The page for range::sort also lists the complexity which mirrors the complexity for std::sort:

Source: boost

O(N log(N)) comparisons (both average and worst-case), where N is distance(rng).

Source: cppreference

O(N·log(N)), where N = std::distance(first, last) comparisons on average. (until C++11)

O(N·log(N)), where N = std::distance(first, last) comparisons. (since C++11)

Upvotes: 4

Related Questions