map и удаление элементов. - C/C++

у меня есть std::map <int, СЛОЖНАЯ_СТРУКТУРА> a. Периодически возникает задача удаления не нужных записей, причем таких записей может быть несколько и расположены они могут быть в произвольных местах. Алгоритм, который мне пришел в голову:
1) Перебираю каждый элемент списка на соответствие некоторым условиям
2) Встретился элемент, который нужно удалить — удалил его и продолжил искать далее

Но вот незадача, после удаления элемента итераторы становятся не действительными, значит их нужно задать заново и с элемента .begin() заново начать поиск (заново, т.к. ни кто гарантий не дает, как будут располагаться элементы. Или я не прав?) Это потенциально долго, а на ключи полагаться нельзя, т.к. в момент работы алгоритма значения ключей не известны.

Вот такая ерунда.
Что псоветуете?

Здравствуйте, Wind, Вы писали:

W>Вот такая ерунда.
W>Что псоветуете?

В похожей ситуайии я ничего умнее не придумал как пробежать по мепу, накопить во временном векторе ключи, соответсвующие структурам, подлежащим удалению, а потом пробежался по этому вектору, и сделал для каждого ключа в векторе map::erase(key).

То есть чтото типа такого

vector<key_type> vs;
for(it = map.begin(); it != map.end();++it)
{
  if (MustRemove((*it).second))
      vs.push_back((*it).first);
}

for(i = vs.begin(); i != vs.end();++i)
  map.erase(*i);

Wind:

> std::map <int, СЛОЖНАЯ_СТРУКТУРА> <...> задача удаления не нужных записей <...>
> 1) Перебираю каждый элемент списка на соответствие некоторым условиям
> 2) Встретился элемент, который нужно удалить — удалил его и продолжил искать далее
> Но вот незадача, после удаления элемента итераторы становятся не действительными

Только непосредственно удаленный.

> Что псоветуете?

for (MyMap::iterator i = m.begin(), e = m.end(); i != e; /* здесь пусто */ )
{
   if ( . . . )
     m.erase(i++);
   else
     ++i;
}

Posted via RSDN NNTP Server 1.9 gamma

ПК>Только непосредственно удаленный.

Угу, согласен — но имхо на это полагаться не стоит — ибо потом контейнер может смениться (ну, например на тот же вектор) — и искать багу придется очень долго....

Sasparella:

> ПК> Только непосредственно удаленный.

> Угу, согласен — но имхо на это полагаться не стоит — ибо потом контейнер может смениться (ну, например на тот же вектор) — и искать багу придется очень долго....

Пытаться писать "контейнеро-независимый" код — дохлый номер. За исключением редких случаев, и у меня ощущение, что данный к ним не относится.

Posted via RSDN NNTP Server 1.9 gamma

Здравствуйте, Sasparella, Вы писали:

ПК>>Только непосредственно удаленный.

S>Угу, согласен — но имхо на это полагаться не стоит — ибо потом контейнер может смениться (ну, например на тот же вектор) — и искать багу придется очень долго....

Как ты себе представляешь смену map на vector?

Здравствуйте, Wind, Вы писали:

W>у меня есть std::map <int, СЛОЖНАЯ_СТРУКТУРА> a. Периодически возникает задача удаления не нужных записей, причем таких записей может быть несколько и расположены они могут быть в произвольных местах. Алгоритм, который мне пришел в голову:
W>1) Перебираю каждый элемент списка на соответствие некоторым условиям
W>2) Встретился элемент, который нужно удалить — удалил его и продолжил искать далее

W>Но вот незадача, после удаления элемента итераторы становятся не действительными, значит их нужно задать заново и с элемента .begin() заново начать поиск (заново, т.к. ни кто гарантий не дает, как будут располагаться элементы. Или я не прав?) Это потенциально долго, а на ключи полагаться нельзя, т.к. в момент работы алгоритма значения ключей не известны.

W>Вот такая ерунда.
W>Что псоветуете?

используй map::erase(key)

Здравствуйте, Wind, Вы писали:

Возможно, будет интересно почитать этот топик.

Здравствуйте, Павел Кузнецов, Вы писали:

У меня вопро на засыпку:

 m.erase(i++);

 i = m.erase(i);

дадут одинаковые значения итератора? если да, то зачем, вообще, из ерейза что-то возвращать?

Удалено излишнее цитирование

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, Wind, Вы писали:

B>Возможно, будет интересно почитать этот топик.

Господа, поправте если ошибаюсь. При добавлении элемента в map элемент автоматически размещается в нужную позицию в соответствии с его ключом. Соответственно, элементы с одинаковым ключём должны размещаться рядом (при этом их может быть несколько).

m_map.erase(key) удалит все элементы с заданым ключом. Для чего нужен цикл, не понятно.

Здравствуйте, itman, Вы писали:

I>Здравствуйте, Павел Кузнецов, Вы писали:

I>У меня вопро на засыпку:
I>

I> m.erase(i++);
I>

I>и
I>

I> i = m.erase(i);
I>

I>дадут одинаковые значения итератора?
Да, одинаковые.
I>если да, то зачем, вообще, из ерейза что-то возвращать?
Возможно, разработчики реализации STL для VC6 посчитали, что это имеет смысл (erse для вектора, например, возвращает итератор). По стандарту erase для map возвращает void.

Здравствуйте, _wind_, Вы писали:

__>Здравствуйте, Bell, Вы писали:

B>>Здравствуйте, Wind, Вы писали:

B>>Возможно, будет интересно почитать этот топик.

__>Господа, поправте если ошибаюсь. При добавлении элемента в map элемент автоматически размещается в нужную позицию в соответствии с его ключом. Соответственно, элементы с одинаковым ключём должны размещаться рядом (при этом их может быть несколько).

__>m_map.erase(key) удалит все элементы с заданым ключом. Для чего нужен цикл, не понятно.
map не сожержит дуприкатов ключей. Этим занимается multimap.

Здравствуйте, itman, Вы писали:

Удалено излишнее цитирование

ПК>>

ПК>>for (MyMap::iterator i = m.begin(), e = m.end(); i != e; /* здесь пусто */ )
ПК>>{
ПК>>   if ( . . . )
ПК>>     m.erase(i++);
ПК>>   else
ПК>>     ++i;
ПК>>}
ПК>>

"Скотт Майрес", Эффективное использование STL, страница 52

Привет
в доке все написано

Iterator map::erase (iterator Where)

Return value:
a bidirectional iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the map if no such element exists
Следовательно делаем так

for (it = map.begin();i != map.end();it++)
{
  if (условие)
  {
     it = map.erase(it); // it будет переброшен на первый верхний неизмененный елемент 
  }
}

Успехов

Здравствуйте, Wind,

Вы писали:

W>у меня есть std::map <int, СЛОЖНАЯ_СТРУКТУРА> a. Периодически возникает задача удаления не нужных записей, причем таких записей может быть несколько и расположены они могут быть в произвольных местах. Алгоритм, который мне пришел в голову:
W>1) Перебираю каждый элемент списка на соответствие некоторым условиям
W>2) Встретился элемент, который нужно удалить — удалил его и продолжил искать далее

W>Но вот незадача, после удаления элемента итераторы становятся не действительными, значит их нужно задать заново и с элемента .begin() заново начать поиск (заново, т.к. ни кто гарантий не дает, как будут располагаться элементы. Или я не прав?) Это потенциально долго, а на ключи полагаться нельзя, т.к. в момент работы алгоритма значения ключей не известны.

W>Вот такая ерунда.
W>Что псоветуете?

Здравствуйте, Bell, Вы писали:

Удалено излишнее цитирование

B>map не сожержит дуприкатов ключей. Этим занимается multimap.

ok

Здравствуйте, _wind_, Вы писали:

__>Здравствуйте, itman, Вы писали:

I>>Здравствуйте, Павел Кузнецов, Вы писали:

ПК>>>

ПК>>>for (MyMap::iterator i = m.begin(), e = m.end(); i != e; /* здесь пусто */ )
ПК>>>{
ПК>>>   if ( . . . )
ПК>>>     m.erase(i++);
ПК>>>   else
ПК>>>     ++i;
ПК>>>}
ПК>>>

__>"Скотт Майрес", Эффективное использование STL, страница 52

тааак, открываю страницу 52 и что я вижу. есессно облом. когда посылаешь неплохо указать точное направление, (намёк издание, год, итд). впрочем, я догадываюсь, что ты хотел этим сказать. ну ладно, тогда правильее было бы переписать цикл так:

for (MyMap::iterator i = m.begin(), e = m.end(); i != e; /* здесь пусто */ )
{
 if ( . . . )
  i = m.erase(i);
 else
  ++i;
}

а теперь таки по поводу конструкции еще раз

m.erase(i++);

i++ возвращает копию итератора i, для erase, после чего наступает sequcne point и i инкрементируется. а уж потом делается erase. вроде все работает правильно, но совершенно неочевидно.

Здравствуйте, serega, Вы писали:

При этом будет регулярно пропускаться один элемент после удаляемого

S>Привет
S>в доке все написано

S>Iterator map::erase (iterator Where)

S>Return value:
S>a bidirectional iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the map if no such element exists
S>Следовательно делаем так

S>

S>for (it = map.begin();i != map.end();it++)
S>{
S>  if (условие)
S>  {
S>     it = map.erase(it); // it будет переброшен на первый верхний неизмененный елемент 
S>  }
S>}
S>

S>Успехов

Удалено излишнее цитирование

Здравствуйте, serega, Вы писали:

S>Привет
S>в доке все написано
S>Iterator map::erase (iterator Where)

Это "фича" реализации STL для VC6/7.По стандарту map::erase (iterator) возвращает void.

Здравствуйте, Аноним, Вы писали:

Удалено излишнее цитирование

А>i++ возвращает копию итератора i, для erase, после чего наступает sequcne point и i инкрементируется. а уж потом делается erase. вроде все работает правильно, но совершенно неочевидно.

инкремент выполнится до начала выполнения функции, но после передачи параметра в функцию

	От:	Wind
	Дата:	27.10.04 21:41
	Оценка:

	От:	Sasparella
	Дата:	27.10.04 21:49
	Оценка:

	От:	Sasparella
	Дата:	27.10.04 21:52
	Оценка:

	От:	Павел Кузнецов
	Дата:	27.10.04 22:20
	Оценка:	30 (5) +2 -2
	#Имя:	FAQ.stl.map.erase

	От:	Sasparella
	Дата:	27.10.04 23:46
	Оценка:

От:	itman	itman.livejournal.com
Дата:	28.10.04 06:50
Оценка:

	От:	serega
	Дата:	28.10.04 07:08
	Оценка:	6 (1) +1 -1