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 04:03:35

On Wed, Apr 29, 2009 at 6:58 PM, Andrew Sutton
<andrew.n.sutton_at_[hidden]> wrote:
>
>>
>> I want to keep a set of paths, which are implemented as a vector of
>> edge_descriptor. I don't care about the order. I just have to add
>> paths and be able to know the number of different paths present in the
>> set.
>>
>> So, I plan to use unordered_set but I'd like to know you opinion about
>> a hash function, since AFAIK, unordered_set is like an hash_set?
>>
>> 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.

-- 
Johan