[boost] [multi_index] intrusive multi_index poll for interest

From: Maxim Yegorushkin (maxim.yegorushkin_at_[hidden])
Date: 2005-12-31 15:01:00

Motivation

Existing practice have shown the need for intrusive containers. Widely used C++
   libraries, such as C++ Standard Library and Boost have long missed such
   facilities so that users had to refrain from using those due to mandatory
   element copying or fall back to techniques like two phase construction to
   insert logically non-copyable elements in containers and initialize them after
   that or insert pointers to dynamically allocated objects which is rather
   inelegant and inefficient since containers also dynamically allocate nodes.

The most common use cases for intrusive containers are:

* when one would like to store non-copyable elements in a container
* when it's beneficial to avoid needless data copy in performance critical
   applications

The most prominent example of both the use cases, although written for the most
   part in C rather than C++, is Linux kernel built solely upon intrusive lists,
   hash tables and trees.

Basic usage

An intrusive container is not a container in a stl sense, since it does not own
   its elements. The sole purpose of an intrusive container is to establish
   ordering between elements. It's a user responsibility to keep an intrusive
   container up-to-date by calling replace() to alter fields upon which an order
   is established as well as erase the nodes from the container prior to node's
   destruction. Aside from that the look and feel are similar to those of an
   non-intrusive container.

Here is how one would declare an intrusive container, an intrusive node and
   insert removes nodes:

   struct record;

   typedef multi_index_container<intrusive<record> > container;

   struct record : container::node_type {};

   bool operator<(record const& a, record const& b);

   void insert_sample(container* c)
   {
       std::auto_ptr<record> p(new record);
       if(c->insert(*p).second)
           p.release();
   }

   void erase_sample(container* c, container::iterator pos)
   {
       std::auto_ptr<record const> p(&*pos);
       c->erase(pos);
   }

Here is how one would make a multi-node, i.e. a node that can be enlisted into
   several containers simultaneously:

   struct record;

   struct tag1;
   struct tag2;

   typedef multi_index_container<intrusive<record, tag1> > container1;
   typedef multi_index_container<intrusive<record, tag2> > container2;

   struct record : container1::node_type, container2::node_type {};

   inline bool operator<(record const& a, record const& b);

   void insert_sample(container1* c1, container2* c2)
   {
       struct guard
       {
           container1* c1;
           container2* c2;
           std::pair<container1::iterator, bool> i1;
           std::pair<container2::iterator, bool> i2;
           std::auto_ptr<record> p;
           ~guard()
           {
              if(i1.second && i2.second) { p.release(); }
              else { c1->erase(i1.first); c2->erase(i2.first); }
           }
           guard(container1* c1, container2* c2, std::auto_ptr<record> p)
               : c1(c1), c2(c2), i1(c1->end(), 0), i2(c2->end(), 0), p(p)
           {}
       } guard(c1, c2, std::auto_ptr<record>(new record));

       guard.i1 = c1->insert(*guard.p);
       guard.i2 = c2->insert(*guard.p);
   }

   void erase_sample(container1* c1, container2* c2, record* r)
   {
       c1->erase(c1->make_iterator(r));
       c2->erase(c2->make_iterator(r));
       delete r;
   }

The examples are included in test_intrusive.cpp.

Current implementation

Current implementation although efficient and mostly functional is a proof of
   concept only. Further design work is required which we rather unclear about
   and therefore would like to poll for interest and suggestions.

Known limitations:
   * partial template specialization support is required
   * dereferencing an intrusive container iterator yields a constant, should
     probably return non-constant
   * safe mode is not implemented for make_iterator() exposed api

http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename=intrusive_multi_index.tar.bz2&directory=Containers&