August 2011 - Boost - lists.boost.org

[fusion] pop_back doesn't work on fwd sequences
by Eric Niebler 12 Aug '11

12 Aug '11

The documented requirement of pop_back are wrong. The docs say that pop_back works on Forward Sequences, however the following does not compile: // ERROR fusion::list<int, int> l(1, 2); fusion::pop_back(l); The problem is that the implementation of pop_back uses prior, which only works on Bidirectional Sequences. That's merely a doc problem, but this is a more serious problem: // ERROR fusion::pop_back(fusion::pop_back( fusion::push_back(fusion::push_back(fusion::nil(), 1), 2))); A sequence created by push_back is a Forward Sequence, which means you can't call pop_back on it. I think that's a serious shortcoming. Fusion needs something like MPL's Back Extensible and Front Extensible concepts. http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/refmanual/back-extensible… Unfortunately, this would likely require a redesign of the whole (push|pop)_(front|back) mechanism. -- Eric Niebler BoostPro Computing http://www.boostpro.com

3 21

[Containers] Review
by Phil Endecott 12 Aug '11

12 Aug '11

Dear All, Following are some comments about Ion's proposed Boost.Containers. I have not really reviewed the code, but frankly that doesn't seem necessary: Ion knows what he's doing, much of this code has already been in Boost for a while as part of Interprocess, and much of it is designed to implement standard interfaces. I'll confine my comments to a few words about the documentation, and some observations about the "flat" containers. Regarding the documentation, I believe that it would benefit from: - The "Acknowledgements" page is currently empty. There are various (c) notices in the source referring to sources from which parts of the code may have come. This page should clarify these sources, including any cases where the original code has now all been replaced, and assert that the licenses are all in order. It should also point out the history of the code in Boost, i.e. that parts were previously in Boost.Interprocess, so that anyone with previous exposure to the Interprocess containers is not confused. - A few lines of rationale for stateful allocators would be useful, i.e. pointing out that although the std::allocator has a typedef for pointer the containers can assume it is T*, and the implications of that. (I dealt with all this back in about 2004, and it took me a long time to get up-to-speed with the issues.) - Similarly, some rationale for string (and pointing out how it differs from std::string in the common implementations) would be useful. (Now, I can't even find where it says that it is non-COW. I know that I've seen that written somewhere. A page specifically about string shown on the top-level table of contents would be appropriate.) - The Doxygen reference docs seem to jump to the header docs from the table of contents; I think it would be more useful to jump primarily to the classes. Is this the same issue that I saw in the last review? Regarding the "flat" containers, I've previously posted about this in a couple of threads on this list. I have used this sort of structure in two applications recently: - In the first case, I store read-only (key,value) data in a binary file. I have a utility that prepares this file offline by inserting into a vector<pair<>>. I then sort it, and save the contents of the vector in the file. In the program that uses the data, I memory-map the file. I then have an adaptor class that takes a pair of pointers to the begin and end of the mapped data and permits read-only access like Ion's flat_multimap<>. - In the second case, I have an insert-only key-value data structure. New data is inserted in batches. I have a vector<pair<>> and insert new data at the end; at the end of each batch, I sort the new values and merge them into the body of the vector using std::inplace_merge. Neither of these cases can be implemented efficiently using the current containers. Doing so would need: - Access to the underlying container, at least for reading. - An "adaptor" version that could wrap a pair of pointers to raw memory, or more generally a pair of iterators, at least for reading. - Some sort of efficient batched insert mode. Regarding the batched insert, we have previously discussed the complexity of inserting a range. Fundamentally, however, I don't think it is acceptable to have efficient insertion ONLY in the case of the insert(begin,end) method: it is too common to want to insert several values in a loop without creating a temporary container. I'm not aware of any established (i.e. std:: or boost::) pattern for doing this: class flat_container { void insert(val); // appends at the end of the vector void commit(); // merges new values into the body of the vector }; - Between calling insert() and calling sort(), what do lookups do? Undefined? Only look at old values? Sort-on-demand? - Is there also an "insert one" method? How are the variants named? - What about erase()? - How about a "batch" or "transaction" object?: flat_container c; { flat_container::insert_batch b(c); b.insert(data1); b.insert(data2); } // b's dtor merges new values. A further interesting case is when the new values are already sorted, because insertion can be more efficient in this case: void insert_sorted(iter first, iter last) { resize vector to make space for new items for each new item in reverse order { find the position where it should be inserted using binary chop move old items after that point forward move the new item in behind them } } I could imagine a general insert_batch and a specialised insert_sorted_batch, for example. Anyway, this is all just food for thought really. It would be interesting to hear from other people who have used data structures like this. In my own code I have taken a rather ad-hoc approach, but that is the nature of custom vs. library development: to be useful, a library needs to try to second-guess the requirements of all potential users, yet do so without becoming too complex for anyone to learn. Hopefully there will be some more discussion about some of this, but as far as the review is concerned we should allow Ion to decide what he eventually commits. Regards, Phil.

6 8

[containers] remarks and questions
by Pierre Morcello 12 Aug '11

12 Aug '11

Hello Ion, This is not a review. I took 3 hours to read the docs, checks some tests, try to check some sources, but I am still not used to read so few comments in the code. I played a little with the library then, tried to encapsulate some std::auto_ptr<X> in the new containers and things like that. Based on that very little experience, I would like to share some thoughts and ask a few questions on the proposed boost.containers library. 1/ I would really appreciate that the docs were more complete, at least for the technical part. => ex : "flat_map : more memory friendly and with faster searches" => In what way? is the algorithm complexity lesser than previous systems? or do you mean that contiguous memory is more cache-friendly? => do you provide different kernel implementations? => is there a paper on the subject? => Is there an evaluated algorithm complexity for the stable_vector? => is memory contiguous like a std::vector? can I use memcpy on several elements? These are just examples of questions that I expect to be answered by the docs. EDIT : I read proposition to embed elements of Joaquin M Lopez Munoz's blog. This is exactly that kind of informations I am looking for. => For the tree class, I can't remember any tree interface in the std. Could you point me to some informations ? Sorry If I miss something obvious. 2/ I was surprised (in a good way) to see some Andrei Alexandrescu's code in the library. Will the Loki licence be shipped now with boost? (This is not a problem for me). 3/ A few tests might be added. ex: Test the fact the vector usually are contiguous in memory. I can write this one if you are interested. 4/ The 'move aware' containers are nice to use but as a drawback We are forced to use macro to define the types using the 'move' semantics. What other container libraries can this work be related to? There are some examples of containers requiring the value_type to support only the "defaut constructor + a swap() function". This is a concept I would really appreciate to see in boost.containers. In that case, I would very happily use this library. Otherwise I think I will stick with other containers classes. 5/ "The aim of the library is to offers advanced features" Is the proposed Boost.containers also an effort towards development of new features for containers? If that is the case, then what are the plans for the future ? Is there a roadmap? To sum up : I am surprised that such a container library was not already integrated in boost. This should be a nice addition. But at the moment I don't think I would use it: my main interest would be for the value_type supporting "defaut constructor + a swap() function" to be added to the library. I also would like more detais in the documentation. In my humble opinion, it would also be easier for exterior people to learn from and to contribute to your library if there were more comments in the code. I congratulate you and the other authors for your work and efforts, and wish you the best for the review. Best regards, Pierre Morcello -- View this message in context: http://boost.2283326.n4.nabble.com/boost-containers-remarks-and-questions-t… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 3

[preprocessor] ifdef equivalent inside a macro, is it possible?
by damien benoist 12 Aug '11

12 Aug '11

Hi all, Would there be a way to do some "ifdef" inside a macro? Could be in the form of a macro taking 3 args, - 1st being the macro to test the existance of, - 2nd being the value to expand in case 1st arg is a defined macro - 3rd being the value to expand in case 1st arg is not a defined macro Exemple: #define DUMMY_MACRO1 foo1 // next is commented out and not defined // #define DUMMY_MACRO2 foo2 PP_IFDEF(DUMMY_MACRO1, DUMMY_MACRO1, bar1) // would expand to foo1 PP_IFDEF(DUMMY_MACRO2, DUMMY_MACRO2, bar2) // would expand to bar2 Seems impossible to me, but boost/preprocessor does so many things that seemed impossible to me. Maybe someone will have some more magic... Thanks. Damien.

4 11

[proto] RValue reference support?
by John Maddock 12 Aug '11

12 Aug '11

Does proto have any support for rvalue references in terminals? I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible. Thanks, John.

5 11

[interprocess] detail/move.hpp macros conflict with boost/move/move.hpp
by Daniel Larimer 12 Aug '11

12 Aug '11

I am attempting to include my own <boost/move/move.hpp> header, but the macros conflict with <boost/interprocess/detail/move.hpp>. It would seem to me that boost interprocess should 'namespace' the macros like it did the types so that when boost/move is included there are no conflicts. When will Boost.Move be included in an official release? Dan

1 0

[tti] Changes will go on Boost trunk
by Edward Diener 11 Aug '11

11 Aug '11

For interested parties, I have put TTI on the Boost trunk and will be making changes there in getting TTI ready for a Boost release. I will keep the reviewed copy in the sandbox until TTI is officially part of a Boost release, after which I will remove the sandbox version.

1 0

[tti] compiler error: shadows template param `class T`
by Lorenzo Caminiti 11 Aug '11

11 Aug '11

Hello, The TTI library macros expand to code that uses naive template parameter names like "T", "F", "U", etc. The library implementation should be changed to use library reserved names to avoid clashing with user template parameter names. For example, the library use a name like boost_tti_aux_T (or even better BOOST_PP_CAT(boost_tti_aux_T_, __LINE__)) instead of T and state in the documentation that any name prefixed by boost_tti_aux (in any namespace) is reserved for the library implementation. The same should be done for any other implementation symbol defined by the TTI library. This is an issue if the macros are expanded for example within a class (which is and should be possible after changing them not to expand in the boost::tti namespace). For example, assuming BOOST_TTI_HAS_COMP_MEMBER_FUNCTION is fixed not to expand in boost::tti then the following: template< typename T > struct myvector { BOOST_TTI_HAS_COMP_MEMBER_FUNCTION_TRAIT(has_push_back, push_back) // expand to code using a template parameter naively named T ... }; Will generate a compiler error on GCC "error: shadows template param class T". --Lorenzo

3 3

[containers review] A reminder that the containers review ends tomorrow
by John Maddock 11 Aug '11

11 Aug '11

Just a quick reminder that the containers lib review ends tomorrow - there have been lots of good comments, but not so many reviews - so now's your chance ;-) If there are any reviews pending that are likely to be late please let me know so we can extend the review period. Documentation from the library may be viewed online here: http://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/index.h… The source may be accessed from the "move" directory of the sandbox SVN or downloaded from http://www.drivehq.com/web/igaztanaga/boost_container.zip. Note that this download contains a copy of the accepted, but not yet release, Boost.Move library - extract the zip over a copy of Boost-1.47 to get a full working copy. Regards, John.

1 0

[Autosave] Re: [math][accumulators] Empirical distribution function
by Simon West 11 Aug '11

11 Aug '11

Hi, On Sun, June 19, 2011 22:36, er wrote: > Hope this can serve as a basis for a conversation: > > > https://svn.boost.org/svn/boost/sandbox/acc_ecdf/ > I'm assisting Eric with the maintenance of Accumulators. I've had a look through the code at the above link, and would like to offer the following comments (if I have misunderstood anything, please let me know). My basic concern with the code is that a map is used to store the counts of data-points that have been added (the map keys are the data-points, the map values are the counts). In real-world floating point data it is rare for two data-points to be exactly the same, so in practice the map would have a single key-value pair for each data-point q_i, of the form (key=q_i,value=1). This is inefficient, because all the key values will be 1. Also, the memory usage will grow linearly with the number of data-points accumulated, which doesn't seem to be in keeping with the spirit of the Accumulators library. For these reasons, I'm not convinced that the code should be added to the library in its current state. Simon.

3 2