удаление некоторых элементов из map - как это работает? - C/C++

Здравствуйте!

В форуме не раз поднимался вопрос — как удалить из std::map некоторые эелементы удовлетворяющие некотрому условию.
_Внимательно изучив старые ветки_, я все таки не до конца проявнил ситуацию. В связи с этим хочу задать пару вопросов

1. при удалении из Map ( а как известно Map это сортированное дерево ) Map перестраиваеться и простой проход по циклу может никогда не закончиться


// Инициализацяи и лишние опрелделения пропущены
// этот код неверен
it = m_map.begin();
while(it != m_map.end)
{
  if(условие)// проверка условия 
  {
    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
    map.erase(it->first)
  }
  it++;
}

2. Можно конечно использовать алгоритм erase и предикат удаления — но я все равно не понимаю как ЭТО работает.
Ведь очевидно , для того чтобы корректно удалить из map несколько элементов — необходимо сначала собрать все ключи элементов подлежащих удалению в отдельный список, а затем удалить их.


// Инициализацяи и лишние опрелделения пропущены

it = m_map.begin();
while(it != m_map.end)
{
  if(условие)
    list.push_back(it->first)  // запоминаем ключи элементов подлежащих удалению

  it++;
}

// теперь удаляем
it = list.begin();
while(it!=list.end() )
{
  m_map.erase(*it);
}

Т.е. иначе, как в два прохода это не сделать...я правильно понимаю

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

M> Здравствуйте!

M>В форуме не раз поднимался вопрос — как удалить из std::map некоторые эелементы удовлетворяющие некотрому условию.
M>_Внимательно изучив старые ветки_, я все таки не до конца проявнил ситуацию. В связи с этим хочу задать пару вопросов

M>1. при удалении из Map ( а как известно Map это сортированное дерево ) Map перестраиваеться и простой проход по циклу может никогда не закончиться

M>


M>// Инициализацяи и лишние опрелделения пропущены
M>// этот код неверен
M>it = m_map.begin();
M>while(it != m_map.end)
M>{
M>  if(условие)// проверка условия 
M>  {
M>    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
M>    map.erase(it->first)
M>  }
M>  it++;
M>}

M>

так делать НИЗЯ!

... после map.erase(it->first) итератор может указывать черт знает куда!
а от чего зависит условие?? почему бы просто не удалять по ключу?

M>2. Можно конечно использовать алгоритм erase и предикат удаления — но я все равно не понимаю как ЭТО работает.
M>Ведь очевидно , для того чтобы корректно удалить из map несколько элементов — необходимо сначала собрать все ключи элементов подлежащих удалению в отдельный список, а затем удалить их.

M>


M>// Инициализацяи и лишние опрелделения пропущены

M>it = m_map.begin();
M>while(it != m_map.end)
M>{
M>  if(условие)
M>    list.push_back(it->first)  // запоминаем ключи элементов подлежащих удалению

M>  it++;
M>}

M>// теперь удаляем
M>it = list.begin();
M>while(it!=list.end() )
M>{
M>  m_map.erase(*it);
M>}

M>

M>Т.е. иначе, как в два прохода это не сделать...я правильно понимаю

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

M>>


M>>// Инициализацяи и лишние опрелделения пропущены
M>>// этот код неверен
M>>it = m_map.begin();
M>>while(it != m_map.end)
M>>{
M>>  if(условие)// проверка условия 
M>>  {
M>>    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
M>>    map.erase(it->first)
       Ну предположим что мы сохранили итератор, потом увеличили и потом удалили сохраненный... вопрос ведь не в этом...
M>>  }
M>>  else it++;
M>>}

M>>

А>так делать НИЗЯ!

... после map.erase(it->first) итератор может указывать черт знает куда!
А>а от чего зависит условие?? почему бы просто не удалять по ключу?
всмысле? а я удаляю не по ключю??? map.erase( а здесь ключ )...

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

M>Здравствуйте, Александр, Вы писали:

M>>>


M>>>// Инициализацяи и лишние опрелделения пропущены
M>>>// этот код неверен
M>>>it = m_map.begin();
M>>>while(it != m_map.end)
M>>>{
M>>>  if(условие)// проверка условия 
M>>>  {
M>>>    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
M>>>    map.erase(it->first)
M>       Ну предположим что мы сохранили итератор, потом увеличили и потом удалили сохраненный... вопрос ведь не в этом...
M>>>  }
M>>>  else it++;
M>>>}

M>>>

А>>так делать НИЗЯ!

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

M>Здравствуйте, Александр, Вы писали:

M>>>


M>>>// Инициализацяи и лишние опрелделения пропущены
M>>>// этот код неверен
M>>>it = m_map.begin();
M>>>while(it != m_map.end)
M>>>{
M>>>  if(условие)// проверка условия 
M>>>  {
M>>>    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
M>>>    map.erase(it->first)
M>       Ну предположим что мы сохранили итератор, потом увеличили и потом удалили сохраненный... вопрос ведь не в этом...
M>>>  }
M>>>  else it++;
M>>>}

M>>>

А>>так делать НИЗЯ!

... после map.erase(it->first) итератор может указывать черт знает куда!
А>>а от чего зависит условие?? почему бы просто не удалять по ключу?
M> всмысле? а я удаляю не по ключю??? map.erase( а здесь ключ )...

map::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
The first member function removes the element of the controlled sequence pointed to by it. The second member function removes the elements in the interval [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

The third member function removes the elements with sort keys in the range [lower_bound(key), upper_bound(key)). It returns the number of elements it removes.

юзай первый вариант, только для начала найди итератор нужного элемента по ключу.

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

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

M>>Здравствуйте, Александр, Вы писали:

M>>>>


M>>>>// Инициализацяи и лишние опрелделения пропущены
M>>>>// этот код неверен
M>>>>it = m_map.begin();
M>>>>while(it != m_map.end)
M>>>>{
M>>>>  if(условие)// проверка условия 
M>>>>  {
M>>>>    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
M>>>>    map.erase(it->first)
M>>       Ну предположим что мы сохранили итератор, потом увеличили и потом удалили сохраненный... вопрос ведь не в этом...
M>>>>  }
M>>>>  else it++;
M>>>>}

M>>>>

А>>>так делать НИЗЯ!

... после map.erase(it->first) итератор может указывать черт знает куда!
А>>>а от чего зависит условие?? почему бы просто не удалять по ключу?
M>> всмысле? а я удаляю не по ключю??? map.erase( а здесь ключ )...

L>map::erase
L>iterator erase(iterator it);
L>iterator erase(iterator first, iterator last);
L>size_type erase(const Key& key);
L>The first member function removes the element of the controlled sequence pointed to by it. The second member function removes the elements in the interval [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

L>The third member function removes the elements with sort keys in the range [lower_bound(key), upper_bound(key)). It returns the number of elements it removes.

L>юзай первый вариант, только для начала найди итератор нужного элемента по ключу.

Если я не ошибаюсь, то это только в вижуаловском компиляторе map::erase() возвращает итератор, а по стандарту он возвращает void, так что такой метод непереносим

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

M>


M>// этот код неверен
M>it = m_map.begin();
M>while(it != m_map.end)
M>{
M>  if(условие)// проверка условия 
M>  {
M>    //- удаление по ключю - MAP перестраиваеться следовательно it может не достигнуть m_map.end()
M>    map.erase(it->first)
M>  }
M>  it++;
M>}

M>

А вот этот верен:

it = m_map.begin();
while(it != m_map.end)
{
  if(условие)// проверка условия 
  {
    //Удаление с использованием итератора эффективнее - не надо проводить поиск 
    //(в отличии от варианта с ключом)
    map.erase(it++);
  }
  else
    ++it;
}

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

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

B>А вот этот верен:

B>

B>it = m_map.begin();
B>while(it != m_map.end)
B>{
B>  if(условие)// проверка условия 
B>  {
B>    //Удаление с использованием итератора эффективнее - не надо проводить поиск 
B>    //(в отличии от варианта с ключом)
B>    map.erase(it++);
B>  }
B>  else
B>    ++it;
B>}
B>

Да в этом и главный вопрос — еще раз его задам — по пунктам — скажите мне где я не прав
1. MAP дерево
2. Итератор указывает на неокторый элемент дерева
3. После удаления элемента — дерево перестравиваеться — это ключевой момент — так ка дерево перестравивается наш текущий итертатор тоже переместился — следовательно вполне вероятна такая ситуация что после перестройки дерева мы можем проскочить несколько элементов ( например несколько элементов из конца дерева попадают куданибудь в начало (условно начало)) и следовательно мы никогда на них не попадем..
4. Значит удаление эелемнтов в цикле может работать некоректно ( иногда не все необходимые элементы будут удалены)

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

M>Да в этом и главный вопрос — еще раз его задам — по пунктам — скажите мне где я не прав
M> 1. MAP дерево
Да, бинарное (обычно красно-черное) дерево.
M> 2. Итератор указывает на неокторый элемент дерева
Ну да, если не считать невалидные итераторы

M> 3. После удаления элемента — дерево перестравиваеться — это ключевой момент — так ка дерево перестравивается наш текущий итертатор тоже переместился — следовательно вполне вероятна такая ситуация что после перестройки дерева мы можем проскочить несколько элементов ( например несколько элементов из конца дерева попадают куданибудь в начало (условно начало)) и следовательно мы никогда на них не попадем..
После erase — а текущий итератор становится невалидным. Однако ассоциативные контейнеры обладают замечателтным свойством: удаление элемента не приводит к инвалидации всех остальных ссылок и итераторов. Теперь глянь на строчку:

map.erase(it++);

итератор инкриментируется (а значит удаление "предыдущего" элемента на него никак не повлияет), но в качестве аргумента erase используется старое (предыдущее) значение, т.е. фактически мы переходим к следующему элементу контейнера, и удаляем текущий.

M> 4. Значит удаление эелемнтов в цикле может работать некоректно ( иногда не все необходимые элементы будут удалены)
Если правильно организовать цикл, то этого не случится.

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

А>Если я не ошибаюсь, то это только в вижуаловском компиляторе map::erase() возвращает итератор, а по стандарту он возвращает void, так что такой метод непереносим

Да, верно, если речь о VC6.

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

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

M>Да в этом и главный вопрос — еще раз его задам — по пунктам — скажите мне где я не прав

ответы со ссылками на авторитетные

источники

M> 1. MAP дерево
Josuttis:

Like all standardized associative container classes, maps and multimaps are usually implemented as balanced binary trees (Figure 6.9). The standard does not specify this but it follows from the complexity of the map and multimap operations.

M> 2. Итератор указывает на неокторый элемент дерева
здесь

end() Returns an iterator pointing one past the last element in the container.

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

M> 4. Значит удаление эелемнтов в цикле может работать некоректно ( иногда не все необходимые элементы будут удалены)

Josuttis:

Here is an example of the correct way to remove elements to which an iterator refers:
   typedef std::map<std::string,float> StringFloatMap;
   StringFloatMap coll;
   StringFloatMap::iterator pos, tmp_pos;
   ...
   //remove all elements having a certain value
   for (pos = c.begin(); pos != c.end(); ) {
       if (pos->second == value) {
           c.erase(pos++);
       }
       else {
           ++pos;
       }
   }
Note that pos++ increments pos so that it refers to the next element but yields a copy of its original value. Thus, pos doesn't refer to the element that is removed when erase() is called.

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

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

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

M>>Да в этом и главный вопрос — еще раз его задам — по пунктам — скажите мне где я не прав

K>ответы со ссылками на авторитетные

источники

M>> 3. После удаления элемента — дерево перестравиваеться — это ключевой момент — так ка дерево перестравивается наш текущий итертатор тоже переместился — следовательно вполне вероятна такая ситуация что после перестройки дерева мы можем проскочить несколько элементов ( например несколько элементов из конца дерева попадают куданибудь в начало (условно начало)) и следовательно мы никогда на них не попадем..

K>здесь:
K>

K>Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Нет похоже мы не понимаем друг друга... — я плохо объясняю.. Уменьшим список вопросов...
Он один.
Пусть есть дерево. Предположим мы обходим его в ширину (или в глубину — что мне кажеться не столь принципиально). Обходя каждый элемент дерева мы помечаем его (Теперь это — меченый элемент

)
Теперь представим что где то в середине нашего обходы мы удаляем текущий узел дерева!
Что происходит — дерево некоторым образом перестраиваеться ( так чтобы еще оставаться деревом, да еще и бинарным..)
Так вот — возможно ли что после перестроения _некоторые_непомеченные_элементы окажуться как бы "левее" текущего узла, т.е. продолжая дальше наш обход мы на них не попадем никогда!...

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

Для vc6 и 7.1 можно что то типа такого использовать:

#include <map>
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <boost/bind.hpp>


int main(int argc, char* argv[])
{
    typedef std::map<std::string, int> Map;
    Map m;
    m["1"] = 1;
    m["2"] = 2;
    m["3"] = 3;
    m["4"] = 2;

    std::transform(m.begin(), m.end(), std::ostream_iterator<int>(std::cout, "\n"), boost::mem_fn(&Map::value_type::second));

    int value_to_search = 2;

    Map::iterator it = std::find_if(m.begin(), m.end(), boost::bind<bool>(std::equal_to<int>(), value_to_search, boost::bind(&Map::value_type::second, _1) ) );
    while(m.end() != it)
        it = std::find_if(m.erase(it), m.end(), boost::bind<bool>(std::equal_to<int>(), value_to_search, boost::bind(&Map::value_type::second, _1) ) );

    std::cout << std::endl;
    std::transform(m.begin(), m.end(), std::ostream_iterator<int>(std::cout, "\n"), boost::mem_fn(&Map::value_type::second));
    return 0;
}

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

M>Нет похоже мы не понимаем друг друга... — я плохо объясняю.. Уменьшим список вопросов...
M>Он один.
M>Пусть есть дерево. Предположим мы обходим его в ширину (или в глубину — что мне кажеться не столь принципиально). Обходя каждый элемент дерева мы помечаем его (Теперь это — меченый элемент

)
M>Теперь представим что где то в середине нашего обходы мы удаляем текущий узел дерева!
M>Что происходит — дерево некоторым образом перестраиваеться ( так чтобы еще оставаться деревом, да еще и бинарным..)
M>Так вот — возможно ли что после перестроения _некоторые_непомеченные_элементы окажуться как бы "левее" текущего узла, т.е. продолжая дальше наш обход мы на них не попадем никогда!...

При итерировании map-а, мы получаем элементы упорядоченные по ключу.
Соответственно то, что произошла перестройка дерева — не наша головная боль.
Итератор продолжит свой путь, и дойдёт до конца, если не делать гадостей

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

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

M>>Нет похоже мы не понимаем друг друга... — я плохо объясняю.. Уменьшим список вопросов...
M>>Он один.
M>>Пусть есть дерево. Предположим мы обходим его в ширину (или в глубину — что мне кажеться не столь принципиально). Обходя каждый элемент дерева мы помечаем его (Теперь это — меченый элемент

)
M>>Теперь представим что где то в середине нашего обходы мы удаляем текущий узел дерева!
M>>Что происходит — дерево некоторым образом перестраиваеться ( так чтобы еще оставаться деревом, да еще и бинарным..)
M>>Так вот — возможно ли что после перестроения _некоторые_непомеченные_элементы окажуться как бы "левее" текущего узла, т.е. продолжая дальше наш обход мы на них не попадем никогда!...

EX>При итерировании map-а, мы получаем элементы упорядоченные по ключу.
EX>Соответственно то, что произошла перестройка дерева — не наша головная боль.
EX>Итератор продолжит свой путь, и дойдёт до конца, если не делать гадостей

Все понял..я просто не думал что итератор идет последовательно по ключам... думал он обход в глубину(ширину) делает,
... т.е. получаеться it++ такая не дешевая операция для map. Log2(N) дейсвтий.. т.е. каждый раз ищем ключ больший текущего...

Спасибо..

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

M>... т.е. получаеться it++ такая не дешевая операция для map. Log2(N) дейсвтий.. т.е. каждый раз ищем ключ больший текущего...

Зачем?

Вот дерево:

итерируем

4->5 
5->6
6->(5)->7
7->8

Там простой алгоритм, посмотри сам.
Если не поймешь, потом напишу, пока времени нет.

M>Все понял..я просто не думал что итератор идет последовательно по ключам... думал он обход в глубину(ширину) делает,
M>... т.е. получаеться it++ такая не дешевая операция для map. Log2(N) дейсвтий.. т.е. каждый раз ищем ключ больший текущего...
Не совсем.

Оценка на сложность одного инкремента действительно O(log n), но учетная стоимость будет ниже -- всего O(1). Иными словами, если сделать k инкрементов, то время работы будет O(n+k), где n -- число элементов в дереве. Поэтому полный обход дерева сортировки выполняется за O(n), а не O(n log n).

	От:	maslukov
	Дата:	06.10.04 06:46
	Оценка:

	От:	Александр
	Дата:	06.10.04 06:55
	Оценка:

	От:	maslukov
	Дата:	06.10.04 07:03
	Оценка:

	От:	Александр
	Дата:	06.10.04 07:13
	Оценка:

	От:	Lapulya
	Дата:	06.10.04 07:19
	Оценка:

	От:	Юнусов Булат
	Дата:	06.10.04 08:47
	Оценка:

От:	Mab	http://shade.msu.ru/~mab
Дата:	06.10.04 10:22
Оценка: