I‘m not sure how you want to do binary search if operator[] is O(n). BTW I can search through a sorted list by going from on element to the next until I‘ve found the correct one which is also O(n) and thus much faster than your proposed O(n log n) algorithm.

And the node not holding the data means we need two allocations instead of just one. Lists are mostly dead by now because of cache locality problems. Just a few years ago Bjarne Stroustrup has demonstrated in a public talk that std::vector is always faster in common code (use a deque instead if you really need faster insertion). Unless you can prove reasonable performance for a list compared to a vector there is no reason to include a variation of an outdated data structure in the standard.

If you really want binary search on a list, use a skip list.

> On 3. Dec 2025, at 12: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`.
>
> --- ## 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]
>
>
> <list.cpp>
> <list.h>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals