AMDG I think that Intrusive should be accepted into Boost. The documentation is good. I had no problems compiling with msvc 8.0 The design and implementation are pretty straightforward. I have needed embedded linked lists at least once in the last year. So, I definitely have a use for this library. intrusive.qbk line 136 [*Boost.Intrusive]container missing space intrusive.qbk lines 169-170 because the object can be destroyed before erasing it from the container. Dangling participle intrusive.qbk line 172 However swapping can be used to implement move-capabilities missing comma after however. intrusive.qbk line 263-264 A class that the user must add as a base class or as a member to its own class its should be his. A user is a person not a thing. intrusive.qbk line 306-307 it can store the number of stored elements to achieve constant-time size information, it can offer debugging facilities... Using store twice sounds a little odd. These are both complete sentences and should therefore be separated by a semicolon instead of a comma. islist is a terrible name. I automatically read this as a predicate (is X a list) the second template parameter of ilist_base_hook &c. could be an mpl::bool_ or better it could be unique type that expresses the meaning better. struct safe_mode {}; struct fast_mode {}; intrusive.qbk line 531 typedef boost::intrusive::ilist_base_hook<Foo>::value_traits<Foo> FooValueTraits; should be typedef boost::intrusive::ilist_base_hook<Tag>::value_traits<Foo> FooValueTraits; intrusive.qbk line 564 Sometimes a 'is-a' relationship a should be an intrusive.qbk line 689-690 That's why you better avoid them in public interfaces of libraries. "That's why you should avoid them in public interfaces of libraries."? ilist_hook.hpp line 121 ilist_base_hook& ilist_base_hook::operator=(const ilist_base_hook& ); I'm not sure that forbidding assignment of nodes that are linked is a good idea. ilist_hook.hpp line 163 bool ilist_base_hook::linked() const; Since this is only allowed in safe mode it should fail to compile instead of asserting at runtime. On further reflection the safe mode and non-safe mode variants are sufficiently different to warrant two specializations. config_begin line 12, config_end.hpp line 15 #ifdef _MSC_VER should be #ifdef BOOST_MSVC I suggest this implementation for the default size_type parameter. As it stands, ADL pulls in namespace std for the containers. (ADL pulls in namespace detail, too but there are no fully generic functions in namespace boost::intrusive::detail) struct default_size_type {}; template<class T> struct get_size_type { typedef T type }; template<> struct get_size_type<default_size_type> { typedef std::size_t type }; template< class ValueTraits , bool ConstantTimeSize = true , class SizeTypeParam = default_size_type> class ilist : private detail::size_holder<ConstantTimeSize, typename get_size_type<SizeTypeParam>::type> { typedef typename get_size_type<SizeTypeParam>::type SizeType; //... }; swap_nodes doesn't handle adjacent nodes correctly. This isn't a problem now but you might make a note of it just in case it does become a problem. For slist you might consider adding a pointer to the last element so that swap can execute in constant time. clone_from can use insert_after to be optimally efficient. I'm unclear about the usefulness of clone_from. First of all it doesn't look more efficient than what I would write by hand. Second, it only provides the basic guarantee although the strong guarantee can be achieved as follows for ilist (assuming that destroyer completely reverses the effects of cloner). template <class Cloner, class Destroyer> void clone_from(const ilist &src, Cloner cloner, Destroyer destroyer) { class cleanup { public: cleanup(Destroyer& d) : destroyer(d) {} ~cleanup() { value.clear_and_destroy(destroyer); } ilist value; Destroyer& destroyer; } temp(destroyer); for(const_iterator b(src.begin()), e(src.end()) ; b != e; ++b){ temp.value.push_back(*cloner(*b)); } this->swap(temp.value); } The principal use I can think of for clone_from is a container that can hold objects of different types. You might change doc_clone_from.cpp to use a polymorphic clone function instead of new so that it doesn't seem quite so contrived. member_hooks do not work with virtual inheritance. This blows up. #include <boost/intrusive/ilist.hpp> struct Y {}; struct X : virtual public Y { boost::intrusive::ilist_member_hook<X> hook; int i; }; typedef boost::intrusive::ilist_member_hook<X>::value_traits<&X::hook> value_traits; int main() { X x; boost::intrusive::ilist<value_traits> list; list.push_back(x); list.front().i = 1; } I don't think that current is a good name for the function that gets an iterator from the value_type. How about something a little more descriptive like get_iterator, iterator_from, or to_iterator? I would prefer to use CRTP for hooks template<class Derived, class Tag, bool SafeMode, class Pointer> struct ilist_base_hook; Or at least use a metafunction instead of a member template for the value_traits. template<class Hook, class T> struct base_hook_value_traits; The base class hooks should be in a nested namespace and be brought into namespace intrusive with using to prevent unwanted ADL. The BOOST_STATIC_ASSERT in ilist needs to be INTERNAL ONLYed. I compared the performance of sort for ilist on a std::random_shuffled set of one million ints with msvc 8.0. (code is attached) INTRUSIVE .51 sec LIST .89 sec LIST POINTER 1.14 sec VECTOR .20 sec VECTOR STABLE .23 sec VECTOR POINTER .46 sec VECTOR POINTER STABLE .42 sec In Christ, Steven Watanabe // sort_benchmark.cpp // // Copyright (c) 2007 // Steven Watanabe // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #include <ctime> #include <vector> #include <list> #include <algorithm> #include <iostream> #include <boost/lambda/lambda.hpp> #include <boost/lambda/bind.hpp> #include <boost/intrusive/ilist.hpp> //#define INTRUSIVE //#define LIST #define VECTOR //#define POINTER #define STABLE struct Y {}; struct X { #ifdef INTRUSIVE boost::intrusive::ilist_member_hook<X> hook; #endif int i; bool operator<(const X& other) const { return(i < other.i); } X(int val) : i(val) {} }; #ifdef POINTER typedef X* x_type; #define PREDICATE *boost::lambda::_1 < *boost::lambda::_2 #define TRANSFORM &boost::lambda::_1 #else typedef X x_type; #define PREDICATE boost::lambda::_1 < boost::lambda::_2 #define TRANSFORM boost::lambda::_1 #endif #ifdef STABLE #define SORT std::stable_sort #else #define SORT std::sort #endif int main() { #ifdef LIST typedef std::list<x_type> list_t; #elif defined(VECTOR) typedef std::vector<x_type> list_t; #elif defined(INTRUSIVE) typedef boost::intrusive::ilist<boost::intrusive::ilist_member_hook<X>::value_traits<&X::hook> > list_t; #endif list_t list; std::vector<X> x; for(int i = 0; i < 1000000; ++i) { x.push_back(X(i)); } std::random_shuffle(x.begin(), x.end()); std::for_each(x.begin(), x.end(), boost::lambda::bind(&list_t::push_back, boost::lambda::var(list), TRANSFORM)); { std::clock_t start_time = std::clock(); #if defined(LIST) || defined(INTRUSIVE) list.sort(PREDICATE); #else SORT(list.begin(), list.end(), PREDICATE); #endif std::cout << "time for sort: " << static_cast<double>(std::clock() - start_time) / CLOCKS_PER_SEC << std::endl; } list_t::const_iterator iter(list.begin()); list_t::const_iterator end(list.end()); list.erase(list.begin(), list.end()); }