Доступ к значению карты по индексу

Question

Если у меня есть структура типа

std::map<string, int> myMap;
myMap["banana"] = 1;
myMap["apple"] = 1;
myMap["orange"] = 1;

Как я могу получить доступ к myMap [0]?

Я знаю, что карта сортируется внутри, и я в порядке с этим, я хочучтобы получить значение на карте по индексу.Я пробовал myMap [0], но я получаю сообщение об ошибке:

Error   1   error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)   

Я понимаю, что могу сделать что-то вроде этого:

string getKeyAtIndex (int index){
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = 0;
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) {
        counter++;

        if (counter == index)
            return it->first;
    }
}

Но, конечно, это крайне неэффективно?Есть ли способ лучше?

Answer 1

Ваш map не должен быть доступен таким образом, он индексируется по ключам, а не по позициям.Итератор map является двунаправленным, как и list, поэтому используемая функция не менее эффективна, чем доступ к позиции list по позиции.Ваша функция может быть написана с помощью std::advance( iter, index ) начиная с begin().Если вам нужен произвольный доступ по позиции, используйте vector или deque.

Answer 2

Для достижения цели может существовать метод реализации (непереносимый), но не переносимый.

В общем случае std::map реализуется как тип двоичного дерева, обычноотсортировано по ключу.Определение первого элемента отличается в зависимости от порядка.Кроме того, по вашему определению, является ли элемент [0] узлом в верхней части дерева или самым левым конечным узлом?

Многие двоичные деревья реализованы в виде связанных списков.К большинству связанных списков нельзя получить прямой доступ, например, к массиву, поскольку для поиска элемента 5 необходимо перейти по ссылкам.Это по определению.

Вы можете решить свою проблему, используя std::vector и std::map:

1. Выделение объекта из динамической памяти.
2. Сохраните указатель вместе с ключом в std::map.
3. Сохраните указатель в std::vector в нужной позиции.

std::map позволит эффективному методу получить доступ к объекту по ключу.
std::vector позволит эффективному методу получить доступ к объекту по индексу.Хранение указателей допускает использование только одного экземпляра объекта вместо необходимости сохранять несколько копий.

Answer 3

Предыдущий ответ.В этот момент вы, конечно, потеряете все преимущества стандартной библиотечной карты.

Answer 4

Ну, на самом деле вы не можете. Способ, который вы нашли, очень неэффективен, он имеет вычислительную сложность O (n) (наихудший случай n операций, где n - количество элементов в карте).

Доступ к элементу в векторе или в массиве имеет сложность O (1) путем сравнения (постоянная вычислительная сложность, одна операция).

Учтите, что карта внутренне реализована как красно-черное дерево (или дерево avl, это зависит от реализации), и каждая операция вставки, удаления и поиска - наихудший случай O (log n) (для операций с базой 2 требуется логарифм найти элемент в дереве), это неплохо.

Способ, с которым вы можете иметь дело, состоит в том, чтобы использовать собственный класс, который имеет как вектор, так и карту. Вставка в конце класса будет усреднена O (1), поиск по имени будет O (log n), поиск по индексу будет O (1), но в этом случае операция удаления будет O (n).

Answer 5

вы можете использовать некоторые другие карты, такие как контейнеры.Сохранение размера полей может сделать двоичное дерево поиска легким для произвольного доступа.вот моя реализация ...стандартный стиль, итератор с произвольным доступом ...сбалансированное по размеру дерево ...https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
и B + дерево ...https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h