link#

• Is Vec<T> a Smart Pointer?

  • 1.1📌 Comparison table
  • 1.2🧠 Why Vec feels like a smart pointer
  • 1.3❌ Why Vecis NOT a smart pointer
    • 1️⃣ Vec<T> is a collection, not a pointer abstraction
    • 2️⃣ Vec<T> does NOT implement Deref<Target = T>
    • 3️⃣ Moving a Vec<T> DOES NOT pin its elements
    • 4️⃣ Vec<T> allows reallocation (key difference)

• Why Rust documentation is strict here

• Dynamic Array

  • 언어별 Growth factor(dynamic array)
    • 자세히 설명하는 영상(250125)In search of the perfect dynamic array growth factor | Kay Lack

• ⚠️ Important contrast: Box<[T]> - IS closer to a smart pointer

• Cost of Collection Operations성능비교Vec vs VecDeque vs LinkedList vs HashMap vs BTreeMap

• 만들어 보면서 익히기

  • Vector 내 맘대로 만들어 보기 하지만 cargo miri를 해보니 UB가 발생함.
  • Vector(벡터)로 스텍 구현 만들기

• Vector Basics in Rust(10 Example)

Vector공식문서|🔝|#

• https://doc.rust-lang.org/stable/std/vec/struct.Vec.html

• 벡터로 스텍 구현 만들기

  • https://younghakim7.github.io/blog/posts/240701_stack_impl/

Cost of Collection Operations|🔝|#

• https://github.com/rust-lang/rust/blob/main/library/std/src/collections/mod.rs#L108-L119

(250125)In search of the perfect dynamic array growth factor | Kay Lack|🔝|#

• https://youtu.be/GZPqDvG615k?si=WMdeEwLmQwHBkCU1

Chapters
00:00 - Intro
03:29 - Golden Ratio
05:11 - 1.5 Factor
07:08 - Lankinen Algorithm
09:53 - Larger simulations
14:18 - Origins
17:36 - Exercise

언어별 Growth factor(dynamic array)|🔝|#

• https://en.wikipedia.org/wiki/Dynamic_array

1. Is Vec<T> a Smart Pointer?|🔝|#

• ✅ Official answer (Rust terminology)

Vec<T> is NOT classified as a smart pointer.

• In Rust, smart pointers are types whose primary purpose is ownership management via pointer semantics, usually by implementing:

  • Deref / DerefMut
  • custom Drop
  • pointer-like behavior (Box, Rc, Arc, etc.)

• Examples:

  • Box<T>
  • Rc<T>
  • Arc<T>
  • RefCell<T>
  • Mutex<T>

• Vec<T> does not fall into this category

Vec<T> = owning, growable buffer
Smart pointer = owning pointer to a single value

Vec<T> is not a smart pointer in Rust because it is a growable collection that dereferences to a slice and may reallocate its elements, whereas smart pointers represent stable ownership of a single value.

Vec<T> (stack)
┌──────────────┐
│ ptr          │──┐
│ len          │  │
│ cap          │  │
└──────────────┘  │
                  ▼
Heap
┌────────────────────────┐
│ T | T | T | ...        │
└────────────────────────┘

Box<T> → one T
Arc<T> → one T

let v: Vec<i32>;
*v        // ❌ does not compile

v[i]      // indexing
v.as_slice()

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

let v2 = v; // move

• v2 points to same allocation
• but elements MAY move on reallocation

v.push(4); // may reallocate

Vector Basic(10 examples)|🔝|#

• examples code(rust)

fn main() {
    let mut v: Vec<i32> = Vec::new();

    v.push(10);
    v.push(20);
    v.push(30);

    println!("{:?}", v);
}

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    println!("{:?}", v);
}

fn main() {
    let v = vec![10, 20, 30];

    let first = v[0];
    let second = v[1];

    println!("{} {}", first, second);
}

fn main() {
    let v = vec![10, 20, 30];

    match v.get(1) {
        Some(value) => println!("Value: {}", value),
        None => println!("Out of bounds"),
    }
}

fn main() {
    let v = vec![1, 2, 3];

    for x in &v {
        println!("{}", x);
    }
}

fn main() {
    let mut v = vec![1, 2, 3];

    for x in &mut v {
        *x *= 10;
    }

    println!("{:?}", v);
}

fn main() {
    let mut v = vec![1, 2, 3];

    let last = v.pop();
    println!("{:?}", last);
    println!("{:?}", v);
}

fn main() {
    let mut v = Vec::with_capacity(10);

    v.push(1);
    v.push(2);

    println!("len = {}", v.len());
    println!("capacity = {}", v.capacity());
}

enum Value {
    Int(i32),
    Float(f64),
    Text(String),
}

fn main() {
    let v = vec![
        Value::Int(10),
        Value::Float(3.14),
        Value::Text(String::from("hello")),
    ];

    for item in v {
        match item {
            Value::Int(i) => println!("Int: {}", i),
            Value::Float(f) => println!("Float: {}", f),
            Value::Text(s) => println!("Text: {}", s),
        }
    }
}

fn consume(v: Vec<i32>) {
    println!("{:?}", v);
}

fn main() {
    let v = vec![1, 2, 3];

    consume(v);
    // println!("{:?}", v); ❌ compile error
}

Box<[T]>

• owns heap memory
• fixed size
• no reallocation
• single owned slice

Collection ≠ smart pointer

impl<T> Deref for Vec<T> {
    type Target = [T];
}

Vector 내 맘대로 만들어 보기 하지만 cargo miri를 해보니 UB가 발생함.|🔝|#

• 문제의 코드

use std::mem::MaybeUninit;
use std::ptr;

#[derive(Debug)]
pub struct Stack<T, const N: usize> {
    data: [MaybeUninit<T>; N],
    len: usize,
}

impl<T, const N: usize> Stack<T, N> {
    /// Create an empty stack
    pub fn new() -> Self {
        // SAFETY: An uninitialized array of MaybeUninit is valid
        let data = unsafe { MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init() };

        Stack { data, len: 0 }
    }

    /// Push to top of stack
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.len == N {
            return Err(value); // stack overflow
        }

        self.data[self.len].write(value);
        self.len += 1;
        Ok(())
    }

    /// Pop from top of stack
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }

        self.len -= 1;

        // SAFETY: element was initialized
        Some(unsafe { self.data[self.len].assume_init_read() })
    }

    /// Push to bottom (front) of stack
    pub fn front_push(&mut self, value: T) -> Result<(), T> {
        if self.len == N {
            return Err(value);
        }

        unsafe {
            // Shift elements right
            ptr::copy(self.data.as_ptr(), self.data.as_mut_ptr().add(1), self.len);
        }

        self.data[0].write(value);
        self.len += 1;
        Ok(())
    }

    /// Peek top element
    pub fn peek(&self) -> Option<&T> {
        if self.len == 0 {
            None
        } else {
            // SAFETY: element is initialized
            Some(unsafe { &*self.data[self.len - 1].as_ptr() })
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn capacity(&self) -> usize {
        N
    }
}

impl<T, const N: usize> Drop for Stack<T, N> {
    fn drop(&mut self) {
        for i in 0..self.len {
            unsafe {
                self.data[i].assume_init_drop();
            }
        }
    }
}

pub struct IntoIter<T, const N: usize> {
    stack: Stack<T, N>,
}

impl<T, const N: usize> Iterator for IntoIter<T, N> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.stack.pop()
    }
}

impl<T, const N: usize> IntoIterator for Stack<T, N> {
    type Item = T;
    type IntoIter = IntoIter<T, N>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter { stack: self }
    }
}

pub struct Iter<'a, T, const N: usize> {
    stack: &'a Stack<T, N>,
    index: usize,
}

impl<'a, T, const N: usize> Iterator for Iter<'a, T, N> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index == 0 {
            return None;
        }
        self.index -= 1;
        // SAFETY: element is initialized
        Some(unsafe { &*self.stack.data[self.index].as_ptr() })
    }
}

pub struct IterMut<'a, T, const N: usize> {
    stack: &'a mut Stack<T, N>,
    index: usize,
}

impl<'a, T, const N: usize> Iterator for IterMut<'a, T, N> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index == 0 {
            return None;
        }
        self.index -= 1;
        // SAFETY: element is initialized and we have exclusive access
        Some(unsafe { &mut *self.stack.data[self.index].as_mut_ptr() })
    }
}

impl<T, const N: usize> Stack<T, N> {
    pub fn iter(&self) -> Iter<'_, T, N> {
        Iter { stack: self, index: self.len }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T, N> {
        let index = self.len;
        IterMut { stack: self, index }
    }
}

fn main() {
    let mut stack: Stack<i32, 8> = Stack::new();

    stack.push(10).unwrap();
    stack.push(20).unwrap();
    stack.front_push(5).unwrap();

    assert_eq!(stack.pop(), Some(20));
    assert_eq!(stack.pop(), Some(10));
    assert_eq!(stack.pop(), Some(5));
    assert_eq!(stack.pop(), None);

    let mut stack02: Stack<i32, 8> = Stack::new();

    stack02.push(200).unwrap();
    stack02.push(100).unwrap();
    stack02.push(100).unwrap();
    stack02.push(100).unwrap();
    stack02.push(100).unwrap();
    stack02.front_push(10).unwrap();

    println!("stack 02 : {:?}", stack02);
    for i in stack02.iter() {
        println!("stack 02 : {:?}", i);
    }

    let data_store = stack02.pop();
    println!("data_store: {:?}", data_store);
}

• cargo miri로 문제를 잡아냄.(nightly)(UB발생)

$ cargo miri run
error: Undefined Behavior: attempting a read access using <288> at alloc117[0x0], but that tag does not exist in the borrow stack for this location
   --> /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:638:9
    |
638 |         crate::intrinsics::copy(src, dst, count)
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ this error occurs as part of an access at alloc117[0x0..0x8]
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <288> was created by a SharedReadOnly retag at offsets [0x0..0x20]
   --> src/main.rs:50:23
    |
 50 |             ptr::copy(self.data.as_ptr(), self.data.as_mut_ptr().add(1), self.len);
    |                       ^^^^^^^^^^^^^^^^^^
help: <288> was later invalidated at offsets [0x0..0x20] by a Unique retag
   --> src/main.rs:50:43
    |
 50 |             ptr::copy(self.data.as_ptr(), self.data.as_mut_ptr().add(1), self.len);
    |                                           ^^^^^^^^^
    = note: stack backtrace:
            0: std::ptr::copy::<std::mem::MaybeUninit<i32>>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:638:9: 638:49
            1: Stack::<i32, 8>::front_push
                at src/main.rs:50:13: 50:83
            2: main
                at src/main.rs:167:5: 167:24
            3: <fn() as std::ops::FnOnce<()>>::call_once - shim(fn())
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5: 250:71
            4: std::sys::backtrace::__rust_begin_short_backtrace::<fn(), ()>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/backtrace.rs:166:18: 166:21
            5: std::rt::lang_start::<()>::{closure#0}
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:206:18: 206:75
            6: std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:287:13: 287:31
            7: std::panicking::catch_unwind::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:581:40: 581:43
            8: std::panicking::catch_unwind::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:544:19: 544:88
            9: std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:359:14: 359:40
            10: std::rt::lang_start_internal::{closure#0}
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:175:24: 175:49
            11: std::panicking::catch_unwind::do_call::<{closure@std::rt::lang_start_internal::{closure#0}}, isize>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:581:40: 581:43
            12: std::panicking::catch_unwind::<isize, {closure@std::rt::lang_start_internal::{closure#0}}>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:544:19: 544:88
            13: std::panic::catch_unwind::<{closure@std::rt::lang_start_internal::{closure#0}}, isize>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:359:14: 359:40
            14: std::rt::lang_start_internal
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:171:5: 193:7
            15: std::rt::lang_start::<()>
                at /home/gy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:205:5: 210:6

error: aborting due to 1 previous error

• https://github.com/YoungHaKim7/blog_code_polyglot/commit/2f023474d7e00c41b4151d426764f0c5f3fd045d#diff-841572ce7e116fbf6881a5d3b4005325d4f3a4658d94c6c327da6b9f4ab45b64R52-R54
• claude에 물어봐서 해결

unsafe {
            // Shift elements right
            ptr::copy(self.data.as_ptr(), self.data.as_mut_ptr().add(1), self.len);
       }

        unsafe {
            // Get raw pointer once - use it for both source and destination
            let data_ptr = self.data.as_mut_ptr();
            // Shift elements right by copying from right to left
            for i in (0..self.len).rev() {
                ptr::copy(data_ptr.add(i), data_ptr.add(i + 1), 1);
            }
        }