эквивалент 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;
}
Решение
Почти.
for(; iter != endIter; ) {
if (Some Condition) {
aMap.erase(iter++);
} else {
++iter;
}
}
То, что у вас было изначально, увеличило бы итератор дважды если вы удалили из него элемент;потенциально вы можете пропустить элементы, которые необходимо удалить.
Это распространенный алгоритм, который я видел и документировал во многих местах.
[EDIT] Вы правы в том, что итераторы становятся недействительными после стирания, но только итераторы, ссылающиеся на стираемый элемент, другие итераторы по-прежнему действительны.Следовательно, используйте iter++ в вызове Erase().
Другие советы
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
});
Я получил эту документацию от отличный справочник по SGI STL:
У карты есть важное свойство, которое вставка нового элемента в карту не лишает аннулирования итераторов, которые указывают на существующие элементы.Стирение элемента с карты также не лишает аннулирования итераторов, за исключением, конечно, для итераторов, которые фактически указывают на элемент, который стерт.
Итак, имеющийся у вас итератор, указывающий на удаляемый элемент, конечно же, будет признан недействительным.Сделайте что-то вроде этого:
if (some condition)
{
iterator here=iter++;
aMap.erase(here)
}
Исходный код имеет только одну проблему:
for(; iter != endIter; ++iter)
{
if(Some Condition)
{
// is it safe ?
aMap.erase(iter++);
}
}
Здесь iter
увеличивается один раз в цикле for и еще раз при стирании, что, вероятно, приведет к какому-то бесконечному циклу.
Сейчас, std::experimental::erase_if
есть в шапке <experimental/map>
.
Видеть: http://en.cppreference.com/w/cpp/experimental/map/erase_if
Из нижних нот:
http://www.sgi.com/tech/stl/PairAssociativeContainer.html
Парный ассоциативный контейнер не может предоставлять изменяемые итераторы (как определено в требованиях к тривиальному итератору), поскольку тип значения изменяемого итератора должен быть назначаемым, а пара не является назначаемой.Однако парный ассоциативный контейнер может предоставлять итераторы, которые не являются полностью постоянными:итераторы такие, что выражение (*i).секунда = d является допустимым.
Первый
Карта имеет важное свойство: вставка нового элемента в карту не делает недействительными итераторы, указывающие на существующие элементы.Удаление элемента с карты также не делает недействительными никакие итераторы, за исключением, конечно, итераторов, которые фактически указывают на стираемый элемент.
Во-вторых, следующий код хорош
for(; iter != endIter; )
{
if(Some Condition)
{
aMap.erase(iter++);
}
else
{
++iter;
}
}
При вызове функции параметры оцениваются перед вызовом этой функции.
Поэтому, когда iter++ вычисляется перед вызовом стирания, оператор итератора ++ вернет текущий элемент и укажет на следующий элемент после вызова.
ИМХО нет remove_if()
эквивалент.
Вы не можете изменить порядок карты.
Так remove_if()
не могу поставить в конце интересующие вас пары, по которым можно позвонить erase()
.
На основе Ответ Железного Спасителя Для тех, кто хотел бы предоставить диапазон, более похожий на стандартные функциональные итераторы.
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 и получить их от итератора.
Ответ Стива Фолли Я чувствую себя более эффективным.
Вот еще один простое, но менее эффективное решение:
В решении используется 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);
Если вы хотите стереть все элементы с ключом больше 2, то лучший способ —
map.erase(map.upper_bound(2), map.end());
Однако работает только для диапазонов, а не для любого предиката.
я использую вот так
std::map<int, std::string> users;
for(auto it = users.begin(); it <= users.end()) {
if(<condition>){
it = users.erase(it);
} else {
++it;
}
}