Skip to content
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.

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

<algorithm>: ranges::minmax initializes minmax_result with the moved value #2900

Closed
hewillk opened this issue Jul 23, 2022 · 2 comments · Fixed by #3366
Closed

<algorithm>: ranges::minmax initializes minmax_result with the moved value #2900

hewillk opened this issue Jul 23, 2022 · 2 comments · Fixed by #3366
Labels
bug Something isn't working fixed Something works now, yay! ranges C++20/23 ranges

Comments

@hewillk
Copy link
Contributor

hewillk commented Jul 23, 2022

minmax_result<_Vty> _Found = {static_cast<_Vty>(*_UFirst), static_cast<_Vty>(*_UFirst)};

This is basically GCC PR104858, which has been resolved in libstdc++.

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

int main() {
  std::vector<std::string> v{"1", "0"};
  auto [min, max] = std::ranges::minmax(
    std::ranges::subrange{
      std::make_move_iterator(v.begin()),
      std::make_move_iterator(v.end())});
  std::cout << min << " " << max << "\n"; // only print 0 in MSVC-STL
}

https://godbolt.org/z/nM5a1Y9Gr

@CaseyCarter
Copy link
Member

<algorithm>: ranges::minmax double dereferences _UFirst

This is not a bug.

std::cout << min << " " << max << "\n"; // only print 0 in MSVC-STL

This is a bug.

@CaseyCarter CaseyCarter added bug Something isn't working ranges C++20/23 ranges labels Jul 23, 2022
@hewillk
Copy link
Contributor Author

hewillk commented Jul 23, 2022

<algorithm>: ranges::minmax double dereferences _UFirst

This is not a bug.

Sorry, I just kept the original title, which doesn't describe the problem properly. Updated.

@hewillk hewillk changed the title <algorithm>: ranges::minmax double dereferences _UFirst <algorithm>: ranges::minmax initializes minmax_result with the moved value Jul 23, 2022
@StephanTLavavej StephanTLavavej added the fixed Something works now, yay! label Feb 3, 2023
CaseyCarter added a commit to CaseyCarter/STL that referenced this issue Feb 3, 2023
The fix for microsoft#2900 in microsoft#3366 did not take advantage of the fact that the minimum and maximum elements of a range are always distinct except when the range has only one element. It couldn't easily do so due to the way `ranges::minmax` and `ranges::minmax_element` share the common backend `ranges::_Minmax_element_unchecked`.

This PR introduces a new backend for `ranges::minmax` (`ranges::_Minmax_fn::_Minmax_fwd_unchecked`) and makes `ranges::_Minmax_element_unchecked` the private member `ranges::_Minmax_element_fn::_Minmax_element_fwd_unchecked`. Since the two are distinct, `_Minmax_fwd_unchecked` can deal in values instead of iterators, and we can unroll the first loop iteration to detect the single-element case naturally. Since no additional branch is needed, we can enable the fix for microsoft#2900 unconditionally.

This refactoring is also probably a minor throughput and perf improvement, since `minmax` no longer needs to instantiate the "old" backend's return type and the new backend is tail-called.

Drive-by: Fully qualify the names of ugly functions called by `ranges::minmax` and `ranges::minmax_element`.
CaseyCarter added a commit to CaseyCarter/STL that referenced this issue Feb 3, 2023
The fix for microsoft#2900 in microsoft#3366 did not take advantage of the fact that the minimum and maximum elements of a range are always distinct except when the range has only one element. It couldn't easily do so due to the way `ranges::minmax` and `ranges::minmax_element` share the common backend `ranges::_Minmax_element_unchecked`.

This PR introduces a new backend for `ranges::minmax` (`ranges::_Minmax_fn::_Minmax_fwd_unchecked`) and makes `ranges::_Minmax_element_unchecked` the private member `ranges::_Minmax_element_fn::_Minmax_element_fwd_unchecked`. Since the two are distinct, `_Minmax_fwd_unchecked` can deal in values instead of iterators, and we can unroll the first loop iteration to detect the single-element case naturally. Since no additional branch is needed, we can enable the fix for microsoft#2900 unconditionally.

Drive-by: Fully qualify the names of ugly functions called by `ranges::minmax` and `ranges::minmax_element`.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working fixed Something works now, yay! ranges C++20/23 ranges
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants