huc::sort::MergeWithBuffer< IT, Compare > Class Template Reference

#include <merge.hxx>

Public Member Functions
void	operator() (IT begin, IT middle, IT end)

Detailed Description

template<typename IT, typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>
class huc::sort::MergeWithBuffer< IT, Compare >

MergeWithBuffer Functor - Merging of two ordered sequences of a collection of elements contained in [begin, middle[ and [middle, end[ using intermediate buffer.

Warning

Both sequence [bengin, middle[ and [middle, end[ need to be ordered.

Remarks

use MergeInPlace to proceed the merge in place: Takes lower memory consumption and higher computation consumption.

Template Parameters

IT	type using to go through the collection.
Compare	functor type (std::less_equal in order, std::greater_equal for inverse order).

Parameters

begin,middle,end

iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns

void.

Definition at line 94 of file merge.hxx.

Member Function Documentation

template<typename IT, typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>

void huc::sort::MergeWithBuffer< IT, Compare >::operator() ( IT  begin, IT  middle, IT  end  )

inline

Definition at line 97 of file merge.hxx.

      {
        if (std::distance(begin, middle) < 1 || std::distance(middle, end) < 1)
          return;

        // Create buffer with appropriate space
        std::vector<typename std::iterator_traits<IT>::value_type> buffer;
        buffer.resize(std::distance(begin, end));
        auto buffIt = buffer.begin();
        auto tmpBegin = begin;

        // Merge into the buffer array taking one by one the lowest sequence element
        const auto curMiddle(middle);
        while (begin != curMiddle && middle != end)
        {
          if (Compare()(*begin, *middle))
            *buffIt++ = *begin++;
          else
            *buffIt++ = *middle++;
        }

        // Finish remaining list into the buffer
        for (; begin != curMiddle; ++buffIt, ++begin)
          *buffIt = *begin;
        for (; middle != end; ++buffIt, ++middle)
          *buffIt = *middle;

        // Refill array given the right position
        for (buffIt = buffer.begin(); buffIt != buffer.end(); ++buffIt, ++tmpBegin)
          *tmpBegin = *buffIt;
      }

---

The documentation for this class was generated from the following file:

• merge.hxx