rust std

even629

2025-10-24 (Updated: 2025-10-24)

Timeline

2025-10-22

add Vec, others todo

This article introduces bit counting operations and basic sequence types in the Rust standard library, focusing on summarizing various construction methods of Vec dynamic arrays (including memory allocation mechanisms and the use of from_raw_parts safety constraints), and explains in detail common methods such as property access, element addition, deletion, modification, query, and slice expansion, along with their exception handling mechanisms.

bit manipulation

Bit Counting

Method Name	Return Type	Description	Example Input	Example Output
`count_ones()`	`u32`	Count the number of`1`in binary	`0b1011_0001u8`	`4`
`count_zeros()`	`u32`	Count the number of`0`in binary	`0b1011_0001u8`	`4`(4 zeros in 8 bits)
`leading_zeros()`	`u32`	CountLeading zeros(Number of zeros from the most significant bit to the first 1)	`0b0001_0000u8`	`3`
`trailing_zeros()`	`u32`	CountTrailing zeros(Starting from the least significant bit)	`0b0010_0000u8`	`5`
`leading_ones()`	`u32`	CountLeading onesNumber	`0b1110_0000u8`	`3`
`trailing_ones()`	`u32`	CountTrailing onesNumber	`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());
}

Output:

[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

Basic sequence type, in the top-level module of the standard library, not in std::collections, in the prelude, no explicit import needed

Vec

Construction

vec![]

Using the vec macro is convenient, as it allows initializing some values during construction.

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

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, 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

Using a C pointer is unsafe because when Vec is dropped, it calls Rust’s allocator dealloc, but this memory was allocated by C, which is unsafe.

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 else where

use std::alloc::{alloc, Layout};

fn main() {
    // Construct a memory layout that can store 16 u32 values.
    let layout = Layout::array::<u32>(16).expect("overflow cannot happen");

    let vec = unsafe {
        // Use a raw allocation function to allocate memory (returns a *mut u8 pointer).
        let mem = alloc(layout).cast::<u32>();
        if mem.is_null() {
            return;
        }
		// Write a value to the first position of the allocated memory.
        mem.write(1_000_000);
        
	    // Wrap this raw memory into a Vec (length 1, capacity 16).
        Vec::from_raw_parts(mem, 1, 16)
    };

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

Attribute access

vec.len

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

Returns the number of elements

vec.is_empty

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

Returns true if there are no elements, otherwise false

Access an element

Modify an element

vec.resize

1	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

1
2
3

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]);

Insert an element

vec.insert

1	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

1	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

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

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

Clones and appends all elements in a slice to theVec.

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

1	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));

Remove an element

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

1	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

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>

drainDrains elements in the specified index range from the Vec, returning an iteratorDrain, allowing access to each removed element one by one.
RCan be any type that represents an index range, such as: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

1	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

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

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

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

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

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 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]);
}

traverse

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.