The Boost C++ Libraries


Chapter 13: Containers


Table of Contents

This book is licensed under a Creative Commons License.

A new edition of this book is available! It has been published as a print book and can be bought from Barnes and Noble, Amazon and other bookstores. The new edition is up-to-date and based on the Boost C++ Libraries 1.47.0 (released in July 2011). Several chapters have been updated (for example to Boost.Spirit 2.x, Boost.Signals 2 and Boost.Filesystem 3) and many new libraries are covered (for example Boost.CircularBuffer, Boost.Intrusive and Boost.MultiArray). For more information please see the publisher's website XML Press.


13.1 General

This chapter introduces various Boost C++ Libraries defining containers that complement the ones known from the C++ standard. It outlines the usage of containers from Boost.Unordered, added to the C++ standard with Technical Report 1, shows how to define containers using Boost.MultiIndex and explains when to use Boost.Bimap, a library developed with the help of Boost.MultiIndex. The first library introduced, however, is Boost.Array which allows to treat traditional arrays just like containers known from the C++ standard.


13.2 Boost.Array

The library Boost.Array defines a template class boost::array in boost/array.hpp. Using this class, an array can be created that exhibits the same properties as a traditional array in C++. In addition, boost::array also conforms to the requirements for C++ containers which makes handling such an array as easy as handling a container. In principle, one can think of boost::array as the C++ container std::vector with the sole difference of the number of elements in boost::array being constant.

#include <boost/array.hpp> 
#include <iostream> 
#include <string> 
#include <algorithm> 

int main() 
{ 
  typedef boost::array<std::string, 3> array; 
  array a; 

  a[0] = "Boris"; 
  a.at(1) = "Anton"; 
  *a.rbegin() = "Caesar"; 

  std::sort(a.begin(), a.end()); 

  for (array::const_iterator it = a.begin(); it != a.end(); ++it) 
    std::cout << *it << std::endl; 

  std::cout << a.size() << std::endl; 
  std::cout << a.max_size() << std::endl; 
} 

As seen in the example, the usage of boost::array is fairly simple and needs no additional explanation since the methods used have the same meaning as their counterparts from std::vector.

One peculiarity is pointed out in the following example though.

#include <boost/array.hpp> 
#include <string> 

int main() 
{ 
  typedef boost::array<std::string, 3> array; 
  array a = { "Boris", "Anton", "Caesar" }; 
} 

An array of type boost::array can be initialized just like a traditional C++ array.

Since this container has been added to the C++ standard with Technical Report 1, it can also be accessed via std::array, defined in array, if the particular implementation of the C++ standard supports the Technical Report 1 accordingly.


13.3 Boost.Unordered

Boost.Unordered complements the C++ containers std::set, std::multiset, std::map and std::multimap with four additional classes: boost::unordered_set, boost::unordered_multiset, boost::unordered_map and boost::unordered_multimap. These classes only differ slightly from the existing containers and even offer a similar interface. In many cases, either one can be used since the resulting application will only be marginally different.

The difference between the containers of the C++ standard and Boost.Unordered is that containers from Boost.Unordered do not sort their elements and thus do not require elements to be sortable. Boost.Unordered makes sense whenever the sortation of stored elements is of no importance.

In order to still find elements quickly, hash values are calculated. Hash values are numbers, uniquely identifying elements within a container, that can be compared more efficiently than other data types such as strings. Since hash values need to be calculated, data types stored inside containers of Boost.Unordered must support calculation of these IDs accordingly. While e.g. std::set requires elements to be sortable, boost::unordered_set requires elements to support hash values. Despite this requirement, Boost.Unordered is usually preferred unless a sortation of elements is desired.

The following example outlines the usage of boost::unordered_set.

#include <boost/unordered_set.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::unordered_set<std::string> unordered_set; 
  unordered_set set; 

  set.insert("Boris"); 
  set.insert("Anton"); 
  set.insert("Caesar"); 

  for (unordered_set::iterator it = set.begin(); it != set.end(); ++it) 
    std::cout << *it << std::endl; 

  std::cout << set.size() << std::endl; 
  std::cout << set.max_size() << std::endl; 

  std::cout << (set.find("David") != set.end()) << std::endl; 
  std::cout << set.count("Boris") << std::endl; 
} 

As the example shows, boost::unordered_set provides similar methods to std::set. The example could have used std::set without bigger changes in the source code as well.

The following example uses boost::unordered_map to store the age of each person in addition to the name.

#include <boost/unordered_map.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::unordered_map<std::string, int> unordered_map; 
  unordered_map map; 

  map.insert(unordered_map::value_type("Boris", 31)); 
  map.insert(unordered_map::value_type("Anton", 35)); 
  map.insert(unordered_map::value_type("Caesar", 25)); 

  for (unordered_map::iterator it = map.begin(); it != map.end(); ++it) 
    std::cout << it->first << ", " << it->second << std::endl; 

  std::cout << map.size() << std::endl; 
  std::cout << map.max_size() << std::endl; 

  std::cout << (map.find("David") != map.end()) << std::endl; 
  std::cout << map.count("Boris") << std::endl; 
} 

As with the example before, there are no major differences between boost::unordered_map and std::map. Again, the example could have been implemented using std::map without any issues.

As mentioned above, Boost.Unordered requires elements stored in the container to support hash values. Miscellaneous data types such as std::string are supported innately. For user-defined types, a corresponding hash function must be defined manually.

#include <boost/unordered_set.hpp> 
#include <string> 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &n, int a) 
    : name(n), age(a) 
  { 
  } 

  bool operator==(const person &p) const 
  { 
    return name == p.name && age == p.age; 
  } 
}; 

std::size_t hash_value(person const &p) 
{ 
  std::size_t seed = 0; 
  boost::hash_combine(seed, p.name); 
  boost::hash_combine(seed, p.age); 
  return seed; 
} 

int main() 
{ 
  typedef boost::unordered_set<person> unordered_set; 
  unordered_set set; 

  set.insert(person("Boris", 31)); 
  set.insert(person("Anton", 35)); 
  set.insert(person("Caesar", 25)); 
} 

The application stores elements of type person in a container of type boost::unordered_set. Since the built-in hash function of boost::unordered_set does not recognize the class person, hash values cannot be calculated. Without providing an alternative hash function, the corresponding code would not compile.

The name of the hash function to be defined is hash_value(). It takes an object of the data type for which a hash value should be calculated as its sole argument. Since hash values are simple numbers, the return value of the function must be std::size_t.

Whenever a hash value needs to be calculated for an object, hash_value() is called automatically. The Boost C++ Libraries already define this function for various data types such as std::string. For user-defined types such as person, it needs to be defined manually though.

The implementation of hash_value() is usually fairly simple: The hash value is calculated by accessing the individual properties sequentially using the boost::hash_combine() function from the Boost.Hash library defined in boost/functional/hash.hpp. This header is automatically included if Boost.Unordered is used since all container calculate hash values based on Boost.Hash.

Besides implementing the hash_value() function, user-defined types need to support the comparison of two objects via the == operator. Therefore, person implements the operator==() operator accordingly.


13.4 Boost.MultiIndex

The Boost.MultiIndex library is much more complex than any of the libraries presented thus far. While both Boost.Array and Boost.Unordered offer containers that can be used immediately, Boost.MultiIndex allows to define new containers. Opposed to the containers from the C++ standard, a user-defined container offers not only one perception to the data but can support an arbitrary number of interfaces. For example, one can create a container that assigns values to keys similar to std::map but also can use the values as keys conversely - something, that without the help of Boost.MultiIndex would require two containers of type std::map and the overhead of synchronizing the two containers to guarantee data integrity.

The following example defines a new container using Boost.MultiIndex that allows to store the name and age of people. Contrary to std::map, the container can be searched for both name and age though.

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <iostream> 
#include <string> 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container< 
  person, 
  boost::multi_index::indexed_by< 
    boost::multi_index::hashed_non_unique< 
      boost::multi_index::member< 
        person, std::string, &person::name 
      > 
    >, 
    boost::multi_index::hashed_non_unique< 
      boost::multi_index::member< 
        person, int, &person::age 
      > 
    > 
  > 
> person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 35)); 
  persons.insert(person("Caesar", 25)); 

  std::cout << persons.count("Boris") << std::endl; 

  const person_multi::nth_index<1>::type &age_index = persons.get<1>(); 
  std::cout << age_index.count(25) << std::endl; 
} 

As mentioned before, Boost.MultiIndex does not provide specific containers but rather classes to define new containers. Typically, the first step is to design the new container by using typedef to access different classes in Boost.MultiIndex.

A class used for every container definition is boost::multi_index::multi_index_container defined in boost/multi_index_container.hpp. Since it is a template class, at least two arguments are required to be passed accordingly. The first argument is the data type the container should store; in the above example a user-defined class named person. The second argument is used to denote different indexes the container should provide.

The key advantage of containers based on Boost.MultiIndex is the ability to access data via different interfaces. The number and type of interfaces for a specific container can now be specified at definition. Since the container in the example application allows to search for people either by name or age, two interfaces have been defined. Boost.MultiIndex calls these interfaces indexes which also influenced the name of the libary.

Interfaces are defined with the help of the boost::multi_index::indexed_by template class. Each interface is passed as an argument accordingly. The example application defines two interfaces of type boost::multi_index::hashed_non_unique which is defined in boost/multi_index/hashed_index.hpp. This interface is used if the container should behave just like one from Boost.Unordered, storing the elements internally using a hash value.

The boost::multi_index::hashed_non_unique class is a template as well and expects a class able to calculate hash values as its sole argument. Since both interfaces of the container should allow to access people by name and age, one interface calculates hash values for the name while the other interface does so for the age, respectively.

Boost.MultiIndex offers the helper template class boost::multi_index::member, defined in boost/multi_index/member.hpp, to access a property. As seen in the above example, several arguments have been specified in order to let boost::multi_index::member know which property of person should be accessed and which data type the property has.

Even though the definition of person_multi looks quite complicated at first: The class itself operates similar to boost::unordered_map from Boost.Unordered with the decisive difference of allowing to use both the name and the age of a person to search the container.

In order to access any MultiIndex container, the interface for the access must be specified - the sole exception being the first defined interface. If the persons object is directly accessed via insert() or count(), the first interface is implicitly used - in the case of the example the hash container for the name property. If a different interface should be used, it needs to be explicitly selected.

Interfaces are numbered consecutively, starting at index 0 for the first interface. In order to access the second interface in the example, the get() method can be used, passing the index of the desired interface as the template argument.

The return value of get() looks kind of complicated: It accesses a class of the MultiIndex container named nth_index which, again, is a template and thus the index of the interface to be used must be specified as the template argument accordingly. This index must be the same as the one passed to the get() method. The final step is to access the type definition type of nth_index using :: - type actually represents the type of the corresponding interface.

While the specifics of an interface do not need to be known since it is automatically derived from nth_index and type, one should still understand what kind of interface is accessed. Given that interfaces are numbered consecutively in the container definition, this can be answered fairly easy given the index that is passed to get() as well as nth_index. age_index in the example is a hash interface as well - accessing people by age.

Since information such as name and age can be keys of the MultiIndex container based on the interface, they cannot be changed arbitrarily any longer. If the age of a person is altered after it has been searched for by name, the interface using the age as the key would not be aware that the key was altered and thus a new hash value needs to be calculated.

Just like the keys in a container of type std::map cannot be modified, information stored within a MultiIndex container cannot be modified either. Strictly speaking, all information stored in a MultiIndex container is constant. To avoid deleting and storing altered versions of the information, Boost.MultiIndex offers a couple of useful methods to modify information directly. Since these methods operate on the MultiIndex container itself and no information is modified directly using the corresponding object, the update is safe. All interfaces are notified and can e.g. calculate new hash values.

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <iostream> 
#include <string> 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container< 
  person, 
  boost::multi_index::indexed_by< 
    boost::multi_index::hashed_non_unique< 
      boost::multi_index::member< 
        person, std::string, &person::name 
      > 
    >, 
    boost::multi_index::hashed_non_unique< 
      boost::multi_index::member< 
        person, int, &person::age 
      > 
    > 
  > 
> person_multi; 

void set_age(person &p) 
{ 
  p.age = 32; 
} 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 35)); 
  persons.insert(person("Caesar", 25)); 

  person_multi::iterator it = persons.find("Boris"); 
  persons.modify(it, set_age); 

  const person_multi::nth_index<1>::type &age_index = persons.get<1>(); 
  std::cout << age_index.count(32) << std::endl; 
} 

Every interface offered by Boost.MultiIndex supports the modify() method which operates directly on the container. The object to be modified is passed using an iterator as the first argument. The second argument is a function or function object that expects an object of the type stored in the container as its first argument - in the example of type person. This function - named set_age() - allows to modify an object in the container.

So far, only one interface has been introduced: boost::multi_index::hashed_non_unique calculates a hash value for the information that does not have to be unparalleled. In order to guarantee that no information is stored twice, boost::multi_index::hashed_unique can be used instead. Please note that information cannot be stored if it does not satisfy the requirements of all interfaces of the particular container. If an interface does not allow copies of information, it does not matter whether a different interfaces does allow them as shown in the following example.

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <iostream> 
#include <string> 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container< 
  person, 
  boost::multi_index::indexed_by< 
    boost::multi_index::hashed_non_unique< 
      boost::multi_index::member< 
        person, std::string, &person::name 
      > 
    >, 
    boost::multi_index::hashed_unique< 
      boost::multi_index::member< 
        person, int, &person::age 
      > 
    > 
  > 
> person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 31)); 
  persons.insert(person("Caesar", 25)); 

  const person_multi::nth_index<1>::type &age_index = persons.get<1>(); 
  std::cout << age_index.count(31) << std::endl; 
} 

The container now uses the boost::multi_index::hashed_unique class as the second interface signifying that no two people can have the same age since otherwise the hash values would be the same.

The application tries to store a person named Anton who is the same age as the already stored person Boris. Since this violates the requirement of having unique hash values for the second interface, the object is not stored in the container accordingly. When searching for people of age 31, the application therefore displays 1; only the person named Boris has been stored.

The following example introduces the remaining three interfaces offered by Boost.MultiIndex: boost::multi_index::sequenced, boost::multi_index::ordered_non_unique and boost::multi_index::random_access.

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/sequenced_index.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/random_access_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <iostream> 
#include <string> 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container< 
  person, 
  boost::multi_index::indexed_by< 
    boost::multi_index::sequenced<>, 
    boost::multi_index::ordered_non_unique< 
      boost::multi_index::member< 
        person, int, &person::age 
      > 
    >, 
    boost::multi_index::random_access<> 
  > 
> person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.push_back(person("Boris", 31)); 
  persons.push_back(person("Anton", 31)); 
  persons.push_back(person("Caesar", 25)); 

  const person_multi::nth_index<1>::type &ordered_index = persons.get<1>(); 
  person_multi::nth_index<1>::type::iterator lower = ordered_index.lower_bound(30); 
  person_multi::nth_index<1>::type::iterator upper = ordered_index.upper_bound(40); 
  for (; lower != upper; ++lower) 
    std::cout << lower->name << std::endl; 

  const person_multi::nth_index<2>::type &random_access_index = persons.get<2>(); 
  std::cout << random_access_index[2].name << std::endl; 
} 

The boost::multi_index::sequenced interface allows to treat a MultiIndex container as a list - similar to std::list. The interface is fairly simple to use in the definition of the container: No template arguments need to be passed. The objects of type person are stored exactly in the given order.

By using the boost::multi_index::ordered_non_unique interface, objects are automatically sorted. This interface requires to specify the sorting criterion while defining the container. The example specifies to sort the objects of type person by age using the helper class boost::multi_index::member.

boost::multi_index::ordered_non_unique provides special methods to find specific ranges within the sorted information. Using lower_bound() and upper_bound(), the application searches for people that are older than 30 but no older than 40 years. These methods are not provided with any other interface since they require the information to be sorted.

The final interface is boost::multi_index::random_access, allowing to treat the MultiIndex container just like a vector of type std::vector. The two prominent methods are operator[]() and at().

Please note that boost::multi_index::random_access completely includes the boost::multi_index::sequenced interface. While using boost::multi_index::random_access, all methods of boost::multi_index::sequenced are therefore available as well.

After covering the four interfaces of Boost.MultiIndex, the remainder of this section focuses on the so-called key extractors. One of the key extractors has been introduced so far: boost::multi_index::member defined in boost/multi_index/member.hpp. This helper class is called key extractor since it allows to explicitly specify which property of a class should be used as the key of an interface.

The following example introduces two more key extractors.

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/identity.hpp> 
#include <boost/multi_index/mem_fun.hpp> 
#include <iostream> 
#include <string> 

class person 
{ 
public: 
  person(const std::string &n, int a) 
    : name(n), age(a) 
  { 
  } 

  bool operator<(const person &p) const 
  { 
    return age < p.age; 
  } 

  std::string get_name() const 
  { 
    return name; 
  } 

private: 
  std::string name; 
  int age; 
}; 

typedef boost::multi_index::multi_index_container< 
  person, 
  boost::multi_index::indexed_by< 
    boost::multi_index::ordered_unique< 
      boost::multi_index::identity<person> 
    >, 
    boost::multi_index::hashed_unique< 
      boost::multi_index::const_mem_fun< 
        person, std::string, &person::get_name 
      > 
    > 
  > 
> person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 31)); 
  persons.insert(person("Caesar", 25)); 

  std::cout << persons.begin()->get_name() << std::endl; 

  const person_multi::nth_index<1>::type &hashed_index = persons.get<1>(); 
  std::cout << hashed_index.count("Boris") << std::endl; 
} 

The key extractor boost::multi_index::identity, defined in boost/multi_index/identity.hpp, is used to utilize data types stored in the container as keys. This requires the person class to be sortable since it is specified as the key for the interface boost::multi_index::ordered_unique. In the example, this is achieved by providing an overload for the operator<() operator.

The header file boost/multi_index/mem_fun.hpp defines both the boost::multi_index::const_mem_fun and boost::multi_index::mem_fun key extractors which can be used to utilize the return value of a method as the key. In the example application, the return value of get_name() is used accordingly. boost::multi_index::const_mem_fun is used for constant methods while boost::multi_index::mem_fun is used for non-constant methods.

Boost.MultiIndex offers two more key extractors named boost::multi_index::global_fun and boost::multi_index::composite_key. While the former can be used for free-standing or static methods, the latter actually allows to design a key extractor comprising of several other key extractors.


13.5 Boost.Bimap

The Boost.Bimap library is based on Boost.MultiIndex and offers a container that can be used immediately without defining it first. The container is similar to std::map with the difference of allowing to search for both the key and the value as shown in the following example.

#include <boost/bimap.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::bimap<std::string, int> bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  std::cout << persons.left.count("Boris") << std::endl; 
  std::cout << persons.right.count(31) << std::endl; 
} 

boost::bimap is defined in boost/bimap.hpp and offers two properties left and right that can be used to access the two containers of type std::map unified by boost::bimap. While left accesses the container using keys of type std::string, right use keys of type int instead.

Besides allowing access to the individual records via a left or right container, boost::bimap allows to view records as relations as shown in the following example.

#include <boost/bimap.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::bimap<std::string, int> bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  for (bimap::iterator it = persons.begin(); it != persons.end(); ++it) 
    std::cout << it->left << " is " << it->right << " years old." << std::endl; 
} 

It is not necessary to access records using left or right. By iterating over the records, the left and right container of the individual record is available through the iterator as well.

While std::map is accompanied by a container named std::multimap that can store multiple records using the same key, there is no such equivalent for boost::bimap. This, however, does not mean that storing records using the same key inside a container of type boost::bimap is not possible. Strictly speaking, the two required template arguments do not specify the data type to store but rather container types used for left and right. If no container type is specified as seen in the example, the container type boost::bimaps::set_of is used by default which - similar to std::map - only allows records with unique keys.

The first example for boost::bimap can be rewritten as follows.

#include <boost/bimap.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::bimap<boost::bimaps::set_of<std::string>, boost::bimaps::set_of<int>> bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  std::cout << persons.left.count("Boris") << std::endl; 
  std::cout << persons.right.count(31) << std::endl; 
} 

Besides boost::bimaps::set_of, other container types exist to customize boost::bimap.

#include <boost/bimap.hpp> 
#include <boost/bimap/multiset_of.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::bimap<boost::bimaps::set_of<std::string>, boost::bimaps::multiset_of<int>> bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  std::cout << persons.left.count("Boris") << std::endl; 
  std::cout << persons.right.count(31) << std::endl; 
} 

The application uses the container type boost::bimaps::multiset_of defined in boost/bimap/multiset_of.hpp. It operates similar to boost::bimaps::set_of with the exception that the key does not need to be unique. Therefore, the example will display 2 when searching for people of age 31.

Since boost::bimaps::set_of is used for containers of type boost::bimap by default, the header file boost/bimap/set_of.hpp does not need to be explicitly included. When using other container types, the corresponding header files must be included accordingly though.

Boost.Bimap offers the classes boost::bimaps::unordered_set_of, boost::bimaps::unordered_multiset_of, boost::bimaps::list_of, boost::bimaps::vector_of and boost::bimaps::unconstrainted_set_of in addition to the ones shown above. Except for boost::bimaps::unconstrainted_set_of, all other container types operate just like their counterparts from the C++ standard or Boost.Unordered.

#include <boost/bimap.hpp> 
#include <boost/bimap/unconstrained_set_of.hpp> 
#include <boost/bimap/support/lambda.hpp> 
#include <iostream> 
#include <string> 

int main() 
{ 
  typedef boost::bimap<std::string, boost::bimaps::unconstrained_set_of<int>> bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  bimap::left_map::iterator it = persons.left.find("Boris"); 
  persons.left.modify_key(it, boost::bimaps::_key = "Doris"); 

  std::cout << it->first << std::endl; 
} 

boost::bimaps::unconstrainted_set_of can be used to disable one container type of boost::bimap making it impossible to access right in order to search for people by age. In this particular case, boost::bimap behaves just like the standard std::map container.

Nonetheless, the example also shows why it can make sense to prefer boost::bimap over std::map. Since Boost.Bimap is based on Boost.MultiIndex, methods known from Boost.MultiIndex are available as well. The example modifies a key using modify_key() which is not possible using std::map.

Please note how the key is modified in detail: A new value is assigned to the current key via boost::bimaps::_key which is a so-called lambda function as introduced in Chapter 3, Function Objects and is defined in boost/bimap/support/lambda.hpp.

boost/bimap/support/lambda.hpp also defines boost::bimaps::_data. The modify_data() method modifies a value in a container of type boost::bimap accordingly.


13.6 Exercises

You can buy solutions to all exercises in this book as a ZIP file.

  1. Develop an application that assigns employees to departments of a company. Store some example records and search through them to identify the department of a particular employee as well as the number of employees working in a particular department.

  2. Extend the application by associating numbers to employees. These numbers must be unique in order to identify employees with the same name unambiguously. Search through the example records to display the information of an employee with a specific number.