Hi, this is the review from Ross Boylan. He is not subscribed to the list, but his review is very insightful, so I'm forwarding it here. Regards, Pavol ----- Forwarded message from Ross Boylan <ross@biostat.ucsf.edu> ----- Date: Tue, 05 Oct 2004 17:19:03 -0700 From: Ross Boylan <ross@biostat.ucsf.edu> Subject: Re: Formal Review of the Smart Containers library To: Pavol Droba <droba@topmail.sk>, boost@lists.boost.org Cc: ross@biostat.ucsf.edu X-Mailer: Ximian Evolution 1.4.6 [I am not subscribed to the boost developers' list, so I'm not sure if this message will appear there.] My review is from a non-expert user perspective. Overall, I think the library should be accepted, though I have some suggested tweaks and improvements. I am also unable to get a program using the library to compile, and that definitely should be fixed if I haven't made a silly mistake. There is one substantive area (incompatibility with some standard algorithms) that is a bit worrisome to me, and merits thought by someone wiser. I used the library (ptr_vector, ptr_set, ptr_map, including nested ptr_maps) in a pre-release form in my application. There were some minor compilation issues with that version, which I worked around, and which I assume Thorsten has fixed. My main motivations for using the library were that I was looking for a way to hide the implementation decision of whether I had containers of objects or pointers, and I had objects that were not copyable (and would have been expensive to copy). Even at that early stage, I found the documentation quite complete and extensive. The library was easy to use, and it worked. COMPILATION TROUBLES I got the version of the code in the review notice, and adjusted my code to use it (some directory names changed). I got a raft of errors, attached. I spent about 15 minutes looking into the first one, and have no immediate explanation for it. I verified that my boost 1.31 libraries have a remove_pointer.hpp file under type_traits. g++ (GCC) 3.3.4 (Debian 1:3.3.4-7) boost 1.31.0-7 Under Debian GNU/Linux. The packages on the system are mostly at the "testing" level, which is slated to become the next release when it's fully cooked. STANDARD REVIEW QUESTIONS I have not studied the design and implementation in any detail, and so have no comments on them. Actually, some of my comments on the documentation really bear on the design. My major concern is that some algorithms are not safe to use on these containers. It is not clear to me that the average user can tell exactly which algorithms there are. If the latter is true, and there is any way to remedy it, it would be very good to do so. I think if this risky area is properly documented, it will be an acceptable risk. I favor a design with maximum compatibility with existing standard containers; it seems to me that has been achieved. The documentation is extensive and quite good. I have many comments, which I will give below. The only point I consider really significant is that some of the reference material is a bit hard to navigate (I actually found the earlier version I looked at a bit clearer in this regard). The library seems quite useful to me, though I'm biased since I needed it :) But it seems to me the features of the library are of pretty broad interest, and they address issues likely to be handled with ad-hoc, partial hacks without the library. I think the current introduction could give more emphasis two significant advantages of the library. First, it can do things that aren't easily done at all with other methods, such as smart pointers. Second, it is conceptually very simple, and provides a very nice abstraction. (Both of these things are discussed early on; this is just a question of emphasis). I did try to use the library, both an earlier version and the current review version. See results discussed at the top of this note. I've spent around a day, maybe more, using the library, studying the docs, and writing this review. As noted at the outset, I only went into the implementation details when I needed to figure out how something worked or debug a problem. Offsetting this signficant amout of time is my non-expertise in these matters! I am fairly knowledgeable as a consumer of standard library containers. I am not so knowledgeable about writing template libraries. I usually proceed in blissful ignorance of the exception safety issues that concerned the author. As noted at the start, I think overall the library should be accepted, after assuring the compilation issues are worked out. You might consider some of the documentation issues. I would also recommend those with greater expertise consider the implications and possible solutions to the breakage of some standard algorithms. DETAILED DOCUMENTATION COMMENTS Here are my comments while reading through the documentation, including answers to some of the issues raised for reviewers in the documentation. I have prefaced individual points with *, and ** for more important ones. file:/usr/local/src/boost/boost/libs/smart_container/doc/smart_container.html *The date at the top lacks a year. * Might be useful to break this page into several distinct pages. * At the very beginning, it might be worth saying that the containers of smart pointers don't work at all if the objects are not Assignable or Copy Constructible. This is mentioned a few paragraphs down, but someone reading the description quickly might think the only benefit of the library is that it offers a more optimal solution to some problems. In fact, it lets you do things you couldn't otherwise do (easily). In case you can't tell, this was a major reason I used the library. * Reference to polymorphic class problem is puzzling in two ways. First, the section on the problem does not seem to state the problem directly (apparently it is how to ensure proper clean up of objects when we refer to them with pointers to a base class; perhaps it is also the fact that one can't have a list of such types directly, but need to use pointers). I had not heard of the problem and it doesn't seem like such a problem. Second, it's not clear to me what smart containers add to this particular problem, given that smart pointers are available. It is true that this library does offer one solution to the problem (if I have understood it correctly). Perhaps if the introduction that now says "In this respect the library is intended to solve the so-called polymorphic class problem." said "The library also offers a solution to the so-called polymorphic class problem." It would be clearer. * Calling this the "smart container" library and then using names like "ptr_xxx" seems an invitation to confusion. "smart_xxx" would be more natural. At this point, it may be too much trouble and possibility for error to change the names, even if you agree with this point. * In the first example, in English the sound of a cow is usually rendered as "Moooh!". * Still in that example, the use of "stable" got me thinking about stable vs unstable. In particular a "stable_type" is not a polymorphic type. I wasn't actually confused, and probably no one else will be, but it did generate a little cognitive interference. You might use "barn" instead of "stable". * do we want the tricky algorithms implemented as members? Not clear to me if to_remove in example 8 is supposed to be something in the container, or if it just needs to be equivalent (I assume the latter, by analogy with existing stuff in the standard library). Will incorrect semantics or errors result from naive use of the corresponding non-member operators? Apparently so, according to later discussion. ** I found it a bit difficult to find reference information. First, the material requires a fair number of clicks to reach. Second, it was not clear to me where to look for information that was not in a given entry. There are several reasons for this. The "see also" heading mixes material you must look at (base classes and pseudo-base classes such as reversible_smart_container) and classes that are simply related (e.g. ptr_vector and ptr_array). So it took me awhile to find the definition for auto_type used in, e.g., ptr_array. If you could distinguish inheritance relations from others, that would be good. I'm sure part of the problem is that some of the material is only a conceptual inheritance, but still it would be useful to know that, for example, ptr_vector has the protocols of ptr_sequence_adapter, which in turn has the protocols of reversible_smart_container. Also, there are notations like "Exception safety: strong guarantee". A link or further explanation would be useful for those who aren't familiar with these terms. * The first FAQ item probably saved me a lot of grief. ** The unsafe mutating algorithms, in the FAQ now, probably deserves more prominence, in a discussion (in the main documentation) of what algorithms are appropriate to use with these containers. This item makes me nervous. First, it sounds as if only an implementor of a library would know which algorithms actually moved things around by swapping. This leaves the average user unsure of which algorithms are safe. Second, it seems like asking for trouble for it to be so easy to cause problems. * FAQ on inserting member function overloading for pointer and reference. Reviewer Q: do we want this behavior? I would say definitely, as it reduces the chances for user error. * Acknowledgements: perhaps "crappy" lacks the elevated tone we seek? And, though I assume it's a good-natured jest, some might take it the wrong way. Review Issues: 4. Is the indirected predicates the right solution? It was exactly what I was looking for, so I'm inclined to say yes :) 5. Should SmartContainer::auto_type expose itself as a move_ptr? Probably; the current name seems derived from the way it's implemented (auto_ptr, I assume). But if it has auto_ptr semantics, and it's important for the user to be aware of those, it's probably best to leave it as is. 6. Should iterator range versions of assign() and insert be replaced by an Boost.Range version? Ie, should we have template< class SinglePassRange > void insert( const Range& r ); instead of template< class InputIterator > void insert( InputIterator f, InputIterator l ); ?? The more this class can behave like any std::container, the better. So I'd lean toward leaving it as is. However, if the Boost.Range thing is compatible (I'm not familar with it), this argument loses force. 7. Should we remove rbegin()/rend()? Boost.Range makes these unnecessary. Same as 6. 8. Should we add const_begin()/const_end() etc to the classes. Again, Boost.Range means we don't need to define them. As these are not in the standard, I don't think adding them is important. In fact, one could argue that adding things not in other containers may confuse users, if they think that learning the interface for one container class gives them protocols they can transfer to others. In plainer language, if this library provided const_begin, people might assume std::vector did as well. 9. Should we add iterators for traversing the keys of a map? This would mean we could say map::key_iterator b = m.begin(), e = m.end(); copy( b, e, some_where ); That would be useful. 10. should transfer() return iterator or iterator/bool pair like erase()/insert() do. I vote for returning an iterator to the start of the inserted sequence, and throwing exceptions if things go wrong. 11. should a templated map::insert() be defined: template< class Convertible2Key > void insert( Convertible2Key&, T* r ); ? This would allow usage like m.insert( "foo", new Foo ); Probably not. It might create unintended conversions, and it's probably better to leave it the client if they want this kind of behavior. 12. should we provide member algorithms for unsafe standard algorithms like unique() and remove? Yes. 13. Is the shared_ptr idea described in future directions a good idea? I'm not sure I grasp the concept well enough to comment, but it seems to me it kind of muddies the waters. That is, shared pointers are a different kind of ownership concept than this library, and I suspect it will be cleaner to keep them separate. I mean, mostly, cleaner for users. -- Ross Boylan wk: (415) 502-4031 530 Parnassus Avenue (Library) rm 115-4 ross@biostat.ucsf.edu Dept of Epidemiology and Biostatistics fax: (415) 476-9856 University of California, San Francisco San Francisco, CA 94143-0840 hm: (415) 550-1062 make[1]: Entering directory `/home/ross/peter/R/mspath/src/debugTest' g++ -I /home/ross/peter/R/mspath/src -I/usr/lib/R/include -MMD -MF /home/ross/peter/R/mspath/src/depends/Path.d -MP -g -O0 -c -o Path.o /home/ross/peter/R/mspath/src/trueSrc/Path.cc g++ -I /home/ross/peter/R/mspath/src -I/usr/lib/R/include -MMD -MF /home/ross/peter/R/mspath/src/depends/PathGenerator.d -MP -g -O0 -c -o PathGenerator.o /home/ross/peter/R/mspath/src/trueSrc/PathGenerator.cc g++ -I /home/ross/peter/R/mspath/src -I/usr/lib/R/include -MMD -MF /home/ross/peter/R/mspath/src/depends/SimpleRecorder.d -MP -g -O0 -c -o SimpleRecorder.o /home/ross/peter/R/mspath/src/trueSrc/SimpleRecorder.cc g++ -I /home/ross/peter/R/mspath/src -I/usr/lib/R/include -MMD -MF /home/ross/peter/R/mspath/src/depends/SuccessorGenerator.d -MP -g -O0 -c -o SuccessorGenerator.o /home/ross/peter/R/mspath/src/trueSrc/SuccessorGenerator.cc g++ -I /home/ross/peter/R/mspath/src -I/usr/lib/R/include -MMD -MF /home/ross/peter/R/mspath/src/depends/StateTimeClassifier.d -MP -g -O0 -c -o StateTimeClassifier.o /home/ross/peter/R/mspath/src/trueSrc/StateTimeClassifier.cc g++ -I /home/ross/peter/R/mspath/src -I/usr/lib/R/include -MMD -MF /home/ross/peter/R/mspath/src/depends/TestRecorder.d -MP -g -O0 -c -o TestRecorder.o /home/ross/peter/R/mspath/src/trueSrc/TestRecorder.cc In file included from /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set.hpp:23, from /home/ross/peter/R/mspath/src/trueSrc/TestRecorder.h:11, from /home/ross/peter/R/mspath/src/trueSrc/TestRecorder.cc:6: /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:22: error: parse error before `<' token /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:25: error: ISO C++ forbids declaration of `value_type' with no type /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:25: error: parse error before `;' token /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp: In member function `void boost::ptr_set_adapter<Set, CloneManager>::transfer(typename PtrContainer::iterator, PtrContainer&)': /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:252: error: parse error before `;' token In file included from /home/ross/peter/R/mspath/src/trueSrc/TestRecorder.cc:6: /home/ross/peter/R/mspath/src/boost/smart_container/detail/associative_smart_container.hpp: At global scope: /home/ross/peter/R/mspath/src/boost/smart_container/detail/associative_smart_container.hpp: In instantiation of `boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>': mspath.web:4864: instantiated from `boost::ptr_set_adapter_base<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>' mspath.web:4864: instantiated from `boost::ptr_set_adapter<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>' mspath.web:4864: instantiated from `boost::ptr_set<mspath::Path, boost::ptr_less<mspath::Path>, boost::heap_clone_manager>' mspath.web:4864: instantiated from here /home/ross/peter/R/mspath/src/boost/smart_container/detail/associative_smart_container.hpp:39: error: no type named `key_type' in `struct boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >' /home/ross/peter/R/mspath/src/boost/smart_container/detail/associative_smart_container.hpp:102: error: no type named `key_type' in `struct boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp: In instantiation of `boost::ptr_set_adapter_base<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>': mspath.web:4864: instantiated from `boost::ptr_set_adapter<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>' mspath.web:4864: instantiated from `boost::ptr_set<mspath::Path, boost::ptr_less<mspath::Path>, boost::heap_clone_manager>' mspath.web:4864: instantiated from here /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:61: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:84: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:90: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:96: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:101: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:107: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:113: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:119: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:125: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:133: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:141: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:150: error: no type named `key_type' in `class boost::detail::associative_smart_container<boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp: In instantiation of `boost::ptr_set_adapter<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>': mspath.web:4864: instantiated from `boost::ptr_set<mspath::Path, boost::ptr_less<mspath::Path>, boost::heap_clone_manager>' mspath.web:4864: instantiated from here /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:180: error: no type named `key_type' in `class boost::ptr_set_adapter_base<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:223: error: no type named `key_type' in `class boost::ptr_set_adapter_base<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>' /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:228: error: no type named `key_type' in `class boost::ptr_set_adapter_base<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, boost::heap_clone_manager>' mspath.web: In member function `virtual boost::indirect_iterator<std::_Rb_tree_iterator<mspath::Path*, mspath::Path* const&, mspath::Path* const*>, boost::use_default, boost::use_default, boost::use_default, boost::use_default> mspath::TestRecorder::PathSet::insertUnique(mspath::Path*)': mspath.web:5319: error: no matching function for call to ` mspath::TestRecorder::PathSet::insert(mspath::Path* const&)' /home/ross/peter/R/mspath/src/boost/smart_container/detail/reversible_smart_container.hpp:449: error: candidates are: void boost::detail::reversible_smart_container<Config, CloneManager>::insert(typename Config::iterator, typename Config::container_type::size_type, typename Config::value_type&) [with Config = boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, CloneManager = boost::heap_clone_manager] /home/ross/peter/R/mspath/src/boost/smart_container/detail/reversible_smart_container.hpp:444: error: typename Config::iterator boost::detail::reversible_smart_container<Config, CloneManager>::insert(typename Config::iterator, typename Config::value_type&) [with Config = boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, CloneManager = boost::heap_clone_manager] /home/ross/peter/R/mspath/src/boost/smart_container/detail/reversible_smart_container.hpp:432: error: typename Config::iterator boost::detail::reversible_smart_container<Config, CloneManager>::insert(typename Config::iterator, typename Config::value_type*) [with Config = boost::set_config<std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> > >, CloneManager = boost::heap_clone_manager] mspath.web: In member function `virtual void mspath::TestRecorder::PathSet::transferUnique(boost::indirect_iterator<std::_Rb_tree_iterator<mspath::Path*, mspath::Path* const&, mspath::Path* const*>, boost::use_default, boost::use_default, boost::use_default, boost::use_default>, mspath::TestRecorder::PathSet&)': mspath.web:5332: error: no matching function for call to `find(mspath::Path&)' mspath.web: In member function `virtual void mspath::TestRecorder::goodPath(const mspath::Path&)': mspath.web:5287: error: `find' undeclared (first use this function) mspath.web:5287: error: (Each undeclared identifier is reported only once for each function it appears in.) /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp: In member function `void boost::ptr_set_adapter<Set, CloneManager>::transfer(typename PtrContainer::iterator, PtrContainer&) [with PtrContainer = mspath::TestRecorder::PathSet, Set = std::set<mspath::Path*, boost::ptr_less<mspath::Path>, std::allocator<mspath::Path*> >, CloneManager = boost::heap_clone_manager]': mspath.web:5335: instantiated from here /home/ross/peter/R/mspath/src/boost/smart_container/ptr_set_adapter.hpp:254: error: ` p' undeclared (first use this function) dî@: In function `_InputIter std::find(_InputIter, _InputIter, const _Tp&) [with _InputIter = __gnu_cxx::__normal_iterator<const mspath::TestRecorder::GeneratorState*, std::vector<mspath::TestRecorder::GeneratorState, std::allocator<mspath::TestRecorder::GeneratorState> > >, _Tp = mspath::TestRecorder::GeneratorState]': mspath.web:5414: instantiated from here dî@:256: error: `<declaration error>' is not a function, /usr/include/c++/3.3/bits/stl_algo.h:293: error: conflict with ` template<class _InputIter, class _Tp> _InputIter std::find(_InputIter, _InputIter, const _Tp&)' /usr/include/c++/3.3/bits/stl_algo.h:298: error: in call to `find' make[1]: *** [TestRecorder.o] Error 1 make[1]: Leaving directory `/home/ross/peter/R/mspath/src/debugTest' make: *** [test] Error 2 ----- End forwarded message -----