Как удалить элемент из map c

Особенности языков программирования

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

Проще всего начать знакомство с STL со стандартных типов для хранения данных — контейнеров. Каждый раз, когда в программе возникает необходимость оперировать множеством элементов, в дело вступают контейнеры. Контейнер — это практическая реализация функциональности некоторой структуры данных. В языке C (не в C++) существовал только один встроенный тип контейнера: массив. Сам по себе массив имеет ряд недостатков: к примеру, размер динамически выделенного массива невозможно определить на этапе выполнения. Однако основной причиной для более внимательного ознакомления с контейнерами STL является отнюдь не вышеперечисленные недостатки массива. Истинная причина кроется несколько глубже. Дело в том, что в реальном мире структура данных, информацию о которых необходимо хранить, далеко не всегда удачно представима в виде массива. В большинстве случаев требуется контейнер несколько иной функциональности. К примеру, нам может потребоваться структура данных «множество строк», поддерживающая следующие функции:
— добавить строку к множеству;
— удалить строку из множества;
— определить, присутствует ли в рассматриваемом множестве данная строка;
— узнать количество различных строк в рассматриваемом множестве;
— просмотреть всю структуру данных, «пробежав» все присутствующие строки. Конечно, легко запрограммировать тривиальную реализацию функциональность подобной структуры данных на базе обычного массива. Но такая реализация будет крайне неэффективной. Для достижения приемлемой производительности имеет смысл реализовать хэш-таблицу или сбалансированное дерево, но задумайтесь: разве реализация подобной структуры данных (хэш либо дерево) зависит от типа хранимых объектов? Если мы потом захотим использовать ту же структуру не для строк, а, скажем, для точек на плоскости — какую часть кода придётся переписывать заново? Реализация подобных структур данных на чистом C оставляла программисту два пути. 1) Жёсткое решение (Hard-Coded тип данных). При этом изменение типа данных приводило к необходимости внести большое число изменений в самых различных частях кода. 2) По возможности сделать обработчики структуры данных независимыми от используемого типа данных. Иными словами, использовать тип void* везде, где это возможно. По какому бы пути реализации структуры данных в виде контейнера вы не пошли, скорее всего, никто другой ваш код понять, и тем более модифицировать, будет не в состоянии. В лучшем случае другие люди смогут им просто пользоваться. Именно для таких ситуаций существуют стандарты — чтобы программисты могли говорить друг с другом на одном и том же формальном языке. Шаблоны (Templates) в C++ предоставляют замечательную возможность реализовать контейнер один раз, формализовать его внешние интерфейсы, дать асимптотические оценки времени выполнения каждой из операций, а после этого просто пользоваться подобным контейнером с любым типом данных. Можете быть уверены: разработчики стандарта C++ так и поступили. В первой части курса мы на практике познакомимся с основными концепциями, положенными в основу контейнеров C++.

Вставка и удаление элементов из std::map в цикле

Можно ли в цикле по std::map на каждом шаге совершать несколько удалений и вставок элементов в этот же контейнер? Т.е. будет ли правильно работать следующий код?

std::map my_map; for (auto&& it = my_map.begin(); it != my_map.end();) < if (pair.second == 42) it = my_map[pair.first].erase(it); if (2 + 2 == 4) it = my_map.emplace(42, 42).first; //. if (no_insert_and_no_erase) ++it; >

Отслеживать
8,602 4 4 золотых знака 30 30 серебряных знаков 53 53 бронзовых знака
задан 15 мая 2017 в 19:48
31 1 1 серебряный знак 2 2 бронзовых знака
Ну по идее должен, почему бы ему не работать? Если только скомпилируется.
15 мая 2017 в 19:50

@VladD я исхожу из той логики, что при удалении возвращенный итератор может проскочить вставленный на этой итерации элемент

15 мая 2017 в 19:53
Ну у вас же сначала удаление?
15 мая 2017 в 19:54
@VladD нет, имеется в виду, что порядок произвольный и количество тоже
15 мая 2017 в 19:55
Только вот непонятна логика со вставкой: если вставка будет в конец, вы перепрыгнете весь список?
15 мая 2017 в 19:55

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

pair < iterator, bool>container::emplace (args) //std::map

iterator container::emplace (args) // std::multimap

Для всех контейнеров(ассоциативных и неупорядоченных) операция вставки сохраняет корректность ссылок на существующие элементы. Для ассоциативных контейнеров все итераторы установленные на существующие элементы остаются корректными.

iterator container::erase(iterator) (С++11)

При удалении элемента главное не удалить итератор ссылающийся на этот элемент.

std::map coll; . for(auto pos = coll.begin(); pos != coll.end(); ++pos) < if(pos->second == value) coll.erase(pos); // Ошибка во время выполнения > 

В С++11 функция-член erase всегда возвращает значение следующего элемента.

std::map coll; . for(auto pos = coll.begin(); pos != coll.end();) < if(pos->second == value) < pos = coll.erase(pos); // C++11 >else < ++pos; >> 

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

template bool replaceKey(Cont& c, const typename Cont::key_type& oldKey, const typename Cont::key_type& newKey) < typename Cont::iterator pos; pos = c.find(oldKey); if(pos != c.end()) < //Вставка нового элемента c.insert( typename Cont::value_type(newKey, pos->second) ); //Удаляем старый элемент c.erase(pos); return true; > else < return false; >> 

Для мапы также существует более простой способ:

coll["newKey"] = coll["oldKey"]; coll.erase("oldKey"); 

Как удалить элемент из map c

GlowCheese → Introducing NeoTLE — the best Discord bot for Codeforces

FunnyScientist → Sum of GCD of all contiguous subsequence

Red0 → Way to Optimize GCC Ordered Set?

Arshavir → A very logical captcha

Kolyanchick → . — День 20

PUSSY_LICKING_LOLI_69 → Need help finding JOI problems and editorials.

Sherif → Have you seen this data structure before?

IanDeHaan → Teams Going to the 2024 ICPC North America Championship

m aroonrk → AtCoder Regular Contest 173 Announcement

Wasif_Shahzad → I, finally, achieved something in CP

ooaa → Codeforces Round #922 (Div. 2) Разбор

Kolyanchick → . — День 19

maomao90 → CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

natalina → Codeforces Round #933 (Div. 3)

Zhtluo → All You Need is Randomly Guessing — How to Improve at Codeforces

harsh__h → Codeforces Round #931 (Div. 2)

GDCass1ni → Stop writting editorials for MIKE.

KADR → Codeforces Beta Round #97: разбор

dakshdixit183 → Ternary Search Implementation

i_love_penguins → Codeforces Round #932 (Div. 2)

awoo → Разбор Educational Codeforces Round 162

nisritha35 → Invitation to Turing Cup 2K24 — organized by Turing Hut, VNRVJIET (Prizes worth Rs 75,000)

pajenegod → Slowdown bug affecting C++ (64 bit) on Codeforces

Alfar_ABI → pen

atcoder_official → AtCoder Beginner Contest 343 Announcement

Как удалить элемент из map c

Здравствуйте, уважаемые знатоки C++.

Нужно удалять элементы из std::map согласно некотому условию. Всегде ли будет работать такой трюк:

 std::map m; std::map::iterator cur, end; cur = m.begin(); end = m.end(); while (cur != end) < if (is_not_OK(*cur)) m.erase(cur++); else ++cur; >

Re: удаление элементов из std::map

Здравствуйте, sigsegv, Вы писали:

S>Здравствуйте, уважаемые знатоки C++.

S>Нужно удалять элементы из std::map согласно некотому условию. Всегде ли будет работать такой трюк:

Да, это стандартный прием.

Любите книгу — источник знаний (с) М.Горький
Re[2]: удаление элементов из std::map

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, sigsegv, Вы писали:

S>>Здравствуйте, уважаемые знатоки C++.

S>>std::map m; S>>std::map::iterator cur, end; S>>cur = m.begin(); S>>end = m.end(); S>>while (cur != end) S>>< S>> if (is_not_OK(*cur)) S>> m.erase(cur++); > else S>> ++cur; S>>>

S>>Нужно удалять элементы из std::map согласно некотому условию. Всегде ли будет работать такой трюк:

B>.

B>Да, это стандартный прием.

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

стандартный прием это воспользоваться тем, что erase возвращает итератор на следующий после последнего удаленого элемент:

while(cur != m.end()) < if(is_not_OK(*cur)) cur = m.erase(cur); else ++cur; >

заранее запомненный m.end() также скорее всего окажется невалидным.

Re[3]: удаление элементов из std::map

Здравствуйте, Sk0rp, Вы писали:

S>не согласен, при удалении может в общем случае произойти реаллокация и итератор станет абсолютно невалидным.
Ассоциативные контейнеры не попадают в этот «общий случай»:

23.1.2/8
The insert members shall not affect the validity of iterators and references to the container,
and the erase members shall invalidate only iterators and references to the erased elements.

Еще раз обращаю внимание на конструкцию

m.erase(cur++); 

S>while(cur != m.end()) S> < S>if(is_not_OK(*cur)) S> cur = m.erase(cur); S> else S> ++cur; S>> S>

B>m.erase(cur++);

iterator erase( iterator _Where ); iterator erase( iterator _First, iterator _Last ); size_type erase( const key_type& _Key );

 std::mapint, int> m; std::mapint, int>::iterator it = m.begin(); it = m.erase( it );

iterator& operator++() < // preincrement ++(*(const_iterator *)this); return (*this); > iterator operator++(int) < // postincrement iterator _Tmp = *this; ++*this; return (_Tmp); >

B>>m.erase(cur++); >