Capítulo 12 15 min de leitura

Vector\<T>

Vector<T> é um array crescente com posse sobre T. Ele mantém um buffer no heap que dobra de tamanho sempre que fica cheio: o acesso a elementos é O(1) e push é amortizado O(1). O vector chama diretamente malloc/free do libc e não é gerenciado pelo auto-drop do Glide, portanto você deve liberá-lo explicitamente com free() — combine-o com defer para tornar vazamentos impossíveis.

Importação

Nenhuma importação necessária — Vector<T> é embutido.

A struct

pub struct Vector<T> {
    data: *T,        // buffer no heap; null enquanto cap == 0
    len: i32,        // número de elementos inicializados (<= cap)
    cap: i32,        // tamanho da alocação em elementos (potência de dois quando não-zero)
    is_arena: bool,  // true quando o buffer foi alocado em arena (caminho do LSP)
}

Todos os quatro campos são privados; interaja com o vector apenas por meio de seus métodos.

Construção

Função	Assinatura	Descrição
`new`	`fn new() -> *Vector<T>`	Vector vazio sem alocação. O primeiro `push` aloca.
`with_cap`	`fn with_cap(cap: i32) -> *Vector<T>`	Vector vazio pré-dimensionado para comportar pelo menos `cap` elementos sem realocar.

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push(10);
    v.push(20);

    let w: *Vector<i32> = Vector::with_cap(64);
    defer w.free();
    for let i: i32 = 0; i < 64; i++ { w.push(i); }
    println!(w.len());   // 64
    return 0;
}

Acesso a elementos e mutação

Método	Assinatura	Descrição
`push`	`fn push(self: *Vector<T>, x: T)`	Adiciona `x` ao final. Realoca (capacidade dobra) quando cheio; amortizado O(1).
`pop`	`fn pop(self: *Vector<T>) -> T`	Remove e retorna o último elemento. Comportamento indefinido se vazio — verifique com `is_empty()` antes.
`get`	`fn get(self: *Vector<T>, i: i32) -> T`	Lê o elemento `i`. Sem verificação de limites.
`set`	`fn set(self: *Vector<T>, i: i32, x: T)`	Substitui o elemento `i`. Sem verificação de limites.
`first`	`fn first(self: *Vector<T>) -> T`	Primeiro elemento. Comportamento indefinido se vazio.
`last`	`fn last(self: *Vector<T>) -> T`	Último elemento. Comportamento indefinido se vazio.
`swap`	`fn swap(self: *Vector<T>, i: i32, j: i32)`	Troca os elementos nas posições `i` e `j` no lugar.
`swap_remove`	`fn swap_remove(self: *Vector<T>, i: i32) -> T`	Remove e retorna o elemento `i` em O(1) trocando-o com o último; reordena os elementos restantes.
`reverse`	`fn reverse(self: *Vector<T>)`	Inverte os elementos no lugar. O(n).

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push(10);
    v.push(20);
    v.push(30);

    println!(v.get(0));       // 10
    v.set(1, 99);
    println!(v.get(1));       // 99
    println!(v.first());      // 10
    println!(v.last());       // 30

    let last: i32 = v.pop();  // 30
    println!(last);           // 30
    println!(v.len());        // 2
    return 0;
}

swap, swap_remove e reverse reorganizam no lugar:

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(10, 20, 30, 40);

    v.swap(0, 3);                         // [40, 20, 30, 10]
    let removed: i32 = v.swap_remove(1);  // remove 20 -> [40, 10, 30]
    println!(removed);                    // 20
    v.reverse();                          // [30, 10, 40]
    println!(v.first(), v.last());        // 30 40
    return 0;
}

Tamanho e tempo de vida

Método	Assinatura	Descrição
`len`	`fn len(self: *Vector<T>) -> i32`	Número de elementos inicializados.
`is_empty`	`fn is_empty(self: *Vector<T>) -> bool`	`true` quando `len() == 0`.
`truncate`	`fn truncate(self: *Vector<T>, n: i32)`	Encurta para no máximo `n` elementos. Sem efeito se já for mais curto; a capacidade não é reduzida.
`clear`	`fn clear(self: *Vector<T>)`	Remove todos os elementos (`len` → 0). A capacidade é preservada.
`extend`	`fn extend(self: Vector<T>, other: Vector<T>)`	Adiciona todos os elementos de `other`; `other` é deixado intacto.
`free`	`fn free(self: *Vector<T>)`	Libera o buffer e a struct. O ponteiro fica inválido após isso.

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(10, 20, 30, 40);

    v.truncate(2);            // [10, 20] — capacidade inalterada
    println!(v.len());        // 2

    let other: *Vector<i32> = Vector::new();
    defer other.free();
    other.push_all!(7, 8);
    v.extend(other);          // v agora é [10, 20, 7, 8]; other inalterado
    println!(v.len());        // 4
    println!(other.len());    // 2

    v.clear();
    println!(v.is_empty());   // true
    return 0;
}

A macro `push_all!`

macro push_all!($($x:expr),*) {
    $( self.push($x); )*
}

Adiciona cada elemento passado. As três formas de chamada são equivalentes:

v.push_all!(1, 2, 3);
Vector::push_all!(v, 4, 5);
Vector::new().push_all!(7, 8, 9);

O builtin `vec_of!`

vec_of!(a, b, c) constrói e retorna um *Vector<T> em uma única expressão — o tipo do elemento T é inferido a partir do primeiro argumento. É um builtin do compilador, então está disponível em qualquer lugar sem import:

let v: *Vector<i32> = vec_of!(10, 20, 30);
defer v.free();

let names = vec_of!("alice", "bob");   // *Vector<string> inferido

Por ser uma expressão, funciona em qualquer lugar que um valor funciona — um inicializador de let, um argumento de função ou um return:

fn soma(v: *Vector<i32>) -> i32 { /* … */ }

let total = soma(vec_of!(1, 2, 3, 4, 5));   // 15

Todos os elementos devem ser do mesmo tipo; uma chamada mista (vec_of!(1, "dois")) ou vazia (vec_of!(), que não tem como inferir T — use Vector::new()) é rejeitada em tempo de compilação com um erro claro.

Iteração

`iter` / `VecIter<T>`

fn iter(self: *Vector<T>) -> *VecIter<T>

pub struct VecIter<T> {
    vec: *Vector<T>,
    idx: i32,
}

impl<T> VecIter<T> {
    pub fn next(self: *VecIter<T>) -> ?T
}

iter() constrói um iterador que produz cada elemento por valor; next() retorna some(x) até o fim, depois none(). O iterador toma empréstimo do buffer do vector durante a travessia — mutar o vector no meio da iteração é comportamento indefinido.

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(10, 20, 30);

    let it: *VecIter<i32> = v.iter();
    let mut total: i32 = 0;
    while true {
        match it.next() {
            some(x) => { total = total + x; },
            none()  => break,
        }
    }
    println!(total);   // 60
    return 0;
}

Combinadores funcionais

Esses métodos são genéricos sobre qualquer Vector<T>. Os que transformam (map/filter/take/skip/take_while/skip_while) retornam um novo *Vector que você possui e deve liberar com free.

Método	Assinatura	Descrição
`map`	`fn map<U>(self: Vector<T>, f: fn(T) -> U) -> Vector<U>`	Aplica `f` a cada elemento; retorna um novo vector.
`filter`	`fn filter(self: Vector<T>, p: fn(T) -> bool) -> Vector<T>`	Mantém apenas os elementos onde `p` é verdadeiro.
`fold`	`fn fold<U>(self: *Vector<T>, init: U, f: fn(U, T) -> U) -> U`	Reduz com acumulador; `f(acc, item)` retorna o novo acumulador.
`take`	`fn take(self: Vector<T>, n: i32) -> Vector<T>`	Os primeiros `n` elementos (limitado ao comprimento).
`skip`	`fn skip(self: Vector<T>, n: i32) -> Vector<T>`	Todos exceto os primeiros `n` elementos.
`take_while`	`fn take_while(self: Vector<T>, p: fn(T) -> bool) -> Vector<T>`	Elementos até `p` retornar falso (então para).
`skip_while`	`fn skip_while(self: Vector<T>, p: fn(T) -> bool) -> Vector<T>`	Descarta os elementos iniciais enquanto `p` é verdadeiro; mantém o restante a partir do primeiro falso.
`any`	`fn any(self: *Vector<T>, p: fn(T) -> bool) -> bool`	`true` se algum elemento satisfaz a condição. Curto-circuita.
`all`	`fn all(self: *Vector<T>, p: fn(T) -> bool) -> bool`	`true` se todos satisfazem. Vector vazio → `true` (verdade vacuosa).
`find`	`fn find(self: *Vector<T>, p: fn(T) -> bool) -> ?T`	Primeiro elemento que satisfaz a condição, ou `none()`.

map / filter / fold

fn double(x: i32) -> i32  { return x * 2; }
fn is_even(x: i32) -> bool { return x % 2 == 0; }
fn add(acc: i32, x: i32) -> i32 { return acc + x; }

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(1, 2, 3, 4, 5);

    // Vincule cada etapa para que cada resultado com posse seja liberado.
    let doubled: *Vector<i32> = v.map(double);
    defer doubled.free();                 // [2, 4, 6, 8, 10]
    let evens: *Vector<i32> = doubled.filter(is_even);
    defer evens.free();                   // [2, 4, 6, 8, 10]
    println!(evens.fold(0, add));         // 30

    println!(v.any(is_even));             // true
    println!(v.all(is_even));             // false

    match v.find(is_even) {
        some(x) => println!(x),           // 2
        none()  => println!("none"),
    }
    return 0;
}

fold é o redutor geral — init semente o acumulador e o tipo de resultado U pode diferir do tipo do elemento. map<U> também muda o tipo do elemento (por exemplo, Vector<i32> → Vector<string>).

take / skip / take_while / skip_while

take/skip fatiam por contagem; take_while/skip_while fatiam por predicado. Todos os quatro retornam um novo vector com posse.

fn lt5(x: i32) -> bool { return x < 5; }

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(1, 3, 7, 2, 9);

    let head: *Vector<i32> = v.take(3);
    defer head.free();                    // [1, 3, 7]

    let clamped: *Vector<i32> = v.take(99);
    defer clamped.free();
    println!(clamped.len());              // 5 (limitado ao comprimento)

    let tail: *Vector<i32> = v.skip(2);
    defer tail.free();                    // [7, 2, 9]

    let tw: *Vector<i32> = v.take_while(lt5);
    defer tw.free();                      // [1, 3]   (para no primeiro >= 5)

    let sw: *Vector<i32> = v.skip_while(lt5);
    defer sw.free();                      // [7, 2, 9] (mantém tudo a partir do primeiro >= 5)
    println!(tw.len(), sw.len());         // 2 3
    return 0;
}

Métodos por tipo de elemento

Glide ainda não tem um trait genérico para números/ordenação, portanto redutores que precisam somar ou comparar elementos residem em blocos concretos de impl Vector<T> por tipo de elemento. Eles só estão disponíveis quando T é exatamente o tipo listado.

`Vector<i32>`

Método	Assinatura	Descrição
`sum`	`pub fn sum(self: *Vector<i32>) -> i32`	Soma de todos os elementos. Vazio → `0`.
`max`	`pub fn max(self: *Vector<i32>) -> ?i32`	Maior elemento, ou `none()` se vazio.
`min`	`pub fn min(self: *Vector<i32>) -> ?i32`	Menor elemento, ou `none()` se vazio.

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(3, 7, 2, 9, 4);
    println!(v.sum());                          // 25
    match v.max() { some(x) => println!(x), none() => {}, }  // 9
    match v.min() { some(x) => println!(x), none() => {}, }  // 2
    return 0;
}

`Vector<f64>`

Método	Assinatura	Descrição
`sum`	`pub fn sum(self: *Vector<f64>) -> f64`	Soma de todos os elementos. Vazio → `0.0`.
`max`	`pub fn max(self: *Vector<f64>) -> ?f64`	Maior elemento, ou `none()` se vazio.
`min`	`pub fn min(self: *Vector<f64>) -> ?f64`	Menor elemento, ou `none()` se vazio.
`avg`	`pub fn avg(self: *Vector<f64>) -> ?f64`	Média aritmética, ou `none()` se vazio.

fn main() -> i32 {
    let v: *Vector<f64> = Vector::new();
    defer v.free();
    v.push_all!(2.0, 4.0, 6.0);
    println!(v.sum());                          // 12.0
    match v.avg() { some(x) => println!(x), none() => {}, }  // 4.0
    match v.max() { some(x) => println!(x), none() => {}, }  // 6.0
    match v.min() { some(x) => println!(x), none() => {}, }  // 2.0
    return 0;
}

`Vector<string>`

Método	Assinatura	Descrição
`join`	`pub fn join(self: *Vector<string>, sep: string) -> string`	Concatena os elementos com `sep` entre eles. Vazio → `""`.
`concat`	`pub fn concat(self: *Vector<string>) -> string`	Concatena os elementos sem separador. Vazio → `""`.
`max`	`pub fn max(self: *Vector<string>) -> ?string`	Elemento lexicograficamente maior, ou `none()`.
`min`	`pub fn min(self: *Vector<string>) -> ?string`	Elemento lexicograficamente menor, ou `none()`.

fn main() -> i32 {
    let v: *Vector<string> = Vector::new();
    defer v.free();
    v.push_all!("apple", "banana", "cherry");
    println!(v.join(", "));   // apple, banana, cherry
    println!(v.concat());     // applebananacherry
    match v.max() { some(s) => println!(s), none() => {}, }  // cherry
    match v.min() { some(s) => println!(s), none() => {}, }  // apple
    return 0;
}

`Vector<bool>`

Método	Assinatura	Descrição
`count_true`	`pub fn count_true(self: *Vector<bool>) -> i32`	Número de elementos `true`.
`count_false`	`pub fn count_false(self: *Vector<bool>) -> i32`	Número de elementos `false`.
`all_true`	`pub fn all_true(self: *Vector<bool>) -> bool`	`true` se todo elemento é `true`. Vazio → `true` (verdade vacuosa).
`any_true`	`pub fn any_true(self: *Vector<bool>) -> bool`	`true` se pelo menos um elemento é `true`. Vazio → `false`.

fn main() -> i32 {
    let v: *Vector<bool> = Vector::new();
    defer v.free();
    v.push_all!(true, false, true, true);
    println!(v.count_true());    // 3
    println!(v.count_false());   // 1
    println!(v.all_true());      // false
    println!(v.any_true());      // true
    return 0;
}

Convenções para vector vazio

Redutores que não conseguem produzir um valor sensato em um vector vazio retornam ?T; os aditivos/booleanos usam identidades fixas. Memorize estas para evitar surpresas:

Chamada	Resultado com vazio
`sum` (i32/f64)	`0` / `0.0`
`max` / `min` / `avg`	`none()`
`all` (combinador) / `all_true`	`true` (verdade vacuosa)
`any` (combinador) / `any_true`	`false`
`count_true` / `count_false`	`0`
`join` / `concat`	`""`

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    println!(v.sum());        // 0
    match v.max() {
        some(x) => println!(x),
        none()  => println!("empty max"),   // executado
    }

    let b: *Vector<bool> = Vector::new();
    defer b.free();
    println!(b.all_true());   // true  (verdade vacuosa)
    println!(b.any_true());   // false
    return 0;
}

Veja também

Strings — concat/cmp/split usados por Vector<string>.
Prelude — some/none e o tipo Option ?T que

find/max/min/avg retornam.

Importação

A struct

Construção

Acesso a elementos e mutação

Tamanho e tempo de vida

A macro push_all!

O builtin vec_of!

Iteração

iter / VecIter<T>

Combinadores funcionais

map / filter / fold

take / skip / take_while / skip_while

Métodos por tipo de elemento

Vector<i32>

Vector<f64>

Vector<string>

Vector<bool>

Convenções para vector vazio

Veja também

A macro `push_all!`

O builtin `vec_of!`

`iter` / `VecIter<T>`

`Vector<i32>`

`Vector<f64>`

`Vector<string>`

`Vector<bool>`