Experiment::ListMergeSort< T, Iterator, Lessor, Metrics > Class Template Reference

Merge Sort algorithm using lists to hold the data. More...

#include <ListMergeSort.h>

Public Types
typedef T	value_type
	Convenience typedef of the type of data in the list. More...
typedef DoubleLinkedList< T >	DataList
	Convenience typedef of the type of list used in this sort. More...
typedef DataList::iterator	DataIter
	Convenience typedef of the iterator of DataList. More...

Public Member Functions
void	sort (const Iterator begin, const Iterator end)
	Sort from begin to end by copying. More...
void	sort (DataList &data)
	Sort the values in data in constant memory by removing the disassembling data, sorting the values and reassembling it. More...

Public Attributes
Metrics	metrics
	Collection of metrics for the caller to inspect details of the sort. More...

Detailed Description

template<class T, class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>
class Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >

Merge Sort algorithm using lists to hold the data.

The real advantage of this class is that sort() taking a DoubleLinkedList will sort without copying the values in the List – the list will be disassembled and reassembled in the correct order.

Template Parameters

T	the data type being sorted
Lessor	to compare items
Metrics	to collect metrics on the sort –

See also

NoSortMetrics as an example

Examples

ListMergeSortExample.cpp.

Definition at line 60 of file ListMergeSort.h.

Member Typedef Documentation

DataIter

template<class T , class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>

typedef DataList::iterator Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >::DataIter

Convenience typedef of the iterator of DataList.

Definition at line 69 of file ListMergeSort.h.

DataList

template<class T , class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>

typedef DoubleLinkedList<T> Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >::DataList

Convenience typedef of the type of list used in this sort.

Definition at line 66 of file ListMergeSort.h.

value_type

template<class T , class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>

typedef T Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >::value_type

Convenience typedef of the type of data in the list.

Definition at line 63 of file ListMergeSort.h.

Member Function Documentation

sort() [1/2]

template<class T , class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>

void Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >::sort ( const Iterator  begin, const Iterator  end  )

inline

Sort from begin to end by copying.

First, this copies all values to temporary storage. Then it stores. Finally, it copies the results back.

This avoids copying values at each stage of the sort as an array-based merge sort would; however, it still copies the values twice.

Parameters

begin	first value to sort
end	the position after the last value to sort

Examples

ListMergeSortExample.cpp.

Definition at line 91 of file ListMergeSort.h.

sort() [2/2]

template<class T , class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>

void Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >::sort ( DataList &  data )

inline

Sort the values in data in constant memory by removing the disassembling data, sorting the values and reassembling it.

Definition at line 126 of file ListMergeSort.h.

Member Data Documentation

metrics

template<class T , class Iterator = T*, class Lessor = std::less<T>, class Metrics = NoSortMetrics<T>>

Metrics Experiment::ListMergeSort< T, Iterator, Lessor, Metrics >::metrics

Collection of metrics for the caller to inspect details of the sort.

Definition at line 275 of file ListMergeSort.h.

---

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

• include/ListMergeSort.h