rust std

---

Timeline

Timeline

2025-10-22

add Vec, others todo

This article introduces bit manipulation methods in the Rust standard library and the usage of the basic collection type Vec. The bit manipulation section summarizes, in table form, the names, return types, and functions of methods for counting the number of 1s or 0s in binary, leading 0s/1s, trailing 0s/1s, etc. The Vec section details its construction methods (such as the vec! macro, Vec::new, Vec::with_capacity、Vec::from_raw_parts), and emphasizes the unsafety of constructing a Vec using C pointers; it also introduces property access (len, is_empty), element access and modification, resizing (resize, resize_with), inserting elements (insert, push, append, extend_from_slice、extend_from_within、into_flattened) and deleting elements (pop, pop_if) and other common operations, and points out the Panics conditions of related methods.

bit manipulation

Bit statistics

Method name	Return value type	Function	Example input	Example output
count_ones()	u32	Count the number of 0s in binary1the number of	0b1011_0001u8	4
count_zeros()	u32	Count the number of 0s in binary0the number of	0b1011_0001u8	4(4 zeros in 8 bits)
leading_zeros()	u32	Countleading zeros(the number of 0s 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

A basic sequence type, located in the top-level module of the standard library, not in std::collections, and in the prelude, so it does not need to be explicitly imported.

Vec

Construct

vec![]

Using the vec! macro is more convenient, as it allows initializing some values at construction time.

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

    Using a C pointer is unsafe, because Vec will call the Rust allocator’s dealloc on Drop, 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 elsewhere

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 {
        // Allocate memory using a raw allocation function (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);
}

Property access.

vec.len

pub const fn len(&self) -> usize

Return the number of elements.

---

vec.is_empty

pub const fn is_empty(&self) -> bool

Returns true if there are no elements, otherwise returns false.

---

Access element

Modify elements

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

---

Insert elements

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

---

Erase elements

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>

drainDrains the elements in the specified index range from the Vec, returning an iterator.Drain, allowing you to access the removed elements 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

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

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.