17

Во многих источниках вроде http://www.amse.ru/courses/cpp1/2010.04.07.html ничего не сказано про инвалидацию итераторов в map.

Является ли опасным и UB код ниже?

std::map<Word32, OnlineUser*>::iterator toDelete, it = onlineUsers.begin();
while (it != onlineUsers.end())
    if (it->second) 
    {
        if (curUnixTimeStamp - it->second->lastActiveTime > MAX_NON_ACTIVETIME)
        {
            toDelete = it;
            it++;
            OnlineUser* userToDelete = toDelete->second;
            onlineUsers.erase(toDelete);
            delete userToDelete;
        } else {
            it++;
        }
    }

К сожалению, у меня gcc version 4.4.7? не поддерживающий ни лямбд, ни возвращающий итератор после erase, так что я не могу сделать так, как советуют на стековерфлоу вроде it = c.erase(it); Update: Пробовал использовать связку erase(remove_if), но у меня сложности с предикатом. Я не могу использовать лямбды из-за версии компилятора, а мой предикат требует использования локальной переменной. Пробовал создать обьект класса

    class Predicate{
public:
    Predicate(Word32 curUnixTimeStamp):_curUnixTimeStamp(curUnixTimeStamp){}
    bool operator()(std::pair<Word32, Sites::OnlineUser*> user){
        return _curUnixTimeStamp - (Word32)user.second->lastActiveTime > (Word32)MAX_NON_ACTIVETIME ;
    }
private:
    Word32 _curUnixTimeStamp;   
};

и использовать

class Predicate p(curUnixTimeStamp);
onlineUsers.erase(std::remove_if(onlineUsers.begin(), onlineUsers.end(),p));

но вываливается ворох ошибок

/usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_pair.h: In member function ‘std::pair<const unsigned int, Sites::OnlineUser*>& std::pair<const unsigned int, Sites::OnlineUser*>::operator=(const std::pair<const unsigned int, Sites::OnlineUser*>&)’:
/usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_pair.h:68:   instantiated from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator<std::pair<const unsigned int, Sites::OnlineUser*> >, _Predicate = Sites::Predicate]’
sites.hpp:195:   instantiated from here
/usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_pair.h:68: error: non-static const member ‘const unsigned int std::pair<const unsigned int, Sites::OnlineUser*>::first’, can't use default assignment operator
In file included from /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/algorithm:62,
                 from sites.hpp:13,
                 from banner.cpp:10:
/usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h: In function ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator<std::pair<const unsigned int, Sites::OnlineUser*> >, _Predicate = Sites::Predicate]’:
/usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:1161: note: synthesized method ‘std::pair<const unsigned int, Sites::OnlineUser*>& std::pair<const unsigned int, Sites::OnlineUser*>::operator=(const std::pair<const unsigned int, Sites::OnlineUser*>&)’ first required here 
gmake: *** [banner.o] Error 1
9
  • 8
    стандарт говорит, что только итератор на удаляемый элемент будет "испорчен". Все остальные будут в порядке - пункт 23.2.4.9. Но я бы рассмотрел возможность использовать remove_if или аналогов.
    – KoVadim
    Commented 19 апр. 2017 в 8:13
  • Не знаю как правильно использовать remove_if. Я не могу использовать лямбды в моей версии gcc, а в моём предикате нужно использовать локальную переменную. Я думал создать что-то вроде обьекта-функтора, перезгрузив operator(), но у меня ворох ошибок компиляции. Обновил пост
    – MayRiv
    Commented 19 апр. 2017 в 8:29
  • 2
    функции-алгоритмы были придуманы, когда ещё лямбд в с++ не было. Там можно просто передать правильную функцию и все будет ок.
    – KoVadim
    Commented 19 апр. 2017 в 8:31
  • Но если мне нужно передать ещё один параметр в эту функцию, как это сделать?
    – MayRiv
    Commented 19 апр. 2017 в 8:33
  • 2
    remove_if не может быть использован с std::map в принципе. Забудьте про remove_if. Commented 12 окт. 2018 в 13:36

3 ответа 3

1

Придётся реализовать удаление ручками. Вместо того, чтобы реализовывать двойной обход по контейнеру (ищем удаляемый элемент, удаляем его, потом начинаем обходить заново с первого элемента), сделаем реализацию с добавочным итератором (itPrev), который будет ссылаться на предыдущий элемент. Как только мы сделали удаление (удаление по итератору!), возвращаем итератор на предыдущую позицию присваиванием значения itPrev. И начинаем всё сначала.

Сложности возникают, когда мы стоим в самом начале и нам нужно удалить первый элемент. На что должен ссылаться itPrev? На элемент, который стоит до первого? Конечно в контейнерах таких элементов нет. Есть только элемент следующий за последним актуальным элементом контейнера: map.end(). Вот его можно взять "якобы" за предыдущего первому элементу. Так как мы не можем с помощью (map.end())++; получить первый элемент, придётся каждый раз проверять, не находимся ли мы на этом элементе. Т.е. если it == map.end() -> тогда смело делаем присваивание: it = map.begin(); вместо it++.

#include <iostream>
#include <map>

class OnlineUser
{
public:
    OnlineUser(int i) : field(i) {}

    int field;
};

int main(int argc, char *argv[])
{

    std::map<int, OnlineUser> onlineUsers;

    onlineUsers.insert( std::pair<int, OnlineUser>(1, OnlineUser( 0 )) );
    onlineUsers.insert( std::pair<int, OnlineUser>(2, OnlineUser( 3 )) );
    onlineUsers.insert( std::pair<int, OnlineUser>(3, OnlineUser( 0 )) );
    onlineUsers.insert( std::pair<int, OnlineUser>(4, OnlineUser( 5 )) );
    onlineUsers.insert( std::pair<int, OnlineUser>(5, OnlineUser( 0 )) );

    std::map<int, OnlineUser>::iterator it = onlineUsers.begin();
    std::map<int, OnlineUser>::iterator itPrev = onlineUsers.end();
    while ( it != onlineUsers.end() )
    {
        if ( it->second.field <= 0 )
        {
            // удаление элемента по итератору за константу
            onlineUsers.erase( it );

            if ( itPrev == onlineUsers.end() )
            {
                it = onlineUsers.end();
            }
            else
            {
                it = itPrev;
            }
        }

        itPrev = it;
        if ( it == onlineUsers.end() )
        {
            it = onlineUsers.begin();
        }
        else
        {
            ++it;
        }
    }

    for (std::map<int, OnlineUser>::iterator it = onlineUsers.begin(); 
                it != onlineUsers.end(); it++)
    {
        std::cout << it->first << std::endl;
    }

    return 0;
}

Код запускал на этом сайте: http://codepad.org. Версия компилятора 4.1.2

P.S. Вместо указателя на OnlineUsers, использовал обычный тип. Добавив указатель в тип и добавив удаление объекта

0

Не проще ли будет отказаться от std::map<Word32, OnlineUser*>в пользу контейнера с "умным" указателем, типа std::map<Word32, std::unique_ptr<OnlineUser> > или std::shared_ptr<OnlineUser> >? Таким образом удаление будет происходить вместе с вызовом метода erase

-1

Приведенный вами код, с одновременным использованием итератора и удалением записей из контейнера, является не безопасным.

Рассмотрим вашу проблемную строку с ошибками сборки:

onlineUsers.erase(std::remove_if(onlineUsers.begin(), onlineUsers.end(),p));

1) Алгоритмы std::remove и std::remove_if нельзя использовать с std::set и std::map, так как first-поле имеет модификатор const, а алгоритмы в своей реализации используют std::move.
2) Даже если исключить первый пункт, то запись будет не корректна, так как std::remove_if уже удалит все элементы одобренные предикатом. При этом в erase отправится итератор на следующий за последним удаленным, а это может оказаться end().

Предлагаю решить проблему простым разделением задач, а именно сначала найти тех кого стоит удалить, а у же потом удалить:

std::list<Word32> delUserKeys; // Будет хранить ключи кандидатов на удаление.
std::map<Word32, OnlineUser*>::iterator users_it = onlineUsers.begin();
while (users_it != onlineUsers.end())
if (users_it->second)
{
    if (curUnixTimeStamp - users_it->second->lastActiveTime > MAX_NON_ACTIVETIME)
    {
        delUserKeys.push_back(users_it->first);             
    }

    users_it++;
}

std::list<Word32>::iterator delUserKeys_it = delUserKeys.begin();
while (delUserKeys_it != delUserKeys.end()) {
    std::map<Word32, OnlineUser*>::iterator thisDel_it = onlineUsers.find(*delUserKeys_it);
    if (thisDel_it != onlineUsers.end()) {
        delete thisDel_it->second;
        onlineUsers.erase(thisDel_it);
    }
}

delUserKeys.clear();
1
  • 3
    Первый пункт правильный. А вот во втором написана какая-то чушь. Что значит "std::remove_if уже удалит все элементы одобренные предикатом"? remove_if никогда ничего не удаляет. Он только копирует/переносит данные. Остальная часть ответа тоже не ясна: какую "проблему" предлагается решить? Исходный код совершенно корректен. Commented 12 окт. 2018 в 13:33

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.