rust std

---

时间轴

时间轴

2025-10-22

add Vec, others todo

本文介绍了Rust标准库中位操作方法及基础集合类型Vec的使用。位操作部分通过表格形式总结了统计二进制中1或0的个数、前导0/1、末尾0/1等方法的名称、返回值类型和作用。Vec部分详细说明了其构造方式（如vec!宏、Vec::new、Vec::with_capacity、Vec::from_raw_parts），并强调了使用C指针构造Vec的不安全性；同时介绍了属性访问（len、is_empty）、元素访问与修改、调整大小（resize、resize_with）、插入元素（insert、push、append、extend_from_slice、extend_from_within、into_flattened）以及删除元素（pop、pop_if）等常用操作，并指出了相关方法的Panics条件。

bit manipulation

位统计

方法名	返回值类型	作用	示例输入	示例输出
count_ones()	u32	统计二进制中1的个数	0b1011_0001u8	4
count_zeros()	u32	统计二进制中0的个数	0b1011_0001u8	4（8 位中有 4 个 0）
leading_zeros()	u32	统计前导 0（从高位到第一个1之间的0数量）	0b0001_0000u8	3
trailing_zeros()	u32	统计末尾 0（从最低位开始）	0b0010_0000u8	5
leading_ones()	u32	统计前导 1数量	0b1110_0000u8	3
trailing_ones()	u32	统计末尾 1数量	0b0001_1111u8	5

fn main() {
    let x: u8 = 0b1011_0001;

    println!("x               = {:08b}", x);
    println!("count_ones      = {}", x.count_ones());
    println!("count_zeros     = {}", x.count_zeros());
    println!("leading_zeros   = {}", x.leading_zeros());
    println!("trailing_zeros  = {}", x.trailing_zeros());

    let y: u8 = 0b1110_0111;
    println!("y               = {:08b}", y);
    println!("leading_ones    = {}", y.leading_ones());
    println!("trailing_ones   = {}", y.trailing_ones());
}

输出：

[zhaohang@cyberboy rust_programming]$ cargo run
   Compiling rust_programming v0.1.0 (/home/zhaohang/repository/rust_programming)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.36s
     Running `target/debug/rust_programming`
x               = 10110001
count_ones      = 4
count_zeros     = 4
leading_zeros   = 0
trailing_zeros  = 0
y               = 11100111
leading_ones    = 3
trailing_ones   = 3

primitive-like collections

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

Vec

构造

vec![]

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

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

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

---

Vec::new()

pub const fn new() -> Vec<T>

• Constructs a new, empty Vec. The vector will not allocate until elements are pushed onto it.

Examples

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

---

Vec::with_capacity()

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

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

• Ifcapacityis zero, the vector will not allocate.

• ForVec<T>whereTis a zero-sized type, there will be no allocation and the capacity will always beusize::MAX.

Panics

Panics if the new capacity exceedsisize::MAXbytes.

Examples

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()

pub unsafe fn from_raw_parts(
    ptr: *mut T,
    length: usize,
    capacity: usize,
) -> Vec<T>

• Creates aVec<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 firstlengthvalues must be properly initialized values of typeT

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

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

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 elsewhere

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

pub const fn len(&self) -> usize

返回元素个数

---

vec.is_empty

pub const fn is_empty(&self) -> bool

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

---

访问元素

修改元素

vec.resize

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

Resizes theVecin-place so thatlenis equal tonew_len.

Examples

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

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

Resizes theVecin-place so thatlenis equal tonew_len.

Examples

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

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

Inserts an element at positionindexwithin the vector, shifting all elements after it to the right.

Panics

Panics ifindex > len.

Examples

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

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

Appends an element to the back of a collection.

Panics

Panics if the new capacity exceedsisize::MAXbytes.

Examples

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

---

vec.append

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

Moves all the elements ofotherintoself, leavingotherempty.

Examples

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

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

Clones and appends all elements in a slice to theVec.

Examples

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

vec.extend_from_within

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

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

srcmust be a range that can form a valid subslice of theVec.

Examples

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

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

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

Examples

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

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

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

Examples

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

---

vec.pop_if

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 returnstrue, or None if the predicate returns false or the vector is empty (the predicate will not be called in that case).

Examples

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

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

Shortens the vector, keeping the firstlenelements and dropping the rest.

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

Examples

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

---

vec.drain

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

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

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

Examples

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

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

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

Panics

Panics ifindexis out of bounds.

Examples

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

---

vec.swap_remove

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

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

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

Retains only the elements specified by the predicate.

Examples

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

---

vec.retain_mut

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

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

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

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

v.clear();

assert!(v.is_empty());

vec.split_off

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

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

---

vec.dedup

pub fn dedup(&mut self)

Removes consecutive repeated elements in the vector according to thePartialEqtrait implementation.

If the vector is sorted, this removes all duplicates.

Examples

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

vec.dedup();

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

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.