Collections & Generics
Escolhendo a estrutura de dados certa em C# -- semantica, complexidade e type safety
Escolha collections por semantica + complexidade:
List<T> para acesso indexado, Dictionary<TKey,TValue> para lookups O(1), Queue<T> para FIFO, Stack<T> para LIFO, e HashSet<T> para unicidade. Generics eliminam boxing e garantem type safety em compile-time. Quando usar cada collection
A escolha da collection correta impacta performance e legibilidade. A regra e: pense na semantica primeiro, depois na complexidade.
| Collection | Semantica | Estrutura interna | Quando usar |
|---|---|---|---|
| Array | Tamanho fixo, indexado | Bloco contiguo na memoria | Tamanho conhecido em compile-time, performance critica |
| List<T> | Tamanho dinamico, indexado | Array redimensionavel (dobra capacidade) | Colecao geral mais comum |
| Dictionary<TKey,TValue> | Mapeamento chave-valor | Hash table com buckets | Lookups por chave, cache, indice |
| HashSet<T> | Conjunto unico (sem duplicatas) | Hash table (so chaves) | Verificar existencia, eliminar duplicatas |
| Queue<T> | FIFO (First-In, First-Out) | Circular array redimensionavel | Filas de processamento, BFS |
| Stack<T> | LIFO (Last-In, First-Out) | Array redimensionavel | Undo, DFS, parsing de expressoes |
| SortedDictionary<K,V> | Chave-valor ordenado | Red-black tree | Iteracao em ordem, range queries |
| LinkedList<T> | Insercao/remocao O(1) em qualquer posicao | Doubly-linked nodes | Raramente -- List<T> e melhor por cache friendliness |
Generics -- por que importam
Sem Generics (boxing)
// Sem generics (ArrayList) -- boxing de value types
var list = new ArrayList();
list.Add(42); // int -> object (BOX: alocacao no heap)
int val = (int)list[0]; // object -> int (UNBOX: cast)
ArrayList armazena object. Value types sofrem boxing (alocacao extra no heap) e unboxing (cast) -- lento e sem type safety.
Com Generics (zero boxing)
// Com generics (List<T>) -- zero boxing
var list = new List<int>();
list.Add(42); // int direto, sem alocacao extra
int val = list[0]; // int direto, sem cast
List<int> armazena int diretamente. Zero boxing, type safety em compile-time, melhor performance.
Constraints de Generics
// Constraints restringem quais tipos T pode ser
public T Max<T>(T a, T b) where T : IComparable<T>
=> a.CompareTo(b) >= 0 ? a : b;
// Multiplas constraints
public T CreateAndInit<T>(string name)
where T : class, IEntity, new()
{
var item = new T(); // new() permite instanciar
item.Name = name; // IEntity garante a propriedade
return item;
}
| Constraint | Significado |
|---|---|
where T : class | T deve ser reference type |
where T : struct | T deve ser value type (non-nullable) |
where T : new() | T deve ter construtor sem parametros |
where T : IComparable<T> | T deve implementar a interface |
where T : unmanaged | T deve ser unmanaged type (blittable) |
where T : notnull | T nao pode ser null |
Variancia -- Covariance e Contravariance
// Covariance (out T) -- pode retornar tipo mais derivado
IEnumerable<Animal> animals = new List<Dog>(); // OK: Dog : Animal
// Contravariance (in T) -- pode aceitar tipo mais base
IComparer<Dog> dogComparer = Comparer<Animal>.Default; // OK
// Invariante -- nem out nem in
// List<Animal> animals = new List<Dog>(); // ERRO! List<T> e invariante
IEnumerable<out T> e covariante (read-only, pode atribuir derivado a base). IComparer<in T> e contravariante (input-only, pode atribuir base a derivado).
Por que usar generics em vez de ArrayList?
Tres razoes: (1) Type safety em compile-time -- erros de tipo sao pegos antes de rodar. (2) Zero boxing para value types -- ArrayList faz box/unbox a cada operacao. (3) Performance -- menos alocacoes, menos pressao no GC, e o JIT pode otimizar melhor com tipos concretos.