Chapter 12. Boost.MultiIndex

Boost.MultiIndex makes it possible to define containers that support an arbitrary number of interfaces. While std::vector provides an interface that supports direct access to elements with an index and std::set provides an interface that sorts elements, Boost.MultiIndex lets you define containers that support both interfaces. Such a container could be used to access elements using an index and in a sorted fashion.

Boost.MultiIndex can be used if elements need to be accessed in different ways and would normally need to be stored in multiple containers. Instead of having to store elements in both a vector and a set and then synchronizing the containers continuously, you can define a container with Boost.MultiIndex that provides a vector interface and a set interface.

Boost.MultiIndex also makes sense if you need to access elements based on multiple different properties. In Example 12.1, animals are looked up by name and by number of legs. Without Boost.MultiIndex, two hash containers would be required – one to look up animals by name and the other to look them up by number of legs.

Example 12.1. Using boost::multi_index::multi_index_container

  1. #include <boost/multi_index_container.hpp>
  2. #include <boost/multi_index/hashed_index.hpp>
  3. #include <boost/multi_index/member.hpp>
  4. #include <string>
  5. #include <iostream>
  7. using namespace boost::multi_index;
  9. struct animal
  10. {
  11.   std::string name;
  12.   int legs;
  13. };
  15. typedef multi_index_container<
  16.   animal,
  17.   indexed_by<
  18.     hashed_non_unique<
  19.       member<
  20.         animal, std::string, &animal::name
  21.       >
  22.     >,
  23.     hashed_non_unique<
  24.       member<
  25.         animal, int, &animal::legs
  26.       >
  27.     >
  28.   >
  29. > animal_multi;
  31. int main()
  32. {
  33.   animal_multi animals;
  35.   animals.insert({"cat", 4});
  36.   animals.insert({"shark", 0});
  37.   animals.insert({"spider", 8});
  39.   std::cout << animals.count("cat") << '\n';
  41.   const animal_multi::nth_index<1>::type &legs_index = animals.get<1>();
  42.   std::cout << legs_index.count(8) << '\n';
  43. }

When you use Boost.MultiIndex, the first step is to define a new container. You have to decide which interfaces your new container should support and which element properties it should access.

The class boost::multi_index::multi_index_container, which is defined in boost/multi_index_container.hpp, is used for every container definition. This is a class template that requires at least two parameters. The first parameter is the type of elements the container should store – in Example 12.1 this is a user-defined class called animal. The second parameter is used to denote different indexes the container should provide.

The key advantage of containers based on Boost.MultiIndex is that you can access elements via different interfaces. When you define a new container, you can specify the number and type of interfaces. The container in Example 12.1 needs to support searching for animals by name or number of legs, so two interfaces are defined. Boost.MultiIndex calls these interfaces indexes – that’s where the library’s name comes from.

Interfaces are defined with the help of the class boost::multi_index::indexed_by. Each interface is passed as a template parameter. Two interfaces of type boost::multi_index::hashed_non_unique, which is defined in boost/multi_index/hashed_index.hpp, are used in Example 12.1. Using these interfaces makes the container behave like std::unordered_set and look up values using a hash value.

The class boost::multi_index::hashed_non_unique is a template as well and expects as its sole parameter a class that calculates hash values. Because both interfaces of the container need to look up animals, one interface calculates hash values for the name, while the other interface does so for the number of legs.

Boost.MultiIndex offers the helper class template boost::multi_index::member, which is defined in boost/multi_index/member.hpp, to access a member variable. As seen in Example 12.1, several parameters have been specified to let boost::multi_index::member know which member variable of animal should be accessed and which type the member variable has.

Even though the definition of animal_multi looks complicated at first, the class works like a map. The name and number of legs of an animal can be regarded as a key/value pair. The advantage of the container animal_multi over a map like std::unordered_map is that animals can be looked up by name or by number of legs. animal_multi supports two interfaces, one based on the name and one based on the number of legs. The interface determines which member variable is the key and which member variable is the value.

To access a MultiIndex container, you need to select an interface. If you directly access the object animals using insert() or count(), the first interface is used. In Example 12.1, this is the hash container for the member variable name. If you need a different interface, you must explicitly select it.

Interfaces are numbered consecutively, starting at index 0 for the first interface. To access the second interface – as shown in Example 12.1 – call the member function get() and pass in the index of the desired interface as the template parameter.

The return value of get() looks complicated. It accesses a class of the MultiIndex container called nth_index which, again, is a template. The index of the interface to be used must be specified as a template parameter. This index must be the same as the one passed to get(). The final step is to access the type definition named type of nth_index. The value of type represents the type of the corresponding interface. The following examples use the keyword auto to simplify the code.

Although you do not need to know the specifics of an interface, since they are automatically derived from nthindex and type, you should still understand what kind of interface is accessed. Since interfaces are numbered consecutively in the container definition, this can be answered easily, since the index is passed to both get() and nth_index. Thus, _legs_index is a hash interface that looks up animals by legs.

Because data such as names and legs can be keys of the MultiIndex container, they cannot be arbitrarily changed. If the number of legs is changed after an animal has been looked up by name, an interface using legs as a key would be unaware of the change and would not know that a new hash value needs to be calculated.

Just as the keys in a container of type std::unorderedmap cannot be modified, neither can data stored within a MultiIndex container. Strictly speaking, all data stored in a MultiIndex container is constant. This includes member variables that aren’t used by any interface. Even if no interface accesses _legs, legs cannot be changed.

To avoid having to remove elements from a MultiIndex container and insert new ones, Boost.MultiIndex provides member functions to change values directly. Because these member functions operate on the MultiIndex container itself, and because no element in a container is modified directly, all interfaces will be notified and can calculate new hash values.

Example 12.2. Changing elements in a MultiIndex container with modify()

  1. #include <boost/multi_index_container.hpp>
  2. #include <boost/multi_index/hashed_index.hpp>
  3. #include <boost/multi_index/member.hpp>
  4. #include <string>
  5. #include <iostream>
  7. using namespace boost::multi_index;
  9. struct animal
  10. {
  11.   std::string name;
  12.   int legs;
  13. };
  15. typedef multi_index_container<
  16.   animal,
  17.   indexed_by<
  18.     hashed_non_unique<
  19.       member<
  20.         animal, std::string, &animal::name
  21.       >
  22.     >,
  23.     hashed_non_unique<
  24.       member<
  25.         animal, int, &animal::legs
  26.       >
  27.     >
  28.   >
  29. > animal_multi;
  31. int main()
  32. {
  33.   animal_multi animals;
  35.   animals.insert({"cat", 4});
  36.   animals.insert({"shark", 0});
  37.   animals.insert({"spider", 8});
  39.   auto &legs_index = animals.get<1>();
  40.   auto it = legs_index.find(4);
  41.   legs_index.modify(it, [](animal &a){ a.name = "dog"; });
  43.   std::cout << animals.count("dog") << '\n';
  44. }

Every interface offered by Boost.MultiIndex provides the member function modify(), which operates directly on the container. The object to be modified is identified through an iterator passed as the first parameter to modify(). The second parameter is a function or function object that expects as its sole parameter an object of the type stored in the container. The function or function object can change the element as much as it wants. Example 12.2 illustrates how to use the member function modify() to change an element.

So far, only one interface has been introduced: boost::multi_index::hashed_non_unique, which calculates a hash value that does not have to be unique. In order to guarantee that no value is stored twice, use boost::multi_index::hashed_unique. Please note that values cannot be stored if they don’t satisfy the requirements of all interfaces of a particular container. If one interface does not allow you to store values multiple times, it does not matter whether another interface does allow it.

Example 12.3. A MultiIndex container with boost::multi_index::hashed_unique

  1. #include <boost/multi_index_container.hpp>
  2. #include <boost/multi_index/hashed_index.hpp>
  3. #include <boost/multi_index/member.hpp>
  4. #include <string>
  5. #include <iostream>
  7. using namespace boost::multi_index;
  9. struct animal
  10. {
  11.   std::string name;
  12.   int legs;
  13. };
  15. typedef multi_index_container<
  16.   animal,
  17.   indexed_by<
  18.     hashed_non_unique<
  19.       member<
  20.         animal, std::string, &animal::name
  21.       >
  22.     >,
  23.     hashed_unique<
  24.       member<
  25.         animal, int, &animal::legs
  26.       >
  27.     >
  28.   >
  29. > animal_multi;
  31. int main()
  32. {
  33.   animal_multi animals;
  35.   animals.insert({"cat", 4});
  36.   animals.insert({"shark", 0});
  37.   animals.insert({"dog", 4});
  39.   auto &legs_index = animals.get<1>();
  40.   std::cout << legs_index.count(4) << '\n';
  41. }

The container in Example 12.3 uses boost::multi_index::hashed_unique as the second interface. That means no two animals with the same number of legs can be stored in the container because the hash values would be the same.

The example tries to store a dog, which has the same number of legs as the already stored cat. Because this violates the requirement of having unique hash values for the second interface, the dog will not be stored in the container. Therefore, when searching for animals with four legs, the program displays 1, because only the cat was stored and counted.

Example 12.4. The interfaces sequenced, ordered_non_unique and random_access

  1. #include <boost/multi_index_container.hpp>
  2. #include <boost/multi_index/sequenced_index.hpp>
  3. #include <boost/multi_index/ordered_index.hpp>
  4. #include <boost/multi_index/random_access_index.hpp>
  5. #include <boost/multi_index/member.hpp>
  6. #include <string>
  7. #include <iostream>
  9. using namespace boost::multi_index;
  11. struct animal
  12. {
  13.   std::string name;
  14.   int legs;
  15. };
  17. typedef multi_index_container<
  18.   animal,
  19.   indexed_by<
  20.     sequenced<>,
  21.     ordered_non_unique<
  22.       member<
  23.         animal, int, &animal::legs
  24.       >
  25.     >,
  26.     random_access<>
  27.   >
  28. > animal_multi;
  30. int main()
  31. {
  32.   animal_multi animals;
  34.   animals.push_back({"cat", 4});
  35.   animals.push_back({"shark", 0});
  36.   animals.push_back({"spider", 8});
  38.   auto &legs_index = animals.get<1>();
  39.   auto it = legs_index.lower_bound(4);
  40.   auto end = legs_index.upper_bound(8);
  41.   for (; it != end; ++it)
  42.     std::cout << it->name << '\n';
  44.   const auto &rand_index = animals.get<2>();
  45.   std::cout << rand_index[0].name << '\n';
  46. }

Example 12.4 introduces the last three interfaces of Boost.MultiIndex: boost::multi_index::sequenced, boost::multi_index::ordered_non_unique, and boost::multi_index::random_access.

The interface boost::multi_index::sequenced allows you to treat a MultiIndex container like a list of type std::list. Elements are stored in the given order.

With the interface boost::multi_index::ordered_non_unique, objects are automatically sorted. This interface requires that you specify a sorting criterion when defining the container. Example 12.4 sorts objects of type animal by the number of legs using the helper class boost::multi_index::member.

boost::multi_index::ordered_non_unique provides special member functions to find specific ranges within the sorted values. Using lower_bound() and upper_bound(), the program searches for animals that have at least four and no more than eight legs. Because they require elements to be sorted, these member functions are not provided by other interfaces.

The final interface introduced is boost::multi_index::random_access, which allows you to treat the MultiIndex container like a vector of type std::vector. The two most prominent member functions are operator[] and at().

boost::multi_index::random_access includes boost::multi_index::sequenced. With boost::multi_index::random_access, all member functions of boost::multi_index::sequenced are available as well.

Now that we’ve covered the four interfaces of Boost.MultiIndex, the remainder of this chapter focuses on key extractors. One of the key extractors has already been introduced: boost::multi_index::member, which is defined in boost/multi_index/member.hpp. This helper class is called a key extractor because it allows you to specify which member variable of a class should be used as the key of an interface.

Example 12.5 introduces two more key extractors.

Example 12.5. The key extractors identity and const_mem_fun

  1. #include <boost/multi_index_container.hpp>
  2. #include <boost/multi_index/ordered_index.hpp>
  3. #include <boost/multi_index/hashed_index.hpp>
  4. #include <boost/multi_index/identity.hpp>
  5. #include <boost/multi_index/mem_fun.hpp>
  6. #include <string>
  7. #include <utility>
  8. #include <iostream>
  10. using namespace boost::multi_index;
  12. class animal
  13. {
  14. public:
  15.   animal(std::string name, int legs) : name_{std::move(name)},
  16.     legs_(legs) {}
  17.   bool operator<(const animal &a) const { return legs_ < a.legs_; }
  18.   const std::string &name() const { return name_; }
  19. private:
  20.   std::string name_;
  21.   int legs_;
  22. };
  24. typedef multi_index_container<
  25.   animal,
  26.   indexed_by<
  27.     ordered_unique<
  28.       identity<animal>
  29.     >,
  30.     hashed_unique<
  31.       const_mem_fun<
  32.         animal, const std::string&, &animal::name
  33.       >
  34.     >
  35.   >
  36. > animal_multi;
  38. int main()
  39. {
  40.   animal_multi animals;
  42.   animals.emplace("cat", 4);
  43.   animals.emplace("shark", 0);
  44.   animals.emplace("spider", 8);
  46.   std::cout << animals.begin()->name() << '\n';
  48.   const auto &name_index = animals.get<1>();
  49.   std::cout << name_index.count("shark") << '\n';
  50. }

The key extractor boost::multi_index::identity, defined in boost/multi_index/identity.hpp, uses elements stored in the container as keys. This requires the class animal to be sortable because objects of type animal will be used as the key for the interface boost::multi_index::ordered_unique. In Example 12.5, this is achieved through the overloaded operator<.

The header file boost/multi_index/mem_fun.hpp defines two key extractors – boost::multi_index::const_mem_fun and boost::multi_index::mem_fun – that use the return value of a member function as a key. In Example 12.5, the return value of name() is used that way. boost::multi_index::const_mem_fun is used for constant member functions, while boost::multi_index::mem_fun is used for non-constant member functions.

Boost.MultiIndex offers two more key extractors: boost::multi_index::global_fun and boost::multi_index::composite_key. The former can be used for free-standing or static member functions, and the latter allows you to design a key extractor made up of several other key extractors.

Exercise

Define the class animals_container with Boost.MultiIndex:

  1. #include <string>
  2. #include <vector>
  3. #include <iostream>
  5. struct animal
  6. {
  7.     std::string name;
  8.     int legs;
  9.     bool has_tail;
  10. };
  12. class animals_container
  13. {
  14. public:
  15.     void add(animal a)
  16.     {
  17.         // TODO: Implement this member function.
  18.     }
  20.     const animal *find_by_name(const std::string &name) const
  21.     {
  22.         // TODO: Implement this member function.
  23.         return nullptr;
  24.     }
  26.     std::vector<animal> find_by_legs(int from, int to) const
  27.     {
  28.         // TODO: Implement this member function.
  29.         return {};
  30.     }
  32.     std::vector<animal> find_by_tail(bool has_tail) const
  33.     {
  34.         // TODO: Implement this member function.
  35.         return {};
  36.     }
  37. };
  39. int main()
  40. {
  41.     animals_container animals;
  42.     animals.add({ "cat", 4, true });
  43.     animals.add({ "ant", 6, false });
  44.     animals.add({ "spider", 8, false });
  45.     animals.add({ "shark", 0, false });
  47.     const animal *a = animals.find_by_name("cat");
  48.     if (a)
  49.         std::cout << "cat has " << a->legs << " legs\n";
  51.     auto animals_with_6_to_8_legs = animals.find_by_legs(6, 9);
  52.     for (auto a : animals_with_6_to_8_legs)
  53.         std::cout << a.name << " has " << a.legs << " legs\n";
  55.     auto animals_without_tail = animals.find_by_tail(false);
  56.     for (auto a : animals_without_tail)
  57.         std::cout << a.name << " has no tail\n";
  58. }