15

Во многих источниках вроде 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
8
  • 7
    стандарт говорит, что только итератор на удаляемый элемент будет "испорчен". Все остальные будут в порядке - пункт 23.2.4.9. Но я бы рассмотрел возможность использовать remove_if или аналогов.
    – KoVadim
    19 апр 2017 в 8:13
  • Не знаю как правильно использовать remove_if. Я не могу использовать лямбды в моей версии gcc, а в моём предикате нужно использовать локальную переменную. Я думал создать что-то вроде обьекта-функтора, перезгрузив operator(), но у меня ворох ошибок компиляции. Обновил пост
    – MayRiv
    19 апр 2017 в 8:29
  • 2
    функции-алгоритмы были придуманы, когда ещё лямбд в с++ не было. Там можно просто передать правильную функцию и все будет ок.
    – KoVadim
    19 апр 2017 в 8:31
  • Но если мне нужно передать ещё один параметр в эту функцию, как это сделать?
    – MayRiv
    19 апр 2017 в 8:33
  • 2
    remove_if не может быть использован с std::map в принципе. Забудьте про remove_if. 12 окт 2018 в 13:36

3 ответа 3

0

Придётся реализовать удаление ручками. Вместо того, чтобы реализовывать двойной обход по контейнеру (ищем удаляемый элемент, удаляем его, потом начинаем обходить заново с первого элемента), сделаем реализацию с добавочным итератором (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 никогда ничего не удаляет. Он только копирует/переносит данные. Остальная часть ответа тоже не ясна: какую "проблему" предлагается решить? Исходный код совершенно корректен. 12 окт 2018 в 13:33

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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