On Wed, 3 Dec 2025 at 11:58, 方晶晶 via Std-Proposals <
std-proposals_at_[hidden]> wrote:

>
> 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`.
>

This sounds interesting, but the attached code is garbage. Has it even been
tested?

All the members are public, which is ... OK, I guess, for a prototype.
There's no allocator support to customize memory allocation.

Your operator[] is not random-access, it's O(n). We could easily add such
an operator[] to std::list if we wanted to, but it would be slow and
expensive. That's why it's not there.
For some reason operator[] and operator= are declared as function
templates, with non-deducible template parameters.

Your list::operator= member isn't even defined anywhere.

There's no copy constructor, so copying a list is a shallow copy, leading
to double frees. Or would do, if any of it could be compiled.

The list destructor does delete this->head but that has type node<void>* so
it tries to instantiate node<void> which has a data member of type void
which is not possible.

Is this a joke? None of this code is even close to compiling.








>
> --- ## 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]
>
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>