- Boost - lists.preview.boost.org

[review] Heaps
by Andrew Sutton 07 Jun '11

07 Jun '11

All, I'd like to announce the beginning of the review of the Heap library, written by Tim Blechmann, and resulting from Tim's 2010 Google Summer of Code project The library implements a number of different heaps (or priority queues) including, a binary heap, d-ary heap, binomial heap, fibonacci heap, pairing heap, and skew heap. The library also provides an adaptor to make heaps mutable, allowing a programmer to modify a value and update its position within the heap. The library also also supports stability, ensuring that elements pushed into a heap with the same priority are popped in the same order. The library is not targeted in any specific domain nor directly related to any specific libraries, but intended to be a collection of general purpose data structures (not unlike the Boost.Unordered library). The documentation and source code can be downloaded from here: Documentation: http://tim.klingt.org/boost_heap Code: http://tim.klingt.org/git?p=boost_heap.git;a=snapshot;h=HEAD;sf=tgz Unlike previous reviews, this review will be assisted by a code review application, Code Collaborator (by SmartBear). The product was tested during a BoostCon session, and we are eager to see how well it scales to a community review. You can use the link below to access and review the Heap library. http://demo.smartbear.com/boost/go?page=ReviewDisplay&reviewid=4 The application allows line-by-line comments of the submitted source code in addition to providing features for general defect and issue reporting. If you are interested in using this system, we will have to register you as a user of the site. You can request access by replying to this message. I'm still learning my way around the system, so there are bound to be some missteps along the way :) If you are not interested in using the system, then feel free to send email like any other review. Reviews of the library should address the following questions. What is your evaluation of the design? What is your evaluation of the implementation? What is your evaluation of the documentation? What is your evaluation of the potential usefulness of the library? Did you try to use the library? With what compiler? Did you have any problems? How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Are you knowledgeable about the problem domain? And finally, every review should answer this question: Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Please note that some questions may be easier to answer in email than with the review tool. As always, reviews are important to the continued quality of the Boost C++ Libraries. Thank you in advance for your comments and contributions. Andrew PS. The review was slated to start on Sunday, but I was not able to make the announcement until today.

7 38

[type_traits] is_constructible, ... when decltype is supported?
by Vicente Botet 07 Jun '11

07 Jun '11

Hi, when decltype is supported (as it is the case for gcc 4.6.0) we can define the C++0x traits is_constructible, is_assignable and the ones that depend on them. These traits are really important to conform with some of the C++11 interfaces. Next follows one examples from the standard: template (*class... UTypes*) explicit tuple(UTypes&&... u) noexcept; 8 Requires: sizeof...(Types) == sizeof...(UTypes). is_constructible(*Ti, Ui&& *)::value is true for all i. 10 Remark: This constructor shall not participate in overload resolution unless each type in UTypes is implicitly convertible to its corresponding type in Types. In Boost there are some libraries as Boost.Array, Boost.Fusion tuple that defines these kind of constructors or assignments and that require that the template types must be constructible or assignable. The problem when these constructors/assignments don't use of SFINAE to avoid that these functions participate on overload resolution is that is_constructible or is_assignable will give false positive results as the expression could be valid, even if the definition doesn't compiles. I don't know if it is worth including these traits in Boost when the compiler supports decltype so we can start writing conforming interfaces, but at least it would be nice if the Boost libraries start using these standard traits when them are available. Any thoughts? Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/type-traits-is-constructible-when-declty… Sent from the Boost - Dev mailing list archive at Nabble.com.

4 6

[review] Heaps: Mergeable Heaps
by Andrew Sutton 07 Jun '11

07 Jun '11

Tim, I think you should define a MergeableHeap that describes heaps that can be merged in O(log n) (i.e., binomial, fibonacci, pairing, skew). Actually, the only heaps that don't satisfy this requirement are binary heaps, b-heaps and d-ary heaps (they all seem to be linear). This is similar to the the AdjacencyMatrix in the BGL. This poses a serious problem, however. The mutable priority queue wrapper implements merge() as, at best, a linear operation, meaning that no mutable priority queue could model the MergeableHeap concept. Andrew

4 13

[Review] Boost.Convert review decision
by Edward Diener 07 Jun '11

07 Jun '11

Because Vladimir Batov has expressed himself by saying that he does not want to continue to offer his Boost.Convert library as a library for Boost, I am respecting his decision and his library is NOT accepted into Boost. I am still going to reserve the right to do an analysis of the various viewpoints and offer some way forward for the Boost.Convert library, if Vladimir Batov wishes to pursue it, or for any other library which wishes to present a convert-like interface. I will post this analysis sometime later in the week. There is also still one person who had asked me personally to do a late review by the end of Wednesday, and if that person still wants to do so I would still appreciate his input. I would like to thank Vladimir Batov for offering the library to Boost and all those who did reviews or offer comments about the library even if they did not do an actual formal review. Edward Diener

3 2

[preprocessor] [variadic] VMD_SIZE using ADD -- why?
by lcaminiti 06 Jun '11

06 Jun '11

Hello all, I am using the VMD Boost Library Under Construction to handle variadic macros. On MVSC, this library uses PP_ADD to calculate the variadic size VMD_SIZE(__VA_ARGS__). However, it does not provide a reentrant version of VMD_SIZE (like VMD_SIZE_D) which is a problem when nesting size calculations within while iterations because PP_ADD uses PP_WHILE. I think, if this implementation is kept, the library should also provide the reentrant variant VMD_SIZE_D that invokes PP_ADD_D instead of PP_ADD. #if defined(BOOST_MSVC) #define BOOST_DETAIL_PP_VMD_DETAIL_DATA_SIZE(...) \ BOOST_PP_ADD(BOOST_DETAIL_PP_VMD_DETAIL_APPLY(BOOST_DETAIL_PP_VMD_DETAIL_ARG_N, (__VA_ARGS__, BOOST_DETAIL_PP_VMD_DETAIL_RSEQ_N())),0) \ /**/ #else #define BOOST_DETAIL_PP_VMD_DETAIL_DATA_SIZE(...) \ BOOST_DETAIL_PP_VMD_DETAIL_APPLY(BOOST_DETAIL_PP_VMD_DETAIL_ARG_N, (__VA_ARGS__, BOOST_DETAIL_PP_VMD_DETAIL_RSEQ_N())) \ /**/ #endif BTW, why is PP_ADD(size, 0) used on MSVC? If this is just for forcing proper macro expansion, I think other techniques (like the ones used by PP_EXPAND) should be used so no PP_WHILE reentrancy dependency is introduced. Thanks, --Lorenzo -- View this message in context: http://boost.2283326.n4.nabble.com/boost-preprocessor-variadic-VMD-SIZE-usi… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 4

[none_t] I/O operators patch
by Gregory Crosswhite 06 Jun '11

06 Jun '11

Hey everyone, Since my idea to add I/O operators for none_t has been approved by the community according to the three-week rule --- which as you all know states that any proposals that have received no feedback on the list after three weeks are therefore automatically approved by the community ;-) --- I have written a patch based on the feedback I have received to implement these operators and attached it to this e-mail. To summarize my earlier e-mail, the advantage of having these operators around is that they allow generic I/O code to be applied to data of type none_t. One decision that I made in this patch that I have mixed feelings about is that I put the operators in the boost namespace. The advantages of this approach are obvious, but the disadvantage is that this "hides" them from the user who might not realize that he or she needs to import operator>> and operator<< in order to access them (since importing qualified operators is something that is not usually done) but instead conclude they they don't exist at all. Alternatives include putting them in the global namespace and putting them in the std namespace. Any thoughts on this? Since the window for adding new features to Boost closes tomorrow, and this patch is relatively small and should be fairly innocuous, is there a chance that this or something like it could be considered for the next release? Thanks! :-) Greg

3 5

Process library with child process events
by Klaim - Joël Lamotte 06 Jun '11

06 Jun '11

Hi, On Wed, Jun 1, 2011 at 14:12, Jeff Flinn <Jeffrey.Flinn(a)gmail.com> wrote: > Gregory Crosswhite wrote: > >> Hey everyone, >> >> Since there is not yet a Boost.Process library, does anyone have a >> suggestion for a lightweight cross-platform C++ library for launching and >> monitoring (i.e. being able to tell if they die) child processes? >> > > I've put the code from the recent boostcon "boost process" presentation > that Boris Schaeling and I gave at: > > https://github.com/JeffFlinn/boost-process > > Initial documentation is at: > > > https://docs.google.com/document/pub?id=1qdpxcJB51WMuNYlKYPkPcZZGuPj7zmeUPI… > > The intent is to get this completed and ask for review this summer. The > areas needing work are: > > I've read the current (clearly incomplete w.i.p.) doc and parsed the headers and I like the design so far. However, I can't find a way to be notified if a child process did end, by getting to the end of the program or by having crashed or by having being shut down by external processes, the OS or the user. Did I miss something? If not, what is supposed to happen in the parent process if a child do get to an end (whatever the cause)? Joël Lamotte

6 11

Gauging interest in new library re: multiscale/multigranular containers
by nathaniel＠tierblend.org 06 Jun '11

06 Jun '11

Hi: I would like to submit a library which would allow functionality related to scale and granularity to be performed on STL-like containers. Until recently I was in a doctoral program specializing in the philosophy of science, and I am especially interested in multiscale data modeling and its applications to e.g. GUI design, code generation, decision procedures, and DSL implementation. For example, one of my projects involves a DSL implemented through multiscale graphs in lieu of conventional syntax trees. I used to study at Buffalo, which houses the National Center for Ontological Research -- headed by the quite broad-ranging scholar Barry Smith -- and has done pioneering work in biomedical ontology and also in ontological models related to complex or "vague" aggregative structures. In these structures collections of objects of some base type T can be defined as aggregates but with varying degrees of looseness or "individual coherence"; and this aggregation can be iterated to produce multiscaled structures which can be queried or represented at different granularities. There are a number of analytic procedures which can be implemented on such structures, some overlapping with graph theoretic or statistical methods. These structures also possess alot of internal structure above and beyond their underlying list of values, so they are suited to memory-optimized C++ code rather than higher-level languages like Java. However, I am not aware of generic libraries which really incorporate these kind of data structures and their analysis in a systematic way, although I have come across non-template libraries which implement some similar features. What I propose is a library which could be used in a fashion similar to std::vector or std::set but which support additional functions along the lines of, e.g., building multigraphs out of T-type nodes; partitions of T-sets with functions to define or measure e.g. intrapartition relevance; defining (or extending) a scale metric on T-objects, T-sets, T-arrays, or other "T- data structures" and using it for rescaling, scale-filter, and other scale-related transformations; defining iterators or "walks" on T-collections which take scale and granularity into account; etc. In a number of cases the algorithms for these kinds of operations have been described in theoretical form or even already implemented in languages like Scheme. I believe that this project is also well-suited to carry over into C++0x, because new features proposed there (such as Concepts, which I know keep moving in and out of the specification) have potential to make this library increasingly generic or "fine-tuneable"; for example, users should be able to specify custom allocators not only for T's but for aggregates or connectors between T's which might be recognized as part of the inner structure of a T-collection. Thanks in advance for any comments or suggestions.

3 2

none_t I/O operators
by Gregory Crosswhite 05 Jun '11

05 Jun '11

Hey everyone, I have recently run into a scenario where it was useful to have << and >> I/O operators defined for none_t. I was using Boost Program Options to create a list of program options, and I wanted one of my options to be a help message. Since this option has no value except for the side effect of printing a help message and exiting, I gave it the type none_t, i.e.: options.add_options() ( "help" ,opts::value<none_t>()->zero_tokens()->notifier(...function that prints help message...) ,"print help message and exit\n" ) When I did this, it complained that the >> operator was not defined for none_t, so I went ahead and defined my own I/O operators, which are essentially just no-ops: inline std::istream& operator>> (std::istream& in, boost::none_t& _) { return in; } inline std::ostream& operator<< (std::ostream& out, const boost::none_t& _) { return out; } It seems to me that these are the natural I/O operators to define for this type, and so it would be useful to have them be officially part of Boost. Although it is unlikely that a user would ever call them directly, their existence could prove useful in various circumstances where a generic I/O function is being applied to a none_t, such as the case I ran into/ If people were willing to accept a patch that adds these operators to Boost, then I would be willing to write such a patch. Obviously I would need to generalize the istream/ostream types to the full generic versions which include the template parameters for character traits, etc. I would also add forward declarations of istream and ostream just before these declarations so that the implementation would not need to have the <istream> and <ostream> headers as dependencies, though this would be tricky because I'd need to figure out how to detect if <istream> and/or <ostream> have not been included yet. Thoughts? Cheers, Greg

3 6

Re: [boost] [msm] need to increase the fusion set and map size to 30
by Christophe Henry 05 Jun '11

05 Jun '11

> So i added these two statements at the beginning, and this solved the > problem. > > # define FUSION_MAX_SET_SIZE 30 > # define FUSION_MAX_VECTOR_SIZE 30 > > Perhaps we can add this somewhere in the doc. Hi Kim, Maybe I should make this subject more visible. It is described here: http://www.boost.org/doc/libs/1_46_1/libs/msm/doc/HTML/ch05.html I think that FUSION_MAX_VECTOR_SIZE is actually enough, but it's only due to the fact that set is implemented in terms of vector (to be exact, as I only use fusion::set, FUSION_MAX_SET_SIZE ought to be enough, but it's not, so I suppose it's a fusion bug). Regards, Christophe

2 2

Re: [boost] [review] Heaps: size and stability
by Brent Spillner 05 Jun '11

05 Jun '11

On 6/2/2011 at 19:27, Tim Blechmann wrote: > The stability issue relates to a previous discussion from a couple > months ago (brought up by Cliff Green, > http://article.gmane.org/gmane.comp.lib.boost.devel/219330) Cliff was > concerned that the implementation of stability added overhead to the > normally unstable heaps (i.e., an extra size_t, I think) from the > implementation. I worry that the use of a policy parameter to specify > stability will result in "accidental overhead" in cases where users > don't fully understand the impact of their configuration choices. >it is not possible to write every heap algorithm as `stable' heap. i do not >recall the exact point that will break stability if one just orders the nodes in >the tree, but there was a non-trivial issue (possibly related to mutable heaps). It should be possible to preserve the correctness of most operations (certainly find, insert, delete, merge, and rebalancing) for ordinary heaps by storing items with the same key value in leftist heap order, i.e. preserving the invariants that: (1) if a subtree contains multiple items with the same key as the subtree root, the item at the root is logically first in the order (i.e., standard heap ordering); (2) if both the left and right subtrees contain items with the same key as the subtree root, all items with that key in the left subtree are logically ordered before any item having the same key in the right subtree (leftist property); and (3) if a subtree contains multiple items with a particular key value K, every item with key value K has as its parent another item with key value K, with the possible exception of the subtree root (locality/compactness property) These properties are preserved by right- or left- rotation around the subtree root. To keep the heap at minimum height, you will also occasionally need a prune-and-splice operation (items with key value K in the right subtree become children of the rightmost node with key value K in the left subtree), followed by further rotations. The compactness property should allow find, insert, and delete to continue running in O(lg n) time when rebalancing is not required. The prune-and-splice operations add O(|K|), where |K| is the total number of nodes having key value K, to the worst-case rebalancing operation, but this |K| quite reasonably ~O(lg n) when the key values are sufficiently distributed. Some merge algorithms would clearly violate the invariants above, but stable merge is still possible in O(n) time. >iac the node versioning seems to be the usual approach for implementing stable >heaps. the type of the version should be exposed to the interface, though, so >one can specify arbitrary-sized integer types to avoid overflows ... Versioning is the simplest way to adapt a non-stable heap implementation for stability, but the space overhead (and concomitant loss of flexibility in using a preexisting array to store the heap) and the risk of overflow make it unsuitable for some applications, including the quite common event queue. With a 32-bit counter value, a queue that receives and average of 100 events/second will overflow in about 16 months--- i.e. 32 bits is just enough space for your library to pass a reasonable test battery and still fail in the real world. (Of course, you need not increment the counter on every single insertion, as I just noted in the Code Collaborator review.) Another option would be chaining, where each heap node contains either a single item or a linked list of items with the same key value. This would minimize the required changes to existing algorithms, support fancier heap types and heaplike structures, and only impose some storage overhead (one or two pointers into the list, perhaps a length counter, and a means of synchronizing list access (which could be an atomic update protocol for the head/tail pointers and/or length counter)) when you actually need it, at the cost of some type erasure within the generic heap structure and possibly extra copying at runtime (when a singleton node first becomes a linked list.) On the subject of counters: On 6/2/2011 at 10:19, Tim Blechmann wrote: >will have a look ... in general boost.heap does not throw any exceptions by >itself, but of course the held type, the container or the allocator can throw Lines 231 & 232 of the review version of stable_heap.cpp are: if (counter_ == std::numeric_limits<std::size_t>::max()) BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow")); (to be fair, this does seem to be the only case in the library... but Thorsten is right that it should be clearly documented.)

3 2

[review] Heaps: mutability
by Andrew Sutton 05 Jun '11

05 Jun '11

Tim, I'm trying to figure out how I can use a mutable queue to write something like Dijkstra's SP. Here's a skeleton with the relevant parts. Queue<Vertex*, Comp> q; Map<Vertex*, Queue::handle_type> h; h[start] = q.push(start); v->distance += x; q.update(h[v]); Comp is an indirect comparison of vertex distances (u->distance < v->distance). Does the mutable heap support this application (i.e., where I'm not directly updating the value type)? It's not clear from the examples supplied with the program. I suspect that it is, but it's not clear. Andrew

3 4

Help with shared_ptr usage?
by Johnny Willemsen 03 Jun '11

03 Jun '11

Hi, I can need some help with getting similar behavior as with shared_ptr for my classes., I have used std::shared_ptr with C++0x which matches the boost support. I have two classes, Base and Derived. Now I want to give our users not directly access to these implementation classes, but to some reference to them. I have created two templates, BaseRef_T and Derived_objref (see below). In Derived_objref I need to add some additional typedefs and type definitions. I have tried first to add these typedefs to a specialization of shared_ptr<> but couldn't get a clean solution. If I now use shared_ptr I can take a shared_ptr for a Derived and assign it to a BaseRef_T. That works without problems. But how to accomplish this with my own wrapper classes. This should only be possible when the types are related to inheritance. If I have now a D that is not derived from Base than that shouldn't work. Johnny #include <memory> class Base { public: }; class Derived : public virtual Base { public: }; template <typename T> class BaseRef_T { public: BaseRef_T (std::shared_ptr <T> t) : impl_ (t) {}; BaseRef_T (T* t) : impl_ (t) {}; BaseRef_T (void) : impl_ () {}; typedef T element_type; inline T* operator-> () { return impl_.get ();} inline T* get() const { return impl_.get ();} explicit operator bool() const // never throws { return impl_ == 0 ? false : true; } void operator=(const std::nullptr_t& t) // never throws { impl_ = t; } // protected: typedef std::shared_ptr <T> shared_ptr_type; shared_ptr_type impl_; }; typedef BaseRef_T <Base> BaseRef; template <typename T> class Derived_objref : public virtual BaseRef_T <T> { public: Derived_objref () : BaseRef_T<T> () {} Derived_objref (T *s) : BaseRef_T<T> (s) {} Derived_objref (const BaseRef_T <T>& o) : BaseRef_T <T> (o) {} void operator=(const std::nullptr_t& t) { this->impl_ = t; } typedef int my_index_type; // Needed as additional typedef for Derived struct Foo {int a;}; }; typedef Derived_objref <Derived> DerivedRef; int main (int,char*[]) { std::shared_ptr<Base> bs (new Base); std::shared_ptr<Derived> ds (new Derived); std::shared_ptr<Base> cs = ds; BaseRef b (new Base); DerivedRef d(new Derived); BaseRef c = d; // <== how to get this working? return 0; }

2 1

Invitation to connect on LinkedIn
by kannan k v via LinkedIn 03 Jun '11

03 Jun '11

LinkedIn ------------ kannan k v requested to add you as a connection on LinkedIn: ------------------------------------------ Yuriy, I'd like to add you to my professional network on LinkedIn. - kannan Accept invitation from kannan k v http://www.linkedin.com/e/bv6hcz-goh9zloe-1g/uV9CsZkavY-uKU5A7C-1JbkavY-u5P… View invitation from kannan k v http://www.linkedin.com/e/bv6hcz-goh9zloe-1g/uV9CsZkavY-uKU5A7C-1JbkavY-u5P… ------------------------------------------ Why might connecting with kannan k v be a good idea? People kannan k v knows can discover your profile: Connecting to kannan k v will attract the attention of LinkedIn users. See who's been viewing your profile: http://www.linkedin.com/e/bv6hcz-goh9zloe-1g/wvp/inv18_wvmp/ -- (c) 2011, LinkedIn Corporation

3 3

parsing strings at compile-time
by Andrzej Krzemienski 03 Jun '11

03 Jun '11

Hi Everyone, This is not directly related to any of the boost libraries, but I thought people from this list may find it interesting or useful. The below are links to three posts where I tried to describe how we can parse strings at compile time and convert them to data structures, still at compile-time in C++0x with generalized constant expressions. I do not have enough time to write a library myself, but perhaps someone would be able to use such techniques for their library. I think Regular Expressions library would benefit from this technique if the compiler would be able to check the correctness of a regex. http://akrzemi1.wordpress.com/2011/05/06/compile-time-computations/ http://akrzemi1.wordpress.com/2011/05/11/parsing-strings-at-compile-time-pa… http://akrzemi1.wordpress.com/2011/05/20/parsing-strings-at-compile-time-pa… Regards, &rzej

2 1

[Proto] Expression as fusion/MPL sequence
by Joel Falcou 03 Jun '11

03 Jun '11

Seems somethign crooky on this front. Calling fusion::at_c on expression ends up in error even after including boost/proto/fusion.hpp. Same way, flatten used as a transform seems to not give me a type that can be passed to any fusion or mpl function. Looking at proto/fusion.hpp I noticed that the iterator is indeed random_access but not the view itself which as a forward_traversal tag. Even after fixing this, no dice, at_c<N>(some_proto_expr) still fails to compile.

3 3

[test] Running regression tests
by Edward Diener 02 Jun '11

02 Jun '11

Attempting to run regression tests for the 'test' library on the Boost trunk I receive as output: "..\..\..\libs\test\build\Jamfile.v2:107: in modules.load rule boost-install unknown in module Jamfile</C:/Programming/VersionControl/boost/libs/test/build>. C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:314: in load-jamfile C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:62: in project.load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:766: in project.use C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:89: in load-used-projects C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:73: in load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:115: in load-parent C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:464: in initialize C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:309: in load-jamfile C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:62: in load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:115: in load-parent C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:464: in initialize C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:309: in load-jamfile C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:62: in load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:168: in project.find C:/Programming/VersionControl/boost/tools/build/v2\build-system.jam:570: in load C:\Programming\VersionControl\boost\tools\build\v2/kernel\modules.jam:283: in import C:\Programming\VersionControl\boost\tools\build\v2\kernel\bootstrap.jam:142: in boost-build C:\Programming\VersionControl\boost\boost-build.jam:17: in module scope" All other regression tests for libraries produce no Boost Build errors. Can anybody tell me what is wrong here ?

4 4

std::map::find() wrapper
by Olaf van der Spek 02 Jun '11

02 Jun '11

Hi, I've written a small wrapper for std::map::find() (and map-like containers/ranges) that returns a pointer to the value if found (or NULL if not found). See https://svn.boost.org/trac/boost/ticket/5227 The advantage is that you don't need the container type name (for ::reference), you can initialize the pointer inside an if condition, you don't have to compare against ::end() and you don't have to use ->second. For containers of pointers to objects, the wrapper could do an additional dereference. Do you think this would be useful for inclusion in Boost? Greetings, Olaf

17 61

[review] Heaps: size and stability
by Andrew Sutton 02 Jun '11

02 Jun '11

Tim, Do you really need to parametrize the constant-time size property? C++11 requires constant time size for all containers. I think that this is also a reasonable requirement for Heaps. I'm not aware of any applications that use so many heaps that the extra 4-8 bytes required by a size parameter would make huge difference in memory usage. Also, for heaps that can be effectively implemented in terms of other containers, they should guarantee O(1) size. The stability issue relates to a previous discussion from a couple months ago (brought up by Cliff Green, http://article.gmane.org/gmane.comp.lib.boost.devel/219330) Cliff was concerned that the implementation of stability added overhead to the normally unstable heaps (i.e., an extra size_t, I think) from the implementation. I worry that the use of a policy parameter to specify stability will result in "accidental overhead" in cases where users don't fully understand the impact of their configuration choices. Would it be better (would it be possible?) to write stable_heap as a heap adaptor? I think that this approach (if possible) has two benefits. First it encapsulates the strategy for implementing stability. It also provides a single point of reference for describing the impact of using that configuration. Andrew

3 4

safe-bool CRTP class
by Krzysztof Czainski 01 Jun '11

01 Jun '11

Hello, Vladimir Batov prepared a safebool helper class as part of his Pimpl library. I quote his rationale: /// An implicit conversion to bool (operator bool() const) is very much /// idiomatic and is often deployed in constructs like "if (foo)" and "if (!foo)" /// (with no explicit op!() defined). However, sadly, implementing "operator bool()" /// is *wrong* as that conversion kicks in far too often and unexpectedly. Like in /// "foo == 1", "foo+1", "1+foo" or potentially during lexical_cast<string>(foo) /// (if there are no op>>() and op<<() defined). Consequently, that "implicit /// conversion to bool" functionality has to be implemented in an indirect and /// somewhat awkward way via an implicit conversion to some other type. The best /// type for the purpose appears to be a pointer to a member function. For more /// see the chapter 7.7 in Alexandrescu's "Modern C++ Design" and the article at /// http://www.artima.com/cppsource/safebool.html by Bjorn Karlsson. In the review of Pimpl Joej Falcou suggested to make safebool a CRTP base class. I had prepared such a class some time ego, and I've been using it for a while now. Is there interest in adding it to boost? Perhaps as part of the operators library? /** * CRTP class, that provides operator unspecified_bool_t() const, implemented in terms of * Derived::operator! */ template < class Derived, class Base = empty_t > class boolable : public Base { void unspecified_bool_t_f() {} typedef void (boolable::*unspecified_bool_t)(); public: operator unspecified_bool_t() const { return ! static_cast<Derived const&>( *this ) ? 0 : &boolable::unspecified_bool_t_f; } }; Usage: struct X : public boolable<X> { bool operator!() const { return condition; } // inherit operator unspecified_bool_t implemented in terms of the above operator! }; Regards, Kris

13 39

[Math and numerics] interest in Circular values math and statistics library ?
by Lior Kogan 01 Jun '11

01 Jun '11

I built a C++0x circular-values math and statistics library, and posted it on CodeProject. See http://www.codeproject.com/KB/recipes/Circular-Values.aspx I wonder if such library may be a welcomed addition to Boost. Thank you, Lior

5 5

Re: [boost] [pimpl] Mini Review
by Sean Chittenden 01 Jun '11

01 Jun '11

>> I've been watching this discussion for a while (with vested >> interest), and want to use a few examples to shore up some of >> the discussion (and possibly move it off list so that things >> can proceed in a constructive manner). The concern is not that >> Pimpl is implementing an opaque pointer, it's the miscellaneous >> copy constructors, constructors, equality or whatever other >> misc "extras" that come along from using Pimpl, right? > > Not quite. Copy constructors and copy assignment, for example, are appropriate. They allow the library to manage copies of the implementation object. Problems arise, for example, from the addition of null(),operator ->(), and operator *(). This is less rhetorical than I'd like, but what's the right amount of baggage that a Pimpl implementation can bring along with it? On one side of the spectrum you have an austere implementation that is literally an opaque pointer with its relevant compilation glue ("the one true/pure pimpl"). On the other side of the spectrum you've got something that overloads functions and operators and makes a pimpl implementation easier to use, ala the Pimpl library. For example: https://github.com/sean-/Boost.Examples/blob/master/pimpl/boost/pimpl/pimpl… Not strictly necessary, but I understand why it's there and why it would be wanted in a Pimpl implementation. I also understand the puritanical argument for why you wouldn't want it. > reset(), which may be protected rather than public (I don't recall), is not as much of a problem, but my suggestion for that was that since the constructors allocate the implementation object, "resetting" the implementation should likewise not involve allocation. For that, I suggested a construct() member function template set, paralleling the constructors that implement "perfect forwarding." A constructor and a reset() that take a deleter would be appropriate for cases in which allocation is not desired. That design would be symmetrical. Got it, ok. >>> class Book : public pimpl< Book >::pointer_semantics { }; >>> // Or is the interface different because the ABI is >>> // different? >>> class Book { >>> class* impl_; >>> }; > > It's different because using inheritance and public member functions, pimpl<Book>::whatever has augmented Book's interface. Correct/agreed. >> With as (in?)efficient compilers sucking up gigs of RAM and >> frequently crashing during compilation[1], having a friendly >> mechanism to hide linkage and implementations behind opaque >> pointers is useful beyond externally exposed APIs in libraries. >> The tedium of doing this frequently makes the Pimpl library an >> easy win for many developers (though possibly not all of them >> and not in all situations). As a Pimpl consumer for over a >> year, I'm trying to concretely demonstrate where the possible >> pitfalls could be lurking with this implementation. Thanks in >> advance. -sc > > I have no problem with using the Pimpl Idiom. Just this past week I was able to advance some application testing readily because we used it in a couple of classes involved in an application's disorderly shutdown due to misconfiguration. My concern is that the Pimpl Library seems to have pushed past the idiom into something else, which is surprising to me and, clearly, to others. I should also be clear that I'm not against what the Pimpl Library has done, in terms of augmenting the derivate's interface via public inheritance, but that doing so should be in a class template and a library of a different name. That feedback makes sense, thanks Robert. I think the unease is coming from the Pimpl library implementing helpers and extending beyond only providing an opaque pointer. TBH, before using Pimpl, I'd implemented a subset of the helper functions in my own home-grown pimpl library so seeing them standardized never struck me as objectionable (the possibility of running in to name clashes, not withstanding). In fact, my search for Boost.Pimpl began because I missed adding a non-const* ->() to my implementation. After wading through pages of gcc error messages (naturally this happened in the middle of a asio/bind/wrap call) I started looking for a reference implementation that had some of this spelled out since I didn't think I should be spending my time reimplementing the wheel. I don't have an answer for what's "right" on the spectrum of austere vs "featureful", but the featureful side of Pimpl has clear merit. I'll move the rest of my comments over to the review tool. -sc http://demo.smartbear.com/boost/go?page=ReviewDisplay&reviewid=5 -- Sean Chittenden sean(a)chittenden.org

2 1

[conversion] ADL and templates
by Vicente BOTET 01 Jun '11

01 Jun '11

Hi, I've tried to add a configuration point in Boost.Conversion via overloading and ADL, but while the internal call of the library can find them using a trick that adds a parameter that contains the type of the return type, the user is not able to find them without using the same this trick, but this is too dark to be natural for user code. Next follows a simplified code of the problem. The following namespace N { struct S{}; template (*typename T*) T fct1(S const& s) { return T(s); } template (*typename T*) void fct2(T &t, S const& s) { t=s; } } void test () { N::S s1; N::S s2; fct2(s2, s1); s2=fct1(*N::S*)(s1); // (1) } Results in a compile error in (1) error: ‘fct1’ was not declared in this scope Is it standard behavior that fct1 can not be found by ADL? Thanks, Vicente P.S. Please replace (* and *) by angle brackets.

4 11

Cross-platform process library?
by Gregory Crosswhite 01 Jun '11

01 Jun '11

Hey everyone, Since there is not yet a Boost.Process library, does anyone have a suggestion for a lightweight cross-platform C++ library for launching and monitoring (i.e. being able to tell if they die) child processes? Thanks! Greg

3 2

Re: [boost] [pimpl] Mini Review
by Sean Chittenden 01 Jun '11

01 Jun '11

>>> Helping to implement copying and assignment is useful, >>> provided the class is supposed to support those operations. >> >> shared_ptr-based Pimpls copying and assignment are done by >> shared_ptr. > > That tells me that Pimpl provides copying and assignment for the derivate. > As you've noted, this is only by virtue of using private inheritance. I still don't think it is correct behavior for a library implementing the Pimpl Idiom to modify the interface class' (Book's) interface. Consider a raw pointer Pimpl design: > > class Book { > // state > }; > > becomes: > > class Book { > struct impl; > impl pimpl_; > }; > > struct Book::impl { > // state > }; > > Adding a pimpl did nothing to Book's interface. Why then should Book's interface chance when using your library? That seems to be an extension of the idiom into the territory of the Bridge Pattern or something else entirely. I've been watching this discussion for a while (with vested interest), and want to use a few examples to shore up some of the discussion (and possibly move it off list so that things can proceed in a constructive manner). The concern is not that Pimpl is implementing an opaque pointer, it's the miscellaneous copy constructors, constructors, equality or whatever other misc "extras" that come along from using Pimpl, right? To recap (using pointer semantics since that's my preferred implementation): > // book.h > class Book : public pimpl< Book >::pointer_semantics { > // interface > }; > > // book_impl.cc > template<> struct pimpl< org::example::String >::implementation : boost::noncopyable { > // impl state > } > Book::Book() : base() { } > > // user.cpp > Book b; > std::cout << "sizeof(Book): " << sizeof(b) << std::endl; From an ABI perspective, Book implemented via Pimpl maintains the same size (currently 16 bytes, regardless of Book::implementation), and thereby provides a stable ABI (if someone really was concerned about future-proofing their frontend ABI, they could pad Book in book.h). I think the concern is coming from: > Book* b2 = new Book(); > Book* b1 = b2; because there possibly isn't a clear understanding of how those mechanics would work with Pimpl (yes?). Or is it because it's unclear how you'd obtain the desired copy semantics - for example - with the proposed Pimpl library? I'm trying to tease out what the actual feedback is or what the possible suggestions could be (vs outright criticism). > Modifying the interface is the part I was referring to. > > You've said that copying and assignment are only supported (for value semantics, anyway) if the derivate provides them. That's a good approach. If everything is of that sort, then all's well, but that's not what I see. How is Book's interface different? > // Is the Interface different because of the inheritance? > class Book : public pimpl< Book >::pointer_semantics { }; > // Or is the interface different because the ABI is different? > class Book { > class* impl_; > }; Would a Pimpl implementation with preprocessor directives be more suitable because of the level of explicitness? Also, Pimpl implements an opaque pointer and successfully breaks compilation dependencies. Pimpl is not a Bridge implementation. > class Book { > PIMPL_PUBLIC_INTERFACE(Book, impl); > }; ? I use similar cpp(1) magic to implement NO_COPY_OR_ASSIGN() because I've found it to be more predictable in working (or failing) than inheriting from boost::noncopyable. With as (in?)efficient compilers sucking up gigs of RAM and frequently crashing during compilation[1], having a friendly mechanism to hide linkage and implementations behind opaque pointers is useful beyond externally exposed APIs in libraries. The tedium of doing this frequently makes the Pimpl library an easy win for many developers (though possibly not all of them and not in all situations). As a Pimpl consumer for over a year, I'm trying to concretely demonstrate where the possible pitfalls could be lurking with this implementation. Thanks in advance. -sc [1] A few years ago I came to terms with it being a Boost "Right Of Passage" to debug your first compiler crash (that wasn't the result of running out of RAM). -- Sean Chittenden sean(a)chittenden.org

2 1