вопрос о std :: vector :: end () - PullRequest
Новая
       17

вопрос о std :: vector :: end ()

2 голосов
/ 01 июля 2010

Я недавно закончил исправлять ошибку в следующей функции, и ответ меня удивил. У меня есть следующая функция (написано, как это было до того, как я нашел ошибку): 

    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 делает обратное и добавляет элементы в 'items'. В первый раз getItemsAt работает нормально. Однако после вызова putItemsAt цикл for в getItemsAt будет запускаться после конца 'items'. 'it' будет указывать на недопустимый указатель Item и getPosition() segfaults. Надеюсь, я изменил it!=items.end() на it<items.end(), и это сработало. Кто-нибудь может сказать мне, почему? Оглядываясь на SO, можно предположить, что erase может сделать недействительным итератор, но все равно не имеет смысла, почему он будет работать в первый раз.

Мне также любопытно, потому что я планирую изменить «элементы» с вектора на список, поскольку стирание списка более эффективно. Я знаю, что должен был бы использовать != для списка, поскольку у него нет оператора <. Я столкнулся бы с той же проблемой, используя список?

Ответы [ 3 ]

10 голосов
/ 01 июля 2010

Когда вы вызываете 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;
    } 
}
5 голосов
/ 01 июля 2010

Вы вызываете неопределенное поведение. Все итераторы вектора становятся недействительными из-за того, что вы вызвали 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, но это работает.

2 голосов
/ 01 июля 2010

Я пойду с объяснением Реми Лебо об аннулировании итератора и просто добавлю, что вы можете сделать свой код действительным и асимптотически более быстрым (линейное время вместо квадратичного времени), используя std::list вместо std::vector.(std::list удаления только делают недействительным итератор, который был удален, а вставки не делают недействительными никакие итераторы.)

Вы также можете предсказуемо идентифицировать аннулирование итератора при отладке, активировав режим отладки реализации STL.В GCC вы используете флаг компилятора -D_GLIBCXX_DEBUG (см. Некоторые предупреждения).

...