Карта в цикле диапазона заказа

Question

Карта в цикле диапазона заказа

Я ищу точный способ измерения Gomap с целью.

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

Все, что я нашел здесь на Stackru и Googling, - это (imho) обходные пути, которые мне не нравятся.

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

Решения, которые я нашел:

Отслеживайте ключи и значения в двух отдельных срезах: звучит как "Не использовать карту", теряя все преимущества использования карт.
Используйте карту, но отслеживайте ключи в другом срезе: это означает дублирование данных, которое может привести к смещению данных и в конечном итоге может привести к множеству ошибок и болезненной отладке.

Что ты предлагаешь?

Отредактируйте в ответ на возможный дубликат флага.

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

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

который не является лексикографическим и поэтому отличается от @gramme.ninja вопрос:

Как получить ключи в порядке / отсортировать карту, чтобы ключи были в порядке и значения соответствовали?

6

loops dictionary go hashmap for-range

Источник

user3119050 12 сен '16 в 12:17

1 ответ

Решение

Другие вопросы по тегам loops dictionary go hashmap for-range

user1705598 12 сен '16 в 12:34 2016-09-12 12:34 · Accepted Answer · 2016-09-12 12:34

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

С ломтиком клавиш

Самый простой способ добиться этого - поддерживать порядок ключей в другом срезе. Всякий раз, когда вы помещаете новую пару в карту, сначала проверьте, есть ли ключ в ней. Если нет, добавьте новый ключ в отдельный фрагмент. Когда вам нужны элементы по порядку, вы можете использовать срез ключей. Конечно, когда вы удаляете пару, вы также должны удалить ее и из среза.

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

Оберните эту новую функциональность (карта + срез ключей) в новый тип и предоставьте методы для него, а также спрячьте карту и срез. Тогда несоответствие данных не может произойти.

Пример реализации:

type Key int   // Key type
type Value int // Value type

type Map struct {
    m    map[Key]Value
    keys []Key
}

func New() *Map {
    return &Map{m: make(map[Key]Value)}
}

func (m *Map) Set(k Key, v Value) {
    if _, ok := m.m[k]; !ok {
        m.keys = append(m.keys, k)
    }
    m.m[k] = v
}

func (m *Map) Range() {
    for _, k := range m.keys {
        fmt.Println(m.m[k])
    }
}

Используй это:

m := New()
m.Set(1, 11)
m.Set(2, 22)
m.Range()

Попробуйте это на игровой площадке Go.

С помощью упаковщика значений, реализующего связанный список

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

Например, если вы хотите карту, как map[Key]Value:

type valueWrapper struct {
    value Value
    next  *Key // Next key
}

Всякий раз, когда вы добавляете пару на карту, вы устанавливаете valueWrapper в качестве значения, и вы должны связать это с предыдущей (последней) парой. Чтобы связать, вы должны установить next поле последней оболочки, указывающей на этот новый ключ. Чтобы легко реализовать это, рекомендуется также хранить последний ключ (чтобы не искать его).

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

Пример реализации:

type Key int   // Key type
type Value int // Value type

type valueWrapper struct {
    v    Value
    next *Key
}

type Map struct {
    m           map[Key]valueWrapper
    first, last *Key
}

func New() *Map {
    return &Map{m: make(map[Key]valueWrapper)}
}

func (m *Map) Set(k Key, v Value) {
    if _, ok := m.m[k]; !ok && m.last != nil {
        w2 := m.m[*m.last]
        m.m[*m.last] = valueWrapper{w2.v, &k}
    }
    w := valueWrapper{v: v}
    m.m[k] = w
    if m.first == nil {
        m.first = &k
    }
    m.last = &k
}

func (m *Map) Range() {
    for k := m.first; k != nil; {
        w := m.m[*k]
        fmt.Println(w.v)
        k = w.next
    }
}

Используя это то же самое. Попробуйте это на игровой площадке Go.

Примечания: Вы можете изменить несколько вещей по своему вкусу:

Вы можете объявить внутреннюю карту как m map[Key]*valueWrapper и так в Set() Вы можете изменить next поле без необходимости назначения нового valueWrapper,
Вы можете выбрать first а также last поля, которые будут иметь тип *valueWrapper
Вы можете выбрать next быть типом *valueWrapper

сравнение

Подход с дополнительным срезом проще и чище. Но удаление элемента из него может стать медленным, если карта становится большой, так как мы также должны найти ключ в срезе, который "не отсортирован", так что это O(n) сложность.

Подход со связанным списком в значении-обертке может быть легко расширен для поддержки быстрого удаления элементов, даже если карта большая, если вы также добавите prev поле к valueWrapper структура. Так что если вам нужно удалить элемент, вы можете очень быстро найти оболочку (O(1)), обновите предыдущую и следующую обертки (чтобы они указывали друг на друга) и выполните простую delete() операция, это O(1),

Обратите внимание, что удаление в первом решении (со срезом) все еще можно ускорить, используя 1 дополнительную карту, которая будет отображаться от ключа к индексу ключа в срезе (map[Key]int), поэтому операция удаления все еще может быть реализована в O(1)В обмен на большую сложность.

См. Связанный вопрос: Почему Go не может повторять карты в порядке вставки?