This resonates deeply with me. I was told by experts familiar with the matter, that the case for standardization of "big integers" was self-evident. No measurements were provided for this assertion. And yet as the two hour conversation unfolded, I did the measurements myself while continuing to probe with questions in real time.
What did I find? It turns out that the crypto/digital currency industry is a major consumer of big integers and they are not suffering from a lack of a standard type. Quite the opposite: there are several implementations with extraordinarily high usage counts.
What makes this even more interesting, the implementations are different, and the differences are vital for the use-cases in which they appear. The conclusion is similar to what Jeremy stated by from a different angle:
A particular _implementation_ in the standard may not satisfy all users (and likely will not).
This is what evidence looks like. If I was a chair, and an R0 proposal did not have this, I would kindly ask the author to provide it.
https://gist.github.com/vinniefalco/ff73c160f18e941c7dd009ccae286525For a Graph library proposal, this would be my checklist for determining the suitability for standardization:
Standardization Evidence Checklist for Graph Library (P3126)
A. Ecosystem Friction
- Count distinct incompatible graph libraries in active use (Boost.Graph, NWGraph, LEMON, igraph C++ bindings, hand-rolled adjacency lists).
- Find conversion code between competing graph representations at library boundaries (BGL-to-NWGraph adapters, CSR-to-adjacency-list transforms, similar).
- Find library authors who chose not to depend on a graph library because Boost.Graph is too complex, NWGraph is too new, etc.
- Find projects using ad-hoc graph representations (nested vectors, raw pointer trees, flat edge arrays) instead of a proper graph type.
- Confirm Boost.Graph does not integrate with modern C++20 ranges or concepts. Document the gap.
- Find developers publicly asking for or complaining about the lack of a standard graph library. Stack Overflow, GitHub issues, Reddit, std-proposals.
- Count distinct graph implementations on GitHub that are not forks of BGL, NWGraph, or LEMON.
B. Vocabulary Type Value
- Find two or more independently-maintained libraries (ML frameworks, route planners, compilers, network analyzers) that would use std::graph types in their APIs.
- Enumerate standard library integrations the graph library would enable (ranges, concepts, algorithms, format) and their value.
- Document the current decision tree a developer faces when choosing a C++ graph library (BGL, NWGraph, LEMON, hand-roll).
- Find projects or organizations that prohibit third-party dependencies but would use graph algorithms if available in the standard library.
- Find cases where graph data structures cross shared library boundaries and a standard representation would help.
C. Language Blessing
- Identify benefits of a standard graph type for constexpr graph evaluation. Can a compiler optimize constant graph construction or traversal?
- Confirm that range-of-ranges as a graph representation benefits from standard concepts that third-party libraries cannot portably define.
- Measure the performance gap between a portable graph traversal and one using implementation-specific optimizations (cache-aware layouts, SIMD-accelerated BFS).
- Assess whether standard graph concepts would enable future compiler diagnostics or static analysis for graph algorithm correctness.
D. Implementation Maturity
- Catalog mature, production-tested graph libraries: Boost.Graph (decades), NWGraph (peer-reviewed 2022), LEMON, igraph.
- Confirm core graph algorithms (BFS, DFS, Dijkstra, Bellman-Ford, topological sort) are stable with well-understood complexity guarantees.
- Compare APIs of BGL, NWGraph, Python NetworkX, Java JGraphT, Rust petgraph. Identify common surface.
- Confirm the
github.com/stdgraph reference implementation exists, builds, passes tests, and has a maintenance timeline.
- Enumerate major open design questions (concept granularity, adjacency list vs. edgelist primacy, allocator support, visitor model, parallel algorithm scope) and proposed resolutions.
E. Cost Assessment
- Get cost estimates from libstdc++, libc++, and Microsoft STL implementers. Note: proposal spans seven papers.
- Estimate total specification page count across all companion papers. Compare to similar-complexity library additions (ranges, mdspan).
- Map interactions with existing standard components (ranges, concepts, iterators, containers, allocators, type traits).
- Identify areas likely to generate LWG/CWG issues. Concepts-in-the-standard question is explicitly unresolved.
- Evaluate ABI risk for compressed_graph and other concrete containers. Address stability of the Graph Container Interface.
- Estimate ongoing maintenance cost over three standard cycles, including interaction with parallel algorithms, constexpr containers, and reflection.
- State what committee and implementer time the graph library displaces and why the tradeoff is justified. Seven interrelated papers is substantial.
F. Comparative Analysis
- Can Boost.Graph serve the vocabulary type role with a modern wrapper? If not, why? The paper calls BGL "expert-friendly" - quantify the usability gap.
- Would a well-packaged graph library in vcpkg/Conan satisfy the same use cases? What specifically requires the standard?
- In languages with standard or dominant graph libraries (Python NetworkX, Java JGraphT, Rust petgraph), does the graph type actually cross library boundaries? Cite specific libraries and APIs.
- Have previous standard library additions of comparable scope (ranges, mdspan) delivered expected value on schedule? Cite outcomes.
- P1709 was the original proposal and is now inactive. Analyze why it stalled and whether P3126 addresses the same obstacles.
G. Scope and Complexity Risk
- Seven interrelated papers (P3126-P3131, P3337). Assess whether the proposal can be reviewed and voted on as a coherent unit.
- Parallel algorithms are explicitly deferred. Confirm this deferral does not paint the design into a corner.
- Sparse vertex IDs, bidirectional graphs, and constexpr graphs are listed as future work. Confirm the current design accommodates them without breaking changes.
- No usage experience outside the proposers (stated in P3126r3). Assess whether this is a blocker for LEWG advancement.
- No deployment experience (stated in P3126r3). Plans for 2025 commercial/academic use exist but are unverified. Track status.
- The unpublished comparison paper (P3337) is cited as motivation. Assess whether LEWG can evaluate the proposal without it.
- Freestanding is explicitly unsupported due to stack, queue, and bad_alloc. Confirm this is acceptable to the committee.