2

最近、次の関数のバグの修正を終えましたが、その答えに驚きました。私は次の関数を持っています（バグを見つける前のように書かれています）：

    void Level::getItemsAt(vector<item::Item>& vect, const Point& pt)
    {
        vector<itemPtr>::iterator it; // itemPtr is a typedef for a std::tr1::shared_ptr<item::Item>
        for(it=items.begin(); it!=items.end(); ++it)
        {
            if((*it)->getPosition() == pt)
            {
                item::Item item(**it);
                items.erase(it);
                vect.push_back(item);
            }
        }
    }

この関数Itemは、特定の位置を持つ「items」ベクトル内のすべてのオブジェクトを検索し、それらを「items」から削除して、「vect」に配置します。後で、という名前の関数putItemsAtは反対のことを行い、アイテムを「アイテム」に追加します。初めて、正常にgetItemsAt動作します。ただし、 afterputItemsAtが呼び出されると、forループインgetItemsAtは'items'の終わりから実行されます。'it'は無効なItemポインタを指し、getPosition()segfaultsします。思い切って、に変更it!=items.end()してit<items.end()、うまくいきました。誰か教えてもらえますか？SOを見回すeraseと、イテレータを無効にする必要があるかもしれませんが、それでも、最初に機能する理由はわかりません。

リストの消去がより効率的であるため、「アイテム」をベクトルからリストに変更することを計画しているので、私も興味があります。リストには演算子!=がないので、リストに使用する必要があることはわかっています。<リストを使用して同じ問題が発生しますか？

4

3 に答える 3

10

erase() を呼び出すと、そのイテレータは無効になります。それはループ反復子であるため、無効化した後に「++」演算子を呼び出すと、未定義の動作になります。erase() は、ベクター内の次の項目を指す新しい有効な反復子を返します。ループのその時点から新しいイテレータを使用する必要があります。つまり、次のようになります。

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt) 
{ 
    vector<itemPtr>::iterator it = items.begin();
    while( it != items.end() )
    {
        if( (*it)->getPosition() == pt )
        {
            item::Item item(**it);
            it = items.erase(it);
            vect.push_back(item);
        }
        else
            ++it;
    } 
}
于 2010-06-30T20:21:56.660 に答える
5

未定義の動作を呼び出しています。ベクトルへのすべてのイテレータは、eraseそのベクトルを呼び出したという事実によって無効になります。実装がやりたいことを何でもすることは完全に有効です。

を呼び出すとitems.erase(it);、itが無効になります。it標準に準拠するには、それが死んでいると想定する必要があります。

の次の呼び出しでその無効なイテレータを使用して、未定義の動作を呼び出しますvect.push_back。

ループitの追跡変数としてを使用して、未定義動作を再度呼び出します。for

を使用して、コードを有効にすることができますstd::remove_copy_if。

class ItemIsAtPoint : std::unary_function<bool, item::Item>
{
    Point pt;
public:
    ItemIsAtPoint(const Point& inPt) : pt(inPt) {}
    bool operator()(const item::Item* input)
    {
        return input->GetPosition() == pt;
    }
};

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt)
{
    std::size_t oldSize = items.size();
    std::remove_copy_if(items.begin(), items.end(), std::back_inserter(vect), 
        ItemIsAtPoint(pt));
    items.resize(vect.size() - (items.size() - oldSize));
}

を使用している場合は、これをかなりきれいにすることができますがboost::bind、これは機能します。

于 2010-06-30T20:11:28.417 に答える
2

イテレータの無効化に関する Remy Lebeau の説明を参照し、 a のstd::list代わりに aを使用することで、コードを有効にし、漸近的に (二次時間ではなく線形時間で) 高速化できることを追加しますstd::vector。(std::list削除は削除されたイテレータのみを無効にし、挿入はイテレータを無効にしません。)

また、STL 実装のデバッグ モードを有効にすることで、デバッグ中にイテレータの無効化を予想通りに特定することもできます。GCC では、コンパイラ フラグを使用します-D_GLIBCXX_DEBUG(いくつかの警告を参照してください)。

于 2010-06-30T20:21:34.350 に答える