Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
purpleKarrot wants to merge 2 commits into
base: master
Choose a base branch
from
Open

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

purpleKarrot wants to merge 2 commits into from
+11 −35

Conversation

@purpleKarrot
Copy link
Contributor

@purpleKarrot purpleKarrot commented Nov 3, 2025

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:

int main()
{
    auto const v12 = std::vector{1, 2};
    auto const v3 = std::vector{3};

    auto const pv12 = prevector<4, int>(v12.begin(), v12.end());
    auto const pv3 = prevector<4, int>(v3.begin(), v3.end());

    assert((v12 < v3) == (pv12 < pv3));
}

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.

@DrahtBot
Copy link
Contributor

DrahtBot commented Nov 3, 2025 •
edited
Loading

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.

@fanquake
Copy link
Member

fanquake commented Nov 3, 2025

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:

In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/chainparams.cpp:6:
In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/chainparams.h:9:
In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/kernel/chainparams.h:11:
In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/primitives/block.h:9:
In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/primitives/transaction.h:12:
In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/script/script.h:11:
/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'?
  446 |         return std::lexicographical_compare_three_way(begin(), end(), other.begin(), other.end());
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                     lexicographical_compare
/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
   42 | lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
      | ^

@DrahtBot DrahtBot removed the CI failed label Nov 3, 2025
stickies-v
stickies-v reviewed Nov 3, 2025
View reviewed changes
Copy link
Contributor

@stickies-v stickies-v left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

@DrahtBot DrahtBot mentioned this pull request Nov 4, 2025
Merged
@l0rinc l0rinc mentioned this pull request Nov 21, 2025
Merged
4 tasks
@DrahtBot
Copy link
Contributor

DrahtBot commented Dec 8, 2025

🐙 This pull request conflicts with the target branch and needs rebase.

@maflcko maflcko mentioned this pull request Dec 9, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@stickies-v stickies-v stickies-v left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

Needs rebase Utils/log/libs

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@purpleKarrot @DrahtBot @fanquake @stickies-v @laanwj