c ++ std :: map вопрос о порядке итераторов

Question

Я новичок в C ++, пытающийся использовать карту, чтобы получить постоянный поиск по методу find ().

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

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

Пожалуйста, дайте мне знать.

Спасибо, JBU

edit: спасибо, что сообщили мне, что map :: find () не является постоянным временем.

Answer 1

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

Нет, это невозможно. Чтобы получить эффективный поиск, контейнеру необходимо упорядочить содержимое таким образом, чтобы обеспечить эффективный поиск. Для std :: map это будет некоторый тип отсортированного порядка; для std :: unordered_map это будет порядок, основанный на хэше ключа.

В любом случае порядок будет отличаться от порядка, в котором они были добавлены.

Answer 2

Прежде всего, std::map гарантирует время поиска O (log n).Возможно, вы думаете о std::tr1::unordered_map.Но это по определению жертвует любым порядком, чтобы получить поиск в постоянном времени.

Вам придется потратить некоторое время на это, но я думаю, что вы можете bash boost::multi_index_container, чтобы сделать то, чтоты хочешь.

Answer 3

Как насчет использования vector для ключей в исходном порядке и map для быстрого доступа к данным?

Примерно так:

vector<string> keys;
map<string, Data*> values;

// obtaining values
...
keys.push_back("key-01");
values["key-01"] = new Data(...);
keys.push_back("key-02");
values["key-02"] = new Data(...);
...

// iterating over values in original order
vector<string>::const_iterator it;
for (it = keys.begin(); it != keys.end(); it++) {
    Data* value = values[*it];
}

Answer 4

Я собираюсь на самом деле ... идти назад.

Если вы хотите сохранить порядок, в котором были вставлены элементы, или вообще контролировать порядок, вам нужна последовательность, которую вы будете контролировать:

• std::vector (да, есть другие, но по умолчанию используйте этот)

Вы можете использовать алгоритм std::find (из <algorithm>) для поиска определенного значения в векторе: std::find(vec.begin(), vec.end(), value);.

О да, линейная сложность O(N), но для небольших коллекций это не имеет значения.

В противном случае, вы можете начать смотреть на Boost.MultiIndex, как уже предлагалось, но для новичка вам, вероятно, придется немного побороться.

Итак, откажитесь от проблемы сложности на данный момент и придумайте что-нибудь, что сработает. Вы будете беспокоиться о скорости, когда будете лучше знакомы с языком.

Answer 5

Элементы упорядочены по operator< (по умолчанию) при применении к ключу.

PS. std :: map не гарантирует поиск в постоянном времени.
Это гарантирует максимальную сложность O (ln (n))

Answer 6

Карта не предназначена для размещения элементов в некотором порядке - используйте вектор для этого.

Если вы хотите найти что-то на карте, вы должны «искать» по ключу, используя [оператор

Если вам нужны оба варианта: итерация и поиск по ключу, посмотрите эту тему

Answer 7

Во-первых, std::map - это не поиск в постоянном времени.Это O (войти N).Просто подумал, что я должен установить это прямо.

В любом случае, вы должны указать свою собственную функцию сравнения, если вы хотите использовать другой порядок.Нет встроенной функции сравнения, которая может упорядочивать по времени вставки, но, если ваш объект содержит поле метки времени, вы можете организовать установку метки времени во время вставки и использовать сравнение по меткам времени.*

Answer 8

Да, вы можете создать такую ​​структуру данных, но не используя стандартную библиотеку ... причина в том, что стандартные контейнеры могут быть вложенными, но не могут быть смешаны.

Нет проблем с реализацией, например, структуры данных карты, где все узлы также находятся в двусвязном списке в порядке вставки, или, например, карты, где все узлы находятся в массиве. Мне кажется, что одна из этих структур может быть тем, что вы ищете (в зависимости от того, какую операцию вы предпочитаете выполнять быстро), но ни одна из них не является тривиальной для построения с использованием стандартных контейнеров, потому что каждый стандартный контейнер (vector, * 1004) *, set, ...) хочет быть единственным и единственным способом доступа к содержащимся элементам.

Например, во многих случаях мне показалось полезным иметь узлы, которые были одновременно в нескольких двусвязных списках, но вы не можете сделать это, используя std::list.