Remove_if для std:: map

Я пытался удалить ряд элементов из карты на основе определенного условия. Как это сделать, используя алгоритмы STL?

Первоначально я думал об использовании remove_if, но это невозможно, так как remove_if не работает для ассоциативного контейнера.

Есть ли какой-либо эквивалентный алгоритм "remove_if", который работает для карты?

Как простой вариант, я подумал о том, чтобы перебирать карту и стирать ее. Но прокручивается карта и стирается безопасный вариант? (Поскольку итераторы становятся недействительными после стирания)

Я использовал следующий пример:

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

Ответы

Ответ 1

Почти.

for(; iter != endIter; ) {
     if (Some Condition) {
          aMap.erase(iter++);
     } else {
          ++iter;
     }
}

То, что у вас изначально было, увеличило бы итератор в два раза, если бы вы удалили из него элемент; Вы можете пропустить элементы, которые необходимо стереть.

Это распространенный алгоритм, который я видел использованным и задокументированным во многих местах.

[EDIT] Вы правы, что итераторы становятся недействительными после стирания, но только итераторы, ссылающиеся на удаляемый элемент, другие итераторы по-прежнему действительны. Следовательно, используя iter++ в вызове erase().

Ответ 2

erase_if для std :: map (и других контейнеров)

Я использую следующий шаблон для этой самой вещи.

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

Это ничего не вернет, но удалит элементы из std :: map.

Пример использования:

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

Второй пример (позволяет передать тестовое значение):

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

Ответ 3

Я получил эту документацию из отличную ссылку SGI STL:

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

Итак, итератор, который у вас есть, который указывает на стираемый элемент, будет, конечно, недействительным. Сделайте что-то вроде этого:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

Ответ 4

Исходный код имеет только одну проблему:

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

Здесь iter увеличивается один раз в цикле for и в другое время стирания, которое, вероятно, закончится в некотором бесконечном цикле.

Ответ 6

Из нижних нот:

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

Пара ассоциативный контейнер не может предоставлять изменяемые итераторы (как определено в требованиях тривиального итератора), потому что тип значения изменяемого итератора должен быть назначаемым, а пара не назначается. Однако ассоциативный контейнер пары может предоставить итераторы, которые не являются полностью постоянными: итераторы, для которых справедливо выражение (* i).second = d.

Ответ 7

ИМХО нет эквивалента remove_if().
Вы не можете изменить порядок карты.
Таким образом, remove_if() не может поместить ваши пары интересов в конец, на который вы можете позвонить erase().

Ответ 8

Первая

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

Во-вторых, хороший код

for(; iter != endIter; )
{
    if(Some Condition)
    {
        aMap.erase(iter++);
    }
    else
    {
        ++iter;
    }
}

При вызове функции параметры оцениваются перед вызовом этой функции.

Итак, когда iter ++ оценивается до вызова для удаления, оператор ++ итератора ++ возвращает текущий элемент и будет указывать на следующий элемент после вызова.

Ответ 9

Основано на ответе Iron Savior. Для тех, кто хотел бы предоставить более широкий диапазон в соответствии со стандартом STD, использующим итераторы.

template< typename ContainerT, class FwdIt, class Pr >
void erase_if(ContainerT& items, FwdIt it, FwdIt Last, Pr Pred) {
    for (; it != Last; ) {
        if (Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

Любопытно, есть ли какой-нибудь способ потерять элементы ContainerT и получить его от итератора.

Ответ 10

Стив Фолли отвечает Я чувствую себя более эффективным.

Вот еще одно эффективное простое и эффективное решение:

В решении используется remove_copy_if для копирования значений, которые мы хотим в новый контейнер, а затем свопинг содержимого исходного контейнера с содержимым нового:

std::map<int, std::string> aMap;

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);

Ответ 11

Если вы хотите удалить все элементы с ключом больше 2, лучший способ -

map.erase(map.upper_bound(2), map.end());

Работает только для диапазонов, но не для какого-либо предиката.

Ответ 12

Я использую как это

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }