"Arjan van Staalduijnen" <<Arjan.van.Staalduijnen[at]rtl.nl>> wrote:
> Hopefully properly answering one of my own questions:
>
>> In this case I was using the multiset as a 'single entry per index
>> only', so the ids[ identifier ] = 1/0 should work just fine for me.
>> Instead of a multiset which sets a specific index to 1 or 0, I
>> could use a mapping and the same construction, using m_delete
>> instead of the setting to 0. Would there be a difference in impact?
>
> Multiset would be faster, because it would only have to do a single
> memory dereference for the index, instead of two for a mapping; one
> for the index, one for the value. If there'd be more differences,
> I'd still be happy to learn about them. :-)
I'm not sure what you mean with those memory dereferences, but if you
want an indexed container without duplicates and where the values
aren't significant then I'd say that a mapping is generally faster.
It's a hash table, and as such people usually consider it O(1) for
lookups. A multiset is a binary tree which has O(log(<size>)) for
lookups.
I often use mappings for such things, and just store a 1 in the value.
E.g:
mapping(MySomething:int(1..1)) my_set_of_stuff = ([]);
// Code to dig up a set of MySomething's that I want to do
// something with.
...
foreach (....)
foreach (....) {
....
if (!my_set_of_stuff[x]) {
...
my_set_of_stuff[x] = 1;
}
}
...
// Now I can iterate over the set of MySomething's.
foreach (my_set_of_stuff; MySomething x;)
werror ("%O\n", x);
|