Re: [Boost-users] [BGL] unordered_set<std::vector<edge_descriptor> >

Subject: Re: [Boost-users] [BGL] unordered_set<std::vector<edge_descriptor> >
From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2009-04-30 10:30:33

On Thu, Apr 30, 2009 at 1:48 PM, Andrew Sutton
<andrew.n.sutton_at_[hidden]> wrote:
>> >> My main issue is to use as few memory as possible, because there will
>> >> have a lot of paths in the set. Any idea?
>> >
>> > How many is a lot? Do you know the number before hand?
>>
>> At least 1e7 paths. And the path size (i.e,
>> vector<edge_descriptor>.size()) is about 10 elements.
>>
>> >
>> > If the order really doesn't matter and  you don't need the associative
>> > properties of a hash table, I'd stick with a list. for forward_list (for
>> > less memory, but no reverse iteration).
>>
>> I do need the associative property. Basically, I will draw a lot of
>> paths and I'd like to know the number of *different* paths I've drawn.
>
> That does seem like a fairly large number :) In that case unordered_map
> should work fine (it's basically the same as hash_map). you might want to

You mean unordered_set, don't you?

> pre-seed it with a large initial (prime) number of buckets to avoid a lot of
> rehashing.

Hum... I don't know this specificity about hashing... I should read
the documentation, but thanks for the information ;)

>
> You can use the Boost.Functional/Hash library to create a hash function for
> paths. That library has some support for computing combined hash keys. There
> may even be an overload for vector, but I'm not sure.
>

Thanks. That's exactly what I'm looking for!

Best,
-- 
Johan