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

Click here to view the latest version of this page.

Boost.MultiIndex Examples



Contents

Example 1: basic usage

See source code.

Basic program showing the multi-indexing capabilities of Boost.MultiIndex with an admittedly boring set of employee records.

Example 2: using member functions as keys

See source code.

Usually keys assigned to an index are based on a member variable of the element, but key extractors can be defined which take their value from a member function. This has some similarity with the concept of calculated keys supported by some relational database engines. The example shows how to use the predefined const_mem_fun key extractor to deal with this situation.

Keys based on member functions usually will not be actual references, but rather the temporary values resulting from the invocation of the member function used. This implies that modify_key cannot be applied to this type of extractors, which is a perfectly logical constraint anyway.

Example 3: constructing multi_index_containers with ctor_args_list

See source code.

We show a practical example of usage of multi_index_container::ctor_arg_list, whose definition and purpose are explained in the Advanced topics section. The program groups a sorted collection of numbers based on identification through modulo arithmetics, by which x and y are equivalent if (x%n)==(y%n), for some fixed n.

Example 4: bidirectional map

See source code.

This example shows how to construct a bidirectional map with multi_index_container. By a bidirectional map we mean a container of elements of std::pair<const FromType,const ToType> such that no two elements exists with the same first or second value (std::map only guarantees uniqueness of the first member). Fast lookup is provided for both keys. The program features a tiny Spanish-English dictionary with online query of words in both languages.

Example 5: sequenced indices

See source code.

The combination of a sequenced index with an index of type ordered_non_unique yields a list-like structure with fast lookup capabilities. The example performs some operations on a given text, like word counting and selective deletion of some words.

Example 6: complex searches and foreign keys

See source code.

This program illustrates some advanced techniques that can be applied for complex data structures using multi_index_container. Consider a car_model class for storing information about automobiles. On a fist approach, car_model can be defined as:

struct car_model
{
  std::string model;
  std:string  manufacturer;
  int         price;
};

This definition has a design flaw that any reader acquainted with relational databases can easily spot: The manufacturer member is duplicated among all cars having the same manufacturer. This is a waste of space and poses difficulties when, for instance, the name of a manufacturer has to be changed. Following the usual principles in relational database design, the appropriate design involves having the manufactures stored in a separate multi_index_container and store pointers to these in car_model:

struct car_manufacturer
{
  std::string name;
};

struct car_model
{
  std::string       model;
  car_manufacturer* manufacturer;
  int               price;
};

Although predefined Boost.MultiIndex key extractors can handle many situations involving pointers (see advanced features of Boost.MultiIndex key extractors in the Advanced topics section), this case is complex enough that a suitable key extractor has to be defined. The following utility cascades two key extractors:

template<class KeyExtractor1,class KeyExtractor2>
struct key_from_key
{
public:
  typedef typename KeyExtractor1::result_type result_type;

  key_from_key(
    const KeyExtractor1& key1_=KeyExtractor1(),
    const KeyExtractor2& key2_=KeyExtractor2()):
    key1(key1_),key2(key2_)
  {}

  template<typename Arg>
  result_type operator()(Arg& arg)const
  {
    return key1(key2(arg));
  }

private:
  KeyExtractor1 key1;
  KeyExtractor2 key2;
};

so that access from a car_model to the name field of its associated car_manufacturer can be accomplished with

key_from_key<
  member<car_manufacturer,const std::string,&car_manufacturer::name>,
  member<car_model,const car_manufacturer *,car_model::manufacturer>
>

The program asks the user for a car manufacturer and a range of prices and returns the car models satisfying these requirements. This is a complex search that cannot be performed on a single operation. Broadly sketched, one procedure for executing the selection is:

  1. Select the elements with the given manufacturer by means of equal_range,
  2. feed these elements into a multi_index_container sorted by price,
  3. select by price using lower_bound and upper_bound;
or alternatively:
  1. Select the elements within the price range with lower_bound and upper_bound,
  2. feed these elements into a multi_index_container sorted by manufacturer,
  3. locate the elements with given manufacturer using equal_range.
An interesting technique developed in the example lies in the construction of the intermediate multi_index_container. In order to avoid object copying, appropriate view types are defined with multi_index_containers having as elements pointers to car_models instead of actual objects. These views have to be supplemented with appropriate dereferencing key extractors.

Example 7: composite keys

See source code.

Boost.MultiIndex composite_key construct provides a flexible tool for creating indices with non-trivial sorting criteria. The program features a rudimentary simulation of a file system along with an interactive Unix-like shell. A file entry is represented by the following structure:

struct file_entry
{
  std::string       name;
  unsigned          size;
  bool              is_dir; // true if the entry is a directory
  const file_entry* dir;    // directory this entry belongs in
};

Entries are kept in a multi_index_container maintaining two indices with composite keys:

The reason that the order is made firstly by the directory in which the files are located obeys to the local nature of the shell commands, like for instance ls. The shell simulation only has three commands: The program exits when the user presses the Enter key at the command prompt.

The reader is challenged to add more functionality to the program (for instance, implementation of the cp command and handling of absolute paths.)




Revised May 28th 2004

© Copyright 2003-2004 Joaquín M López Muñoz. 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)