If someone needs a container which supports indexing, why not use an
existing container which provides it, like vector? If someone needs to
store heterogeneous elements in a container, why not use any, or a
unique_ptr to a base type? If someone needs both, why not use a vector of
any or something similar? What does this provide over the existing
orthogonal building blocks which can be combined to achieve the same
functionality?

On Wed, Dec 3, 2025 at 1:38 PM 方晶晶 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`.
>
> --- ## 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
>