9 ms·

Other advantages of zero based indexing, beyond being 'closer to the machine': It works better with the modulo operator: `array[i%length]` vs `array[(i+length-

• msdrigg 4y ago
  This is the reason I always think of when I hear the question
• bluetomcat 4y ago
  A disadvantage comes to mind. While the following loop works as expected: for (size_t i = 0; i < length; i++) ... The following causes an unsigned integer underflow and is an infinite loop: for (size_t i = length - 1; i >= 0; i--) ...
  • ncmncm 4y ago
    If you have foolishly turned off -W in your build system, that could happen. Otherwise, you get a nice warning pointing out your folly.
  • 10000truths 4y ago
    for (size_t i = 0; i < length; i++) { size_t j = (length - 1) - i; ... } EDIT: change i to j
    • yuliyp 4y ago
      That's quite broken (you'd want a different variable inside the body, vs clobbering the iteration counter, else this would process the last item in your list, then exit).
    • unwind 4y ago
      Uh no don't reassign the loop variable in the inner scope. Use: const j = (length - 1) - i; in that case. Much safer.
    • rabbidruster 4y ago
      I hope you haven't done this anywhere. Makes my brain hurt, but I think this will only run through the loop one time looking at the last element of the array.
    • Banana699 4y ago
      You should save the old value of i somewhere and restore it back at the very end of the loop. Or simply define a new j like another comment says.
  • xxs 4y ago
    the correct way/idiom to reverse iterate an array is for (size_t i = length; i-- > 0; )... It's surprising how often the issue pops, it works well with both signed and unsigned integers. (edit) I've started with one based indexing (basic)... mixed with 0 based (assembly), more 1 based (pascal), then more stuff (all zero based). I am, yet, to see a real advantage of a one based indexing... after the initial process.
    • empiricus 4y ago
      Is this cache friendly?
      • msk-lywenn 4y ago
        It’s not. It was nice on architectures were cache didn’t matter much and were subtracting and comparing to zero was just one instruction (looking at you old core ARM)
      • sgtnoodle 4y ago
        Sure, why wouldn't it be? As far as a cache is concerned, I don't think reverse sequential iteration would be any different than forward sequential. The actual RAM accesses may be less optimal if there's some speculative pre-fetching with assumed forward sequential access, but that's conjecture.
        • chii 4y ago
          i would suspect that the cache prefetch/prediction could use the "velocity" of the memory access to predict the next access; so if the access pattern was going backwards, the "velocity" would be negative, but prefetching would still work if they just followed the predicted pattern.
        • ehvatum 4y ago
          With some exceptions, hardware prefetch works in terms of ascending accesses. To learn if a particular CPU will prefetch for descending access, benchmarking is essential. Best to use soft prefetch calls if performance is critical.
  • operator-name 4y ago
    In that specific case I'd do the following: for (size_t i = n; i-- > 0 ;) ... Or count from `length` to 1, but subtract 1 in the loop body, or count up and subtract the length in the loop body. Any modern compiler should be able to optimise these to be equivalent. In the majority of cases, counting down is not necessarily. Nor is ordered iteration. Most languages have a `for each` style syntax that's preferable anyway.
    • cylon13 4y ago
      Ah yes, the goes-to operator -->
      • tomjakubowski 4y ago
        And the wink operator, so the compiler knows you know the deal
        • wizofaus 4y ago
          Gold - have an upvote!
        • bmacho 4y ago
          I like how GP is called "operator-name" and instead of doing himself, he makes others joking with operator names. Although I'm not sure if it's altruism or highly manipulative behaviour.
    • divbzero 4y ago
      Or alternatively: size_t i = length; while (i--) ...
      • jecel 4y ago
        Unless I am remembering C wrong, this would work but the for (size_t i = length; i-- > 0 ; ) ... that several other people posted would not execute for index 0. Shouldn't it be this instead? for (size_t i = length; --i > 0 ; ) ...
  • mananaysiempre 4y ago
    As Jens Gustedt points out[1], the following intentional unsigned overflow works perfectly for downwards iteration (even when length is 0 or SIZE_MAX), though it looks a bit confusing at first: for (size_t i = length - 1; i < length; i--) ... You are also free to start at any other (not necessarily in-bounds) index, just like with ascending iteration. [1] https://gustedt.wordpress.com/2013/07/15/a-praise-of-size_t-and-other-unsigned-types/ https://gustedt.wordpress.com/2013/07/15/a-praise-of-size_t-...
    • xxs 4y ago
      the footnote [1] should be [0], just for the sake of this very topic. Seriously though, while the idiom does work for unsigned integers, it's a bad idiom to learn [makes code reviews harder]. The post-decrement one in the loop body works with everything (signed/unsigned), and it's well known.
    • 411111111111111 4y ago
      Uh I'm confused but don't know c++. why doesn't that loop end instantly? I mean length - 1 < length should always be true, right? Or does it only terminate when the number underflows? Terribly confused here
      • msk-lywenn 4y ago
        It’s a condition to run, not a condition to stop
        • wizofaus 4y ago
          That was my reaction - why should anyone think it might be the latter? Are there languages that do have such a syntax without explicit keywords ("do...until")?
          • msk-lywenn 4y ago
            I think lisp or scheme does. I was often confused by that when I was playing with it
  • bregma 4y ago
    In the C programming language unsigned integers do not overflow. They wrap. This is well-defined behaviour and the example code is simply incorrect. Most modern compilers will give you a diagnostic for this.
  • nemetroid 4y ago
    Unless wrapping underflow is sensible for the domain (which it isn’t when representing the size of something), unsigned integers are usually a bad idea.
  • deleted 4y ago
    [deleted]
  • pwdisswordfish9 4y ago
    You can always rip a page out of C++’s playbook: for (size_t i = length; i > 0; i--) { // ... item = array[i - 1]; (This is how reverse iterators work in C++.)
• mananaysiempre 4y ago
  A rare case where 1-based indexing is more convenient is complete binary trees laid out breadth-first (as in a standard binary heap): parent is i div 2 and children are 2i and 2i+1 when starting at one and who knows what when starting at zero. But that’s the only one I know.
  • btilly 4y ago
    With 0-based indexing the children are at 2i+1 and 2i+2. The parent is at (i-1) div 2. Not hard to figure out.
    • JadeNB 4y ago
      > With 0-based indexing the children are at 2i+1 and 2i+2. The parent is at (i-1) div 2. > Not hard to figure out. While that's true, "you just shift by 1" is equally good at all arguments for or against 0-based indexing, so deploying it here probably won't convince.
      • btilly 4y ago
        I was not trying to convince. That said, the effort of one versus the other is so trivial that there is no point in ever using effort as an argument either way. Doubly so because what seems like effort to us is simple unfamiliarity. What is important is which one leads to more careless errors in practice. As a trivial example, consistent indentation takes effort, but failing to do it leads to more careless errors. Therefore everyone indents code. The only data point I've seen on that is the side remark about Mesa in https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/E.... That remark, therefore, is the only argument that I care about.
  • wizofaus 4y ago
    Except 1-based indexing is what we use in normal language. We don't use "zeroeth" or "player (number) zero" etc. And the word "first" is shortened to 1st etc. Personally I think we'd be better off if programming languages stuck to the same convention - off-by-1 errors aren't the hardest problems to deal with but they're still annoying.
• tabtab 4y ago
  In many domains code maintenance is more important than hardware costs. In many domains 1-based indexing is a better fit, meaning less conversion code, meaning simpler code. Thus, the best indexing choice depends on the domain and circumstances, as do many controversial questions. Most tend to specialize in specific kinds of domains and over-extrapolate their experience into other domains.
  • wizofaus 4y ago
    I'd agree so why did languages that allow specifying the base die (other than maybe VBA).
    • btilly 4y ago
      Because changing the base is a great source of bugs. That said, not all languages have given up on this. For example Julia allows it. https://docs.julialang.org/en/v1/devdocs/offset-arrays/ https://docs.julialang.org/en/v1/devdocs/offset-arrays/ Ironically I learned this from a discussion of Julia bugs. Apparently changing offsetting of arrays has proven to be a source of bugs in Julia. So maybe someday they will come to the same conclusion as languages like Perl and stop allowing it.
      • wizofaus 4y ago
        I'd argue 0-base is a source of bugs too! Ideally we'd be able to catch more array indexing bugs at compile time - there are definitely cases where it should be possible to determine that arrays are being incorrectly indexed via static analysis.
        • btilly 4y ago
          The problem is that libraries which assume 0-base break when you have a 1-based array. And vice versa. Trying to combine libraries with different conventions becomes impossible. Therefore changing the base leads to more bugs than either base alone. That said, the more you can just use a foreach to not worry about the index at all, the better. Of 0-based and 1-based, the only data point I have is a side comment of Dijkstra's that the language Mesa allowed both, and found that 0-based arrays lead to the fewest bugs in practice. I'd love better data on that, but this is a good reason to prefer 0-based. That said, I can work with either. But Python uses 0-based and plpgsql uses 1-based. Switching back and forth gets..annoying.
• youor 4y ago
• OscarCunningham 4y ago
  I think the 1-indexing folks would have to argue that a%b should return a value from 1 to b inclusive. This does make the same sort of intuitive sense as 1-indexing. For example we number clocks from 1 to 12.
  • vore 4y ago
    % is defined as (mostly) a remainder operator. I don't think you want to change the semantics of division itself.
    • OscarCunningham 4y ago
      Right. Ultimately the 1-indexers are wrong.
  • black_knight 4y ago
    But interestingly, the number at the top is 12, not 1.
  • cryptonector 4y ago
    12 is zero, in 12-hour clocks.
  • pvinis 4y ago
    No we don't. Clocks start at 0. what time is it when it's half an hour after midnight? 00:30.
    • chii 4y ago
      but nobody "says" zero o'clock - it's always twelve o'clock! and the example is in 24hr format - which needs to have the 00 to differentiate it from being 12:30. But if you write in 12hr format, you don't ever use 00 - it's always 12:30am or 12:30pm
      • pvinis 4y ago
        First of all, you don't. Or I guess most Americans don't. I do, or most Europeans do. 12.30am and 12.30pm feels just very wrong in Europe. But yea, I do agree with you. we don't say 0, we say 12, no matter if it's noon or midnight. That's because we humans avoid saying zero when we mean zero. It's the same with other comments here, talking about counding seconds, we say "ok go, one, two,.. and not "zero, one, two,..". We say 3 months old baby, and not 0 years old baby. We use 0-index in so many things, we just avoid saying the word "zero", and we use other names or other units to avoid that word.
• armchairhacker 4y ago
  Another advantage is with ranges: 0-based indexing and exclusive ranges work well. This is apparent with cursor position in text selection Consider: Characters h e l l o Cursor index 0 1 2 3 4 5 Char index 0 1 2 3 4 Range [0,3) [0,1,2] Range [2,5) [2,3,4] Range [1,1) [] If we used 1-based indexing and exclusive ranges, it leads to ranges where the end index is greater than the string's length... Characters h e l l o Cursor index 0 1 2 3 4 5 Char index 1 2 3 4 5 Range [1,4) [1,2,3] Range [3,6) (!) [3,4,5] Range [2,2) [] but if we use inclusive ranges, it leads to ranges where the end index is less than the start index... Characters h e l l o Cursor index 0 1 2 3 4 5 Char index 1 2 3 4 5 Range [1,3] [1,2,3] Range [3,5] [3,4,5] Range [2,1) (!) [] Also: Characters h e l l o Cursor index 0 1 2 3 4 5 0-based range [0,3) [0,1,2] 1-based range [1,4) [1,2,3] for the 0-based range [0, 3), the left array bracket is at cursor index 0, and the right bracket is at index 3. With 1-based indexing it doesn't work like that because the range is [1, 4)
  • samatman 4y ago
    This is the bane of my existence working with Lua. Iterating an array or adding to the end are fine, we have ipairs and insert for that, but ranges on strings I'm constantly having to think harder and write more code than necessary. I love the language, wouldn't trade it for another, but the 1-based indexing on strings, which represents an empty string at position 3 as (3,2), it's egregious. Not as egregious as a dynamic language where 0 is false though.
    • chii 4y ago
      > a dynamic language where 0 is false though. well, C also considers 0 being false (and you can argue that C is "dynamic"!).
  • yccs27 4y ago
    Yeah, offsets are just easier to mathematically manipulate than ordinals. It's not just pointer arithmetic where it matters that item i corresponds to start+i*step. Any time you want to convert between integer indices and general linearly-spaced values, 0-based indexing is more convenient.