tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare > Class Template Reference
Algorithms

Range used in quicksort to split elements into subranges based on a value. More...

`#include <parallel_sort.h>`

Inheritance diagram for tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >:
Collaboration diagram for tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >:

## Public Member Functions

| quick_sort_range (RandomAccessIterator begin_, size_t size_, const Compare &comp_)
bool | empty () const
bool | is_divisible () const
| quick_sort_range (quick_sort_range &range, split)

## Public Attributes

const Compare & | comp
size_t | size
RandomAccessIterator | begin

## Static Public Attributes

static const size_t | grainsize = 500

## Private Member Functions

size_t | median_of_three (const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
size_t | pseudo_median_of_nine (const RandomAccessIterator &array, const quick_sort_range &range) const
size_t | split_range (quick_sort_range &range)
Private Member Functions inherited from tbb::internal::no_assign
void | operator= (const no_assign &)=delete
| no_assign (const no_assign &)=default
| no_assign ()=default

## Detailed Description

### template<typename RandomAccessIterator, typename Compare>
class tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >

Range used in quicksort to split elements into subranges based on a value.

The split operation selects a splitter and places all elements less than or equal to the value in the first range and the remaining elements in the second range.

Definition at line 46 of file parallel_sort.h.

## Constructor & Destructor Documentation

## quick_sort_range() [1/2]

template<typename RandomAccessIterator , typename Compare >

tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::quick_sort_range | ( | RandomAccessIterator | begin_,
|  | size_t | size_,
|  | const Compare & | comp_
| ) |  |

inline

Definition at line 106 of file parallel_sort.h.

:
comp(comp_), size(size_), begin(begin_) {}
tbb::interface9::internal::quick_sort_range::size
size_t size
Definition: parallel_sort.h:103
tbb::interface9::internal::quick_sort_range::comp
const Compare & comp
Definition: parallel_sort.h:102
tbb::interface9::internal::quick_sort_range::begin
RandomAccessIterator begin
Definition: parallel_sort.h:104

## quick_sort_range() [2/2]

template<typename RandomAccessIterator , typename Compare >

tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::quick_sort_range | ( | quick_sort_range< RandomAccessIterator, Compare > & | range,
|  | split |
| ) |  |

inline

Definition at line 112 of file parallel_sort.h.

: comp(range.comp)
, size(split_range(range))
// +1 accounts for the pivot element, which is at its correct place
// already and, therefore, is not included into subranges.
, begin(range.begin+range.size+1) {}
tbb::interface9::internal::quick_sort_range::split_range
size_t split_range(quick_sort_range &range)
Definition: parallel_sort.h:62

## Member Function Documentation

## empty()

template<typename RandomAccessIterator , typename Compare >

bool tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::empty | ( |  | ) | const

inline

Definition at line 109 of file parallel_sort.h.

{return size==0;}

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

## is_divisible()

template<typename RandomAccessIterator , typename Compare >

bool tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::is_divisible | ( |  | ) | const

inline

Definition at line 110 of file parallel_sort.h.

{return size>=grainsize;}
tbb::interface9::internal::quick_sort_range::grainsize
static const size_t grainsize
Definition: parallel_sort.h:101

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::grainsize, and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

## median_of_three()

template<typename RandomAccessIterator , typename Compare >

size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::median_of_three | ( | const RandomAccessIterator & | array,
|  | size_t | l,
|  | size_t | m,
|  | size_t | r
| ) |  | const

inline private

Definition at line 48 of file parallel_sort.h.

{
return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp( array[l], array[r]) ? r : l ) )
: ( comp(array[r], array[m]) ? m : ( comp( array[r], array[l] ) ? r : l ) );
}

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::comp.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine().

Here is the caller graph for this function:

## pseudo_median_of_nine()

template<typename RandomAccessIterator , typename Compare >

size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine | ( | const RandomAccessIterator & | array,
|  | const quick_sort_range< RandomAccessIterator, Compare > & | range
| ) |  | const

inline private

Definition at line 53 of file parallel_sort.h.

{
size_t offset = range.size/8u;
return median_of_three(array,
median_of_three(array, 0, offset, offset*2),
median_of_three(array, offset*3, offset*4, offset*5),
median_of_three(array, offset*6, offset*7, range.size - 1) );
}
tbb::interface9::internal::quick_sort_range::median_of_three
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
Definition: parallel_sort.h:48

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::median_of_three(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range().

Here is the call graph for this function:
Here is the caller graph for this function:

## split_range()

template<typename RandomAccessIterator , typename Compare >

size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range | ( | quick_sort_range< RandomAccessIterator, Compare > & | range | ) |

inline private

Definition at line 62 of file parallel_sort.h.

{
using std::iter_swap;
RandomAccessIterator array = range.begin;
RandomAccessIterator key0 = range.begin;
size_t m = pseudo_median_of_nine(array, range);
if (m) iter_swap ( array, array+m );
size_t i=0;
size_t j=range.size;
// Partition interval [i+1,j-1] with key *key0.
for(;;) {
__TBB_ASSERT( i<j, NULL );
// Loop must terminate since array[l]==*key0.
do {
--j;
__TBB_ASSERT( i<=j, "bad ordering relation?" );
} while( comp( *key0, array[j] ));
do {
__TBB_ASSERT( i<=j, NULL );
if( i==j ) goto partition;
++i;
} while( comp( array[i],*key0 ));
if( i==j ) goto partition;
iter_swap( array+i, array+j );
}
partition:
// Put the partition key were it belongs
iter_swap( array+j, key0 );
// array[l..j) is less or equal to key.
// array(j..r) is greater or equal to key.
// array[j] is equal to key
i=j+1;
size_t new_range_size = range.size-i;
range.size = j;
return new_range_size;
}
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::interface9::internal::quick_sort_range::pseudo_median_of_nine
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
Definition: parallel_sort.h:53

References __TBB_ASSERT, tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::begin, tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::comp, tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

Here is the call graph for this function:

## Member Data Documentation

## begin

template<typename RandomAccessIterator , typename Compare >

RandomAccessIterator tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::begin

Definition at line 104 of file parallel_sort.h.

Referenced by tbb::interface9::internal::quick_sort_body< RandomAccessIterator, Compare >::operator()(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range().

## comp

template<typename RandomAccessIterator , typename Compare >

const Compare& tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::comp

Definition at line 102 of file parallel_sort.h.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::median_of_three(), tbb::interface9::internal::quick_sort_body< RandomAccessIterator, Compare >::operator()(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range().

## grainsize

template<typename RandomAccessIterator , typename Compare >

const size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::grainsize = 500

static

Definition at line 101 of file parallel_sort.h.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::is_divisible().

## size

template<typename RandomAccessIterator , typename Compare >

size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size

Definition at line 103 of file parallel_sort.h.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::empty(), tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::is_divisible(), tbb::interface9::internal::quick_sort_body< RandomAccessIterator, Compare >::operator()(), tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range().

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

- parallel_sort.h

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.