remove_if эквивалентно для std :: map

Question

Я пытался стереть ряд элементов с карты в зависимости от конкретного условия. Как мне это сделать с использованием алгоритмов 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;
}

Answer 1

Почти.

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

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

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

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

Answer 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
});

Answer 3

Я получил эту документацию от превосходного SGI STL :

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

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

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

Answer 4

Теперь std::experimental::erase_if доступно в заголовке <experimental/map>.

См .: http://en.cppreference.com/w/cpp/experimental/map/erase_if

Answer 5

Оригинальный код имеет только одну проблему:

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

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

Answer 6

Основано на ответе 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 и получить его от итератора.

Answer 7

Первый

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

Во-вторых, следующий код хорош

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

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

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

Answer 8

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

Answer 9

С нижних нот:

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

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

Answer 10

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

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