就业培训     下载中心     Wiki     联络 登录   注册
  1. 首页
  2. C4D R23.110 C++ SDK
公共成员函数 | 私有成员函数 | 所有成员列表

BaseSort< SORTCLASS, FLAGS > Class Template Reference Data Structures

#include <sort.h>

详细描述

template<typename SORTCLASS, BASESORTFLAGS FLAGS = BASESORTFLAGS::NONE>
class maxon::BaseSort< SORTCLASS, FLAGS >

Template for sorting arrays and searching in sorted arrays

To use this template derive a class from it and define the member 'LessThan' that implements an element comparison. If you do searching the member 'IsEqual' needs to be implemented that does an element comparison with the search key as the first argument. If the search key is different from the element type a second LessThan routine is needed (comparing SEARCHKEY to an element).

Template Parameters
SORTCLASS The class itself. This has to be a derived class of BaseSort .
FLAGS See BASESORTFLAGS.
注意
Note that the classes that will be sorted have special requirements regarding copy and move constructors .
Note that the comparison must fulfill the condition (a < b) == !(b < a). If this is not the case the sort algorithm will crash. To avoid mistakes when comparing tuples use LexicographicalCompare.

Example for traditional C-style arrays:

class Sort1 : public BaseSort<Sort1> { public : static inline Bool LessThan ( Int a, Int b) { return a < b; } };
... Int array1[100]; ... Sort1 sort1; sort1.Sort(&array1[0], &array1[100]); // note that the 'end' iterator is the last element + 1 and not the last element! sort1.Sort(array1, 100); // even easier
注意
LessThan can be a member of the sort class itself (not static), but needs to be const in that case.

Example for arrays:

class Sort2 : public BaseSort<Sort2> { public : static inline Bool LessThan ( Int a, Int b) { return a < b; } }; ... BlockArray< Int > array2; ... Sort2 sort2; sort2.Sort(array2.Begin(), array2.End()); // do not write Sort(&array2[0], &array2[array2.GetCount()]) as this will create a debug assert (the second array access is illegal) sort2.Sort(array2); // any arrays derived from BaseArray can be passed directly

Example for arbitrary structures with multiple sort criteria:

class MyStruct { public : String _str; Int _index; Float _weight; }; class Sort3 : public BaseSort<Sort3> { public : static inline Bool LessThan ( const MyStruct& a, const MyStruct& b) { if (a._weight < b._weight) return true ; if (a._weight > b._weight) return false ; return a._index < b._index; // if weights are identical sort by index } }; ... BlockArray<MyStruct> array3; ... Sort3 sort3; sort3.Sort(array3);

Searching Example:

class MyStruct { public : String _str; Int _index; Float _weight; }; class MySearch : public BaseSort <MySearch, BlockArray<MyStruct>::Iterator> { public : // for sorting: compare array element to array element static inline Bool LessThan ( const MyStruct& a, const MyStruct& b) { return LexicographicalCompare (a._weight, b._weight, a._index, b._index); }

// for searching: compare search key to array element static inline Bool LessThan ( Float weight, const MyStruct& b) { return weight < b._weight; }

// for searching: compare search key to array element static inline Bool IsEqual ( Float weight, const MyStruct& b) { return weight == b._weight; } }; ... BlockArray<MyStruct> array4; ... MySearch search; search.Sort(array4); ...

// array is now sorted, we can search it MyStruct* result = search.Find(5.0, array4);

公共成员函数

template<typename ITERATOR >
void  Sort (ITERATOR start, ITERATOR end ) const
template<typename ITERATOR >
void  Sort (ITERATOR start, Int count) const
template<typename ARRAY >
void  Sort (ARRAY &arr) const
template<typename SEARCHTYPE , typename ITERATOR >
Int   FindIndex (const SEARCHTYPE &key, ITERATOR arr, Int count) const
template<typename SEARCHTYPE , typename ITERATOR >
ITERATOR  Find (const SEARCHTYPE &key, ITERATOR arr, Int count) const
template<typename ARRAY , typename SEARCHTYPE >
ARRAY::ValueType *  Find (const SEARCHTYPE &key, const ARRAY &arr) const
template<typename SEARCHTYPE , typename ITERATOR >
ITERATOR  FindInsertionIndex (const SEARCHTYPE &key, ITERATOR arr, Int count, Int &insertionIndex) const
template<typename ARRAY , typename SEARCHTYPE >
ARRAY::ValueType *  FindInsertionIndex (const SEARCHTYPE &key, const ARRAY &arr, Int &insertionIndex) const

私有成员函数

Int   Log2 ( Int n) const
template<typename ITERATOR , typename CONTENT >
void  ISort (ITERATOR start, Int count, const CONTENT &valType) const

成员函数文档编制

◆  Sort() [1/3]

void Sort ( ITERATOR  start ,
ITERATOR  end  
) const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n))

参数
[in] start The start iterator of an array.
[in] end The end iterator of an array. Note that this is not the last element! It needs to be the boundary (which is last element + 1). See in the BaseSort class description for examples.

◆  Sort() [2/3]

void Sort ( ITERATOR  start ,
Int   count  
) const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n))

参数
[in] start The start iterator of an array.
[in] count The number of elements to be sorted.

◆  Sort() [3/3]

void Sort ( ARRAY &  arr ) const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n))

参数
[in] arr The array to be sorted.

◆  FindIndex()

Int FindIndex ( const SEARCHTYPE &  key ,
ITERATOR  arr ,
Int   count  
) const

Find an element in an array. The array must be in a sorted state. The time for searching will be O(log(n))

参数
[in] key The key that the array is searched for.
[in] arr The array to be searched.
[in] count The number of elements of the array.
返回
If an element is found its index will be returned, otherwise the result is the bitwise inverse of the index where key would be inserted (which is always negative). If multiple elements have the same key value the index of the first of those elements will be returned.

◆  Find() [1/2]

ITERATOR Find ( const SEARCHTYPE &  key ,
ITERATOR  arr ,
Int   count  
) const

Find an element in an array. The array must be in a sorted state. The time for searching will be O(log(n))

参数
[in] key The key that the array is searched for.
[in] arr The array to be searched.
[in] count The number of elements of the array.
返回
If an element is found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

◆  Find() [2/2]

ARRAY::ValueType* Find ( const SEARCHTYPE &  key ,
const ARRAY &  arr  
) const

Find an element in an array derived from BaseArray . The array must be in a sorted state. The time for searching will be O(log(n))

参数
[in] key The key that the array is searched for.
[in] arr The array to be searched.
返回
If an element is found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

◆  FindInsertionIndex() [1/2]

ITERATOR FindInsertionIndex ( const SEARCHTYPE &  key ,
ITERATOR  arr ,
Int   count ,
Int &  insertionIndex  
) const

Find an element in an array and return the insertion index if the element was not found. The array must be in a sorted state. The time for searching will be O(log(n))

参数
[in] key The key that the array is searched for.
[in] arr The array to be searched.
[in] count The number of elements of the array.
[out] insertionIndex The index an element needs to be inserted at if it does not exist in the array. Inserting at the designated place ensures that the array stays sorted.
返回
If an element was found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

◆  FindInsertionIndex() [2/2]

ARRAY::ValueType* FindInsertionIndex ( const SEARCHTYPE &  key ,
const ARRAY &  arr ,
Int &  insertionIndex  
) const

Find an element in an array derived from BaseArray and return the insertion index if the element was not found. The array must be in a sorted state. The time for searching will be O(log(n))

参数
[in] key The key that the array is searched for.
[in] arr The array to be searched.
[out] insertionIndex The index an element needs to be inserted at if it does not exist in the array. Inserting at the designated place ensures that the array stays sorted.
返回
If an element was found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

◆  Log2()

Int Log2 ( Int   n ) const
private

◆  ISort()

void ISort ( ITERATOR  start ,
Int   count ,
const CONTENT &  valType  
) const
private
maxon::IsEqual
MAXON_ATTRIBUTE_FORCE_INLINE Bool IsEqual(PREDICATE &&predicate, const T1 &a, const T2 &b)
定义： collection.h:102
Int
maxon::Int Int
定义： ge_sys_math.h:62
maxon::LessThan
Bool LessThan(UInt a1, UInt a2, UInt b1, UInt b2)
定义： integer.h:151
Float
maxon::Float Float
定义： ge_sys_math.h:64
maxon::LexicographicalCompare
COMPARERESULT LexicographicalCompare()
定义： compare.h:572
String
定义： c4d_string.h:38
Bool
maxon::Bool Bool
定义： ge_sys_math.h:53