1. 25
  1.  

  2. 7

    Should the second code block be i--?

    1. 5

      Heh. That was not the bug I was trying to demonstrate.

      1. 2

        Also:

        Unsigned numbers will only ever be greater than 0.

        That should be “greater than or equal to”, right? (As in the code.)

        1. 9

          Damn kids and their reading!

      2. 2
        1. 2

          [insert Bettlejuice reference]

          1. 2

            I’m pretty sure that’s what jcs just did.

      3. 3

        That’s one reason why I’m a fan of “stricter” for loop constructs (i.e. not a while loop in disguise) such as for i = 0 to n-1 and for j = n-1 downto 0; the job of making sure the backward loop works with unsigned values falls upon the compiler writer rather than every single programmer.

        1. 3

          Yep, though if we’re allowing better language constructs then we’d want to express the intent even more directly than that. In Scala I’d just do:

          burritos.reverse.find(wantBurrito)
          
        2. 2

          There’s a few reasons to do things this way. Maybe the super burritos are at the end of the list, and we’d obviously prefer bigger. Because better.

          A simple, yet intuitive example of this is in Java’s LinkedList implementation. When you’re trying to get the nth element out of a linked list, the implementation will divide the size of the list in half, and if n is greater than that halfway mark, it will traverse the linked list backwards from the end, but if it’s less than that halfway mark, it’ll traverse the list forward from the beginning. The implementation can be found here, but I also will write it here for convenience:

          Node<E> node(int index) {
              // assert isElementIndex(index);
              if (index < (size >> 1)) {
                  Node<E> x = first;
                  for (int i = 0; i < index; i++)
                      x = x.next;
                  return x;
              } else {
                  Node<E> x = last;
                  for (int i = size - 1; i > index; i--)
                      x = x.prev;
                  return x;
              }
          }
          
          1. 2

            @tedu:

            I would say the most wizened sourcerers will elect to go full stupid:

            for (size_t i = numBurritos; --i;)
                if (wantBurrito(i - 1))
                    break;
            

            Actually, is that a variable?

            if (numBurritos)
                for (size_t i = numBurritos; --i;)
                    if (wantBurrito(i - 1))
                        break;
            

            (This is, of course, close to your point about how counting and indexing don’t need to be the same operation, if to a different conclusion.)

            1. 1

              Yup., Some variation putting the decrement in the test is possible, but much too wizened for me. :)

              1. 1

                Err, yes, that was a last-moment change and I should’ve known better. I even half-realised it, hence the if (numBurritos), sigh. Anyway, the original I should have stuck with was

                for (size_t i = numBurritos; i; --i)
                    if (wantBurrito(i - 1))
                        break;
                

                The point (which I have by now thoroughly detracted from…) was to avoid comparing quantities, hence full stupid.

            2. 1

              Is it intended that the second code example which is supposed to decrement i actually increments it?

              1. 1

                Why not just use the iterator pattern?

                1. 2

                  What is the iterator pattern?

                  1. 4

                    It is a pattern used in C++ that matches point semantics from C.

                    Consider you have an array:

                    int array[10];
                    

                    That is full, we have a beginning:

                    int *it = &array[0];
                    

                    and an end:

                    int *last = &array[10];
                    

                    The end being defined as one past the last element. The iterator pattern would be to use a for loop, say to sum:

                    int sum = 0;
                    for (int *it = &array[0]; it != &array[10]; ++it) {
                        sum += *it;
                    }
                    

                    This pattern can be generalized with the same interface to many different kinds of containers. If I had a vector<int> instead, I would do begin(myvec) and end(myvec) instead, but I could do the same operations: dereferencing, and incrementing.

                    EDIT: I wanted to add that the purpose of the iterator pattern is to abstract away from dealing with indices, which can be problematic as the article does point out. You will find many languages supporting this to one extent or another, an example being Java.

                    1. 1

                      Ah, ok, pointer arithmetic can work in some cases. I have written quite some loops that are basically while (p < endp). Although for the troublesome scenario, working backwards, it’s not always any better because while a pointer one past the end is legal, a pointer one before the beginning is not. (And not all loops iterate over basic arrays.)

                      1. 1

                        We got you covered here too.

                        rbegin and rend do the same thing as begin and end, except they operate in reverse. So rbegin is the last item, and rend is one before the beginning — yet operate in the normal way with ++.

                        vector<int> array { 3, 6, 8, ... };
                        int sum = 0;
                        for (auto &&it = rbegin(array); it != rend(array); ++it) {
                            sum += *it;
                        }
                        

                        Now C++ doesn’t actually define what the end iterator has to be, but it is clear that you do not dereference it under any circumstances. The power of these things amazes me sometimes.

                        1. 1

                          I think tedu’s saying that while C++ reverse iterators may work in C++, he can’t solve his problem in C the same way, because a pointer one before the beginning isn’t legal C even if you don’t dereference it. I don’t know C inside and out myself; that’s just how I read the comment you’re replying to.

                          If you’re saying he should be writing C++ rather than C to be able to use iterators, you probably won’t get far with that.

                          1. 1

                            You are correct, it appears that C++ reverse iterators are really just adaptors around regular iterators.

                            I do not advocate C++, just observing a useful pattern that got its start in C and now used all over the place in a more general way than its original.

                      2. 1
                        int *last = &array[10];
                        

                        Isn’t this undefined behavior when the array only has 10 elements? (even when the 11th element is never dereferenced)

                        1. 2

                          It is not undefined behaviour.

                          int *last = &array[10];
                          

                          Is the same as:

                          int *last = array + 10;
                          

                          The undefined behaviour would be beyond the one past the end.

                          In section 5.7 of the N3797 draft it says:

                          Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

                          So there are limits to where you can add or subtract. Further I was able to find

                          begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container.

                          From section 23.2.1 of the N3797 draft. The ‘past-the-end’ value is not defined anywhere, but for an array or a vector it could easily be implemented directly as adding one to the last pointer in the container.

                          1. 1

                            Ah, thanks. I remembered there was some undefined behavior possible here during pointer arithmetic, turns out it’s for when comparing pointers to different array objects.

                            I knew that the end iterator in c++ always “pointed” one beyond the last element but figured it was implemented as just an index.

                            1. 1

                              Well, you might actually be able to find a container where the iterator itself would be best implemented that way. That is certainly the benefit of the abstraction.