Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Boost.MultiIndex Tutorial: Container creation

Key extraction

Boost.MultiIndex tutorial

Debugging support

Value semantics
Use of ctor_args_list
Special allocator support
Serialization

Value semantics

multi_index_containers have the usual value semantics associated to copy construction and assignment, i.e. copies of the elements from the source container are created and inserted into the destination container. More interestingly, copying also recreates the original order in which elements are arranged for every index of the container. This implies that equality of all indices is preserved under copying or assignment, for those index types where equality is defined. This behavior can be regarded as a natural extension to the general rule on copy semantics stating that if y is a copy of x, then y==x.

Use of `ctor_args_list`

Although in most cases multi_index_containers will be default constructed (or copied from a preexisting multi_index_container), sometimes it is necessary to specify particular values for the internal objects used (key extractors, comparison predicates, allocator), for instance if some of these objects do not have a default constructor. The same situation can arise with standard STL containers, which allow for the optional specification of such objects:

// example of non-default constructed std::set
template<typename IntegralType>
struct modulo_less
{
  modulo_less(IntegralType m):modulo(m){}

  bool operator()(IntegralType x,IntegralType y)const
  {
    return (x%modulo)<(y%modulo);
  }

private:
  IntegralType modulo;
};

typedef std::set<unsigned int,modulo_less<unsigned int> > modulo_set;

modulo_set m(modulo_less<unsigned int>(10));

multi_index_container does also provide this functionality, though in a considerably more complex fashion, due to the fact that the constructor of a multi_index_container has to accept values for all the internal objects of its indices. The full form of multi_index_container constructor is

explicit multi_index_container(
    const ctor_args_list& args_list=ctor_args_list(),
    const allocator_type& al=allocator_type());

The specification of the allocator object poses no particular problems; as for the ctor_args_list, this object is designed so as to hold the necessary construction values for every index in the multi_index_container. From the point of view of the user, ctor_args_list is equivalent to the type

boost::tuple<C₀,...,C_I-1>

where I is the number of indices, and C_i is

nth_index<i>::type::ctor_args

that is, the nested type ctor_args of the i-th index. Each ctor_args type is in turn a tuple holding values for constructor arguments of the associated index: so, ordered indices demand a key extractor object and a comparison predicate, hashed indices take an initial number of buckets, a key extractor, a hash function and an equality predicate; while sequenced and random access indices do not need any construction argument. For instance, given the definition

typedef multi_index_container<
  unsigned int,
  indexed_by<
    hashed_unique<identity<unsigned int> >,
    ordered_non_unique<identity<unsigned int>, modulo_less<unsigned int> >,
    sequenced<>,
    random_access<>
  >
> modulo_indexed_set;

the corresponding ctor_args_list type is equivalent to

boost::tuple<
  // ctr_args of index #0
  boost::tuple<
    std::size_t, // initial number of buckets; 0 if unspecified
    identity<unsigned int>,
    boost::hash<unsigned int>,
    std::equal_to<unsigned int> >,    

  // ctr_args of index #1
  boost::tuple<
    identity<unsigned int>,
    modulo_less<unsigned int> >,
  
  // sequenced indices do not have any construction argument
  boost::tuple<>,

  // neither do random access indices
  boost::tuple<>
>

Such a modulo_indexed_set cannot be default constructed, because modulo_less does not provide a default constructor. The following shows how the construction can be done:

modulo_indexed_set::ctor_args_list args_list=
  boost::make_tuple(
    // ctor_args for index #0 is default constructible
    modulo_indexed_set::nth_index<0>::type::ctor_args(),
    
    boost::make_tuple(identity<unsigned int>(),modulo_less<unsigned int>(10)),
    
    // these are also default constructible (actually, empty tuples) 
    modulo_indexed_set::nth_index<2>::type::ctor_args(),
    modulo_indexed_set::nth_index<3>::type::ctor_args()
  );

modulo_indexed_set m(args_list);

A program is provided in the examples section that puts in practise these concepts.

Special allocator support

Boost.MultiIndex allows for a slightly more general class of allocators than strictly required by the C++ standard, as explained in detail in the reference. An important type of non-standard allocators supported are those provided by the Boost Interprocess Library; this opens up the possibility of placing multi_index_containers in shared memory.

#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/managed_shared_memory.hpp>

namespace bip=boost::interprocess;

// a shared memory compatible allocator of ints
typedef bip::allocator<
  int,bip::managed_shared_memory::segment_manager
> shared_int_allocator;

// define a shared memory compatible multi_index_container
// using shared_int_allocator
typedef multi_index_container<
  int,
  indexed_by<
    sequenced<>,
    ordered_unique<identity<int> >
  >,
  shared_int_allocator
> unique_int_list;

...

// create a managed memory segment
bip::managed_shared_memory seg(
  bip::create_only,"SharedMemoryID",65536);

// construct a unique_int_list into the segment
unique_int_list* puil=seg.construct<unique_int_list>
  ("UniqueIntListID") // object identifier within the segment
  // Construction args: first a ctor arg list, then a
  // shared memory allocator obtained from the segment object.
  (unique_int_list::ctor_args_list(),
   unique_int_list::allocator_type(seg.get_segment_manager()));

The examples section includes a program that further explores this capability.

Serialization

multi_index_containers can be archived and retrieved by means of the Boost Serialization Library. Both regular and XML archives are supported. The usage is straightforward and does not differ from that of any other serializable type. For instance:

#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <fstream>

...

void save(const employee_set& es)
{
  std::ofstream ofs("data");
  boost::archive::text_oarchive oa(ofs);
  oa<<es;
}

void load(employee_set& es)
{
  std::ifstream ifs("data");
  boost::archive::text_iarchive ia(ifs);
  ia>>es;
}

...

employee_set es;
... // fill it with data
save(es);

...

employee_set restored_es;
load(restored_es);

Serialization capabilities are automatically provided by just linking with the appropriate Boost.Serialization library module: it is not necessary to explicitly include any header from Boost.Serialization, apart from those declaring the type of archive used in the process. If not used, however, serialization support can be disabled by globally defining the macro BOOST_MULTI_INDEX_DISABLE_SERIALIZATION. Disabling serialization for Boost.MultiIndex can yield a small improvement in build times, and may be necessary in those defective compilers that fail to correctly process Boost.Serialization headers.

In accordance with Boost.MultiIndex value semantics, retrieving an archived multi_index_container restores not only the elements, but also the order they were arranged into for every index of the container. There is an exception to this rule, though: for hashed indices, no guarantee is made about the order in which elements will be iterated in the restored container; in general, it is unwise to rely on the ordering of elements of a hashed index, since it can change in arbitrary ways during insertion or rehashing --this is precisely the reason why hashed indices and TR1 unordered associative containers do not define an equality operator.

Iterators to indices of a multi_index_container can also be serialized. Serialization of iterators must be done only after serializing their corresponding container.

Example 9 in the examples section shows the serialization capabilities of Boost.MultiIndex.