Инвалидация итератора в std::map
1,00
р.
Во многих источниках вроде http://www.amse.ru/courses/cpp1/2010.04.07.html ничего не сказано про инвалидацию итераторов в map.
Является ли опасным и UB код ниже?
std::map::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 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/bitstl_pair.h: In member function ‘std::pair& std::pair::operator=(const std::pair&)’: /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bitstl_pair.h:68: instantiated from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator >, _Predicate = Sites::Predicate]’ sites.hpp:195: instantiated from here /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bitstl_pair.h:68: error: non-static const member ‘const unsigned int std::pair::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/bitstl_algo.h: In function ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator >, _Predicate = Sites::Predicate]’: /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bitstl_algo.h:1161: note: synthesized method ‘std::pair& std::pair::operator=(const std::pair&)’ first required here gmake: *** [banner.o] Error 1
Ответ
Придётся реализовать удаление ручками. Вместо того, чтобы реализовывать двойной обход по контейнеру (ищем удаляемый элемент, удаляем его, потом начинаем обходить заново с первого элемента), сделаем реализацию с добавочным итератором (itPrev), который будет ссылаться на предыдущий элемент. Как только мы сделали удаление (удаление по итератору!), возвращаем итератор на предыдущую позицию присваиванием значения itPrev. И начинаем всё сначала.
Сложности возникают, когда мы стоим в самом начале и нам нужно удалить первый элемент. На что должен ссылаться itPrev? На элемент, который стоит до первого? Конечно в контейнерах таких элементов нет. Есть только элемент следующий за последним актуальным элементом контейнера: map.end(). Вот его можно взять "якобы" за предыдущего первому элементу. Так как мы не можем с помощью (map.end())++ получить первый элемент, придётся каждый раз проверять, не находимся ли мы на этом элементе. Т.е. если it == map.end() -> тогда смело делаем присваивание: it = map.begin() вместо it++.
#include #include
class OnlineUser { public: OnlineUser(int i) : field(i) {}
int field }
int main(int argc, char *argv[]) {
std::map onlineUsers
onlineUsers.insert( std::pair(1, OnlineUser( 0 )) ) onlineUsers.insert( std::pair(2, OnlineUser( 3 )) ) onlineUsers.insert( std::pair(3, OnlineUser( 0 )) ) onlineUsers.insert( std::pair(4, OnlineUser( 5 )) ) onlineUsers.insert( std::pair(5, OnlineUser( 0 )) )
std::map::iterator it = onlineUsers.begin() std::map::iterator itPrev = onlineUsers.end() while ( it != onlineUsers.end() ) { if ( it->second.field <= 0 ) { // удаление элемента по итератору за константу onlineUsers.erase( it ) <br> if ( itPrev == onlineUsers.end() ) { it = onlineUsers.end() } else { it = itPrev } }
itPrev = it if ( it == onlineUsers.end() ) { it = onlineUsers.begin() } else { ++it } }
for (std::map::iterator it = onlineUsers.begin() it != onlineUsers.end() it++) { std::cout << it->first << std::endl }<br> return 0 }
Код запускал на этом сайте: http://codepad.org. Версия компилятора 4.1.2
P.S. Вместо указателя на OnlineUsers, использовал обычный тип. Добавив указатель в тип и добавив удаление объекта
Является ли опасным и UB код ниже?
std::map::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 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/bitstl_pair.h: In member function ‘std::pair& std::pair::operator=(const std::pair&)’: /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bitstl_pair.h:68: instantiated from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator >, _Predicate = Sites::Predicate]’ sites.hpp:195: instantiated from here /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bitstl_pair.h:68: error: non-static const member ‘const unsigned int std::pair::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/bitstl_algo.h: In function ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator >, _Predicate = Sites::Predicate]’: /usr/lib/gcc/i686-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bitstl_algo.h:1161: note: synthesized method ‘std::pair& std::pair::operator=(const std::pair&)’ first required here gmake: *** [banner.o] Error 1
Ответ
Придётся реализовать удаление ручками. Вместо того, чтобы реализовывать двойной обход по контейнеру (ищем удаляемый элемент, удаляем его, потом начинаем обходить заново с первого элемента), сделаем реализацию с добавочным итератором (itPrev), который будет ссылаться на предыдущий элемент. Как только мы сделали удаление (удаление по итератору!), возвращаем итератор на предыдущую позицию присваиванием значения itPrev. И начинаем всё сначала.
Сложности возникают, когда мы стоим в самом начале и нам нужно удалить первый элемент. На что должен ссылаться itPrev? На элемент, который стоит до первого? Конечно в контейнерах таких элементов нет. Есть только элемент следующий за последним актуальным элементом контейнера: map.end(). Вот его можно взять "якобы" за предыдущего первому элементу. Так как мы не можем с помощью (map.end())++ получить первый элемент, придётся каждый раз проверять, не находимся ли мы на этом элементе. Т.е. если it == map.end() -> тогда смело делаем присваивание: it = map.begin() вместо it++.
#include #include
class OnlineUser { public: OnlineUser(int i) : field(i) {}
int field }
int main(int argc, char *argv[]) {
std::map onlineUsers
onlineUsers.insert( std::pair(1, OnlineUser( 0 )) ) onlineUsers.insert( std::pair(2, OnlineUser( 3 )) ) onlineUsers.insert( std::pair(3, OnlineUser( 0 )) ) onlineUsers.insert( std::pair(4, OnlineUser( 5 )) ) onlineUsers.insert( std::pair(5, OnlineUser( 0 )) )
std::map::iterator it = onlineUsers.begin() std::map::iterator itPrev = onlineUsers.end() while ( it != onlineUsers.end() ) { if ( it->second.field <= 0 ) { // удаление элемента по итератору за константу onlineUsers.erase( it ) <br> if ( itPrev == onlineUsers.end() ) { it = onlineUsers.end() } else { it = itPrev } }
itPrev = it if ( it == onlineUsers.end() ) { it = onlineUsers.begin() } else { ++it } }
for (std::map::iterator it = onlineUsers.begin() it != onlineUsers.end() it++) { std::cout << it->first << std::endl }<br> return 0 }
Код запускал на этом сайте: http://codepad.org. Версия компилятора 4.1.2
P.S. Вместо указателя на OnlineUsers, использовал обычный тип. Добавив указатель в тип и добавив удаление объекта
