Почему Go не может перебирать карты в порядке вставки?

У меня есть Navbar в качестве карты:

var navbar = map[string]navbarTab{
}

куда navbarTab имеет различные свойства, дочерние элементы и так далее. Когда я пытаюсь сделать Navbar (с for tabKey := range navbar) это появляется в случайном порядке. я знаю range случайным образом сортирует при запуске, но, похоже, нет способа получить упорядоченный список ключей или выполнить итерацию в порядке вставки.

Ссылка на игровую площадку находится здесь: http://play.golang.org/p/nSL1zhadg5 хотя, похоже, она не демонстрирует такого же поведения.

Как я могу перебрать эту карту, не нарушая порядок вставки?

Источник

2 ответа

Решение

Карты Go не поддерживают порядок вставки; вам придется реализовать это поведение самостоятельно.

Пример:

type NavigationMap struct {
    m map[string]navbarTab
    keys []string
}

func NewNavigationMap() *NavigationMap { ... }

func (n *NavigationMap) Set(k string, v navbarTab) {
    n.m[k] = v
    n.keys = append(n.keys, k)
}

Этот пример неполон и не охватывает все варианты использования (например, обновление порядка вставки на дубликаты ключей).

Если ваш вариант использования включает повторную вставку одного и того же ключа несколько раз (это не изменит порядок вставки для ключа k, если он уже был на карте):

func (n *NavigationMap) Set(k string, v navbarTab) {
    _, present := n.m[k]
    n.m[k] = v
    if !present {
        n.keys = append(n.keys, k)
    }
}

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

Источник

Общая концепция структуры данных карты состоит в том, что она представляет собой набор пар ключ-значение. "Упорядоченный" или "отсортированный" нигде не упоминается.

Википедия определение:

В информатике ассоциативный массив, карта, таблица символов или словарь - это абстрактный тип данных, состоящий из набора (key, value) пары, так что каждый возможный ключ появляется только один раз в коллекции.

Карта является одной из наиболее полезных структур данных в компьютерных науках, поэтому Go предоставляет ее как встроенный тип. Однако в спецификации языка указана только общая карта ( типы карт):

Карта - это неупорядоченная группа элементов одного типа, называемая типом элемента, индексируемая набором уникальных ключей другого типа, называемого типом ключа. Значение неинициализированной карты nil,

Обратите внимание, что спецификация языка не только пропускает "упорядоченные" или "отсортированные" слова, но и прямо заявляет об обратном: "неупорядоченный". Но почему? Потому что это дает большую свободу времени выполнения для реализации типа карты. Спецификация языка позволяет использовать любую реализацию карты, такую ​​как хэш- карта, древовидная карта и т. Д. Обратите внимание, что в текущей (и предыдущих) версиях Go используется реализация хэш-карты, но вам не нужно знать, что для ее использования.

Сообщение в блоге Go maps in action является обязательным для прочтения по этому вопросу.

До Go 1, когда карта не изменялась, среда выполнения возвращала ключи в том же порядке, когда вы перебирали ее ключи / записи несколько раз. Обратите внимание, что этот порядок мог бы измениться, если бы карта была изменена, так как реализация могла бы потребовать перефразирования для размещения большего количества записей. Люди начали полагаться на один и тот же порядок итераций (когда карта не изменялась), поэтому, начиная с Go 1, порядок итераций карты случайных чисел во время выполнения был нацелен на то, чтобы привлечь внимание разработчиков к тому, что порядок не определен и на него нельзя положиться,

Что делать то?

Если вам нужен отсортированный набор данных (будь то коллекция пар ключ-значение или что-то еще) либо по порядку вставки, либо по естественному порядку, определенному типом ключа или произвольным порядком, map это не правильный выбор. Если вам нужен предопределенный порядок, срезы (и массивы) - ваш друг. И если вам нужно иметь возможность искать элементы по предопределенному ключу, вы можете дополнительно построить карту из среза, чтобы позволить быстрый поиск элементов по ключу.

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

В вышеупомянутом блоге Go maps в действии есть раздел, посвященный порядку итерации:

При итерации по карте с помощью цикла диапазона порядок итераций не указывается и не гарантируется, что он будет одинаковым от одной итерации к следующей. Начиная с Go 1 среда выполнения рандомизирует порядок итераций карты, так как программисты полагались на стабильный порядок итераций предыдущей реализации. Если вам требуется стабильный порядок итераций, вы должны поддерживать отдельную структуру данных, которая определяет этот порядок. В этом примере используется отдельный отсортированный фрагмент ключей для печати map[int]string в ключевом порядке:

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}

PS:

... хотя, похоже, не проявляют такого же поведения.

Похоже, вы видите "тот же порядок итераций" на Go Playground, потому что выходные данные приложений / кодов на Go Playground кэшируются. Как только новый, пока что уникальный код выполняется, его выходные данные сохраняются как новые. После выполнения того же кода сохраненный вывод представляется без повторного запуска кода. Так что, по сути, это не тот же порядок итераций, который вы видите, это точно такой же вывод без повторного выполнения кода.

Источник
Другие вопросы по тегам