SortedMap
SortedMap<K, V> é um mapa ordenado de chave → valor implementado sobre uma árvore binária de busca balanceada. Ele mantém cada entrada ordenada pela chave. O handle nativo é liberado automaticamente quando a variável sai de escopo.
Construção
| Sintaxe | Descrição |
|---|---|
SortedMap<K, V>() | Cria um novo mapa ordenado vazio |
K pode ser qualquer tipo inteiro, qualquer tipo de ponto flutuante, boolean ou string. V pode ser qualquer tipo.
Métodos
| Método | Assinatura | Retorna | Descrição |
|---|---|---|---|
set | (K, V) => void | void | Insere ou substitui a entrada para key |
get | (K) => V? | V? | Valor para key, ou nenhum valor quando ausente |
has | (K) => boolean | boolean | Se key está presente |
delete | (K) => boolean | boolean | Remove a entrada para key; retorna true quando ela estava presente |
min | () => K? | K? | Menor chave, ou nenhum valor quando vazio |
max | () => K? | K? | Maior chave, ou nenhum valor quando vazio |
len | () => usize | usize | Número de entradas |
isEmpty | () => boolean | boolean | Se o mapa está vazio |
clear | () => void | void | Remove todas as entradas |
Complexidade
| Operação | Complexidade Temporal |
|---|---|
set | O(log n) |
get / has | O(log n) |
delete | O(log n) |
min / max | O(log n) |
len / isEmpty | O(1) |
clear | O(n) |
A árvore permanece balanceada, então toda busca, inserção e remoção é logarítmica independentemente da ordem de inserção.
Exemplos
Exemplo completo
tyrus
import { SortedMap } from "tyrus:algorithm";
const main = (): void => {
const m = SortedMap<i32, string>();
m.set(3, "c");
m.set(1, "a");
m.set(2, "b");
m.set(2, "B");
print(m.len()); // 3 (the entry for key 2 was replaced)
print(m.has(2)); // true
print(m.get(2) ?? "none"); // "B"
print(m.min() ?? 0); // 1
print(m.max() ?? 0); // 3
m.delete(2);
print(m.has(2)); // false
print(m.isEmpty()); // false
m.clear();
print(m.isEmpty()); // true
print(m.len()); // 0
};Chaves de string
tyrus
import { SortedMap } from "tyrus:algorithm";
const main = (): void => {
const m = SortedMap<string, i32>();
m.set("banana", 2);
m.set("apple", 1);
m.set("cherry", 3);
print(m.min() ?? "none"); // "apple"
print(m.max() ?? "none"); // "cherry"
print(m.get("apple") ?? 0); // 1
};