Need for (C++20) Contiguous Range

Ola Fosheim Grøstad ola.fosheim.grostad at gmail.com
Fri Oct 9 17:09:44 UTC 2020


On Friday, 9 October 2020 at 16:57:52 UTC, Steven Schveighoffer 
wrote:
> The question is, would there be any purpose to returning 
> something OTHER than a slice for unordered? And I don't mean, 
> you happen to get benefits because it's sequential, it has to 
> be something that the algorithm will do differently because it 
> sees it's a special type.

Yes, at least the following:

1. alignment guarantees (so you don't have to check that at 
runtime)
2. min-size guarantees (e.g. all slices are at least 2 elements)
3. annotation of elements being valid or not (scanning hashtables 
etc)
4. other guarantees (not-null, not-Nan etc)

You also have the bitsequences/masks I've mentioned that could be 
more extensive, giving various qualities of the slice, so that 
you can scan faster without even loading the data. Both point 3.) 
and 4.) could be bitmasks.

There are also some compression techniques that provide 
skip-pointers. Kinda like skip-lists:

https://en.wikipedia.org/wiki/Skip_list

There are certainly many interesting possibilities, but I think 
bitmasks would go a long way (with the option to skip all-zero 
masks).




More information about the Digitalmars-d mailing list