SHA_Sort::MergeWithBuffer< Container, IT > Class Template Reference

#include <merge.hxx>

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

Detailed Description

template<typename Container, typename IT>
class SHA_Sort::MergeWithBuffer< Container, IT >

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

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.

Complexity

O(N).

Template Parameters

IT

type.

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 99 of file merge.hxx.

Member Function Documentation

template<typename Container, typename IT>

void SHA_Sort::MergeWithBuffer< Container, IT >::operator() ( IT  begin, IT  middle, IT  end  )

inline

Definition at line 102 of file merge.hxx.

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

      Container buffer;
      buffer.resize(std::distance(begin, end)); // Reserve right space (e.g. string container)
      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 (*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