как вставка multimap в stl учитывает порядок упорядочения?
https://stackoverflow.com/questions/1595270
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть некоторые данные, которые имеют целочисленный индекс.Я постоянно генерирую новые данные, которые необходимо добавить в имеющуюся у меня коллекцию данных, отсортированных по этому индексу, в то же время я хочу легко иметь возможность перейти к началу данных и выполнять итерации по ним.Похоже, std:: multimap - это как раз то, что мне нужно.
Однако мне также нужно, чтобы данные с тем же индексом сохранялись в том порядке, в котором они были вставлены, в данном случае это означает, что когда я перебираю данные, я получаю более ранние данные перед более поздними.
Делает ли это multimap?
Я не нашел никаких гарантий, что это так.В руководстве sgi я не видел никаких упоминаний о том, является ли.Я попробовал это в реализации gcc 4.3.4, и это, казалось, было верно для некоторых ограниченных тестовых случаев, но, конечно, мне было интересно, требует ли этого стандарт, и я могу положиться на этот факт.
Редактировать: Чтобы было понятнее в ответ на некоторые ответы, я хотел, чтобы данные были отсортированы сначала по (неуникальному) индексу, а затем по времени вставки.Я надеялся, что, возможно, вторая часть будет доступна бесплатно вместе с multimap, но, похоже, это не так.
Решение
Если я что-то не упустил, стандарт не предоставляет такой гарантии.
Самый очевидный обходной путь — включить порядковый номер в качестве вторичного ключа.Например, в свой класс включите статическое беззнаковое длинное значение, и каждый раз, когда вы создаете объект для вставки в мультикарту, помещайте его текущее значение в свой объект и увеличивайте его.В функции сравнения вашего объекта используйте этот счетчик в качестве решающего фактора для упорядочивания, если данные, которые вы в настоящее время используете в качестве ключа, сравниваются равными.Обратите внимание, что в этом случае каждый ключ будет уникальным, поэтому вместо мультикарты вы можете использовать карту.
Другие советы
Кажется, новый стандарт (C++11) изменил это:
Порядок пар ключ-значение, ключи которых сравниваются эквивалентно, является порядком вставки и не меняется.[cppreference]
Однако я не решаюсь использовать его, так как кажется, что эту деталь легко упустить из виду при изменении стандартной библиотеки для обеспечения совместимости с C++11, и это такая деталь, которая незаметно вызовет ошибки, если библиотека вашего компилятора не будет реализована должным образом.
Способствовать росту multi_index поддерживает то, что вы пытаетесь сделать, если вы не хотите использовать обходной путь, указанный Джерри Коффин.
Если я вас правильно понял — вам нужны данные, отсортированные по какому-то ключу.Всякий раз, когда вы вставляете 2 объекта с одним и тем же ключом, вам необходимо извлечь их в порядке вставки.
Если это так, то вам нужно взглянуть на реализацию вашей мультикарты.В зависимости от того, как он обрабатывает случай нескольких вставок с одним и тем же ключом, он может иметь или не иметь эту гарантию.Я предполагаю, что стандарт не предлагает такой гарантии, поскольку он ограничивает реализацию очень особым случаем.
Другой подход — использовать карту (не Multi) и создать составной ключ..Ключ состоит из обычного ключа, который вы выбираете, и постоянно увеличивающегося счетчика.При сравнении с одинаковыми ключами номер вставки делает ключ уникальным.Таким образом вы устанавливаете уникальные ключи и порядок равных «обычных» ключей (надеюсь, это было понятно).
Думаю, последний подход проще всего реализовать.
Вариант:(не желательно)
С этой гарантией вы всегда можете использовать самодельную структуру данных.Я бы выбрал дерево (например, Red-Black или AVL) с вектором для хранения вставленных данных.На итерации вам нужно найти узел, перейти к вектору и перебрать его содержимое.Всякий раз, когда вы заканчиваете работу с вектором, вы переходите к следующему узлу.
Нет, не будет.Если вы этого хотите, вам следует использовать «контейнер последовательности», например вектор.Например, вы можете загрузить вектор с помощью std::pairs?
Похоже, multimap - это то, что вам нужно...
Однако мне также нужны данные с тем же индексом, которые должны храниться в том порядке, в котором они были вставлены, в данном случае это означает, что когда я выполняю итерацию по данные, которые я получаю от более ранних данных до более поздних данных.
Это будет в порядке следования индексу.Если индекс увеличивается с течением времени по мере того, как вы вставляете больше элементов, то да, из-за характера вашего индекса "более ранние" данные будут на первом месте.
В противном случае - нет.Вы могли бы сохранить две мультикарты для одних и тех же данных.Один хранится в порядке индекса, другой - в порядке времени вставки:
std::multimap<index, T*> orderedByIndex;
std::multimap<time, T*> orderedByInsertionTime;
Это дает вам возможность повторять карту в обоих направлениях.
(Редактировать Я читаю это, чтобы означать, что вы хотите иногда выполнять итерацию по индексу или иногда выполнять итерацию по времени вставки, но смотрите Приведенный выше Ответ, если вы имеете в виду сначала индекс, а затем время вставки.)
Элементы, принадлежащие одному и тому же ключу, упорядочены по нижняя граница и верхняя граница функции, когда вы получаете информацию, поэтому у вас нет гарантии, что вы получите доступ (по равный_диапазон) элементы в том порядке, в котором они были вставлены.
