2. User Journey & API Signatures

Installing the library is as simple as pip install pythonstl. Below is a side-by-side comparison highlighting how PythonSTL bridges the gap between C++ semantics and Python interfaces.

std::vector<int> v;
v.push_back(100);
v.reserve(1000);  // Explicit memory allocation
v.shrink_to_fit();

from pythonstl import vector

v = vector()
v.push_back(100)
v.reserve(1000)      # Memory reservation
v.shrink_to_fit()    # Truncate unused buffer

3. The Facade Design & Dual-Engine Routing

To maintain absolute cross-platform availability, PythonSTL follows a Facade Design Pattern. The user always interacts with a clean Python API. Under the hood, the facade dynamically evaluates the execution environment:

4. FFI Bindings & GIL Management

Rust compiled modules communicate with CPython through PyO3 and the Maturin build compiler. Managing reference count operations at the FFI boundary is crucial. Every arbitrary Python object loaded into a Rust-managed collection is held as a PyObject, which is an incremented smart-pointer to the Python heap.

struct PyObjectOrd(PyObject);

impl Ord for PyObjectOrd {
    fn cmp(&self, other: &Self) -> Ordering {
        Python::with_gil(|py| {
            let self_ref = self.0.bind(py);
            let other_ref = other.0.bind(py);
            
            // Fast-path extraction for primitives to bypass CPython RichCompare
            if let (Ok(a), Ok(b)) = (self_ref.extract::<i64>(), other_ref.extract::<i64>()) {
                return a.cmp(&b);
            }
            if let (Ok(a), Ok(b)) = (self_ref.extract::<&str>(), other_ref.extract::<&str>()) {
                return a.cmp(&b);
            }
            
            // Fallback: Invoking Python comparison logic via FFI C-API
            if self_ref.eq(other_ref).unwrap_or(false) {
                Ordering::Equal
            } else if self_ref.lt(other_ref).unwrap_or(false) {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        })
    }
}

5. The Pure Python Fallback Engine: AVL Trees

When a compiled Rust backend is not available, we require an ordered set/map implementation with logarithmic complexity guarantees. PythonSTL implements a self-balancing binary search tree—specifically, an AVL Tree—written in pure Python under pythonstl/core/avl_tree.py.

An AVL tree enforces a strict balance invariant: the heights of two child subtrees from any node can differ by at most one:

When an insertion or deletion breaks this constraint, the tree uses four structural rotations to rebalance nodes:

• Left-Left (LL) Case: A single right rotation is executed.
• Right-Right (RR) Case: A single left rotation is executed.
• Left-Right (LR) Case: A double rotation (left rotation on left child, right rotation on parent).
• Right-Left (RL) Case: A double rotation (right rotation on right child, left rotation on parent).

6. Quickselect & Pivot Selection Safety

The library replicates the standard C++ nth_element algorithm, which rearranges elements so that the value at the $n$-th index matches its sorted position. It is implemented using the Quickselect selection algorithm.

A naive implementation of Quickselect using a Lomuto partitioning scheme (with the rightmost element as the pivot) degrades to a quadratic complexity of O(N²) when sorting pre-sorted or reversed lists. In our initial test suites, this caused severe slowdowns (up to 70.85 seconds) on large data ranges.

To solve this, we implemented a Middle Pivot Selection Strategy. Before partitioning, the middle element is selected and swapped to the end:

This modification ensures average-case O(N) execution times, drastically reducing runtime on pre-sorted arrays of size 100,000 from 70.85 seconds down to 0.0064 seconds—a speedup of over 11,000x!

7. Performance Benchmarks & FFI Overhead

To evaluate the efficiency of our hybrid compilation approach, we built a comparative performance harness testing the Pure-Python fallback, the Rust-backed engine, and Python's native structures.

8. Memory Safety & Thread Safety Constraints

Unlike native C++ where invalid vector indexing (e.g. v[idx]) can trigger buffer overflows or memory segmentation faults, PythonSTL implements strict safety wrappers:

• Bounds Verification: The vector facade and Rust bindings perform explicit index inspections on every indexing request. If boundaries are violated, an OutOfRangeError exception is raised safely before a pointer mutation occurs.
• Thread-Safety Limitations: Despite having a backend written in Rust, the collections are not thread-safe. Every mutation modifying a PyObject requires acquiring Python's GIL. Mutating these containers from parallel threads without synchronizing via a Python-side threading.Lock() will trigger CPython memory race conditions.

9. Key Architecture & Technology Trade-offs

A detailed one-by-one analysis of the architectural design decisions and performance trade-offs made in PythonSTL.

10. Common Myths vs. Technical Reality

Addressing common misconceptions around hybrid Python-Rust libraries, performance expectations, and CPython internals.