0

マージソートを使用して、符号なし long に変換された IP アドレスのリストをソートしようとしています。それが違いを生むかどうかにかかわらず、ベクトルには18647個の数値が含まれます。以前に C# を使用してマージ ソートを行ったことがありますが、C++ で試したのはこれが初めてなので、何か単純なものが欠けているかどうかはわかりません。現時点で持っているコードは次のとおりです。

vector<unsigned long> Sorter::mergeSort( vector<unsigned long> v){
    if( v.size() <= 1 ){
        return v;
    }
    vector<unsigned long> left, right;
    int mid = v.size() / 2;
    for( int i = 0; i < mid; i++ ){
        left.push_back( v[i] );
    }
    for( unsigned int j = mid; j <= v.size(); j++ ){
        right.push_back( v[j] );
    }
    left = Sorter::mergeSort( left );
    right = Sorter::mergeSort( right );
    return Sorter::merge( left, right );
}

vector<unsigned long> Sorter::merge( vector<unsigned long> left, vector<unsigned long> right){
    vector<unsigned long> result;
    while( left.size() > 0 || right.size() > 0 ){
        if( left.size() > 0 && right.size() > 0 ){
            if( left[0] <= right[0] ){
                result.push_back( left[0] );
                left.erase( left.begin() );
            }else{
                result.push_back( right[0] );
                right.erase( right.begin() );
            }
        }else if( left.size() > 0 ){
            result.push_back( left[0] );
            left.erase( left.begin() );
        }else if( right.size() > 0 ){
            result.push_back( right[0] );
            right.erase( right.begin() );
        }
    }
    return result;
}
4

1 に答える 1

2 
for( unsigned int j = mid; j <= v.size(); j++ )
                             ^^

j < v.size() または j <= v.size() -1 (配列インデックスは 0 から開始) を使用する必要があります。そうしないと、インデックス範囲外エラーが発生します。

一方、コストを節約するために、ベクトルを参照渡しすることをお勧めします。

もう1つのポイントは、ベクターを使用したため、ベクターヘッダーのメモリスペースはスタックに割り当てられますが、ベクターの要素はフリーストアに割り当てられるため、18647個の数値を使用しても問題ありません。詳細については、次のスレッドを参照してください。

ベクトルが割り当てられるとき、それらはヒープまたはスタックのどちらでメモリを使用しますか?

于 2013-03-15T03:36:27.427 に答える