--- ## IV. Impact On the Standard This proposal is a **pure extension**—it does **not modify** existing standard components. It introduces a new container (`std::flex_list` or similar; naming TBD) that coexists with `std::list`.
### Dependencies: - Requires `` for bounds checking. - Uses standard allocation/deallocation semantics (no custom allocators in initial version). - Compatible with C++17 and later; no new language features required.
### Implementation feasibility: Fully implementable with current C++ compilers (tested with GCC 11+, Clang 14+). Template instantiation rules are standard-compliant.
--- ## V. Design Decisions
### 1. Templated `node` as a public class Instead of hiding nodes internally (as in `std::list`), we expose a lightweight `node` template. This simplifies construction and allows external ownership or reuse. **Tradeoff**: Slightly increased API surface, but enables composition and interoperability.
### 2. Heterogeneous storage via `node` base The `list` class internally stores `node*`, allowing insertion of any `node*`. Type safety is preserved at the point of access via `operator[](index)`. **Alternative considered**: Type erasure with `std::any` or virtual functions — rejected due to runtime overhead. **Consequence**: Users must know the type at access time, but gain zero-cost abstraction when types are known statically.
### 3. `operator[]` with compile-time type parameter We overload `operator[]` as a **template member function**: ```cpp template node& operator[](int index); ``` This enables syntax like `mylist[3]`, combining positional access with type resolution. **Why not `at(index)`?** `operator[]` aligns with user expectations from arrays and vectors, and template syntax makes type explicit. ### 4. Binary search on sorted lists The `binarySearch(value)` method assumes the list is sorted by `T::value`. This is a **contractual precondition**, not enforced at runtime. **Safety note**: Like `std::binary_search`, misuse on unsorted data yields undefined results—but the interface makes intent clear.
--- ## VI. Technical Specifications Below is a simplified specification of the proposed interface. Full "standardese" will follow if the proposal is accepted for wording review.
### Class `node` ```cpp template class node { public: T value; node* prev = nullptr; node* next = nullptr; constexpr node(T val); constexpr node(T val, node* nxt); ~node(); // recursively deletes next chain (for simplicity; alternatives possible) }; ```
### Class `flex_list` (provisional name) ```cpp class flex_list { private: node* head = nullptr; node* tail = nullptr; int m_size = 0; public: flex_list(); ~flex_list(); template void add(node* n); template node& operator[](int index); // throws std::out_of_range if invalid template int binarySearch(const T& value); // returns index or -1 int size() const noexcept; void clear(); }; ```
### Requirements: - `T` must be copyable (for node construction). - `operator<` and `operator==` must be defined for `binarySearch`. - Thread safety: same as `std::list` (not thread-safe by default).
### Complexity guarantees: - `add`: O(1) - `operator[]`: O(n) — **not** O(1); documented as linear-time random access - `binarySearch`: O(n log n) due to linear `operator[]` calls (still better than O(n²) naive search in some contexts) > **Note**: While `operator[]` is O(n), it enables familiar syntax and algorithm expression. For true O(1) access, `std::vector` remains preferable. This design targets **expressiveness**, not asymptotic optimality.
--- ## VII. Acknowledgements Thanks to the C++ community for inspiring flexible container designs, and to early reviewers who highlighted tradeoffs in type safety vs. heterogeneity.
--- ## VIII. References
1. ISO/IEC 14882:2020 — Programming Languages — C++
2. N3370 — Call for Library Proposals
3. Boost.Container and Boost.TypeErasure libraries
4. Stroustrup, B. *The Design and Evolution of C++
* 5. Submitted implementation: `list.h`, `list.cpp` (attached)