Estruturas de Dados Genéricas: Conjuntos, Filas, Mapas

Q: Por que map[T]struct{} para conjuntos?

Valores de struct vazios não ocupam bytes. A associação é O(1) em média com boas propriedades de hash em T.

Q: Filas devem ser genéricas em APIs públicas?

Frequentemente mantenha filas internas. Exporte o comportamento (processador em lote), não os tipos Queue[T], a menos que a biblioteca seja um kit de estruturas de dados.

Q: Como iterar um Conjunto?

for k := range s no padrão de mapa subjacente. Adicione um método Values() retornando []T se os chamadores precisarem de slices.

Q: Conjuntos genéricos são thread-safe?

Não - mapas padrão não são seguros para escritas concorrentes. Adicione um wrapper de mutex ou use mapas concorrentes.

Q: Posso serializar Set[T] para JSON?

Converta para []T para marshaling. map[T]struct{} não é marshaled em JSON como um array por padrão.

Q: Fila vs canal?

Canais sincronizam goroutines. Filas genéricas servem para processamento em lote na memória dentro de uma goroutine ou com bloqueio externo.

Q: Quantos parâmetros de tipo para mapas?

K comparable e V any cobrem a maioria dos auxiliares. Adicione um terceiro parâmetro apenas para pipelines de transformação.

Q: Conjunto precisa de ponteiros?

Não para valores comparáveis pequenos. Use ponteiros como elementos quando os valores forem grandes e a identidade importar.

Q: E quanto a conjuntos ordenados?

Use um mapa mais um cache de slice ordenado, ou estruturas de tree de pacotes de terceiros. Genéricos não implicam ordenação.

Q: Quando a geração de código ainda é melhor?

Dezenas de instanciações em alvos embarcados minúsculos onde o tamanho do binário domina. Meça antes de escolher.

Genéricos permitem que você envie conjuntos, filas e auxiliares de mapa tipados uma vez por módulo em vez de manter StringSet, IntSet e saídas do go generate.

Resumo

Um conjunto genérico é geralmente map[T]struct{} com chaves comparable.

Filas envolvem slices com índices de cabeça/cauda ou usam buffers circulares para capacidade fixa.

Auxiliares de mapa centralizam a lógica segura de obter-ou-padrão, copiar e transformar com dois parâmetros de tipo K e V.

Mantenha as APIs de contêiner exportadas pequenas e documente o comportamento do valor zero.

Receita

Cartão de receita de referência rápida - pronto para copiar e colar.

type Set[T comparable] map[T]struct{}
 
func NewSet[T comparable](vals ...T) Set[T] {
    s := make(Set[T], len(vals))
    for _, v := range vals {
        s.Add(v)
    }
    return s
}
 
func (s Set[T]) Add(v T)     { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool { _, ok := s[v]; return ok }

Quando usar isso:

Padrões duplicados de map[string]struct{} entre pacotes.
Filas de trabalho FIFO dentro de workers sem conversões de interface{}.
Bibliotecas internas compartilhadas por manipuladores HTTP e serviços gRPC.

Exemplo de Trabalho

package main
 
import (
    "fmt"
)
 
type Set[T comparable] map[T]struct{}
 
func (s Set[T]) Add(v T) { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool {
    _, ok := s[v]
    return ok
}
 
type Queue[T any] struct {
    buf []T
}
 
func (q *Queue[T]) Enqueue(v T) { q.buf = append(q.buf, v) }
 
func (q *Queue[T]) Dequeue() (T, bool) {
    if len(q.buf) == 0 {
        var zero T
        return zero, false
    }
    v := q.buf[0]
    q.buf = q.buf[1:]
    return v, true
}
 
func GetOr[K comparable, V any](m map[K]V, k K, def V) V {
    if v, ok := m[k]; ok {
        return v
    }
    return def
}
 
func main() {
    s := make(Set[string])
    s.Add("go")
    fmt.Println(s.Has("go"), s.Has("rust"))
 
    var q Queue[int]
    q.Enqueue(1)
    q.Enqueue(2)
    v, _ := q.Dequeue()
    fmt.Println(v)
 
    m := map[string]int{"a": 1}
    fmt.Println(GetOr(m, "b", 0))
}

O que isso demonstra:

Set[T] requer comparable para chaves de mapa.
Queue[T] usa any porque os elementos são apenas armazenados e movidos.
GetOr separa a comparabilidade da chave da flexibilidade do tipo de valor.

Mergulho Profundo

Como Funciona

Tipos nomeados genéricos (type Set[T comparable] map[T]struct{}) criam um tipo nomeado distinto para cada instanciação.
Métodos se anexam ao tipo genérico e compartilham seus parâmetros.
Nos bastidores, o compilador monomorfiza cada instanciação que você usa no grafo de pacotes.
Valores zero são utilizáveis: var q Queue[int] é uma fila vazia; make(Set[string]) aloca o mapa.

Padrões de Contêiner

Estrutura	Restrição	Suporte	Notas
Conjunto	`comparable`	`map[T]struct{}`	Valores de struct vazios não usam memória de valor extra
Fila (simples)	`any`	Slice com re-slicing	Enqueue O(1) amortizado; Dequeue desloca ou copia a cabeça
Fila (circular)	`any`	`[]T` fixo + índices	Melhor para profundidade máxima conhecida
Pilha	`any`	Slice	Igual a LIFO append/pop
Auxiliar de mapa	`K comparable`, `V any`	Mapa do chamador	Sem propriedade - funções puras

Notas de Go

// Fila circular evita dequeue O(n) de reslicing de slice em escala
type RingQueue[T any] struct {
    buf  []T
    head int
    tail int
    n    int
}
 
func NewRingQueue[T any](cap int) *RingQueue[T] {
    return &RingQueue[T]{buf: make([]T, cap)}
}

Para conjuntos concorrentes, envolva com sync.Mutex ou use sync.Map quando as chaves forem any e os padrões de contenção se encaixarem.
A serialização JSON de conjuntos genéricos geralmente requer MarshalJSON personalizado por instanciação ou funções auxiliares - mapas são serializados corretamente quando as chaves são strings.
Considere container/list apenas quando precisar de links intrusivos; genéricos mais slices cobrem a maioria das filas de serviço.

Armadilhas

Dequeue com slice buf = buf[1:] - Mantém o array de suporte vivo, vazando memória em filas de longa duração. Correção: use buffer circular ou cópia periódica quando len << cap.
Conjunto como mapa sem inicialização - O valor zero Set[T] é um mapa nil; escritas causam pânico. Correção: make(Set[T]) ou construtor.
Elemento não comparável no conjunto - Chaves do tipo slice falham na compilação. Correção: crie um hash para o tipo da chave ou use map[uint64]struct{}.
Exportar contêineres genéricos muito cedo - Bloqueio de API entre módulos. Correção: mantenha não exportado até que a forma se estabilize.
Cópia profunda omitida - Auxiliares map[K]*V copiam ponteiros, não os dados apontados. Correção: documente semânticas rasas ou clone valores.
Tamanho TinyGo/WASM - Muitas instanciações incham o WASM. Correção: limite as instanciações ou use caminhos não genéricos em alvos pequenos.

Alternativas

Alternativa	Usar Quando	Não Usar Quando
`go generate` por tipo	Controle máximo, sem sintaxe de colchetes na API	Poucos tipos, equipe prefere genéricos
Apenas `map[string]struct{}`	Conjunto de string único	Múltiplos tipos de elementos
`container/heap`	Semântica de fila de prioridade	FIFO simples
Fila de buffer de canal	Passagem de goroutine	Processamento em lote single-threaded

FAQs

Por que map[T]struct{} para conjuntos?

Valores de struct vazios não ocupam bytes.

A associação é O(1) em média com boas propriedades de hash em T.

Filas devem ser genéricas em APIs públicas?

Frequentemente mantenha filas internas.

Exporte o comportamento (processador em lote), não os tipos Queue[T], a menos que a biblioteca seja um kit de estruturas de dados.

Como iterar um Conjunto?

for k := range s no padrão de mapa subjacente.

Adicione um método Values() retornando []T se os chamadores precisarem de slices.

Conjuntos genéricos são thread-safe?

Não - mapas padrão não são seguros para escritas concorrentes.

Adicione um wrapper de mutex ou use mapas concorrentes.

Posso serializar Set[T] para JSON?

Converta para []T para marshaling.

map[T]struct{} não é marshaled em JSON como um array por padrão.

Fila vs canal?

Canais sincronizam goroutines.

Filas genéricas servem para processamento em lote na memória dentro de uma goroutine ou com bloqueio externo.

Quantos parâmetros de tipo para mapas?

K comparable e V any cobrem a maioria dos auxiliares.

Adicione um terceiro parâmetro apenas para pipelines de transformação.

Conjunto precisa de ponteiros?

Não para valores comparáveis pequenos.

Use ponteiros como elementos quando os valores forem grandes e a identidade importar.

E quanto a conjuntos ordenados?

Use um mapa mais um cache de slice ordenado, ou estruturas de tree de pacotes de terceiros.

Genéricos não implicam ordenação.

Quando a geração de código ainda é melhor?

Dezenas de instanciações em alvos embarcados minúsculos onde o tamanho do binário domina.

Meça antes de escolher.

Posso incorporar Set em outros genéricos?

Sim - componha Set[T] dentro de tipos no estilo Graph[N comparable].

Observe o tempo de compilação e o tamanho do binário.

Como testar contêineres genéricos?

Testes de tabela com múltiplas instanciações (Set[int], Set[string]) no mesmo arquivo de teste de pacote.

Relacionados

Conjuntos de Tipos e a Restrição comparable - requisitos de chave de conjunto
Noções Básicas de Genéricos - exemplo de pilha
Algoritmos Genéricos: Pacotes slices, maps e cmp - auxiliares de cópia de mapa
Implicações de Desempenho dos Genéricos - custo de instanciação
Quando Evitar Genéricos em APIs Go - orientação de exportação

Versões do Stack: Esta página foi escrita para Go 1.26.x (padrão GC Green Tea, go fix modernizers - verifique o patch na compilação), chi (última versão - verifique na compilação), gin (última versão - verifique na compilação), echo (última versão - verifique na compilação), google.golang.org/grpc (última versão - verifique na compilação), sigs.k8s.io/controller-runtime (última versão - verifique na compilação), kubebuilder (última versão - verifique na compilação), tinygo (última versão - verifique os alvos de placa na compilação), wazero (última versão - verifique na compilação) e golangci-lint (última versão - verifique o conjunto de linters na compilação).

Resumo

Um conjunto genérico é geralmente map[T]struct{} com chaves comparable.

Filas envolvem slices com índices de cabeça/cauda ou usam buffers circulares para capacidade fixa.

Auxiliares de mapa centralizam a lógica segura de obter-ou-padrão, copiar e transformar com dois parâmetros de tipo K e V.

Mantenha as APIs de contêiner exportadas pequenas e documente o comportamento do valor zero.

Receita

Cartão de receita de referência rápida - pronto para copiar e colar.

type Set[T comparable] map[T]struct{}
 
func NewSet[T comparable](vals ...T) Set[T] {
    s := make(Set[T], len(vals))
    for _, v := range vals {
        s.Add(v)
    }
    return s
}
 
func (s Set[T]) Add(v T)     { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool { _, ok := s[v]; return ok }

Quando usar isso:

Padrões duplicados de map[string]struct{} entre pacotes.
Filas de trabalho FIFO dentro de workers sem conversões de interface{}.
Bibliotecas internas compartilhadas por manipuladores HTTP e serviços gRPC.

Exemplo de Trabalho

package main
 
import (
    "fmt"
)
 
type Set[T comparable] map[T]struct{}
 
func (s Set[T]) Add(v T) { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool {
    _, ok := s[v]
    return ok
}
 
type Queue[T any] struct {
    buf []T
}
 
func (q *Queue[T]) Enqueue(v T) { q.buf = append(q.buf, v) }
 
func (q *Queue[T]) Dequeue() (T, bool) {
    if len(q.buf) == 0 {
        var zero T
        return zero, false
    }
    v := q.buf[0]
    q.buf = q.buf[1:]
    return v, true
}
 
func GetOr[K comparable, V any](m map[K]V, k K, def V) V {
    if v, ok := m[k]; ok {
        return v
    }
    return def
}
 
func main() {
    s := make(Set[string])
    s.Add("go")
    fmt.Println(s.Has("go"), s.Has("rust"))
 
    var q Queue[int]
    q.Enqueue(1)
    q.Enqueue(2)
    v, _ := q.Dequeue()
    fmt.Println(v)
 
    m := map[string]int{"a": 1}
    fmt.Println(GetOr(m, "b", 0))
}

O que isso demonstra:

Set[T] requer comparable para chaves de mapa.
Queue[T] usa any porque os elementos são apenas armazenados e movidos.
GetOr separa a comparabilidade da chave da flexibilidade do tipo de valor.

Mergulho Profundo

Como Funciona

Tipos nomeados genéricos (type Set[T comparable] map[T]struct{}) criam um tipo nomeado distinto para cada instanciação.
Métodos se anexam ao tipo genérico e compartilham seus parâmetros.
Nos bastidores, o compilador monomorfiza cada instanciação que você usa no grafo de pacotes.
Valores zero são utilizáveis: var q Queue[int] é uma fila vazia; make(Set[string]) aloca o mapa.

Padrões de Contêiner

Estrutura	Restrição	Suporte	Notas
Conjunto	`comparable`	`map[T]struct{}`	Valores de struct vazios não usam memória de valor extra
Fila (simples)	`any`	Slice com re-slicing	Enqueue O(1) amortizado; Dequeue desloca ou copia a cabeça
Fila (circular)	`any`	`[]T` fixo + índices	Melhor para profundidade máxima conhecida
Pilha	`any`	Slice	Igual a LIFO append/pop
Auxiliar de mapa	`K comparable`, `V any`	Mapa do chamador	Sem propriedade - funções puras

Notas de Go

// Fila circular evita dequeue O(n) de reslicing de slice em escala
type RingQueue[T any] struct {
    buf  []T
    head int
    tail int
    n    int
}
 
func NewRingQueue[T any](cap int) *RingQueue[T] {
    return &RingQueue[T]{buf: make([]T, cap)}
}

Para conjuntos concorrentes, envolva com sync.Mutex ou use sync.Map quando as chaves forem any e os padrões de contenção se encaixarem.
A serialização JSON de conjuntos genéricos geralmente requer MarshalJSON personalizado por instanciação ou funções auxiliares - mapas são serializados corretamente quando as chaves são strings.
Considere container/list apenas quando precisar de links intrusivos; genéricos mais slices cobrem a maioria das filas de serviço.

Armadilhas

Dequeue com slice buf = buf[1:] - Mantém o array de suporte vivo, vazando memória em filas de longa duração. Correção: use buffer circular ou cópia periódica quando len << cap.
Conjunto como mapa sem inicialização - O valor zero Set[T] é um mapa nil; escritas causam pânico. Correção: make(Set[T]) ou construtor.
Elemento não comparável no conjunto - Chaves do tipo slice falham na compilação. Correção: crie um hash para o tipo da chave ou use map[uint64]struct{}.
Exportar contêineres genéricos muito cedo - Bloqueio de API entre módulos. Correção: mantenha não exportado até que a forma se estabilize.
Cópia profunda omitida - Auxiliares map[K]*V copiam ponteiros, não os dados apontados. Correção: documente semânticas rasas ou clone valores.
Tamanho TinyGo/WASM - Muitas instanciações incham o WASM. Correção: limite as instanciações ou use caminhos não genéricos em alvos pequenos.

Alternativas

Alternativa	Usar Quando	Não Usar Quando
`go generate` por tipo	Controle máximo, sem sintaxe de colchetes na API	Poucos tipos, equipe prefere genéricos
Apenas `map[string]struct{}`	Conjunto de string único	Múltiplos tipos de elementos
`container/heap`	Semântica de fila de prioridade	FIFO simples
Fila de buffer de canal	Passagem de goroutine	Processamento em lote single-threaded

FAQs

Por que map[T]struct{} para conjuntos?

Valores de struct vazios não ocupam bytes.

A associação é O(1) em média com boas propriedades de hash em T.

Filas devem ser genéricas em APIs públicas?

Frequentemente mantenha filas internas.

Exporte o comportamento (processador em lote), não os tipos Queue[T], a menos que a biblioteca seja um kit de estruturas de dados.

Como iterar um Conjunto?

for k := range s no padrão de mapa subjacente.

Adicione um método Values() retornando []T se os chamadores precisarem de slices.

Conjuntos genéricos são thread-safe?

Não - mapas padrão não são seguros para escritas concorrentes.

Adicione um wrapper de mutex ou use mapas concorrentes.

Posso serializar Set[T] para JSON?

Converta para []T para marshaling.

map[T]struct{} não é marshaled em JSON como um array por padrão.

Fila vs canal?

Canais sincronizam goroutines.

Filas genéricas servem para processamento em lote na memória dentro de uma goroutine ou com bloqueio externo.

Quantos parâmetros de tipo para mapas?

K comparable e V any cobrem a maioria dos auxiliares.

Adicione um terceiro parâmetro apenas para pipelines de transformação.

Conjunto precisa de ponteiros?

Não para valores comparáveis pequenos.

Use ponteiros como elementos quando os valores forem grandes e a identidade importar.

E quanto a conjuntos ordenados?

Use um mapa mais um cache de slice ordenado, ou estruturas de tree de pacotes de terceiros.

Genéricos não implicam ordenação.

Quando a geração de código ainda é melhor?

Dezenas de instanciações em alvos embarcados minúsculos onde o tamanho do binário domina.

Meça antes de escolher.

Posso incorporar Set em outros genéricos?

Sim - componha Set[T] dentro de tipos no estilo Graph[N comparable].

Observe o tempo de compilação e o tamanho do binário.

Como testar contêineres genéricos?

Testes de tabela com múltiplas instanciações (Set[int], Set[string]) no mesmo arquivo de teste de pacote.

Relacionados

Conjuntos de Tipos e a Restrição comparable - requisitos de chave de conjunto
Noções Básicas de Genéricos - exemplo de pilha
Algoritmos Genéricos: Pacotes slices, maps e cmp - auxiliares de cópia de mapa
Implicações de Desempenho dos Genéricos - custo de instanciação
Quando Evitar Genéricos em APIs Go - orientação de exportação

Versões do Stack: Esta página foi escrita para Go 1.26.x (padrão GC Green Tea, go fix modernizers - verifique o patch na compilação), chi (última versão - verifique na compilação), gin (última versão - verifique na compilação), echo (última versão - verifique na compilação), google.golang.org/grpc (última versão - verifique na compilação), sigs.k8s.io/controller-runtime (última versão - verifique na compilação), kubebuilder (última versão - verifique na compilação), tinygo (última versão - verifique os alvos de placa na compilação), wazero (última versão - verifique na compilação) e golangci-lint (última versão - verifique o conjunto de linters na compilação).

Estruturas de Dados Genéricas: Conjuntos, Filas, Mapas

Buscar na documentação

Estruturas de Dados Genéricas: Conjuntos, Filas, Mapas