[c++, stl] как удалить текущий ключ?

pitrik2

это вообще как-нибудь документировано?
чото в гугле не нахожу нормального ответа
пока придумал делать так: пройтись по мапе, сохранить в вектор ключи которые хочу удалить, потом удалить эти ключи методами erase(key)
неужели это и есть правильный способ?
многие предлагают в гугле такой подход: перескочить итератором на следующий элемент а потом удалить текущий
но это точно будет работать? оно документировано? итератор целостность не потеряет? а то может при таком способе я не все элементы проитерирую...

for (MyMap::iterator i = mymap.begin end = mymap.end; i != end;)

{

    if (hasToBeErased(*i

        mymap.erase(i++);

    else

        ++i;

}

SEMEN73

Как это ни странно, все описано в хелпе по функции erase

Return Value
... a bidirectional iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the map if no such element exists.

pitrik2

Как это ни странно, все описано в хелпе по функции erase

я про стандарт спрашивал
в стандарте функция erase объявлена с возвратом void
так что или у тебя какой-то новый стандарт (типа с++0x) либо вообще не стандарт

SEMEN73

Упс. Erase возвращает итератор только для sequence контейнеров. А я не глядя скопировал кусок из MSDN'а.
Для ассоциативных контейнеров "the erase members shall invalidate only iterators and references to the erased elements" (пункт 23.1.2.8).

katrin2201

пока придумал делать так: пройтись по мапе, сохранить в вектор ключи которые хочу удалить, потом удалить эти ключи методами erase(key)

Еще можно клонировать мапу и итерироваться по клону, а удалять из оригинала.

ppplva

а то может при таком способе я не все элементы проитерирую...

Все, которые были в мапе к началу прохода. Удаление не меняет порядка элементов и не инвалидирует итератор (если его заранее переставить на следующий элемент).

pitrik2

Еще можно клонировать мапу и итерироваться по клону, а удалять из оригинала.

ага, ужо подумал про это
посмотрел сурцы - клон делает полный обход всего дерева и вызывает конструкторы копирования для всех ключей и значений
т.е. это явно долгая операция
думаю вот терь, может создать две мапы
типа параллельно их наполнять
еще думаю может ваще мапа не нужна...
код выглядит типа так:
очищается мапа, пихается в нее 50 элементов, каждый из элементов находится
может быстрее на векторе будет работать? обходов там получится ровно арифм. прогрессия до 50, зато добавления быстрее
у вектора: 50 операций добавлений + S_50 операций поиска = 50 + 50*49/2 = 1275
у мапы: 50*ln(50) на поиск + S[lnx] на добавление = 344
блин, мапа таки быстрее, даже ее проклонировать: 344*2 < 1275

pitrik2

Удаление не меняет порядка элементов

ну вот я и спрашиваю
это точно есть в стандарте?

ppplva

Что именно? То, что если A<B и из M удалили C, то A<B?

katrin2201

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

ну, про мапы указателей думаю, ты тем более уже подумал =)

pitrik2

Что именно? То, что если A<B и из M удалили C, то A<B?

эээ
а есть гарантия что итератор обходит элементы учитывая порядок?
упс
похоже так иесть:

Internally, map containers keep their elements ordered by their keys from lower to higher , therefore begin returns the element with the lowest key value in the map.

тогда все вопросы снимаются

pitrik2

ну, про мапы указателей думаю, ты тем более уже подумал =)

ну я это к тому что это не просто тупо memcpy

klyv

Internally, map containers keep their elements ordered by their keys from lower to higher , therefore begin returns the element with the lowest key value in the map.

Это из стандарта?

enochka1145

Посмотри в книге "Effective STL", там этому целый Item отведён.

williamsmith61

Тока седня так как раз делал. Вроде работает.

vasena

Самый простой способ это создать новую мапу в которой только те элементы, которые тебе нужны. Он всегда будет работать.
Насчет "перескочить итератором на следующий элемент а потом удалить текущий
": это точно работает не всегда, так как в стандарте это не описанно и знаю людей, которые долго мучались при портировании таких фильтраций с одного стл на другой.

Andbar

Короче, в студии работает такой код:

	for(std::map<..., ...>::iterator it = m.begin next = it; (m.end!=it) && (++next, 1); it = next)

	{

		//... do something with *it

		if(hasToBeErased(*it m.erase(it);

	}

Не очень хорошо смотрится (++next, 1 зато нет ни одного оператора в теле цикла, относящегося к проходу map'а. Ещё можно закешировать m.end но мне кажется, что сложность доставания последнего элемента не должна быть сложной операцией...

kokoc88

(m.end!=it) && (++next, 1)

Это можно как-то красивее записать, типа

++next, it != m.end

Andbar

На последней проверке будет ошибка, т.к. next будет уже указывать на end соответственно приращивать его некуда.
Короче, смысл этой конструкции можно передать функцией вида

{

  bool b = m.end!=it;

  if(b) ++next;

  return b;

}

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

kokoc88

На последней проверке будет ошибка

Понятно. Хочется придумать что-то красивое, но похоже, что все записи внутри условия получаются примерно одинаковыми.

erotic

Насчет "перескочить итератором на следующий элемент а потом удалить текущий": это точно работает не всегда, так как в стандарте это не описанно и знаю людей, которые долго мучались при портировании таких фильтраций с одного стл на другой.

Может быть это проблема конкретный реализаций stl? Я всегда считал, как тут и было написано выше, что erase не инвалидирует следующий за удаляемым итератором итератор.

slonishka

он эксепшен кидает:

throw std::logic_error ("Осторожно, двери закрываются. Следующая станция -- УНИВЕРСИТЕТ.");

vasena

Ошибки в реализации нет, так как в стандарте про это ничего не написанно.
Это кстати одна из известных проблем stl, типа описанно внешнее поведение метода, но нет четкого описания внутреннего и как следствие делают как хотят.

Andbar

Ошибки в реализации нет, так как в стандарте про это ничего не написанно.
Это кстати одна из известных проблем stl, типа описанно внешнее поведение метода, но нет четкого описания внутреннего и как следствие делают как хотят.

Кстати, я при беглом просмотре не смог найти, где конкретно в стандарте написано, что удаление из set/map не должно портить итераторы кроме удаляемого. Хотя в различных более или менее популярных ресурсах по stl это описано как одна из важных фич этих контейнеров. Мб. кто-то знает, где конкретно это описывается (в описании set/map написаны только базовые вещи и примерный интерфейс).
Кстати, а нет ли какого-нить распространённого теста для компилятора/стандартной библиотеки, который бы проверял их на соответствие стандарту (что-то подобное acidtest'у в мире браузеров а также, возможно, на не совсем стандартные, но часто используемые возможности?

ppplva

23.1.2 Associative containers

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.

И все же, что конкретно не написано в стандарте? Итераторы при удалении не инвалидируются, порядок элементов, как выяснили выше в треде, не нарушается. Что может пойти не так?
Или говорит о багах и нестандартностях в каких-то версиях stl? Дело пахнет майкрософтом

Andbar

Дело пахнет майкрософтом

В версии stl, идущей с cl всё ок, во всяком случае с тем, что касается данной темы
Спасибо за цитату, похоже проскочил мимо этого текста при беглом поиске.

bleyman

порядок элементов, как выяснили выше в треде, не нарушается. Что может пойти не так?

Ну как бы если вдруг кто-нибудь решит сделать std::map не деревом, а хэштейблом (к чему, если мне не изменяет память, в стандарте предпосылки есть, порядок обхода от минимального к максимальному не гарантируется причём умеющим шринкаться, то все дружно отсосут.
И кстати, я вдобавок не очень понимаю, как гарантируется порядок обхода даже в случае дерева. Там же куски поворачиваются при удалении! Типа, я пришёл в ноду, запомнил её в переменную, пришёл в чайлд ноду, удалил родителя. Произошло переворачивание. В результате у меня есть хорошие шансы пропустить поддерево, а то и два (не помню, как именно оно происходило в красно-чёрных, но ведь стандарт не мешает реализовать и AVL, там точно бывают весьма стрёмные перевороты и/или прийти в некоторые ещё раз. Если, конечно, девелоперы об этом не подумали и не решили зачем-то гарантировать мне порядок обхода (это не то же самое, что "invalidate only iterators and references to the erased elements"! наваяв хз какой дико сложный и наверняка дегрейдящий производительность алгоритм, который я даже представить себе не могу, кроме как если у дерева есть список всех своих итераторов и оно умеет их патчить.

Andbar

Разве в бинарном упорядоченном дереве для любой вершины не всегда известно, где ближайший больший/меньший элемент? Ведь в итераторах можно хранить указатели на вершины, а не путь до текущего элемента.

ppplva

Серьезно, почитай стандарт. Тот же раздел, пункт 9.

The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive,
value_comp(*j, *i) == false

Никакого hashmap. Это нестандартное расширение, и у него даже интерфейс другой, чтобы не путали. Никаких lower_bound и пр.
Единственно, у меня возникают некоторые подозрения относительно несравнимых элементов (т.е. эквивалентных). Их, получается, можно проходить в любом порядке. Наверное все же есть где-то оговорка. В любом случае, для map проблем быть не должно.

Andbar

Единственно, у меня возникают некоторые подозрения относительно несравнимых элементов (т.е. эквивалентных). Их, получается, можно проходить в любом порядке. Наверное все же есть где-то оговорка. В любом случае, для map проблем быть не должно.

А что не так с multimap'ом?

#include <iostream>

#include <map>



typedef std::pair<int, bool> val;

typedef std::multimap<int, val> valmap;



void mfill(valmap &m)

{

	m.clear;

	m.insert(valmap::value_type(1, val(1, true;

	m.insert(valmap::value_type(1, val(2, false;

	m.insert(valmap::value_type(1, val(3, false;

	m.insert(valmap::value_type(2, val(4, false;

	m.insert(valmap::value_type(2, val(5, false;

	m.insert(valmap::value_type(2, val(6, true;

	m.insert(valmap::value_type(2, val(7, true;

	m.insert(valmap::value_type(3, val(8, false;

	m.insert(valmap::value_type(3, val(9, true;

}



void mout(valmap &m)

{

	for (valmap::iterator it = m.begin next = it;

		(next != m.end && (++next, true); it = next)

	{

		std::cout << it->first << ':' << it->second.first <<

			(it->second.second?"* ":" ");

	}

	std::cout << std::endl;

}



int main

{

	valmap m;

	mfill(m);

	for (valmap::iterator it = m.begin next = it;

		(next != m.end && (++next, true); it = next)

	{

		std::cout << it->first << ':' << it->second.first <<

			(it->second.second?"* ":" ");

		if (it->second.second)

		{

			if (1 == it->first)

			{

				m.insert(it, valmap::value_type(1, val(0, true;

				m.insert(valmap::value_type(1, val(0, false;

				m.insert(m.lower_bound(1 valmap::value_type(1, val(10, false;

				m.insert(m.upper_bound(1 valmap::value_type(1, val(11, false;

			}

			m.erase(it);

		}

	}

	std::cout << std::endl;

	mout(m);

}

На cl 15.00.30729.01 и gcc 4.1.2 20061115 результаты одинаковые и вполне предсказуемые.

rosali

> кто-нибудь решит сделать std::map не деревом, а хэштейблом
O_o а lower_bound как реализовывать будешь?

vasena

erase members shall invalidate only iterators and references to the erased elements

Согласен, ошибался. Просто встречался несколько раз, что удаление приводит к перестроению map'a и даже казалось, что заглядывал в стандарт, правда видимо хреново заглядывал ).

margadon

Ну как бы если вдруг кто-нибудь решит сделать std::map не деревом, а хэштейблом (к чему, если мне не изменяет память, в стандарте предпосылки есть, порядок обхода от минимального к максимальному не гарантируется причём умеющим шринкаться, то все дружно отсосут

ну не факт - смотря как хештейбл реализован
Я пытался заставить сосать __gnu_cxx::hash_map - не сосёт
У него внутри не обычный массив пар, куда бьёт хеш-функция, а массив указателей на цепочки из склеившихся элементов.

slonishka

Я пытался заставить сосать __gnu_cxx::hash_map - не сосёт

просто ты уважаешь его как личность лол