- Boost - lists.boost.org

C++ random container
by AngleWyrm 02 Sep '04

02 Sep '04

A proposal for inclusion into the boost libraries: ----------------------------------------------- The hat container derives it's name from the act of pulling names from a hat. It is a container which provides random selection of it's contents, where the items can have differing probabilities, and can either be removed like cards from a deck, or come up again like rolling dice. Rationale ======= There are easy ways to generate uniform chance containers. If one wishes to roll a die, it's a simple matter of scaling a random number to the appropriate range, and then picking from an ordered set. If one wishes to draw cards from a deck, then it is also easy to place all the cards in a container and perform a random_shuffle, then take as many as desired from one end. In 1977, A.J. Walker published a method for the non-uniform first case, in "An Efficient Method for Generating Discrete Random Variables with General Distributions" to the ACM, and Donald Knuth, in his second volume of The Art Of Computer Programming, "Seminumerical Algorithms" presents an implementation of Walker's alias algorithm. This alias technique is very efficient when the probability distribution is fixed before selection, and answers a large subset of uses. It performs in constant time, once a table has been set up, which requires linear time. But there is still one class of problem left out. In the case where the distribution changes dynamically as choices are added to or removed from the set, the above technique must recalculate a lookup table for each insert/delete operation, a linear-time operation. Examples of this problem space are: Drawing lottery balls, random selection from a changing client list, or situations where a random sample is taken before all data is gathered. The hat container provides a solution for all four of the above scenarios: uniform and non-uniform distributions, both with and without replacement. Furthermore, it performs these functions with a time complexity of O( log n ). -:|:- AngleWyrm hat container and documentation at http://home.comcast.net/~anglewyrm/hat.html

4 3

RE: Serialization questions
by Robert Ramey 02 Sep '04

02 Sep '04

> Hello again, > > I have started using your serialization library. It is working pretty > well, but I have run into a few small problems: > > 1) No serialization for bitset: No big deal, because I can just > convert to ulong, but I was surprised it wasn't there. Feel free to add it in along with a test. I would like to see people adding serialization bit by bit to the existing data structures as the need becomes apparent. We're coming to the view that these things should be added to the data structures themselves rather than the serialization library. I'm trying to get myself out of the business of serializing things. > > 2) I have a text archive with a bunch of pairs of strings. I want to > append another pair. There doesn't seem to a way to append items > to an archive. LOL - an interesting question that only recently - (in the last couple of months) occurred to me. There is no reason that you can't create an archive and just append to it as many times as you see fit. Oa << t; ... Oa << t; EXCEPT that the t (and its constituents) should have its serialization trait set so that memory tracking is turned off. Otherwise, copies subsequent to the first one won't copy any data - just a pointer to the original. I have considered making and testing an example of such a thing, but I've been busy. To support this and make a good example what is really needed is: a) another archve construction flag - "no_tracking" to suppress memory tracking for the archive regardless of the setting for each individual type. b) serialization added to boost::any and/or boost::variant. Probably doable but maybe a little tricky. In this way one could just save willy-nilly anything to the archive and load later. This would be very interesting for things like database transaction logs which want to implement rollback/rollforward and things like that. It would also make a dynamite log for debugging. Again, feel free to explore this at your leisure. > 3) similarly, if I'm reading items from an archive, there is no simple > way to keep reading until the end of the file. I have to catch the > exception, which seems wrong for such an unexceptional > circumstance. Setting a fail bit as with streams would be nicer. Checking the fail bit on the stream before reading the next archived item should work. It's intended to anyway. If it doesn't work it's a bug. There might be a little tweaking required as I didn't test for this specifically. If you try this and it doesn't work and you find the oversight let me know and I'll add the fix. Better yet, make and test a small test and submit it to me and I'll add it into the test suite. > However, you could take the view that you should always know what > is in the archive, and to have a method of failure that does not > throw an exception would invite errors. That suggests that a > constructor flag might work (e.g. throw_on_eof default to true). I recently discovered that one can set a flag on an input stream so that an attempt to read past eof will throw an exception. This would leave all options open. After learning ths I'm considering removing the code that checks the fail bit as I would like to leave the flexibility for the user and make the serialization library smaller. BTW the fail bit means - "the next operation is expected to fail", NOT "the last operation failed". This confused me for quite a while until I actually carefully read the documentation for stream rather than presuming what I thought was obvious. > 4) A minor point: It would be nice to be able to construct an archive > with a boost::filesystem::path, instead of creating an fstream and > then using that to create the archive. It is certainly nice that I > can attach an existing stream to an archive, but directly using a > path would reduce some clutter. It would also make it a little > safer, because I couldn't accidently insert something into the > stream that was not serialized. Feel free to make your own - it should be trivial exercise. It should be easy to do deriving from any of the current archives. Polymorhphic archive works this way. Its one template that "adapts" any archive it's applied to. Also the current setup is specifically designed to permit serialized data to be embedded within some other data stream if the user requires it. I haven't specifically tested this either. > I have read large parts of the discussions when you were submitting > your library, but not all. If I have missed something, you can just > point me to it. Seems like you've pretty much got it. The thing that takes special care is the serialization of pointers through abstract base pointers. This works fine but there are a couple of non-intuitive aspects that can trip you up. The manual is pretty complete. This is mostly because I kept adding to it as questions kept coming up on the list. So I would hope that one can understand and use the package without going back and trolling through the list. If you don't mind, I'm posting this to the list. Your questions are interesting, good grist for the list, and help diminish the frequency of the same questions getting asked multiple times. Robert Ramey

2 1

IOStream mmap too restrictive?
by Neal D. Becker 01 Sep '04

01 Sep '04

"Files must exist before being opened, and are never truncated; attempting to write past the end of a file results in an error. " This is quite restrictive, compared to the capabilities of posix mmap. Are these restrictions really necessary?

2 3

lambda; ->*
by Goran Mitrovic 01 Sep '04

01 Sep '04

Is it normal that boost lambda's member pointer operator fails on member functions that have throw() modifier? Compiler is VC7.1. Is there a solution?

1 0

integer tests not working on 64 bit platforms
by Markus Schöpflin 01 Sep '04

01 Sep '04

Currently the integer tests report an error on 64 bit platforms, as can be seen on http://tinyurl.com/6whtg The following code in integer_test.cpp causes the problem: PRIVATE_FIT_TESTS( int_t, least, long, LONG_MAX ); PRIVATE_FIT_TESTS( int_t, fast, long, LONG_MAX ); PRIVATE_FIT_TESTS( uint_t, least, unsigned long, ULONG_MAX ); PRIVATE_FIT_TESTS( uint_t, fast, unsigned long, ULONG_MAX ); The first line expands to: do { long v = LONG_MAX ; PRIVATE_FIT_TEST(int_t, 32, least, v); v >>= 1; PRIVATE_FIT_TEST(int_t, 31, least, v); v >>= 1; ... } which becomes: do { long v = LONG_MAX ; BOOST_TEST( int_t < 32 > :: least ( v ) == v ); v >>= 1; BOOST_TEST( int_t < 31 > :: least ( v ) == v ); v >>= 1; ... } which of course alway fails on 64 bit platforms because LONG_MAX is a 64 bit number. A possible fix would be to start the test with 64 bit and not 32 on 64 bit platforms. But how can 64 bit platforms be detected? Probably with #if (LONG_MAX > INT_MAX) ... #endif or something like this. Another fix (which ignores 64 bit values alltogether) would be to change the lines above to not use long and LONG_MAX but int and INT_MAX. Opinions, anyone? Markus

3 2

Boost::Python exception translation not working?
by Dan 01 Sep '04

01 Sep '04

I attempted a simple exception translation that was almost an exact copy of the examples in the docs. struct MySQLException : public std::exception { MySQLException( const char * what = "MySQL Exception" ) : std::exception( what ) {} }; And then in a class's default constructor I throw this exception. I tried exposing it as both a function and a functor: void mysql_translate( MySQLException& e ) { PyErr_SetString( PyExc_RuntimeError, e.what() ); } BOOST_PYTHON_MODULE(pymysql) { // regular expression translation py::register_exception_translator< MySQLException >( &mysql_translate ); } And... struct mysql_translate { void operator ()( const MySQLException& e ) const { PyErr_SetString( PyExc_RuntimeError, e.what() ); } }; BOOST_PYTHON_MODULE(pymysql) { // regular expression translation py::register_exception_translator< MySQLException >( mysql_translate() ); } Both had the same result when I created the exported object. "RuntimeError: unidentifiable C++ exception". What am I doing wrong? Thanks, -Dan

2 4

Re: [boost] CodeWarrior and alignment_of (help!)
by JOAQUIN LOPEZ MU?Z 01 Sep '04

01 Sep '04

----- Mensaje original ----- De: Doug Gregor <dgregor(a)cs.indiana.edu> Fecha: Miércoles, Septiembre 1, 2004 6:46 pm Asunto: [boost] CodeWarrior and alignment_of (help!) > Some of the Graph tests are failing on CodeWarrior due to some > strange > interaction within alignment_of, where it doesn't like > mpl::size_t. I > don't have the compiler to test on :( > > Here's one example of the failures: http://tinyurl.com/4dapg > I think current results are built from a CVS merge in progress by Aleksey, and as such one shouldn't pay them too much attention until they're stabilized. The particular problem you refer to has to do (I think) with some haeder making the symbol size_t ambiguous; this pops with variations in other tests. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

tuple and std::set question
by Trey Jackson 01 Sep '04

01 Sep '04

All, I was trying to use the tuple in a set, and the STL complained about not having an operator&() - I think. My question is, is tuple supposed to be usable in a set? I read the STL docs: no mention of operator&() required. I tried both STLport and gcc's stl. I'm using gcc 3.2.2, and the snippet of code is real easy: ,---------------- | #include <boost/tuple/tuple.hpp> | #include <set> | | using namespace std; | | using namespace boost; | | int | main(int, char *[]) | { | typedef tuple<int, int, int> Things; | | std::set<Things> mySet; | | Things oneThing(1,2,3); | mySet.insert(oneThing); | | return 0; | } `---------------- tia, TJ -- Trey Jackson tjackson(a)ichips.intel.com "Nobody can give you wiser advice than yourself." -- Cicero

2 2

Nightly CVS documentation
by Jurko Gospodneti� 01 Sep '04

01 Sep '04

1 0

regression tests broken?
by Bronek Kozicki 01 Sep '04

01 Sep '04

I'm no longer able to run regression tests, and quick look at ftp://fx.meta-comm.com/boost-regression/CVS-HEAD/ reveals that few others have this problem too. Apparently bjam is called from regression.py in wrong way, or Jamfile is broken, as bjam.log ends with: don't know how to make None don't know how to make -sALL_LOCATE_TARGET=C:\MinGW\Bronek\boost\results ...found 2 targets... ...can't find 2 targets... B.

3 5