1 // Boost.Bimap 2 // 3 // Copyright (c) 2006-2007 Matias Capeletto 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 9 /// \file bimap.hpp 10 /// \brief Includes the basic bimap container 11 12 /** \mainpage notitle 13 \n 14 \image html http://matias.capeletto.googlepages.com/boost.bimap.reference.logo.png 15 16 \section Introduction 17 18 This is the complete reference of Boost.Bimap. 19 20 After getting a good understanding of the library from a user perspective 21 the next step will be: 22 23 - Understand the tagged idiom. (boost::bimaps::tags) 24 - Understand the internals of the relation class (boost::bimaps::relation) 25 - Read the container_adaptor toolbox docs (boost::bimaps::container_adaptor) 26 - Understand the internals of the bimap class. (boost::bimaps, boost::bimaps::views 27 and boost::bimaps::detail) 28 29 30 **/ 31 32 /** \defgroup mutant_group mutant idiom 33 \brief A safe wrapper around reinterpret_cast 34 **/ 35 36 /** \defgroup relation_group relation 37 \brief The relation 38 **/ 39 40 /** \defgroup tags_group tagged idiom 41 \brief The tagged idiom 42 **/ 43 44 45 #ifndef BOOST_BIMAP_BIMAP_HPP 46 #define BOOST_BIMAP_BIMAP_HPP 47 48 #if defined(_MSC_VER) 49 #pragma once 50 #endif 51 52 #include <boost/config.hpp> 53 #include <boost/bimap/detail/user_interface_config.hpp> 54 #include <boost/mpl/aux_/na.hpp> 55 56 #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION 57 #include <boost/serialization/nvp.hpp> 58 #endif // BOOST_BIMAP_DISABLE_SERIALIZATION 59 60 // Boost.Bimap 61 #include <boost/bimap/detail/bimap_core.hpp> 62 #include <boost/bimap/detail/map_view_base.hpp> 63 #include <boost/bimap/detail/modifier_adaptor.hpp> 64 #include <boost/bimap/relation/support/data_extractor.hpp> 65 #include <boost/bimap/relation/support/member_with_tag.hpp> 66 67 #include <boost/bimap/support/map_type_by.hpp> 68 #include <boost/bimap/support/map_by.hpp> 69 #include <boost/bimap/support/iterator_type_by.hpp> 70 71 /// \brief The namespace where all the boost libraries lives. 72 73 namespace boost { 74 75 /// \brief Boost.Bimap library namespace 76 /** 77 All the entities in the library are defined in this namespace. 78 **/ 79 namespace bimaps { 80 81 /// \brief The bimap class is the entry point to the library. 82 /** 83 This class manages the instantiation of the desired bimap type. 84 As there are several types of bidirectional maps that can be 85 created using it. the main job of it is to find the desired 86 type. This is done using metaprogramming to obtain the relation 87 type that will be stored, the map_view type of each side and 88 the set_view type of the general relationship. The instantiation 89 is kept simple using an extended standard set theory, where a 90 bidirectional map type is defined by the set types it relates. 91 For example, a bidirectional map that has multimap semantics 92 viewed from both sides is defined by specifying that the two 93 keys sets are of \c multiset_of<Key> type. 94 This allows the bimap class to support seamingless N-N, 1-N, 95 ordered/unordered and even vector-list types of mapping. 96 The three last parameters are used to specify the set type of 97 the relation, an inplace hooked data class and the allocator 98 type. As a help to the bimap user, these parameters support 99 default types but use a special idiom that allow them to be 100 specified without interleaving the usual use_default keyword. 101 The possible bimap instantiation are enumerated here: 102 \c {Side}KeyType can be directly a type, this is default to 103 \c set_of<{Side}KeyType>, or can be a \c {SetType}_of<Type> 104 specification. Additionally this two parameters can be tagged 105 to specify others tags instead of the usual \c member_at::{Side} 106 ones. 107 108 109 \code 110 111 typedef bimap 112 < 113 LeftCollectionType, RightCollectionType 114 115 [ , SetTypeOfRelation ] // Default to left_based 116 [ , info_hook< Info > ] // Default to no info 117 [ , Allocator ] // Default to std::allocator<> 118 119 > bm; 120 121 \endcode 122 123 **/ 124 125 126 template 127 < 128 class KeyTypeA, class KeyTypeB, 129 class AP1 = ::boost::mpl::na, 130 class AP2 = ::boost::mpl::na, 131 class AP3 = ::boost::mpl::na 132 > 133 class bimap 134 : 135 // Bimap Core, use mpl magic to find the desired bimap type 136 137 public ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>, 138 139 // You can use bimap as a collection of relations 140 141 public ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3> 142 ::relation_set, 143 144 // Include extra typedefs (i.e. left_local_iterator for unordered_map) 145 146 public ::boost::bimaps::detail:: left_map_view_extra_typedefs< 147 BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::left_map_view_type< 148 ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3> 149 >::type 150 >, 151 public ::boost::bimaps::detail::right_map_view_extra_typedefs< 152 BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::right_map_view_type< 153 ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3> 154 >::type 155 > 156 { 157 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail:: 158 bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3> base_; 159 160 BOOST_DEDUCED_TYPENAME base_::core_type core; 161 162 public: 163 164 // metadata -------------------------------------------------------- 165 166 /* 167 // The rest is computed in the core, because it is quite difficult to 168 // expose a nice interface with so many metaprogramming stuff. 169 170 // Map by {side} metadata 171 172 typedef -unspecified- {side}_tag; 173 typedef -unspecified- {side}_data_type; 174 typedef -unspecified- {side}_value_type; 175 typedef -unspecified- {side}_key_type; 176 177 // There are other typedefs for definitions of different map views 178 179 ------------------------------------------------------------------*/ 180 181 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail:: 182 left_map_view_type<base_>::type left_map; 183 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail:: 184 right_map_view_type<base_>::type right_map; 185 186 typedef BOOST_DEDUCED_TYPENAME 187 left_map::iterator left_iterator; 188 typedef BOOST_DEDUCED_TYPENAME 189 left_map::const_iterator left_const_iterator; 190 191 typedef BOOST_DEDUCED_TYPENAME 192 right_map::iterator right_iterator; 193 typedef BOOST_DEDUCED_TYPENAME 194 right_map::const_iterator right_const_iterator; 195 196 typedef BOOST_DEDUCED_TYPENAME 197 left_map::reference left_reference; 198 typedef BOOST_DEDUCED_TYPENAME 199 left_map::const_reference left_const_reference; 200 201 typedef BOOST_DEDUCED_TYPENAME 202 right_map::reference right_reference; 203 typedef BOOST_DEDUCED_TYPENAME 204 right_map::const_reference right_const_reference; 205 206 typedef BOOST_DEDUCED_TYPENAME base_::relation::info_type info_type; 207 208 typedef BOOST_DEDUCED_TYPENAME base_::core_type::allocator_type allocator_type; 209 210 /// Left map view 211 left_map left; 212 213 /// Right map view 214 right_map right; 215 216 typedef BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag 217 logic_relation_set_tag; 218 typedef BOOST_DEDUCED_TYPENAME base_::logic_left_tag logic_left_tag; 219 typedef BOOST_DEDUCED_TYPENAME base_::logic_right_tag logic_right_tag; 220 typedef BOOST_DEDUCED_TYPENAME base_::core_type::ctor_args_list 221 ctor_args_list; 222 bimap(const allocator_type & al=allocator_type ())223 bimap(const allocator_type& al = allocator_type()) : 224 225 base_::relation_set( 226 ::boost::multi_index::get< 227 logic_relation_set_tag 228 >(core) 229 ), 230 231 core(al), 232 233 left ( 234 ::boost::multi_index::get< 235 logic_left_tag 236 >(core) 237 ), 238 right ( 239 ::boost::multi_index::get< 240 logic_right_tag 241 >(core) 242 ) 243 244 {} 245 246 template< class InputIterator > bimap(InputIterator first,InputIterator last,const allocator_type & al=allocator_type ())247 bimap(InputIterator first,InputIterator last, 248 const allocator_type& al = allocator_type()) : 249 250 base_::relation_set( 251 ::boost::multi_index::get< 252 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(core) 253 ), 254 255 core(first,last,ctor_args_list(),al), 256 257 left ( 258 ::boost::multi_index::get< 259 BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(core) 260 ), 261 right ( 262 ::boost::multi_index::get< 263 BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(core) 264 ) 265 266 {} 267 bimap(const bimap & x)268 bimap(const bimap& x) : 269 270 base_::relation_set( 271 ::boost::multi_index::get< 272 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(core) 273 ), 274 275 core(x.core), 276 277 left ( 278 ::boost::multi_index::get< 279 BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(core) 280 ), 281 right ( 282 ::boost::multi_index::get< 283 BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(core) 284 ) 285 286 {} 287 operator =(const bimap & x)288 bimap& operator=(const bimap& x) 289 { 290 core = x.core; 291 return *this; 292 } 293 294 // Projection of iterators 295 296 template< class IteratorType > project_left(IteratorType iter)297 left_iterator project_left(IteratorType iter) 298 { 299 return core.template project< 300 BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base()); 301 } 302 303 template< class IteratorType > project_left(IteratorType iter) const304 left_const_iterator project_left(IteratorType iter) const 305 { 306 return core.template project< 307 BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base()); 308 } 309 310 template< class IteratorType > project_right(IteratorType iter)311 right_iterator project_right(IteratorType iter) 312 { 313 return core.template project< 314 BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base()); 315 } 316 317 template< class IteratorType > project_right(IteratorType iter) const318 right_const_iterator project_right(IteratorType iter) const 319 { 320 return core.template project< 321 BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base()); 322 } 323 324 template< class IteratorType > 325 BOOST_DEDUCED_TYPENAME base_::relation_set::iterator project_up(IteratorType iter)326 project_up(IteratorType iter) 327 { 328 return core.template project< 329 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base()); 330 } 331 332 template< class IteratorType > 333 BOOST_DEDUCED_TYPENAME base_::relation_set::const_iterator project_up(IteratorType iter) const334 project_up(IteratorType iter) const 335 { 336 return core.template project< 337 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base()); 338 } 339 340 // Support for tags 341 342 template< class Tag, class IteratorType > 343 BOOST_DEDUCED_TYPENAME ::boost::bimaps::support:: 344 iterator_type_by<Tag,bimap>::type project(IteratorType iter)345 project(IteratorType iter) 346 { 347 return core.template project<Tag>(iter.base()); 348 } 349 350 template< class Tag, class IteratorType > 351 BOOST_DEDUCED_TYPENAME ::boost::bimaps::support:: 352 const_iterator_type_by<Tag,bimap>::type project(IteratorType iter) const353 project(IteratorType iter) const 354 { 355 return core.template project<Tag>(iter.base()); 356 } 357 358 template< class Tag > 359 struct map_by : 360 public ::boost::bimaps::support::map_type_by<Tag,bimap>::type 361 { 362 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support:: 363 map_type_by<Tag,bimap>::type type; 364 map_byboost::bimaps::bimap::map_by365 private: map_by() {} 366 }; 367 368 template< class Tag > 369 BOOST_DEDUCED_TYPENAME ::boost::bimaps::support:: by()370 map_type_by<Tag,bimap>::type &by() 371 { 372 return ::boost::bimaps::support::map_by<Tag>(*this); 373 } 374 375 template< class Tag > 376 const BOOST_DEDUCED_TYPENAME ::boost::bimaps::support:: by() const377 map_type_by<Tag,bimap>::type &by() const 378 { 379 return ::boost::bimaps::support::map_by<Tag>(*this); 380 } 381 382 383 #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION 384 385 // Serialization support 386 387 private: 388 389 friend class boost::serialization::access; 390 391 template<class Archive> serialize(Archive & ar,const unsigned int)392 void serialize(Archive & ar, const unsigned int) 393 { 394 ar & serialization::make_nvp("mi_core",core); 395 } 396 397 #endif // BOOST_BIMAP_DISABLE_SERIALIZATION 398 }; 399 400 } // namespace bimaps 401 } // namespace boost 402 403 404 /** \namespace boost::bimaps::support 405 \brief Metafunctions to help working with bimaps. 406 **/ 407 408 /** \namespace boost::bimaps::views 409 \brief Bimap views. 410 **/ 411 412 /** \namespace boost::bimaps::views::detail 413 \brief Bimap views details. 414 **/ 415 416 417 418 // Include basic tools for user commodity 419 420 #include <boost/bimap/tags/tagged.hpp> 421 #include <boost/bimap/relation/member_at.hpp> 422 #include <boost/multi_index/detail/unbounded.hpp> 423 424 // Bring the most used namespaces directly to the user main namespace 425 namespace boost { 426 namespace bimaps { 427 428 using ::boost::bimaps::tags::tagged; 429 430 namespace member_at = ::boost::bimaps::relation::member_at; 431 432 using ::boost::multi_index::unbounded; 433 434 } // namespace bimaps 435 } // namespace boost 436 437 438 #endif // BOOST_BIMAP_BIMAP_HPP 439