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

c++ stl map

48551 просмотра

12 ответа

Я пытался стереть ряд элементов с карты в зависимости от конкретного условия. Как мне это сделать, используя алгоритмы 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;
}
Автор: aJ. Источник Размещён: 08.07.2019 02:46

Ответы (12)


107 плюса

Решение

Почти.

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

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

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

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

Автор: Steve Folly Размещён: 29.04.2009 05:20

65 плюса

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
});
Автор: Iron Savior Размещён: 16.05.2013 08:39

3 плюса

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

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

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

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}
Автор: 1800 INFORMATION Размещён: 29.04.2009 05:22

2 плюса

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

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

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

Автор: partha biswas Размещён: 16.01.2013 06:14

2 плюса

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

Смотрите: http://en.cppreference.com/w/cpp/experimental/map/erase_if

Автор: user1633272 Размещён: 07.04.2017 03:41

1 плюс

Снизу ноты:

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

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

Автор: piotr Размещён: 29.04.2009 08:59

1 плюс

Первый

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

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

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

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

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

Автор: Vincent Размещён: 25.08.2009 01:54

1 плюс

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

Автор: user109134 Размещён: 19.05.2009 09:28

1 плюс

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

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элементы и получить их от итератора.

Автор: Greg Domjan Размещён: 01.06.2015 10:52

0 плюса

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

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

Решение использует 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);
Автор: aJ. Размещён: 25.05.2009 06:13

0 плюса

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

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

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

Автор: Tadeusz Kopec Размещён: 10.08.2011 09:33

0 плюса

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

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }
Автор: voltento Размещён: 27.11.2018 08:13
32x32