C++ STL Algorithms & Binary Search Suites (Rust Backend)

I am excited to announce the release of v1.1.5 of pythonstl, introducing the C++ STL Algorithms and Binary Search suites backed by a compiled Rust core (PyO3/Maturin) and fully optimized pure-Python fallbacks.

This release also resolves packaging configurations and cleans up all codebase style linters (flake8: PASSED).

---

Key Feature Additions

1. C++ STL Algorithms Suite (<algorithm>)

• next_permutation / prev_permutation: In-place lexicographical permutation generators.
• nth_element: In-place selection (Quickselect) that partitions arrays around the $N$-th index in $O(N)$ expected average time.
• partition: In-place separation of elements based on a custom Python predicate.

2. Binary Search Suite

• lower_bound: Locates first index where element is $\ge$ value.
• upper_bound: Locates first index where element is $>$ value.
• binary_search: Fast presence check ($O(\log N)$).
• equal_range: Returns (lower_bound, upper_bound) index bounds.

---

Performance Benchmarks

1. Algorithms performance

Algorithm Name	Pure Python (Middle Pivot)	Python + Rust	Pure C++ (O3)	Rust Speedup
next_permutation	0.3158s	0.2530s	0.0020s	1.2x
nth_element	0.0068s	0.0047s	0.0000s	1.5x (Median of 50k)
partition	0.0193s	0.0197s	0.0000s	1.0x

2. Binary Search (5k queries on 1M items)

Search Mode / Comparator	Pure Python	Python + Rust	Pure C++ (O3)	Rust Speedup
Standard (< comparison)	0.0214s	0.0028s	0.0000s	7.5x faster
Custom Comparator (lambda)	0.0251s	0.0074s	N/A	3.4x faster

---

Systems Design Highlights

1. GIL-Bound Indexing Optimization: We bypass copying the Python list (which takes $O(N)$ time) and instead index elements directly from Rust via arr.get_item(mid). This preserves the strict $O(\log N)$ complexity of binary search.
2. Algorithmic Worst-case Prevention: Switched the pure-Python fallback pivot selection from Lomuto (rightmost element) to a middle-pivot. This avoids $O(N^2)$ worst cases on sorted/reversed lists, yielding a 10,000x+ speedup (down to 0.0068s from 70.85s).
3. Linter & Test Verification: Codebase is clean of PEP8/flake8 errors. All 81 tests are passing.

---

Installation

pip install pythonstl==1.1.5

pythonstl v0.1.0 - Initial Public Release

We are excited to announce the first public release of pythonstl - a C++ STL-style container library for Python, built using the Facade Design Pattern.

This release introduces a structured, STL-compliant API layer on top of Python, designed for:

• C++ developers transitioning to Python
• DSA learners
• Competitive programming practice
• Educational use cases

---

Installation

pip install pythonstl

PyPI: https://pypi.org/project/pythonstl/

---

Features

STL-Style Containers

• vector
• stack
• queue
• stl_set
• stl_map
• priority_queue

All containers maintain C++ STL naming conventions such as:

• push()
• pop()
• top()
• insert()
• erase()
• empty()
• size()

---

🔁 Iterator Support

• begin()
• end()
• rbegin()
• rend()
• Python-native iteration (for x in container)

---

Python Integration

Supports Python magic methods:

• len(container)
• if container:
• value in container
• == comparisons
• copy() and deepcopy()

---

Vector Enhancements

• reserve()
• shrink_to_fit()
• Capacity management similar to C++ std::vector

---

Architecture

• Facade Design Pattern
• Strict encapsulation
• Private implementation layer
• Clean separation of concerns
• Type hints throughout
• Fully test-covered

---

Modern Packaging

• PEP 517 compliant (pyproject.toml)
• Python 3.10+
• CI/CD via GitHub Actions
• Benchmarks included

---

Complexity Overview

Container	Operation	Complexity
Stack	push/pop	O(1)
Queue	push/pop	O(1)
Vector	push_back	O(1) amortized
Set / Map	insert/find	O(1) average
Priority Queue	push/pop	O(log n)

---

Thread Safety

Containers are not thread-safe by default.
Users must apply their own synchronization in multi-threaded environments.

---

Project Vision

pythonstl is not meant to replace Python built-ins.

Instead, it provides:

A familiar STL experience in Python — without losing Python’s ecosystem power.

---

Roadmap

Planned future enhancements:

• deque
• list (doubly linked list)
• multiset
• multimap
• STL-style algorithms module

---

Thank you for checking out pythonstl.

Feedback, issues, and contributions are welcome!