Document number: P9999R0
Date: 2025-12-03
Audience: Library Evolution Working Group
Reply-to: C++ Proposer <20090187_at_[hidden]>


--- ## I. Table of Contents
1. Introduction
2. Motivation and Scope
3. Impact On the Standard
4. Design Decisions
5. Technical Specifications
6. Acknowledgements
7. References


--- ## II. Introduction
This proposal introduces a redesigned `list` container that enhances the standard `std::list` by supporting **heterogeneous node types**, **simplified templated node management**, and **random-access-like indexing via `operator[]`**, enabling efficient **binary search** on sorted lists. The design leverages modern C++ generic programming techniques while maintaining compatibility with existing idioms.


--- ## III. Motivation and Scope
### Why is this important?
The current `std::list` in the C++ Standard Library is a doubly-linked list that supports only homogeneous element types and lacks random access, making operations like binary search impossible without linear traversal. In many real-world applications—particularly those involving mixed-type metadata or embedded systems where memory layout flexibility is crucial—developers require a list that can store nodes of different types or support indexed access for algorithmic efficiency.


### Problems addressed:
1. **Node heterogeneity**: Traditional `std::list` forces all elements to be of type `T`. Our design decouples node storage from list ownership, allowing a single list instance to hold nodes of multiple types (e.g., via `node` or type-erased wrappers).
2. **Code verbosity**: By templating the `node` class directly and integrating it into the list interface, boilerplate code for node management is reduced.
3. **Algorithmic limitations**: Without `operator[]`, algorithms requiring positional access (like binary search) cannot be applied efficiently. This proposal enables such algorithms **if the list is kept sorted**.


### Intended users: - Intermediate to expert C++ developers working on data-intensive or embedded systems. - Library authors seeking flexible, low-overhead containers beyond STL’s current offerings. - Educators demonstrating advanced generic programming patterns.


### Existing practice: While not part of the standard, similar designs appear in: - Custom game engines using heterogeneous entity-component systems. - Research prototypes (e.g., “polymorphic containers” in Boost.TypeErasure discussions). - Internal company libraries where performance and flexibility outweigh strict type safety. A reference implementation is provided in the accompanying `list.h` and `list.cpp`.


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








 方晶晶
20090187_at_[hidden]