1

同じプログラムに関する私の最近の投稿をご覧になった方もいらっしゃると思います。私はそれに問題を抱え続けています。繰り返しますが、まだ学習中、あまり進んでいない、ポインターをよく理解していない、クラスを受講していない、OOP の概念をまったく理解していないなどです。ベクター。少なくとも、それが機能することを願っています。教えて：

    //int num is to find the size of the original vector and
    //build up farray and sarray; not used in the merge process
    int num = original.size() 
    std::vector<int> final;

    std::vector<int>::iterator it = farray.begin();
    std::vector<int>::iterator iter = sarray.begin();

    //farray.size() == (0 thru (num / 2))
    //sarray.size() == ((num / 2) thru num)
    for (;it != farray.end() && iter != sarray.end();) {
        if (*it > *iter) {
            final.push_back(*it);
            it++;
        }    
        else
        {
            final.push_back(*iter);
            iter++;
        }

            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

マージソート関数のマージ部分を書き直して...まあ、それが機能するようにしました。実際、このコードについていくつか質問があります。

  1. for ループが次のパスでステートメントを変更する可能性がある場合、最後の 2 つの if ステートメントを std::vector::iterators it && iter と比較するのは良い形式ですか?
  2. このループの最後のパスで iter と it の値が変更され、コードが台無しになりますか? *it と *iter の比較の前に、最後の if ステートメントを配置しますか?
  3. end() メンバー関数は、それを呼び出しているものの最後の値を参照していますか? 何とかそれを超えて伸びそうです。

編集: 明日すべての返信に返信しますので、詳細をお知りになりたい場合はその時点で確認してください。真夜中過ぎです。おやすみ。

4

5 に答える 5

3

私はあなたのアルゴリズムの実装をチェックしませんでした。あなたの 3 つの質問を参照します。

  1. イテレーターは、コンテナーの値へのポインターによく似ています。for ループで size_t i を使用してから ++i を使用するのとまったく同じです。farray[i] と sarray[i] を比較することに問題があると思いますか? おそらくそうではないので、問題ありません。
  2. ここであなたがコードで行っているのは、*it と *iter の値を読み取るだけで、実際には変更していないため、変更されないということです。
  3. end() が無効な場所を指しています。最後の値ではなく、「それ以降」を指します。これは「NULL」のようなものです。したがって、if(iter == sarray.end()) が true の場合、*iter を記述するとクラッシュします。end() に等しいイテレータを逆参照できないためです。
于 2009-04-20T06:58:43.940 に答える
3

1. for ループ条件と同じコンテナーからの反復子を比較することは問題ありませんが、これは、for ループ ステートメントのインクリメント部分または for ループ自体の本体で 1 つまたは他の反復子を移動している場合にのみ意味があります。この for ループでは比較iterしますsarray.end()が、for ループは変更されませんiter。これは、反復がないか、for ループが終了しないことを意味します。また、比較のためでは!=なく、おそらく使用したいでしょう。すべてのイテレータで機能しますが、機能しません。<==!=<

            for (int i = 0; iter != sarray.end(); i++) {
                final.push_back(*iter);
            }

iterループを開始したい場所から開始すると、次のようなものが必要になる場合があります。

            for (; iter != sarray.end(); ++iter) {
                final.push_back(*iter);
            }

あなたはまだ学んでいるので (私たち全員ではありません!)、このようなアルゴリズムを使用することはおそらく有益ですstd::mergeが、おそらくどちらがあなたの望むことを行うかを認識しておく必要があります。

std::merge( farray.begin(), farray.end(), sarray.begin(), sarray.end(), std::back_inserter( final ) );

(する必要が#include <iterator>あり<algorithm>ます。)

2. iter をインクリメントしたり、外側の for ループでそれが後の for ループのロジックを無効にしたりすることはありません。

3. end()はコンテナーの末尾を 1 つ過ぎたところを指すため、ループ終了チェックに使用できますが、" ==" から " " へのイテレーターを逆参照しようとするべきではありません.end()。

于 2009-04-20T06:55:08.113 に答える
1

一般的なアドバイス: 変数名について考える必要があります。イテレータを 'it' および 'iter' と呼ぶと、ある時点で混乱するでしょう。実際、よく見ると、すでにあります。「farray」と「sarray」が意味のある名前である場合、「fiter」と「siter」はどうでしょうか。

また、マージソートが何をしているのかを考えてみてください。これらの最後の 2 つのブロックは、どちらのイテレータに何かが残っていても「ドレイン」するためだけに存在します。したがって、最初のループにいる必要はありません。

私はおそらく（疑似コード）のように書くでしょう：

while not (list1.empty and list2.empty):
    if list1.empty:
        result.push(list2.pop)
    else if list2.empty:
        result.push(list1.pop)
    else if list1.top > list2.top:
        result.push(list2.pop)
    else:
        result.push(list1.pop)

または、ややさびたカーゴカルトの C++ で:

std::vector<int>::iterator fiter = farray.begin();
std::vector<int>::iterator siter = sarray.begin();

while (fiter != farray.end() || siter != sarray.end()) {
    if (fiter == farray.end())      final.push_back(*siter++);
    else if (siter == sarray.end()) final.push_back(*fiter++);
    else if (*fiter > *siter)       final.push_back(*siter++);
    else                            final.push_back(*siter++);
}
于 2009-04-20T06:56:59.823 に答える
0

while (condition)1 つの簡単なコメント:の代わりに使用しない理由for(; !condition; )。

後者の構造は規格外でわかりにくい！

于 2009-04-20T12:47:28.110 に答える
0

ここで考えるべきことがいくつかあります。

まず、2 つの範囲をマージする場合は、独自の範囲をローリングするよりもstd::merge関数を使用する方がはるかに優れています。

インデントにさまざまなスタイルを使用し、中括弧をどこに配置するかによって、コードが少し読みにくくなっています。スタイルを選んでそれに固執します。

for ループの最初の部分は、マージの正しい実装のようです。

for (;it != farray.end() && iter != sarray.end();) {
    if (*it > *iter) {
        final.push_back(*it);
        it++;
    }    
    else
    {
        final.push_back(*iter);
        iter++;
    }

...そして、これで作業を完了できます。

ループの 2 番目の部分には、いくつかの問題があります。

   for (;it != farray.end() && iter != sarray.end();) {
         :   :
            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

1 つには、 for() 条件文は、 と の両方がそれぞれのコレクションの を指してはならないように記述されていitます。そうしないと、ループが終了しますiter。end()したがって、 を指したり、をit指したりすることはできず、どちらのステートメントも起動できません。どちらもデッド (到達不能) コードです。sarray.end()iterfarray.end()if

しかし、それらがデッド コードではなかったとしても、バグがあります。for(...)イテレータがコレクションの最後を指している場合、の条件によってループが中断されますが、このイテレータは移動されないため、無限ループが発生します。

繰り返しますが、これらfor(...)の s は両方とも不要なデッド コードです。これは、イテレータがベクトルの末尾を指すことができないためです。

于 2009-04-20T12:28:33.757 に答える