Вот проблема, которую я хотел бы решить: в C++ итераторы для карты, мультикарты и т. д. отсутствуют две желательные функции: (1) их нельзя проверить во время выполнения на достоверность и (2) нет оператора ‹ определены для них, что означает, что они не могут использоваться в качестве ключей в другом ассоциативном контейнере. (Меня не волнует, имеет ли оператор ‹ какое-либо отношение к порядку ключей; я просто хочу, чтобы некоторые ‹ были доступны по крайней мере для итераторов той же карты.)
Вот возможное решение этой проблемы: убедите map, multimap и т. д. хранить свои пары ключ/данные в векторе, а затем сделать итераторы небольшой структурой, содержащей указатель на сам вектор и индекс индекса. Затем можно было бы сравнить два итератора, по крайней мере, для одного и того же контейнера (путем сравнения их нижних индексов), и можно было бы проверить во время выполнения, является ли итератор допустимым.
Это решение достижимо в стандартном С++? В частности, могу ли я определить «Распределитель» для класса карты, чтобы фактически поместить элементы в вектор, а затем определить тип Allocator::pointer как небольшую структуру, описанную в последнем абзаце? Как итератор для карты связан с типом Allocator::pointer? Должен ли Allocator::pointer быть фактическим указателем или это может быть что угодно, поддерживающее операцию разыменования?
ОБНОВЛЕНИЕ 2013-06-11: Я не понимаю ответы. Если пары (ключ, данные) хранятся в векторе, то для получения элементов с заданным индексом требуется O (1), что лишь немного хуже, чем если бы у вас был прямой указатель, поэтому асимптотика не меняется. Почему респондент говорит, что итераторы карты «не хранятся»? Стандарт говорит, что итераторы остаются в силе до тех пор, пока элемент, на который они ссылаются, не удален. Что касается «настоящей проблемы»: скажем, я использую мультикарту для таблицы символов (имя переменной -> место хранения; это мультикарта, а не карта, потому что имена переменных во внутренней области видимости могут затенять переменные с тем же именем), и скажем, теперь мне нужна вторая структура данных с переменными. По-видимому, самое простое решение — использовать в качестве ключа для второй карты итератор для конкретного экземпляра имени переменной в первой карте, который работал бы, если бы только итераторы имели оператор‹.
std::map
и друзей. - person aschepler   schedule 10.06.2013