时间轴

2025-10-22

add Vec, others todo

primitive-like collections

基础序列类型，在标准库的顶层模块里，而不是std::collections，在预导入模块里，不用显示导入

Vec

构造

vec![]

用vec宏比较方便，可以在构造时初始化一些值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
macro_rules! vec {
    () => (
        $crate::vec::Vec::new()
    );
    ($elem:expr; $n:expr) => (
        $crate::vec::from_elem($elem, $n)
    );
    ($($x:expr),+ $(,)?) => (
        <[_]>::into_vec(
            // Using the intrinsic produces a dramatic improvement in stack usage for
            // unoptimized programs using this code path to construct large Vecs.
            $crate::boxed::box_new([$($x),+])
        )
    );
}

Examples

1
2
3
4
let v = vec![1, 2, 3];
assert_eq!(v[0], 1);
assert_eq!(v[1], 2);
assert_eq!(v[2], 3);

Vec::new()

1
pub const fn new() -> Vec<T>
  • Constructs a new, empty Vec. The vector will not allocate until elements are pushed onto it.

Examples

1
let mut vec: Vec<i32> = Vec::new();

Vec::with_capacity()

1
pub fn with_capacity(capacity: usize) -> Vec<T>

  • Constructs a new, empty Vec<T> with at least the specified capacity.

  • If capacity is zero, the vector will not allocate.

  • For Vec<T> where T is a zero-sized type, there will be no allocation and the capacity will always be usize::MAX.

Panics

Panics if the new capacity exceeds isize::MAX bytes.

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let mut vec = Vec::with_capacity(10);

// The vector contains no items, even though it has capacity for more
assert_eq!(vec.len(), 0);
assert!(vec.capacity() >= 10);

// These are all done without reallocating...
for i in 0..10 {
    vec.push(i);
}
assert_eq!(vec.len(), 10);
assert!(vec.capacity() >= 10);

// ...but this may make the vector reallocate
vec.push(11);
assert_eq!(vec.len(), 11);
assert!(vec.capacity() >= 11);

// A vector of a zero-sized type will always over-allocate, since no
// allocation is necessary
let vec_units = Vec::<()>::with_capacity(10);
assert_eq!(vec_units.capacity(), usize::MAX);

Vec::from_raw_parts()

1
2
3
4
5
pub unsafe fn from_raw_parts(
    ptr: *mut T,
    length: usize,
    capacity: usize,
) -> Vec<T>

  • Creates a Vec<T> directly from a pointer, a length, and a capacity.

  • This is highly unsafe, due to the number of invariants that aren’t checked:

    • T needs to have the same alignment as what ptr was allocated with.

    • ptr must have been allocated using the global allocator, such as via the alloc::alloc function

      用C的ptr是不安全的，因为Vec在Drop时会调用rust allocator的dealloc，但这个内存是C分配的，不安全

    • length needs to be less than or equal to capacity

    • The first length values must be properly initialized values of type T

    • capacity needs to be the capacity that the pointer was allocated with

    • The allocated size in bytes must be no larger than isize::MAX

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use std::ptr;
use std::mem;

let v = vec![1, 2, 3];

// Prevent running `v`'s destructor so we are in complete control
// of the allocation.
let mut v = mem::ManuallyDrop::new(v);

// Pull out the various important pieces of information about `v`
let p = v.as_mut_ptr();
let len = v.len();
let cap = v.capacity();

unsafe {
    // Overwrite memory with 4, 5, 6
    for i in 0..len {
        ptr::write(p.add(i), 4 + i);
    }

    // Put everything back together into a Vec
    let rebuilt = Vec::from_raw_parts(p, len, cap);
    assert_eq!(rebuilt, [4, 5, 6]);
}

using memory that was allocated else where

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
use std::alloc::{alloc, Layout};

fn main() {
    // 构造一个可以存16个 u32 的内存布局
    let layout = Layout::array::<u32>(16).expect("overflow cannot happen");

    let vec = unsafe {
        // 使用裸分配函数分配内存（返回 *mut u8 指针）
        let mem = alloc(layout).cast::<u32>();
        if mem.is_null() {
            return;
        }
		// 往分配的内存第一个位置写入一个值
        mem.write(1_000_000);
        
	    // 把这块原始内存包装成一个 Vec（长度1，容量16）
        Vec::from_raw_parts(mem, 1, 16)
    };

    assert_eq!(vec, &[1_000_000]);
    assert_eq!(vec.capacity(), 16);
}

属性访问

vec.len

1
pub const fn len(&self) -> usize

返回元素个数

vec.is_empty

1
pub const fn is_empty(&self) -> bool

没有元素就返回真，否则返回false

访问元素

修改元素

vec.resize

1
pub fn resize(&mut self, new_len: usize, value: T)

Resizes the Vec in-place so that len is equal to new_len.

Examples

1
2
3
4
5
6
7
let mut vec = vec!["hello"];
vec.resize(3, "world");
assert_eq!(vec, ["hello", "world", "world"]);

let mut vec = vec!['a', 'b', 'c', 'd'];
vec.resize(2, '_');
assert_eq!(vec, ['a', 'b']);

vec.resize_with

1
2
3
pub fn resize_with<F>(&mut self, new_len: usize, f: F)
where
    F: FnMut() -> T

Resizes the Vec in-place so that len is equal to new_len.

Examples

1
2
3
4
5
6
7
8
let mut vec = vec![1, 2, 3];
vec.resize_with(5, Default::default);
assert_eq!(vec, [1, 2, 3, 0, 0]);

let mut vec = vec![];
let mut p = 1;
vec.resize_with(4, || { p *= 2; p });
assert_eq!(vec, [2, 4, 8, 16]);

插入元素

vec.insert

1
pub fn insert(&mut self, index: usize, element: T)

Inserts an element at position index within the vector, shifting all elements after it to the right.

Panics

Panics if index > len.

Examples

1
2
3
4
5
let mut vec = vec!['a', 'b', 'c'];
vec.insert(1, 'd');
assert_eq!(vec, ['a', 'd', 'b', 'c']);
vec.insert(4, 'e');
assert_eq!(vec, ['a', 'd', 'b', 'c', 'e']);

vec.push

1
pub fn push(&mut self, value: T)

Appends an element to the back of a collection.

Panics

Panics if the new capacity exceeds isize::MAX bytes.

Examples

1
2
3
let mut vec = vec![1, 2];
vec.push(3);
assert_eq!(vec, [1, 2, 3]);

vec.append

1
pub fn append(&mut self, other: &mut Vec<T, A>)

Moves all the elements of other into self, leaving other empty.

Examples

1
2
3
4
5
let mut vec = vec![1, 2, 3];
let mut vec2 = vec![4, 5, 6];
vec.append(&mut vec2);
assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
assert_eq!(vec2, []);

vec.extend_from_slice

1
pub fn extend_from_slice(&mut self, other: &[T])

Clones and appends all elements in a slice to the Vec.

Examples

1
2
3
let mut vec = vec![1];
vec.extend_from_slice(&[2, 3, 4]);
assert_eq!(vec, [1, 2, 3, 4]);

vec.extend_from_within

1
2
3
pub fn extend_from_within<R>(&mut self, src: R)
where
    R: RangeBounds<usize>,

Given a range src, clones a slice of elements in that range and appends it to the end.

src must be a range that can form a valid subslice of the Vec.

Examples

1
2
3
4
5
6
7
8
9
10
11
let mut characters = vec!['a', 'b', 'c', 'd', 'e'];
characters.extend_from_within(2..);
assert_eq!(characters, ['a', 'b', 'c', 'd', 'e', 'c', 'd', 'e']);

let mut numbers = vec![0, 1, 2, 3, 4];
numbers.extend_from_within(..2);
assert_eq!(numbers, [0, 1, 2, 3, 4, 0, 1]);

let mut strings = vec![String::from("hello"), String::from("world"), String::from("!")];
strings.extend_from_within(1..=2);
assert_eq!(strings, ["hello", "world", "!", "world", "!"]);

vec.into_flattened

1
pub fn into_flattened(self) -> Vec<T, A>

Takes a Vec<[T; N]> and flattens it into a Vec<T>.

Examples

1
2
3
4
5
let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
assert_eq!(vec.pop(), Some([7, 8, 9]));

let mut flattened = vec.into_flattened();
assert_eq!(flattened.pop(), Some(6));

删除元素

vec.pop

1
pub fn pop(&mut self) -> Option<T>

Removes the last element from a vector and returns it, or None if it is empty.

Examples

1
2
3
let mut vec = vec![1, 2, 3];
assert_eq!(vec.pop(), Some(3));
assert_eq!(vec, [1, 2]);

vec.pop_if

1
pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T>

Removes and returns the last element from a vector if the predicate returns true, or None if the predicate returns false or the vector is empty (the predicate will not be called in that case).

Examples

1
2
3
4
5
6
let mut vec = vec![1, 2, 3, 4];
let pred = |x: &mut i32| *x % 2 == 0;

assert_eq!(vec.pop_if(pred), Some(4));
assert_eq!(vec, [1, 2, 3]);
assert_eq!(vec.pop_if(pred), None);

vec.truncate

1
pub fn truncate(&mut self, len: usize)

Shortens the vector, keeping the first len elements and dropping the rest.

If len is greater or equal to the vector’s current length, this has no effect.

Examples

1
2
3
let mut vec = vec![1, 2, 3, 4, 5];
vec.truncate(2);
assert_eq!(vec, [1, 2]);

vec.drain

1
2
3
pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A> ⓘ
where
    R: RangeBounds<usize>

drain 会“抽干”Vec里指定索引范围的元素，返回一个迭代器 Drain，可以逐个访问这些被移除的元素。

R 可以是任何表示索引范围的类型，比如：0..3、2..、..5。

Examples

1
2
3
4
5
6
7
8
let mut v = vec![1, 2, 3];
let u: Vec<_> = v.drain(1..).collect();
assert_eq!(v, &[1]);
assert_eq!(u, &[2, 3]);

// A full range clears the vector, like `clear()` does
v.drain(..);
assert_eq!(v, &[]);

vec.remove

1
pub fn remove(&mut self, index: usize) -> T

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

Panics

Panics if index is out of bounds.

Examples

1
2
3
let mut v = vec!['a', 'b', 'c'];
assert_eq!(v.remove(1), 'b');
assert_eq!(v, ['a', 'c']);

vec.swap_remove

1
pub fn swap_remove(&mut self, index: usize) -> T

Removes an element from the vector and returns it.

The removed element is replaced by the last element of the vector.

Examples

1
2
3
4
5
6
7
let mut v = vec!["foo", "bar", "baz", "qux"];

assert_eq!(v.swap_remove(1), "bar");
assert_eq!(v, ["foo", "qux", "baz"]);

assert_eq!(v.swap_remove(0), "foo");
assert_eq!(v, ["baz", "qux"]);

vec.retain

1
2
3
pub fn retain<F>(&mut self, f: F)
where
    F: FnMut(&T) -> bool,

Retains only the elements specified by the predicate.

Examples

1
2
3
let mut vec = vec![1, 2, 3, 4];
vec.retain(|&x| x % 2 == 0);
assert_eq!(vec, [2, 4]);

vec.retain_mut

1
2
3
pub fn retain_mut<F>(&mut self, f: F)
where
    F: FnMut(&mut T) -> bool

Retains only the elements specified by the predicate, passing a mutable reference to it.

Examples

1
2
3
4
5
6
7
8
let mut vec = vec![1, 2, 3, 4];
vec.retain_mut(|x| if *x <= 3 {
    *x += 1;
    true
} else {
    false
});
assert_eq!(vec, [2, 3, 4]);

vec.clear

1
pub fn clear(&mut self)

Clears the vector, removing all values.

Note that this method has no effect on the allocated capacity of the vector.

Examples

1
2
3
4
5
let mut v = vec![1, 2, 3];

v.clear();

assert!(v.is_empty());

vec.split_off

1
2
3
pub fn split_off(&mut self, at: usize) -> Vec<T, A>
where
    A: Clone,

Splits the collection into two at the given index.

Returns a newly allocated vector containing the elements in the range [at, len).

Examples

1
2
3
4
let mut vec = vec!['a', 'b', 'c'];
let vec2 = vec.split_off(1);
assert_eq!(vec, ['a']);
assert_eq!(vec2, ['b', 'c']);

vec.dedup

1
pub fn dedup(&mut self)

Removes consecutive repeated elements in the vector according to the PartialEq trait implementation.

If the vector is sorted, this removes all duplicates.

Examples

1
2
3
4
5
let mut vec = vec![1, 2, 2, 3, 2];

vec.dedup();

assert_eq!(vec, [1, 2, 3, 2]);
1
2
3
4
5
6
7
8
fn main() {
    let mut vec = vec![1, 2, 2, 3, 2];
    vec.sort();
    vec.dedup();

    assert_eq!(vec, [1, 2, 3]);
}

遍历

String

std::collections

VecDeque

LinkedList

HashMap

BTreeMap

BinaryHeap

Cost of Collection Operations

get(i) insert(i) remove(i) append(Vec(m)) split_off(i) range append
Vec O(1) O(n-i)* O(n-i) O(m)* O(n-i) N/A N/A
VecDeque O(1) O(min(i, n-i))* O(min(i, n-i)) O(m)* O(min(i, n-i)) N/A N/A
LinkedList O(min(i, n-i)) O(min(i, n-i)) O(min(i, n-i)) O(1) O(min(i, n-i)) N/A N/A
HashMap O(1)~ O(1)~* O(1)~ N/A N/A N/A N/A
BTreeMap O(log(n)) O(log(n)) O(log(n)) N/A N/A O(log(n)) O(n+m)

Note that where ties occur, Vec is generally going to be faster than VecDeque, and VecDeque is generally going to be faster than LinkedList.