ceph/src/boost/libs/bimap/doc/quick_tutorial.qbk

   1 [/license
   2
   3 Boost.Bimap
   4
   5 Copyright (c) 2006-2007 Matias Capeletto
   6
   7 Distributed under the Boost Software License, Version 1.0.
   8 (See accompanying file LICENSE_1_0.txt or copy at
   9 http://www.boost.org/LICENSE_1_0.txt)
  10
  11 ]
  12
  13 [/ QuickBook Document version 1.4 ]
  14
  15 [section One minute tutorial]
  16
  17 [heading What is a bimap?]
  18
  19 A Bimap is a data structure that represents bidirectional relations between
  20 elements of two collections. The container is designed to work as two opposed STL maps. A bimap between a collection `X` and a collection `Y` can be viewed as a map from `X` to `Y` (this view will be called the ['left map view]) or as a map from `Y` to `X` (known as the ['right map view]). Additionally, the bimap can also be viewed as a set of relations between `X` and `Y` (named the ['collection of relations view]).
  21
  22 The following code creates an empty bimap container:
  23
  24     typedef bimap<X,Y> bm_type;
  25     bm_type bm;
  26
  27 Given this code, the following is the complete description of the resulting bimap.
  28 [footnote A type is ['signature-compatible] with other type if it has the same
  29 signature for functions and metadata. Preconditions, postconditions and the order
  30 of operations need not be the same.
  31 ]
  32
  33 * `bm.left` is signature-compatible with `std::map<X,Y>`
  34 * `bm.right` is signature-compatible with `std::map<Y,X>`
  35 * `bm` is signature-compatible with `std::set< relation<X,Y> >`
  36
  37 __SIMPLE_BIMAP__
  38
  39 You can see how a bimap container offers three views over the same collection of bidirectional relations.
  40
  41 If we have any generic function that work with maps
  42
  43     template< class MapType >
  44     void print_map(const MapType & m)
  45     {
  46         typedef typename MapType::const_iterator const_iterator;
  47         for( const_iterator iter = m.begin(), iend = m.end(); iter != iend; ++iter )
  48         {
  49             std::cout << iter->first << "-->" << iter->second << std::endl;
  50         }
  51     }
  52
  53 We can use the ['left map view] and the ['right map view] with it
  54
  55     bimap< int, std::string > bm;
  56     ...
  57     print_map( bm.left  );
  58     print_map( bm.right );
  59
  60 And the output will be
  61
  62 [pre
  63 [^1 --> one]
  64 [^2 --> two]
  65 ...
  66 [^one --> 1]
  67 [^two --> 2]
  68 ...
  69 ]
  70
  71 [heading Layout of the relation and the pairs of a bimap]
  72
  73 The `relation` class represents two related elements. The two values are
  74 named left and right to express the symmetry of this type.
  75 The bimap pair classes are signature-compatible with `std::pairs`.
  76
  77 __RELATION_AND_PAIR__
  78
  79 [heading Step by step]
  80
  81 [import ../example/step_by_step.cpp]
  82
  83 A convenience header is available in the boost directory:
  84
  85     #include <boost/bimap.hpp>
  86
  87 Lets define a bidirectional map between integers and strings:
  88
  89 [code_step_by_step_definition]
  90
  91 [heading The collection of relations view]
  92
  93 Remember that `bm` alone can be used as a set of relations.
  94 We can insert elements or iterate over them using this view.
  95
  96 [code_step_by_step_set_of_relations_view]
  97
  98 [heading The left map view]
  99
 100 `bm.left` works like a `std::map< int, std::string >`. We use it
 101 in the same way we will use a standard map.
 102
 103 [code_step_by_step_left_map_view]
 104
 105 [heading The right map view]
 106
 107 `bm.right` works like a `std::map< std::string, int >`. It is
 108 important to note that the key is the first type and the data
 109 is the second one, exactly as with standard maps.
 110
 111 [code_step_by_step_right_map_view]
 112
 113 [heading Differences with std::map]
 114
 115 The main difference between bimap views and their standard containers counterparts
 116 is that, because of the bidirectional nature of a bimap, the values stored in
 117 it can not be modified directly using iterators.
 118 For example, when a `std::map<X,Y>` iterator is dereferenced the return type is
 119 `std::pair<const X, Y>`, so the following code is valid:
 120 `m.begin()->second = new_value;`.
 121 However dereferencing a `bimap<X,Y>::left_iterator` returns a type that is
 122 ['signature-compatible] with a `std::pair<const X, const Y>`
 123
 124     bm.left.find(1)->second = "1"; // Compilation error
 125
 126 If you insert `(1,"one")` and `(1,"1")` in a `std::map<int,std::string>` the second insertion will have no effect. In a `bimap<X,Y>` both keys have to remain unique. The insertion may fail in other situations too. Lets see an example
 127
 128     bm.clear();
 129
 130     bm.insert( bm_type::value_type( 1, "one" ) );
 131
 132     bm.insert( bm_type::value_type( 1, "1"   ) ); // No effect!
 133     bm.insert( bm_type::value_type( 2, "one" ) ); // No effect!
 134
 135     assert( bm.size() == 1 );
 136
 137 [heading A simple example]
 138
 139 Look how you can reuse code that is intend to be used with std::maps, like the
 140 print_map function in this example.
 141
 142 [@../../example/simple_bimap.cpp Go to source code]
 143
 144 [code_simple_bimap]
 145
 146 The output of this program will be the following:
 147 [pre
 148 [^The number of countries is 4]
 149
 150 [^The winner is Argentina]
 151
 152 [^Countries names ordered by their final position:]
 153 [^1) Argentina]
 154 [^2) Spain]
 155 [^3) Germany]
 156 [^4) France]
 157
 158 [^Countries names ordered alphabetically along with their final position:]
 159 [^Argentina ends in position 1]
 160 [^France ends in position 4]
 161 [^Germany ends in position 3]
 162 [^Spain ends in position 2]
 163 ]
 164
 165
 166 [heading Continuing the journey]
 167
 168 For information on function signatures, see any standard library
 169 documentation or read the [link boost_bimap.reference reference] section of
 170 this documentation.
 171
 172 [caution
 173 Be aware that a bidirectional map is only signature-compatible with standard
 174 containers. Some functions may give different results, such as in the case of
 175 inserting a pair into the left map where the second value conflicts with a
 176 stored relation in the container. The functions may be slower in a bimap
 177 because of the duplicated constraints. It is strongly recommended that
 178 you read [link boost_bimap.the_tutorial The full tutorial] if you intend to
 179 use a bimap in a serious project.
 180 ]
 181
 182 [endsect]