Каков наилучший шаблон для перебора карт и удаления объектов?

Question

Я работаю над кодом, который в основном делает:

mapSize = map.size();
for(iter=map.begin;iter!=map.end();)
{
  call function which might delete a map item;
  if(map.size()==mapSize )
  {
     iter++;
  }
  else
  {
     mapSize = map.size();
     iter=map.begin(); /* Start again if something was deleted */
  }
}

Я думаю, что должен быть лучший способ сделать это.Есть предложения?

Answer 1

Функция должна вернуть следующий действительный итератор для вас.Вот как работает нормальная erase функция map.

Answer 2

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

EDIT

забыл пример

for(iter=map.begin;iter!=map.end();)
{
  map< type >::iterator itCopy( iter++ );

  // call function which might delete a map item;
  foo( itCopy );
}

Answer 3

Я не совсем уверен, в чем вопрос: название говорит о «картах карт», но я не вижу ничего в коде примера.

Кроме этого: что должно произойти, еслиэлемент был удален функцией?Вы хотите перезапустить итерацию с самого начала или продолжить с того места, где остановились (зная, что там, где вы остановились, возможно, были удалены карты)?Во-первых, ваш код в основном правильный, и я не думаю, что есть лучшее решение;по крайней мере, я не могу думать об одном от руки.Во-вторых, я думаю, вы хотели бы что-то вроде:

iter = map.begin();
while ( iter != map.end() ) {
    key = iter->first;
    //  call function...
    iter = map.upper_bound( key );
}

Это, наверное, самое простое решение.map.upper_bound равно O(lg n), однако;если карта большая, это может быть проблемой.В зависимости от реализации map (и частоты, с которой ваша функция удаляет элементы), использование ++ на итераторе, если ничего не было удалено с карты, может быть быстрее.

Конечно, если выЕсли вы можете гарантировать, что рассматриваемая функция никогда не удалит элемент после того, на котором вы находитесь, вы можете увеличить итератор перед вызовом функции.Однако решение с upper_bound работает безоговорочно, независимо от того, какая функция изменяется на карте.

Answer 4

Следует знать, что префиксный оператор ++ возвращает предыдущее значение итератора (копию) и переводит текущий итератор в следующее значение.Поэтому следующий код очень интересен в вашем случае:

for (iter = map.begin(); iter != map.end(); )
{
  // call function which might delete the item
  your_function(++iter);

  // and... that's all !
}

Таким образом, ваш текущий итератор не будет аннулирован удалением, если вы удалите в своей функции через erase ошибку, принимая итератор в параметре, иты в безопасности.

Answer 5

У меня есть небольшое соображение по поводу вашего кода.Если вы посмотрите на это функционально, я думаю, вам следует переписать его, чтобы не использовать реальный цикл, а, может быть, алгоритмическую функцию, такую ​​как remove_if, выполняемую столько раз, сколько вам нужно для обработки / удаления всех необходимых элементов.,Я думаю, что это приводит к гораздо более четкому коду, не имея дело с явной инициализацией цикла for.Например, в чистом C ++ (не лямбда, не C ++ 0x, это облегчит эту задачу):

template <typename I>
class Processor
{
    bool operator(I const& i)
    { // process, return true if it has to be removed
    }
};

, а затем в вашем коде:

std::remove_if(map.begin(), map.end(), Processor<Item_type>());

икакой-то флаг, который нужно определить, когда ни один элемент не был удален, поэтому вы можете продолжить (возможно, элемент класса Processor).

Answer 6

Прежде всего вызов map.size () может стоить дорого, поэтому не используйте его слишком много.

for(iter=map.begin;iter!=map.end();)
{
  current_iter = iter;
 ++iter;
  // call function which might delete a map item;
  my_function(current_iter);
}

Answer 7

Наилучшим способом будет

• Только карты карт, а не карты указателей на карты
• Вставка в них объектов ... или shared_ptr

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