prevector: simplify implementation of comparison operators and match behavior of std::vector #33772

pull purpleKarrot wants to merge 2 commits into bitcoin:master from purpleKarrot:prevector-cmp changing 1 files +4 −36
  1. purpleKarrot commented at 2:23 pm on November 3, 2025: contributor

    The reduced amount of code reduces maintenance. Providing prevector::operator<=> allows classes that are implemented in terms of prevector to use the compiler provided operator<=>.

    However, there is a breaking change!

    The old implementation claims to be a drop-in replacement for std::vector. However, the implementation for operator< is different when comparing two vectors of different length, as can be presented with the following code:

    0int main()
    1{
    2    auto const v12 = std::vector{1, 2};
    3    auto const v3 = std::vector{3};
    4
    5    auto const pv12 = prevector<4, int>(v12.begin(), v12.end());
    6    auto const pv3 = prevector<4, int>(v3.begin(), v3.end());
    7
    8    assert((v12 < v3) == (pv12 < pv3));
    9}
    

    With the old implementation of prevector, the assertion fails. With my change, it passes. I ask the reviewers to confirm whether this change in behavior is acceptable or not.

  2. DrahtBot commented at 2:23 pm on November 3, 2025: contributor

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Code Coverage & Benchmarks

    For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33772.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    Concept NACK stickies-v

    If your review is incorrectly listed, please copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.

    Conflicts

    No conflicts as of last run.

  3. fanquake commented at 3:23 pm on November 3, 2025: member

    As indicated by the CI, the macOS SDK we are targeting doesn’t (yet) support lexicographical_compare_three_way. A Guix build will fail the same way:

     0In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/chainparams.cpp:6:
     1In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/chainparams.h:9:
     2In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/kernel/chainparams.h:11:
     3In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/primitives/block.h:9:
     4In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/primitives/transaction.h:12:
     5In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/script/script.h:11:
     6/distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/prevector.h:446:21: error: no member named 'lexicographical_compare_three_way' in namespace 'std'; did you mean 'lexicographical_compare'?
     7  446 |         return std::lexicographical_compare_three_way(begin(), end(), other.begin(), other.end());
     8      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     9      |                     lexicographical_compare
    10/root/SDKs/Xcode-15.0-15A240d-extracted-SDK-with-libcxx-headers/usr/include/c++/v1/__algorithm/lexicographical_compare.h:42:1: note: 'lexicographical_compare' declared here
    11   42 | lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
    12      | ^
    
  4. DrahtBot added the label CI failed on Nov 3, 2025
  5. purpleKarrot force-pushed on Nov 3, 2025
  6. DrahtBot removed the label CI failed on Nov 3, 2025
  7. stickies-v commented at 11:19 pm on November 3, 2025: contributor
    I like the idea, and it would be an improvement to both simplify the prevector implementation and move it closer to being a std::vector drop-in. However, the different operator< implementation has a lot of potential behaviour change (not just direct comparison such as in CNoDestination::operator<, but also in e.g. all maps and sets of CScript), and assuring myself the changes are safe is going to take more time than seems worth it for the stated benefits. So: Concept ACK, but Priority NACK for me.
  8. laanwj added the label Utils/log/libs on Nov 4, 2025
  9. DrahtBot added the label Needs rebase on Dec 8, 2025
  10. maflcko commented at 11:22 am on February 2, 2026: member
    are you still working on this?
  11. prevector: simplify `operator==` acae1ccd13
  12. prevector: match `std::vector::operator<=>` behavior 57c4fd8378
  13. purpleKarrot force-pushed on Feb 3, 2026
  14. purpleKarrot commented at 10:00 pm on February 3, 2026: contributor

    are you still working on this? @maflcko, I have rebased on master and removed the fallback for lexicographical_compare_three_way. The first commit should not be controversial; only the second one involves a breaking change. Do you want me to split the PR in two?

  15. DrahtBot removed the label Needs rebase on Feb 3, 2026
  16. DrahtBot added the label CI failed on Feb 3, 2026
  17. DrahtBot removed the label CI failed on Feb 4, 2026
  18. maflcko commented at 9:22 am on February 4, 2026: member
    Yeah, I guess you can split up the first commit

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-02-10 18:13 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me