- Boost - lists.boost.org

[aligned_storage] problems with GCC 4.0.0 20050309
by Joaquín Mª López Muñoz 11 Mar '05

11 Mar '05

The class aligned_storage in boost/aligned_storage.hpp has the following decl: template < std::size_t size_ , std::size_t alignment_ = std::size_t(-1) > class aligned_storage; GCC 4.0 complains about the default value for aligmnent_ saying that: '(size_t)((-1))' is not a valid template argument for type 'unsigned int' because it is a non-constant expression Is GCC right or shall I submit a bug report at gcc.gnu.org/bugzilla? Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

YALo: Yet Another Logo
by David B. Held 11 Mar '05

11 Mar '05

This should give some idea as to what I think of as a "scalable logo" or a "scale-free logo". It's rather crude yes, but that's partly the point. Instead of rendering the word "Boost" in a nice font of the same or some appropriate color, I shamelessly stole one from another logo. The colors aren't really important, because they aren't the point (a graphic artist could pick much better colors). I don't know if rounded edges are better or straight lines. And perhaps even this example has more angles than I like in a scale-free logo. Perhaps we could even do without the fins, I'm not sure. The angles could be adjusted to be more pleasing. Now some might say: "Well, Rene made an abstract looking rocket too." And that is true. But Rene's rocket has some very subtle features, like the edges near the flames, which is an area of "high entropy" so to speak. My rocket has no detail frills, and could easily be compressed to an absurdly small vector file. Perhaps something with a nonnegative amount of artistic talent could play with the idea a bit without adding too much information to the logo. I realize that the contest is closed, but I'd like to explore a more simplistic direction just to get an idea of some areas of the design space that I don't think have been hit very heavily. I don't intend the word "Boost" to be a necessary part of the logo. I just think that in large-scale contexts, a caption would be nice, whether it be on the side or the bottom or a word or a phrase. Any takers? Dave

2 1

Re: [boost] Re: Re: Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 10 Mar '05

10 Mar '05

Hi Peter, ----- Mensaje original ----- De: Peter Dimov <pdimov(a)mmltd.net> Fecha: Jueves, Marzo 10, 2005 11:51 pm Asunto: Re: [boost] Re: Re: Re: [review] hash functions > JOAQUIN LOPEZ MU?Z wrote: > > > > The idea is that you can alter only some part of the > > hashing scheme and benefit of the preexisting definitions: [...] > > I think I see your point. You want something like this: [...] > will automatically propagate it downwards if one invokes > hash_value on > vector<vector<vector<int> > >. Sort of, I think. Your formulation is somewhat more generic in that you pass combiners around where I rely on tag dispatching (the *_impl markers.) > Interesting, but overkill, IMO. ;-) Can't say the contrary :) I see it as I way to get everybody happy: regular users don't notice the difference and playful ones can easily plug in their superhashing schemes. Anyway. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

Re: [boost] Re: Re: Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 10 Mar '05

10 Mar '05

----- Mensaje original ----- De: Peter Dimov <pdimov(a)mmltd.net> Fecha: Jueves, Marzo 10, 2005 10:35 pm Asunto: Re: [boost] Re: Re: Re: [review] hash functions > JOAQUIN LOPEZ MU?Z wrote: > > > > Maybe the following approach could be taken to > > allow for alternative implementations to be plugged into > > the framework: [...] > > > unordered_set<my_type,boost::hash<my_type,crypto_impl> > us; > > The proposal is not a framework, it contains two simple tools for > constructing hash_value overloads for compound types and a suite > of > _default_ hash functions. > > Alternative implementations (who may or may not use the supplied > tools) are > supported by unordered_set by simply using > > unordered_set< my_type, my_hash > us; > > There's no need to plug them in. The idea is that you can alter only some part of the hashing scheme and benefit of the preexisting definitions: template<typename It> std::size_t hash_range(It first,It last,crypto_impl) { ... } // third_party_type is an external type with its own // hash_value overload unordered_set< std::vector<third_party_type>, boost::hash<std::vector<third_party_type>, crypto_impl> > us; // here, we automatically get an impl of hashing for // strings using the crypto_impl hash_range unordered_set< std::string, boost::hash<std::string, crypto_impl> > us2; But I won't defend this to death :) I just felt like throwing the idea in. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

stl-like containers of pointers
by Felipe Magno de Almeida 10 Mar '05

10 Mar '05

I heard that boost is going to have all the stl-like containers, but with reference semantics and will treat the indirection in the iterators and etc... I would like to know where I can get this. It is not in the cvs either... Thanks in advance, -- Felipe Magno de Almeida UIN: 2113442 email: felipe.almeida at ic unicamp br, felipe.m.almeida at gmail com, felipe at synergy com I am a C, modern C++, MFC, ODBC, Windows Services, MAPI developer from synergy, and Computer Science student from State University of Campinas(UNICAMP). To know more about: Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br current work: http://www.mintercept.com

2 10

Re: [boost] Re: Re: Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 10 Mar '05

10 Mar '05

----- Mensaje original ----- De: Peter Dimov <pdimov(a)mmltd.net> Fecha: Jueves, Marzo 10, 2005 6:01 pm Asunto: Re: [boost] Re: Re: Re: [review] hash functions > Thorsten Ottosen wrote: > > > > so basically you're saying that any collision is much worse than a > > slower hash function because we must use == to go through the > bucket ? > > Something like that, yes; of course it depends on the level of > slowness. > Cryptographic hash functions are typically overkill. Increasing > the number > of collisions slightly is tolerable (but can easily negate the > effect of the > faster hash function). Hitting a pathological case where a > significant > percentage of the key set maps to the same bucket is a serious > problem. > Maybe the following approach could be taken to allow for alternative implementations to be plugged into the framework: struct std_impl{}; template<typename T,typename Impl=std_impl> struct hash { std::size_t operator()(const T& x)const { return hash_value(x,Impl()); } }; template<typename T,typename Impl> std::size_t hash_value(const T& x,Impl impl) { return hash_value(x); } // standard hash_value overloads for integral types and pointers ... // template<typename T,typename Impl> void hash_combine(size_t& seed,const T& x,Impl impl) { seed^=hash_value(x,impl)+(seed<<6)+(seed>>2); } template<typename A,typename B,typename Impl> std::size_t hash_value(const std::pair<A,B>& x,Impl impl) { std::size_t seed=0; hash_combine(seed,x.first,impl); hash_combine(seed,x.second,impl); return seed; } template<typename It,typename Impl> std::size_t hash_range(It first,It last,Impl impl) { std::size_t=0; for(;first!=last;++first){ hash_combine(seed,*first,impl); } return seed; } template<typename E,typename T,typename A,typename Impl> std::size_t hash_value(const std::basic_string<E,T,A>& x,Impl impl) { return hash_range(x.begin(),x.end(),impl); } // same as previous for the rest of STL containers This framework is transparent to the regular user, who never specifies an alternative implementation and can define hashing for her own types as before: std::size_t hash_value(const my_type& x) { //... } unordered_set<my_type,/* boost::hash<my_type> */> us; But the "advanced" user can tweak one or more parts of the hashing framework ad libitum: struct crypto_impl{}; std::size_t hash_value(int x,crypto_impl) { // smart hash for ints } // we modify also range hashing template<typename It> std::size_t hash_range(It first,It last,crypto_impl) { std::size_t seed=0; std::size_t n=1; for(;first!=last;++first){ hash_combine(seed,*first,crypto_impl); seed*=n; // for instance n*=2; } return seed; } unordered_set<my_type,boost::hash<my_type,crypto_impl> > us; What do you think? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

4 3

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

10 Mar '05

In-Reply-To: <d0pe8q$tdi$1(a)sea.gmane.org> daniel(a)calamity.org.uk (Daniel James) wrote (abridged): > But it will be easy to make mistakes for more complicated (possibly > recursive) types. Especially since hash_combine is not associative or > transitive. I could see that leading to mistakes. I can see that it's possible to call the function with the wrong arguments, but that kind of problem can be addressed with documentation and/or by careful naming. I don't think that's worth distorting the interface and introducing side effects and spurious variables and inefficiency to fix it. > And it would be quite easy to forget to call hash_value (because > many types are implicitly convertible to std::size_t) Since that conversion is all hash_value does, why does it matter? That said, I agree the second argument should not be hash value. If we care about the first argument, perhaps the problem could be identified with an overload or specialisation. template < typename T, typename S> size_t hash_combine( S seed, const T &v ) { BOOST_STATIC_ASSERT( false ); } template <typename T, typename S> size_t hash_combine<>( size_t seed, const T &v ) { const size_t c = 0x12345678; // Or some other value. return seed ^ (hash_value(v) + c + (seed<<6) + (seed>>2)); } (I'm not so hot on templates so the above may be wrong, but I hope it conveys the idea.) > size_t my_hash_function(int x[4]) { > using namespace boost; > > return hash_combine( > hash_combine(hash_value(x[0]), hash_value(x[1])), > hash_combine(hash_value(x[2]), hash_value(x[3]))); > } I agree this is wrong. I think: return hash_combine( hash_combine( hash_combine( hash_value( x[0] ), x[1] ), x[2] ), x[3] ); is reasonable and ideally would be supported. > An alternative would be to implement hash_combine as an object. > Something like: > > struct hash_seed { > hash_seed(); > template <class T> void combine(T const&); > std::size_t value() const; > }; > > Then it could initialise itself to whatever it wants. Do you mean the seed should be an object? I can see advantages to that, although it seems like overkill. Adding an optional seed argument to hash_range and/or hash_combine sounds like a good idea, though. -- Dave Harris, Nottingham, UK

3 2

[foreach] and reverse iteration
by Russell Hind 10 Mar '05

10 Mar '05

Is there a way to reverse iterator using BOOST_FOREACH? From a quick browse of the docs, it isn't mentioned. I guess it could be done using a std::pair of reverse iterators, but would it be easy to build a BOOST_REVERSE_FOREACH construct or BOOST_RFOREACH that just runs from rbegin to rend? Cheers Russell

2 1

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

10 Mar '05

In-Reply-To: <018901c52569$ea842610$6601a8c0@pdimov> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > That would be bad because the hash value of the pair (x, y) would no > longer match the hash value of the sequence (x, y). Why is it necessary for pairs and sequences to have the same hash value? They are different things. If it is necessary, we can avoid the problem by fixing hash_range: template <typename It> size_t hash_range( It first, It last ) { if (first == last) return 0x87654321; // Or some other value; size_t seed = hash_value(*first); for (++first; first != last; ++first) seed = hash_combine( seed, *first ); return seed; } This also gives hash_range( &a, &a+1 ) the same result as hash_value(a), which your approach does not. > Do you have a different hash_combine in mind that doesn't suffer from > this problem and is better than the proposed implementation? ;-) > (Keeping in mind that even the current hash_combine is perceived as > slower than necessary, of course.) I had in mind something like: template <typename T> size_t hash_combine( size_t seed, const T &v ) { const size_t c = 0x12345678; // Or some other value. return seed ^ (hash_value(v) + c + (seed<<6) + (seed>>2)); } This costs one extra addition, which can probably be scheduled in parallel with other operations anyway. -- Dave Harris, Nottingham, UK

2 1

[test] missing test file
by Vladimir Prus 10 Mar '05

10 Mar '05

When running "bjam -n" in the libs/test/test directory, I get: don't know how to make <@boost!libs!test!test>foreach_test.cpp Gennadiy, seems like you either forgot to commit that file, or forgot to commit some changes to Jamfile. Can you fix this? - Volodya

2 1