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

Subject: Re: [Boost-users] [BGL] unordered_set<std::vector<edge_descriptor> >
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-04-30 07:48:01

>
> >> 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
pre-seed it with a large initial (prime) number of buckets to avoid a lot of
rehashing.

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.

Andrew Sutton
andrew.n.sutton_at_[hidden]