0

実世界のスタックのように機能するスタックを実装するプログラムを書いています。つまり、スタックのサイズがしきい値に達すると倒れるため、その新しい要素を挿入するために新しいスタックを作成する必要があります。

以下はこのための私のプログラムです：

#include <iostream>
#include<vector>
#include<stack>

using namespace std;

class stack_of_plates
{
   vector<stack<int> > stacks;
   unsigned int stack_size;
   public:
   stack_of_plates(unsigned int size=100)
   {
       stack_size=size;
   }

   void push(int data)
   {
       if(stacks.empty())
       {
           stack<int> *sptr= new stack<int>; //on debugging Segmentation fault at thisline
           stacks.push_back(*sptr);
       }

       vector<stack<int> >::iterator it=stacks.end();
       if(it->size()==stack_size)
       {
           stack<int> *sptr= new stack<int>; //on debugging Segmentation fault at thisline
           stacks.push_back(*sptr);
       }
       it->push(data);
   }

   void pop()
   {
       if(stacks.empty())
       {
           cout<<"\nEmpty Stack";
           return ;
       }
       vector<stack<int> >::iterator it=stacks.end();
       if(it->empty())
       {
           it--;
       }
       it->pop();
   }
   int top()
   {
       if(stacks.empty())
       {
           cout<<"\nEmpty Stack";
           return 0;
       }
       vector<stack<int> >::iterator it=stacks.end();
       if(it->empty())
       {
           it--;
       }
       return it->top();
   }
};


int main()
{
   stack_of_plates ss;
   ss.push(1);
   ss.push(2);
   cout<<ss.top();
   return 0;
}

コンパイル時にエラーや警告は表示されません。ただし、プログラムは異常なエラーで終了します。新しいスタックの割り当てに問題があることを示すセグメンテーション違反エラーのデバッグ時。新しいスタックを割り当てるときにコードを変更する方法を教えてください。このエラーを取り除くのを手伝ってください。

4

3 に答える 3

3

stacks.end();ベクトルの終わりの後の（存在しない）要素を指します。逆参照することはできません。これを行うと、未定義の動作が発生し、セグメンテーション違反が発生する可能性があります。

そこで何をしているのかは明確ではありませんが、最後の要素にイテレータが必要な場合は、次のいずれかをデクリメントします。

vector<stack<int> >::iterator it=stacks.end();  // points past the end
--it;                                           // points to last element

または、逆イテレータを使用します（この場合、シーケンスを逆方向に移動するの++ではなく、を使用します）。--

vector<stack<int> >::reverse_iterator it=stacks.rbegin();

ベクトルに要素を追加すると無効になる可能性があるためit->push_back(data)、最後のpush()が正しくありません。ここではイテレータの使用を避けることができます。

void push() {
    if (stacks.empty() || stacks.back().size()==stack_size) {
        // See below for explanation of this change
        stacks.push_back(stack<int>());
    }
    stacks.back().push(data);
}

ではpop()、最後のスタックが空の場合は、おそらくそれを削除する必要があります。そうしないと、最後に2つの空のスタックが作成され、コードは誤ってpopそのうちの1つからスタックを試行します。繰り返しますが、これを行うと、セグメンテーション違反またはその他の未定義の動作が発生する可能性があります。あなたはおそらく次のようなものが欲しいでしょう：

void pop() {
    if (stacks.empty()) {
        cout<<"\nEmpty Stack";
        return ;
    }
    stacks.back().pop();
    if (stacks.back().empty()) {
        stacks.pop_back();
    }
}

そして今、最後のスタックが空にtopなることはないという不変条件を確立しました。少し簡単にすることができます。

int top() {
    if (stacks.empty()) {
        cout<<"\nEmpty Stack";
        return 0;
    }
    return stacks.back().top();
}

また、通常、を使用してオブジェクトを作成することは望ましくありませんnew。特に、オブジェクトのコピーをベクターに入れてからポインターを破棄し、割り当てられたメモリをリークするような場合は特にそうです。次のように、空のスタックをベクトルに追加できます。

stacks.push_back(stack<int>());

場合によっては（この場合はそうではありませんが）、割り当てられたオブジェクトへのポインターをコンテナーに格納したい場合があります。その場合は、コンテナから削除するときに忘れずに削除するか、などのスマートポインタを保存してstd::unique_ptrください。ただし、この場合は、オブジェクトを保存するだけです。

于 2012-08-22T11:00:54.023 に答える
1

コードには多くの問題があるため、問題の直接の原因がどれであるかを判断するのは困難です。それらを1つずつクリーンアップしてから、再テストする必要があります。それでも問題が解決しない場合は、ここに新しいコードを投稿してください。

リストは次のとおりです。

  1. newを使用した割り当てからメモリリークが発生しました。スタックのベクトルがあるので、ベクトルのサイズを変更するだけで、新しいスタックが割り当てられます。それで

    stacks.resize(stacks.size() + 1);

    それ以外の

    stack<int> *sptr= new stack<int>; stacks.push_back(*sptr);

  2. vector <>。end（）は、最後の要素の後の要素を指すイテレータを返します。そのため、@ Joachimは、使用する前にイテレータをデクリメントする必要があると提案しました。

  3. ストレージを新しいスタックに転送するかどうかを確認すると、論理エラーが発生します。最後のスタックのサイズが最大であるかどうかを確認した後、新しいスタックを作成した後、古いスタックをプッシュし続けます。

これがお役に立てば幸いです。

于 2012-08-22T10:57:17.080 に答える
0

std::stack<int>例で示した機能がすでにあるため、。は必要ありませんstd::vector< std::stack<int> >。プッシュしてポップするだけstd::stack<int>で、コードにある問題のほとんどを回避できます。に制限std::stack<int>する理由はありませんstack_size。

その隣で、コンテナの最後のエントリが必要な場合は、のback()代わりにを使用しend()ます。

于 2012-08-22T11:07:13.743 に答える