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

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. prevector: simplify `operator==` 0645fa19b0
3. 
   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 react with 👎 to this comment and the bot will ignore it on the next update.

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #33771 (refactor: C++20 operators by purpleKarrot)

   If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

4. 
   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      | ^
   

5. DrahtBot added the label CI failed on Nov 3, 2025
6. prevector: match `std::vector::operator<=>` behavior f6f7adbe91
7. purpleKarrot force-pushed on Nov 3, 2025
8. DrahtBot removed the label CI failed on Nov 3, 2025
9. 
   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.
10. laanwj added the label Utils/log/libs on Nov 4, 2025

Contributors
purpleKarrot DrahtBot fanquake stickies-v

Labels
Utils/log/libs