March 2005 - Boost - lists.boost.org

Re: [boost] Re: [review] hash functions
by brangdon＠cix.compulink.co.uk 22 Mar '05

22 Mar '05

In-Reply-To: <003501c52a54$a28c4b90$6601a8c0@pdimov> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > > size_t hash_value( int v ) { > > return size_t(v) + default_seed; > > } > > I wonder what do we gain from this. As you pointed out when I first suggested adding the constant in hash_combine: This would mean N fixes for a sequence of length N, when one simple fix is enough. The initial value of the seed is arbitrary so we can vary it at will. hash_combine, on the other hand, is based on research and has apparently been selected as one of the best amongst the shift+xor family. This doesn't mean that it's sacred, just that if we change it we'll no longer be able to just point at a PDF as a rationale but will need to do our own research (which might be a good idea anyway, though.) :-) > From the point of view of hash_combine the effect is the same The difference shows when you have something like: struct A { int x, y; }; struct B { A a, b, c; }; size_t hash_value( const A &a ) { size_t hash = 0xbead1; hash_combine( hash, a.x ); hash_combine( hash, a.y ); return hash; } size_t hash_value( const B &b ) { size_t hash = 0xbead2; hash_combine( hash, b.a ); hash_combine( hash, b.b ); hash_combine( hash, b.c ); return hash; } Here hash_combine is called 9 times, but hash_value(int) is only called 6 times, so we get different results depending on where the constant is added. > and we now rely on the user overloads of hash_value to not produce > a zero. That's surely reasonable. The hash_value of any user-defined class should be defined in terms of the hash_values of primitives, and boost provides all of those. > This reflects their intended use. The two argument overload is used > when one has a whole range and wants its hash value, as in the > hash_value overload for std::vector, for example. I actually think this is going to be fairly rare. This is mainly because there will usually be a constant thrown in to represent the type of the object. (I appreciate you won't do that for std containers, but I maintain its a good idea for user-defined types.) The 2-argument version is strictly redundant as it must be defined in terms of the 3-argument version. It's just a convenience function, used mainly by the std containers. Admittedly hash_combine is also (nearly) redundant, being definable as: void hash_combine( size_t &hash, const T &t ) { hash_range( hash, &t, &t+1 ); } if T does not overload address-of. Incidently, do you agree we will sometimes want to pass a hash value as the second argument to hash_combine? Like: hash_combine( hash, hash_range( first, last ) ); hash_combine( hash, obj.get_hash( some_arg ) ); If not, then maybe we should have a hash_combine that just combines hashes. At the moment the combining is mixed in with the getting; it's not a very orthogonal API. -- Dave Harris, Nottingham, UK

3 3

Re: [boost] Re: [review results] hash functions accepted
by brangdon＠cix.compulink.co.uk 22 Mar '05

22 Mar '05

In-Reply-To: <d1p2mg$mfk$1(a)sea.gmane.org> nesotto(a)cs.auc.dk (Thorsten Ottosen) wrote (abridged): > There is a small utility in the Pointer Container library which is more > general that hash_ptr ect. You can simply say > > unordered_set< MyType*, indirect_fun< boost::hash<MyType> >, > > indirect_fun< std::equal<MyType set; > > for the rare cases where the index is a pointer. OK. It might be worth mentioning in the documentation. -- Dave Harris, Nottingham, UK

1 0

Re: [boost] Re: [review] hash functions
by brangdon＠cix.compulink.co.uk 22 Mar '05

22 Mar '05

In-Reply-To: <007b01c52ede$3ceefd80$6501a8c0@pdimov2> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > So, in my opinion, your original suggestion is still the best one, even > though I did not seem to agree at first. ;-) OK. > > If not, then maybe we should have a hash_combine that just combines > > hashes. At the moment the combining is mixed in with the getting; > > it's not a very orthogonal API. > > ... yes, hash_value( size_t ) is the identity function partly for this > reason. Cool. (And this is another argument for adding the non-zero fix in hash_combine rather than hash_value.) -- Dave Harris, Nottingham, UK

1 0

Re: [boost] Re: [review results] hash functions accepted
by brangdon＠cix.compulink.co.uk 22 Mar '05

22 Mar '05

In-Reply-To: <004c01c52edb$d07ee5e0$6501a8c0@pdimov2> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > > Is it worth considering using x + x / sizeof(*p) instead? > > This will not work for incomplete types, including void. Good point :-) > I'd prefer equal hash_values for an incomplete T*, complete T*, > and void* with the same value. Indeed. Presumably this means casting to void* eg for the case where sizeof(void*) != sizeof(char *). > We'll lose one potential bit of enthropy when alignof(x) == 16, but > this seems sufficiently rare in practice. I was a bit concerned about cases where the heap produces a de facto alignment. Especially if there is a different pool for each size of object, or a user-defined X::operator new() that allocates from a huge array of X. I guess it can't be helped. -- Dave Harris, Nottingham, UK

1 0

[Boost-bugs] [ boost-Bugs-1168431 ] LEDA graph adaptors do not handle hidden nodes properly
by SourceForge.net 22 Mar '05

22 Mar '05

Bugs item #1168431, was opened at 2005-03-22 10:39 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168431&group_… Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Douglas Gregor (dgregor) Assigned to: Douglas Gregor (dgregor) Summary: LEDA graph adaptors do not handle hidden nodes properly Initial Comment: Hidden nodes are completely ignored by the LEDA graph adaptors. This may cause problems when, for instance, there are hidden nodes but the equivalent of vertex_index is used to construct a (BGL) property map. The LEDA adaptors should probably take the same approach as filtered_graph: let num_vertices() return the number of the nodes in the graph plus the number of hidden nodes, but vertices() filters out the hidden nodes. Similarly for edges. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168431&group_… ------------------------------------------------------- This SF.net email is sponsored by: 2005 Windows Mobile Application Contest Submit applications for Windows Mobile(tm)-based Pocket PCs or Smartphones for the chance to win $25,000 and application distribution. Enter today at http://ads.osdn.com/?ad_id=6882&alloc_id=15148&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[Boost-bugs] [ boost-Bugs-1168424 ] LEDA adaptors for node_array, edge_array
by SourceForge.net 22 Mar '05

22 Mar '05

Bugs item #1168424, was opened at 2005-03-22 10:36 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168424&group_… Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Douglas Gregor (dgregor) Assigned to: Douglas Gregor (dgregor) Summary: LEDA adaptors for node_array, edge_array Initial Comment: LEDA has constructs similar to property maps, called node_array and edge_array, that allow the user to create external mappings from vertices or edges to user-defined data. Both classes are templated over the data type T. The BGL LEDA adaptors should provide a wrapper for these data structures to make them into property maps, so that LEDA graphs and LEDA's form of external property maps can be used with BGL algorithms. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168424&group_… ------------------------------------------------------- This SF.net email is sponsored by: 2005 Windows Mobile Application Contest Submit applications for Windows Mobile(tm)-based Pocket PCs or Smartphones for the chance to win $25,000 and application distribution. Enter today at http://ads.osdn.com/?ad_id=6882&alloc_id=15148&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[Boost-bugs] [ boost-Bugs-1168420 ] LEDA graph adaptors for undirected graphs
by SourceForge.net 22 Mar '05

22 Mar '05

Bugs item #1168420, was opened at 2005-03-22 10:33 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168420&group_… Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Douglas Gregor (dgregor) Assigned to: Douglas Gregor (dgregor) Summary: LEDA graph adaptors for undirected graphs Initial Comment: The LEDA graph adaptors in the BGL seem to work properly for directed graphs (the LEDA type GRAPH<...>), but there are no corresponding adaptors for the undirected LEDA graph type (UGRAPH<...>). Undirected LEDA graphs follow a very different model than the undirected graphs in the BGL, which will require some special machinery. The LEDA type UGRAPH<...> is actually just a class derived from GRAPH<...> that applies the "make_undirected()" member function upon initialization. make_undirected() moves all of the in-edges of each vertex to the out-edges list. This has several unfortunate consequences: 1) The in-degree of an undirected LEDA graph is always zero, even when the out-degree is greater than zero. The in_edges list is therefore empty. 2) When traversing the list of out-edges for a vertex u, the edges returned may have u as their target but not their source. This breaks an important invariant in the BGL, which mandates that source(e, g)==u if e came from out_edges(u, g). Similarly for in-edges. Thus, an undirected LEDA graph adaptor will need to introduce special adaptors for the out_edge_iterator and in_edge_iterator types, which return a new edge_descriptor type for LEDA that can swap the source and target of a LEDA edge as needed. Additionally, graph-mutating operations (such as add_edge) may need to ensure that the graph remains undirected, as if make_undirected() had been called. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168420&group_… ------------------------------------------------------- This SF.net email is sponsored by: 2005 Windows Mobile Application Contest Submit applications for Windows Mobile(tm)-based Pocket PCs or Smartphones for the chance to win $25,000 and application distribution. Enter today at http://ads.osdn.com/?ad_id=6882&alloc_id=15148&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[Boost-bugs] [ boost-Bugs-1168411 ] adjacency_matrix should model BidirectionalGraph
by SourceForge.net 22 Mar '05

22 Mar '05

Bugs item #1168411, was opened at 2005-03-22 10:24 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168411&group_… Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Douglas Gregor (dgregor) Assigned to: Douglas Gregor (dgregor) Summary: adjacency_matrix should model BidirectionalGraph Initial Comment: Class template adjacency_matrix should model the BidirectionalGraph concept. This will require the introduction of an in_edge_iterator that strides across the rows of the adjacency matrix. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168411&group_… ------------------------------------------------------- This SF.net email is sponsored by: 2005 Windows Mobile Application Contest Submit applications for Windows Mobile(tm)-based Pocket PCs or Smartphones for the chance to win $25,000 and application distribution. Enter today at http://ads.osdn.com/?ad_id=6882&alloc_id=15148&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Re: [boost] Re: [review results] hash functions accepted
by brangdon＠cix.compulink.co.uk 22 Mar '05

22 Mar '05

In-Reply-To: <d1na66$6p2$1(a)sea.gmane.org> daniel(a)calamity.org.uk (Daniel James) wrote (abridged): > > 5. change implementation of hash values for pointers so undefined > > behavior is gone (and consider adding x + (x >> 3) ) > > I'm going to do that. Is it worth considering using x + x / sizeof(*p) instead? -- Dave Harris, Nottingham, UK

2 1

Re: [boost] [review results] hash functions accepted
by brangdon＠cix.compulink.co.uk 22 Mar '05

22 Mar '05

In-Reply-To: <d1mq8d$b5q$1(a)sea.gmane.org> nesotto(a)cs.auc.dk (Thorsten Ottosen) wrote (abridged): > 7. the hash_ptr<> suggestion is better done with general indirected > function Did I miss where this was discussed? To recap, we were talking about adding something like: template<typename T> struct hash_ptr { size_t operator()(const T *p) const { return hash_value( *p ); } }; template<typename T> struct equal_ptr { bool operator()( const T *a, const T *b ) const { return *a == *b; } }; to the hash library for use as, eg: unordered_set< MyType *, hash_ptr<MyType>, equal_ptr<MyType> > What do you mean by using a "general indirected function" instead? -- Dave Harris, Nottingham, UK

2 1