1

ソートするベクトルの最初、最後、および中央の要素の中央値を取得して、クイックソートのピボットを選択しようとしています。int の範囲で多くの実装を見てきましたが、イテレータを使用してそれを実行しようとしていました (とにかくそれほど異なるべきではありません)。ただし、私のコードは、私がやりたいことをまったく実行しません。T が int の場合は機能しますが、他のクラスではタイムアウトします。何か案は？コードは次のとおりです。

template <class T>
int ParallelSort::partition(typename vector<T>::iterator &start, typename        vector<T>::iterator &end)
{
int Index = (end-start)/2;
T tmpSwap = start[Index];
//the three if statement get the three part median for the vector. 
if(start[Index] < *start)
{
    start[Index] = *start;
    *start = tmpSwap;
}
if(*end < *start)
{
    tmpSwap = *end;
    *end = *start;
    *start = tmpSwap;
}
if(*end < start[Index])
{
    tmpSwap = start[Index];
    start[Index] = *end;
    *end = tmpSwap;
}
T pivot = start[Index];
//rest of the code .....
//i'm sure that the rest of the code works correctly
4

1 に答える 1

0

typename std::vector<T>::size_typeまず、ではなくを使用する必要がありますint。次に、 を使用std::distanceして、 に格納する必要がある 2 つの反復子の違いを見つけますtypename std::vector<T>::difference_type。最後に、反復子は通常、参照渡しではなく、値渡しです。

あなたの問題は、おそらく逆参照しているという事実ですend。これは未定義の動作です。おそらく逆参照したかったのでしょう--end。

また、イテレータの要点は、(理論的には) 特定のコンテナに限定されないようにすることです。これはおそらく署名付きで書かれているはずです：

template <typename SizeType, typename RandomAccessIterator>
SizeType ParallelSort::partition(RandomAccessIterator start, RandomAccessIterator end)
于 2013-03-25T03:27:44.033 に答える