7

This question comes from this comment:

If you have say two vectors a and b, the total order is permitted to be &a[0], &b[0], &a[1], &b[1], &a[2], &b[2], ..., i.e., with the elements interleaved.

Is that order permitted?

I don't known much about the standard. That seems correct if I read only sections directly related to std::less.

And I found that Herb Sutter's gcpp library have a similar usage(link):

    //  Return whether p points into this page's storage and is allocated.
    //
    inline
    bool gpage::contains(gsl::not_null<const byte*> p) const noexcept {
        //  Use std::less<> to compare (possibly unrelated) pointers portably
        auto const cmp = std::less<>{};
        auto const ext = extent();
        return !cmp(p, ext.data()) && cmp(p, ext.data() + ext.size());
    }
Daniel Langr
  • 22,196
  • 3
  • 50
  • 93
VainMan
  • 2,025
  • 8
  • 23
  • As the elements of a vector are required to be contiguous, the hardware would need a very strange addressing scheme. This strange addressing scheme would still not be visible in C++ as elements would still have to be contiguous. – Richard Critten Sep 24 '21 at 06:54
  • 2
    @RichardCritten I believe `std::less` does not need to just compare addresses. It may define its own ordering (according to [comparison.general.2.1](http://eel.is/c++draft/comparisons#general-2.sentence-1)), such as even addresses first and odd second. Sure, any sane implementation would not do this, but this is a _language-lawyer_ question. – Daniel Langr Sep 24 '21 at 06:56
  • @DanielLangr I agree on the language-lawyer aspect but I was just observing that `(&v[0] + 1)` is required to be the same address as `&v[1]` (assuming the elements exist) so how would the interleaving be observable ? ie if you can never observe the interleaving from C++ then `std::less` cannot / has no need to make any special case adjustments. – Richard Critten Sep 24 '21 at 07:10
  • I think that `std::less` actually can apply special adjustments. Consider 4 elements of a `std::vector v` being stored from address 100. Then, `std::less` can order them as (100,102,101,103), therefore, (`&v[0]`, `&v[2]`, `&v[1]`, `&v[3]`). I don't see anything in the standard that would hinder it. But, there is actually a [note](http://eel.is/c++draft/comparisons#general-note-1) that says this is not possible. But notes are not normative. – Daniel Langr Sep 24 '21 at 07:31
  • 2
    I see that note as explaining the implications of point [(2)](http://eel.is/c++draft/comparisons#general-2) just above it. This combined with the reference to [defns.order.ptr](http://eel.is/c++draft/defns.order.ptr) I think does not allow the proposed order. – Richard Critten Sep 24 '21 at 07:39
  • 2
    To me this would naturally occur on segmented memory architectures where you first compare the reference within each segment, and then iff that is equal you compare which memory segments they are in. – Hans Olsson Sep 24 '21 at 07:39
  • 1
    @RichardCritten You're right, I didn't know about [defns.order.ptr]. It explains a lot in this context. But the OP's "interleaved" ordering still seems to be applicable. – Daniel Langr Sep 24 '21 at 07:53
  • https://stackoverflow.com/questions/64042325/in-c-how-to-check-a-pointer-lies-within-a-range https://stackoverflow.com/questions/65472617/how-to-correcly-check-whether-a-pointer-belongs-within-an-allocated-block – Language Lawyer Sep 24 '21 at 08:23
  • 1
    @LanguageLawyer Following the links finds the answer in https://stackoverflow.com/questions/39160613/can-the-following-code-be-true-for-pointers-to-different-things which goes into details and https://devblogs.microsoft.com/oldnewthing/20170927-00/?p=97095 – Hans Olsson Sep 24 '21 at 08:27

1 Answers1

1

Yes, different arrays (that are not part of the same complete object) can be interleaved in the ordering, but each array must separately be ordered correctly—this is what it means that the total order must be consistent with the partial order established by the built-in operators. The fact that a+1 points to the element immediately after *a is irrelevant to the question of unrelated arrays since the partial order is exactly that the obvious relationship between indices and pointer order pertains within one complete object. (In fact, “immediately after” is circular here, since the only observable immediacy is in the array indices themselves. Integer casts need not respect it, so you can’t see “the real addresses”.)

Davis Herring
  • 36,443
  • 4
  • 48
  • 76