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.

Both sequence [bengin, middle[ and [middle, end[ need to be ordered.
use MergeInPlace to proceed the merge in place: Takes lower memory consumption and higher computation consumption.
Template Parameters
ITtype using to go through the collection.
Comparefunctor type (std::less_equal in order, std::greater_equal for inverse order).
begin,middle,enditerators 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.

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 

Definition at line 97 of file merge.hxx.

98  {
99  if (std::distance(begin, middle) < 1 || std::distance(middle, end) < 1)
100  return;
102  // Create buffer with appropriate space
103  std::vector<typename std::iterator_traits<IT>::value_type> buffer;
104  buffer.resize(std::distance(begin, end));
105  auto buffIt = buffer.begin();
106  auto tmpBegin = begin;
108  // Merge into the buffer array taking one by one the lowest sequence element
109  const auto curMiddle(middle);
110  while (begin != curMiddle && middle != end)
111  {
112  if (Compare()(*begin, *middle))
113  *buffIt++ = *begin++;
114  else
115  *buffIt++ = *middle++;
116  }
118  // Finish remaining list into the buffer
119  for (; begin != curMiddle; ++buffIt, ++begin)
120  *buffIt = *begin;
121  for (; middle != end; ++buffIt, ++middle)
122  *buffIt = *middle;
124  // Refill array given the right position
125  for (buffIt = buffer.begin(); buffIt != buffer.end(); ++buffIt, ++tmpBegin)
126  *tmpBegin = *buffIt;
127  }

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