станд. C++:: вопрос о карте о порядке итератора
Я - новичок C++, пытающийся использовать карту, таким образом, я могу получить постоянные поиски времени для находки () метод.
Проблема состоит в том, что, когда я использую итератор для осмотра через элементы в карте, элементы не появляются в том же порядке, что они были размещены в карту.
Не поддерживая другую структуру данных, там способ достигнуть в повторении порядка, все еще сохраняя постоянную способность к поиску времени?
Пожалуйста, дайте мне знать.
Спасибо, jbu
править: благодарит сообщить мне карту:: найдите (), не постоянное время.
6 ответов
Можно ли без поддержки другой структуры данных выполнить итерацию по порядку, сохранив при этом возможность поиска в постоянном времени?
Нет, это не так. возможный. Чтобы получить эффективный поиск, контейнеру необходимо будет упорядочить содержимое таким образом, чтобы сделать эффективный поиск возможным. Для std :: map это будет какой-то тип сортировки; для std :: unordered_map это будет порядок, основанный на хэше ключа.
В любом случае порядок будет отличаться от порядка, в котором они были добавлены.
Элементы упорядочиваются оператором < (по умолчанию) при применении к ключ.
PS. std :: map не гарантирует постоянный поиск времени.
Гарантирует максимальную сложность O (ln (n))
Во-первых, std::map не является поиском с постоянным временем. Это O(log n). Я просто подумал, что должен это уточнить.
В любом случае, вы должны указать собственную функцию сравнения, если хотите использовать другое упорядочивание. Не существует встроенной функции сравнения, которая может упорядочивать по времени вставки, но, если ваш объект содержит поле timestamp, вы можете организовать установку timestamp в момент вставки и использовать сравнение по timestamp.
Прежде всего, std::map гарантирует время поиска O(log n). Возможно, вы думаете о std::tr1::unordered_map. Но он по определению жертвует любым упорядочиванием, чтобы получить постоянное время поиска.
Вам придется потратить на это некоторое время, но я думаю, что вы можете использовать boost::multi_index_container для того, чтобы сделать то, что вы хотите.
На самом деле я собираюсь ... вернуться назад.
Если вы хотите сохранить порядок, в котором были вставлены элементы, или вообще контролировать порядок, вам нужна последовательность, которой вы будете управлять:
std :: vector(да, есть и другие, но по умолчанию используйте этот)
Вы можете использовать алгоритм std :: find (из ) для поиска определенного значения в векторе: std :: find (vec.begin (), vec.end (), значение); .
Да, у него линейная сложность O (N) , но для небольших коллекций это не имеет значения.
В противном случае вы можете начать поиск по Boost.MultiIndex , как уже предлагалось, но для новичка вы, вероятно, немного затруднитесь.
Итак, на время отойдите от вопроса сложности и придумайте что-нибудь, что работает. Вы будете беспокоиться о скорости, когда будете более знакомы с языком.
Карта не предназначена для размещения элементов в определенном порядке - используйте для этого вектор.
Если вы хотите найти что-то на карте, вы должны «искать» по ключу, используя [оператор
. Если вам нужны итерация, и поиск по ключу, см. Эту тему