Skip to content

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 ​

SintaxeDescriçã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étodoAssinaturaRetornaDescrição
set(K, V) => voidvoidInsere ou substitui a entrada para key
get(K) => V?V?Valor para key, ou nenhum valor quando ausente
has(K) => booleanbooleanSe key está presente
delete(K) => booleanbooleanRemove 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() => usizeusizeNúmero de entradas
isEmpty() => booleanbooleanSe o mapa está vazio
clear() => voidvoidRemove todas as entradas

Complexidade ​

OperaçãoComplexidade Temporal
setO(log n)
get / hasO(log n)
deleteO(log n)
min / maxO(log n)
len / isEmptyO(1)
clearO(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
};