hashed array?

[Dmitry Olshansky]

11/12/2012 8:52 PM, Joseph Rushton Wakeling пишет:
> On 11/12/2012 05:27 PM, Dmitry Olshansky wrote:
>>> The current "workaround" is to just dummy it.
>>> alias bool Dummy;
>>> Dummy[string] names;
>>> names["Paul"] = true; //Ew.
>>
>> Make a wrapper?
>
> The problem with wrapped versions of associative arrays is that they
> just don't scale with number of keys.  If I want to store (say) a set of
> 3 million size_t's, then it costs a lot more than 3_000_000 *
> size_t.sizeof() to do so this way.
>
> Do dedicated set implementations do better than this?

Yes, sure they can. Starting with e.g. a bitset.
If the distribution is sparce then inversion lists can do wonders. They 
work especially well if your distribution has contiguous intervals, 
searching would be logN though.

I use one for unicode character sets and it saves a LOT of space.

Otherwise if it's sparce but doesn't have contiguous interval it seems 
entirely doable to combine the two in a universal datastructure for 
integral sets. Say a sorted array of 32/64-element bitsets (depending on 
architecture):

//denotes a small bit set covering interval of [start..start+32/64)
struct node{
	size_t start;
	size_t bits;
};

Should be quite compact & fast.

>
> I should say that my own interests in an implementation of set are
> twofold -- first, efficient storage; and second, being able to do an
> efficient foreach across the stored values, without any concern for order.
>
>> Or rather call them sets and have them in the library.
>
> The whole builtin-vs.-library thing seems a big distraction -- if
> something needs to be implemented, the library seems the natural place
> unless there's a very good reason otherwise.


-- 
Dmitry Olshansky