Some tweaks to RandomAccessIteratorTransformer

[Quuxplusone]

This is three commits: new tests (without changing behavior), better operators (without observably changing behavior, and unrelated to the new tests), and then an ambitious change to the C++20 iterator-concept machinery (which does change behavior, reflected in the new tests). Each one could be taken upstream independently from any of the others, if you like.

[alexkaratarakis]

Each one could be taken upstream independently from any of the others, if you like.

Thanks, I did test them individually!

I'm actually not sure how VecType::const_iterator::value_type was getting the correct value before this commit.

There is a (subtle?) fix with the last commit.

using ConstVecType = const VecType;
// Before has const
static_assert(std::is_same_v<const int, typename ConstVecType::iterator::value_type>);
 // After does not
static_assert(std::is_same_v<int, typename ConstVecType::iterator::value_type>);

New behavior is the correct one and matches the result for std::vector in msvc/clang/gcc. I added a commit with tests that showcase this, and then it is fixed in the last commit.

What's interesting is that std::vector has not moved to contiguous_iterator_tag. Demo: https://godbolt.org/z/ejWqq8o5Y

What's more interesting is there is discrepancy in pointer_traits::element_type, where msvc yields T, but clang/gcc (->stdlib) yield T*. Demo: https://godbolt.org/z/3sMnox46j

arrow_proxy

Have tried this before: https://github.com/teslamotors/fixed-containers#arrowproxy and there are some issues. I am on the lookout for a solution that allows the removal of the API discrepancy, but so far the current implementation seems like the least-downsides option in my opinion. There was a suggestion about flat_map having a solution for this here, will look into it.

[alexkaratarakis]

Thank you for this modernization!

[Quuxplusone]

I'm actually not sure how VecType::const_iterator::value_type was getting the correct value before this commit.

There is a (subtle?) fix with the last commit.

using ConstVecType = const VecType;
// Before has const
static_assert(std::is_same_v<const int, typename ConstVecType::iterator::value_type>);
 // After does not
static_assert(std::is_same_v<int, typename ConstVecType::iterator::value_type>);

New behavior is the correct one and matches the result for std::vector in msvc/clang/gcc.

What you wrote there isn't quite correct (ConstVecType::iterator should be VecType::const_iterator), but what you wrote in the new test (line 53) is correct. I was confused by the fact that my assert (line 44) passed before the change:

static_assert(std::is_same_v<std::iter_value_t<VecType::const_iterator>, int>);  // before and after

but I see now that that was only because C++20 iter_value_t quietly strips cv-qualifiers ("overloads" 5,6,7 here). So that answers my confusion: VecType::const_iterator::value_type was getting the wrong value, but I failed to see that it was wrong, because I was looking only at std::iter_value_t<VecType::const_iterator>, which masks the difference. All good now. :)

What's interesting is that std::vector has not moved to contiguous_iterator_tag. Demo: https://godbolt.org/z/ejWqq8o5Y

I'm 99% sure that it would be conforming for vector to advertise contiguous_iterator_tag. I think the reason existing vendors haven't changed their vectors is because they're worried about user code in the wild that checks for random-access-ness via std::is_same_v<std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag> instead of using std::is_convertible/std::is_base_of. Such a check was fine pre-'20, but does the wrong thing for contiguous iterators in '20 and later. A C++20 library targeting devs who "live at head" shouldn't need to worry about that.

What's more interesting is there is discrepancy in pointer_traits::element_type, where msvc yields T, but clang/gcc (->stdlib) yield T*. Demo: https://godbolt.org/z/3sMnox46j

Hmm, I've been here before. :) I filed libc++ bug #31354 for exactly this issue back in early 2017, but then decided that it wasn't really a bug because C++20 contiguous_iterator wasn't yet on anyone's radar. Now that C++20 contiguous iterators are a thing — in fact they are exactly the same thing as pre-C++20 fancy pointers — I think that bug should probably be reopened and __wrap_iter<T> should provide an element_type the same way your library now does.

arrow_proxy

Have tried this before: https://github.com/teslamotors/fixed-containers#arrowproxy and there are some issues. I am on the lookout for a solution that allows the removal of the API discrepancy, but so far the current implementation seems like the least-downsides option in my opinion. There was a suggestion about flat_map having a solution for this here, will look into it.

By non-random coincidence, I'm the author of sg14::flat_map and libc++ std::flat_map, both of which use the arrow_proxy pattern. (And I did a blog post on it, back in the day.) I don't think I understand the problem you were seeing well enough to say with confidence that you were wrong; but it certainly does seem like there's nothing special about your use-case that would preclude the same kind of arrow_proxy that so many other libraries have used successfully.

[alexkaratarakis]

What you wrote there isn't quite correct

Ah, sorry about the typo, likely copy-pasted incorrectly.

Hmm, I've been here before. :) I filed https://github.com/llvm/llvm-project/issues/31354

Nice read. The results are definitely on the surprising side.

arrow-proxy

I will try the arrow_proxy pattern again. The problems from last time are catalogued in the README, but maybe there was an oversight.

[alexkaratarakis]

Thanks for the above @Quuxplusone ! I was able to find a solution that no longer requires an API discrepancy. PR here

With a small delta on top of that, here is the ArrowProxy approach as well. It matches a flat_map exactly (as in, all static_assert()s yield the same results for iterators of EnumMap/FixedMap/flat_map). The implementation is simpler, but not returning an l-value has some issues from a user's perspective:

1) Need to suppress -Wrange-loop-bind-reference globally because they trigger on common loops (in contrast to std::map):

    for (const auto& key_and_value : s) { }

    for (const auto& [key, value] : s) { }

2) These non-cost & don't work at all (in contrast to std::map):

        // error: non-const lvalue reference to type 'pair<...>' cannot bind to a temporary of type
        // 'pair<...>'
       for (auto& key_and_value : s) { }

        // error: non-const lvalue reference to type 'pair<...>' cannot bind to a temporary of type
        // 'pair<...>'
        for (auto& [key, value] : s) { }

3) range-v3 has issues (but not std::ranges, std::map works with either):

    int first_entry = (*f.begin()).second;  // Can't use arrow with range-v3 because it requires
                                            // l-value. Note that std::ranges works

Minor issues, but possibly worthwhile going for l-value to be closer to a drop-in-replacement-of-std::map.