Am Sat, 01 Jun 2013 23:20:19 +0200
schrieb "renoX" <renozyx@gmail.com>:

> On Saturday, 1 June 2013 at 18:23:31 UTC, Mehrdad wrote: [cut]
> >
> > You shouldn't be using 32-bit indices on x64, that defeats the whole point of x64.
> 
> Some would disagree: have a look at x32:
> http://en.wikipedia.org/wiki/X32_ABI
> Being able to use efficiently 64 bit doesn't mean that you *have*
> to use 64bit when 32bit is enough..
> renoX

No wait, the whole 'efficiency' point was that on x64 you don't have to waste memory with the native word size for indexes, but can go with 32-bits. So it saves memory.

But Mehrdad argued that we have x64 to be able to address beyond 2^32 (bytes, items, objects). And 32-bit indexes in generic code are thus asking for overflow bugs on x64 one day.

x32 adds nothing to the discussion as you'd always use 32-bit indexes there. There is no point in storing more than 2^32 items when the address space is 32-bit. (Exceptions: bit arrays, file offsets, etc.)

-- 
Marco

On Sat, 01 Jun 2013 04:11:59 -0400, bearophile <bearophileHUGS@lycos.com> wrote:

> David Piepgrass:

>> In fact, most STL algorithms require exactly two iterators--a range--and none require only a single iterator<
>
> I think there are some C++ data structures that store many single iterators. If you instead store ranges you double the data amount.

This is true.  In dcollections, I have the concept of cursors.  These are 1 or 0 element ranges (they are 0 after the first popFront).  For almost all cases, they require an extra boolean to designate the "empty" state.

So while not consuming 2x, it's more like 1.5x-ish.  Because of alignment, it pretty much requires 2x.  There have been suggestions on utilizing perhaps unused bits in the pointer to designate the empty flag, but I'm a bit aprehensive on that, especially if the node is GC-managed.

But besides the space requirements the *concept* of a single-element pointer is very much needed.  And cursors fill that role.

As an example, std.algorithm.find consumes a range until it finds the specific value.  It then returns a range of the remaining data.  But what if you wanted the range of the data UNTIL the first value?

In std.container, we have three functions to deal with this, upperBound, lowerBound, and equalRange.  But even with these, it can be difficult to construct intersections of these two ranges.

In dcollections, we have one function, find, which returns a cursor.  Then using the cursor, you can construct the range you need:

auto r = mymap[mymap.find(5)..$]; // opDollar not supported yet, but will be.

auto rbefore = mymap[mymap.begin()..mymap.find(5)];

All of this is safe and correct, and I think it reads rather well.

There are other good places where single-element ranges are useful.  It is important to note that a cursor is NOT equivalent to a range of one element.  Such a range in a node-based container has two node pointers.  A cursor MUST only point at exactly one element.  This is important when considering cursor invalidation -- removing an element unreferenced by a cursor should not invalidate that cursor (depending on how the container is structured).  For example, adding a new value to a hash set, or removing an unrelated value from a hash set may invalidate all ranges, but not cursors.

-Steve

On 05/31/2013 11:17 PM, David Piepgrass wrote:
> I'm adding D-style ranges to my new C# collections library. In case
> anyone would like to comment, please see here:
>
> http://loyc-etc.blogspot.ca/2013/06/d-style-ranges-in-c-net.html

(I wrote the following comment on the blog page but it is not visible at this time.)

Thank you for writing this.

I think the range article that you mentioned is Andrei Alexandrescu's "On Iteration":

  http://www.informit.com/articles/article.aspx?p=1407357

Ali