ceph/src/boost/boost/multi_index/detail/ord_index_impl.hpp

   1 /* Copyright 2003-2020 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  *
   8  * The internal implementation of red-black trees is based on that of SGI STL
   9  * stl_tree.h file:
  10  *
  11  * Copyright (c) 1996,1997
  12  * Silicon Graphics Computer Systems, Inc.
  13  *
  14  * Permission to use, copy, modify, distribute and sell this software
  15  * and its documentation for any purpose is hereby granted without fee,
  16  * provided that the above copyright notice appear in all copies and
  17  * that both that copyright notice and this permission notice appear
  18  * in supporting documentation.  Silicon Graphics makes no
  19  * representations about the suitability of this software for any
  20  * purpose.  It is provided "as is" without express or implied warranty.
  21  *
  22  *
  23  * Copyright (c) 1994
  24  * Hewlett-Packard Company
  25  *
  26  * Permission to use, copy, modify, distribute and sell this software
  27  * and its documentation for any purpose is hereby granted without fee,
  28  * provided that the above copyright notice appear in all copies and
  29  * that both that copyright notice and this permission notice appear
  30  * in supporting documentation.  Hewlett-Packard Company makes no
  31  * representations about the suitability of this software for any
  32  * purpose.  It is provided "as is" without express or implied warranty.
  33  *
  34  */
  35
  36 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP
  37 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP
  38
  39 #if defined(_MSC_VER)
  40 #pragma once
  41 #endif
  42
  43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  44 #include <algorithm>
  45 #include <boost/call_traits.hpp>
  46 #include <boost/core/addressof.hpp>
  47 #include <boost/core/no_exceptions_support.hpp>
  48 #include <boost/detail/workaround.hpp>
  49 #include <boost/foreach_fwd.hpp>
  50 #include <boost/iterator/reverse_iterator.hpp>
  51 #include <boost/move/core.hpp>
  52 #include <boost/move/utility_core.hpp>
  53 #include <boost/mpl/bool.hpp>
  54 #include <boost/mpl/if.hpp>
  55 #include <boost/mpl/push_front.hpp>
  56 #include <boost/multi_index/detail/access_specifier.hpp>
  57 #include <boost/multi_index/detail/adl_swap.hpp>
  58 #include <boost/multi_index/detail/allocator_traits.hpp>
  59 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
  60 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
  61 #include <boost/multi_index/detail/index_node_base.hpp>
  62 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
  63 #include <boost/multi_index/detail/node_handle.hpp>
  64 #include <boost/multi_index/detail/ord_index_node.hpp>
  65 #include <boost/multi_index/detail/ord_index_ops.hpp>
  66 #include <boost/multi_index/detail/safe_mode.hpp>
  67 #include <boost/multi_index/detail/scope_guard.hpp>
  68 #include <boost/multi_index/detail/unbounded.hpp>
  69 #include <boost/multi_index/detail/value_compare.hpp>
  70 #include <boost/multi_index/detail/vartempl_support.hpp>
  71 #include <boost/multi_index/detail/ord_index_impl_fwd.hpp>
  72 #include <boost/ref.hpp>
  73 #include <boost/tuple/tuple.hpp>
  74 #include <boost/type_traits/is_same.hpp>
  75 #include <utility>
  76
  77 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  78 #include <initializer_list>
  79 #endif
  80
  81 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  82 #include <boost/archive/archive_exception.hpp>
  83 #include <boost/bind/bind.hpp>
  84 #include <boost/multi_index/detail/duplicates_iterator.hpp>
  85 #include <boost/throw_exception.hpp>
  86 #endif
  87
  88 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  89 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x)                    \
  90   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  91     detail::make_obj_guard(x,&ordered_index_impl::check_invariant_);         \
  92   BOOST_JOIN(check_invariant_,__LINE__).touch();
  93 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT                          \
  94   BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(*this)
  95 #else
  96 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x)
  97 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
  98 #endif
  99
 100 namespace boost{
 101
 102 namespace multi_index{
 103
 104 namespace detail{
 105
 106 /* ordered_index adds a layer of ordered indexing to a given Super and accepts
 107  * an augmenting policy for optional addition of order statistics.
 108  */
 109
 110 /* Most of the implementation of unique and non-unique indices is
 111  * shared. We tell from one another on instantiation time by using
 112  * these tags.
 113  */
 114
 115 struct ordered_unique_tag{};
 116 struct ordered_non_unique_tag{};
 117
 118 template<
 119   typename KeyFromValue,typename Compare,
 120   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
 121 >
 122 class ordered_index;
 123
 124 template<
 125   typename KeyFromValue,typename Compare,
 126   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
 127 >
 128 class ordered_index_impl:
 129   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
 130
 131 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 132   ,public safe_mode::safe_container<
 133     ordered_index_impl<
 134       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy> >
 135 #endif
 136
 137 {
 138 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
 139     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
 140 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
 141  * lifetime of const references bound to temporaries --precisely what
 142  * scopeguards are.
 143  */
 144
 145 #pragma parse_mfunc_templ off
 146 #endif
 147
 148   typedef typename SuperMeta::type                   super;
 149
 150 protected:
 151   typedef ordered_index_node<
 152     AugmentPolicy,typename super::index_node_type>   index_node_type;
 153
 154 protected: /* for the benefit of AugmentPolicy::augmented_interface */
 155   typedef typename index_node_type::impl_type        node_impl_type;
 156   typedef typename node_impl_type::pointer           node_impl_pointer;
 157
 158 public:
 159   /* types */
 160
 161   typedef typename KeyFromValue::result_type         key_type;
 162   typedef typename index_node_type::value_type       value_type;
 163   typedef KeyFromValue                               key_from_value;
 164   typedef Compare                                    key_compare;
 165   typedef value_comparison<
 166     value_type,KeyFromValue,Compare>                 value_compare;
 167   typedef tuple<key_from_value,key_compare>          ctor_args;
 168   typedef typename super::final_allocator_type       allocator_type;
 169   typedef value_type&                                reference;
 170   typedef const value_type&                          const_reference;
 171
 172 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 173   typedef safe_mode::safe_iterator<
 174     bidir_node_iterator<index_node_type>,
 175     ordered_index_impl>                              iterator;
 176 #else
 177   typedef bidir_node_iterator<index_node_type>       iterator;
 178 #endif
 179
 180   typedef iterator                                   const_iterator;
 181
 182 private:
 183   typedef allocator_traits<allocator_type>           alloc_traits;
 184
 185 public:
 186   typedef typename alloc_traits::size_type           size_type;
 187   typedef typename alloc_traits::difference_type     difference_type;
 188   typedef typename alloc_traits::pointer             pointer;
 189   typedef typename alloc_traits::const_pointer       const_pointer;
 190   typedef typename
 191     boost::reverse_iterator<iterator>                reverse_iterator;
 192   typedef typename
 193     boost::reverse_iterator<const_iterator>          const_reverse_iterator;
 194   typedef typename super::final_node_handle_type     node_type;
 195   typedef detail::insert_return_type<
 196     iterator,node_type>                              insert_return_type;
 197   typedef TagList                                    tag_list;
 198
 199 protected:
 200   typedef typename super::final_node_type            final_node_type;
 201   typedef tuples::cons<
 202     ctor_args,
 203     typename super::ctor_args_list>                  ctor_args_list;
 204   typedef typename mpl::push_front<
 205     typename super::index_type_list,
 206     ordered_index<
 207       KeyFromValue,Compare,
 208       SuperMeta,TagList,Category,AugmentPolicy
 209     > >::type                                        index_type_list;
 210   typedef typename mpl::push_front<
 211     typename super::iterator_type_list,
 212     iterator>::type    iterator_type_list;
 213   typedef typename mpl::push_front<
 214     typename super::const_iterator_type_list,
 215     const_iterator>::type                            const_iterator_type_list;
 216   typedef typename super::copy_map_type              copy_map_type;
 217
 218 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 219   typedef typename super::index_saver_type           index_saver_type;
 220   typedef typename super::index_loader_type          index_loader_type;
 221 #endif
 222
 223 protected:
 224 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 225   typedef safe_mode::safe_container<
 226     ordered_index_impl>                              safe_super;
 227 #endif
 228
 229   typedef typename call_traits<
 230     value_type>::param_type                          value_param_type;
 231   typedef typename call_traits<
 232     key_type>::param_type                            key_param_type;
 233
 234   /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
 235    * expansion.
 236    */
 237
 238   typedef std::pair<iterator,bool>                   emplace_return_type;
 239
 240 public:
 241
 242   /* construct/copy/destroy
 243    * Default and copy ctors are in the protected section as indices are
 244    * not supposed to be created on their own. No range ctor either.
 245    * Assignment operators defined at ordered_index rather than here.
 246    */
 247
 248   allocator_type get_allocator()const BOOST_NOEXCEPT
 249   {
 250     return this->final().get_allocator();
 251   }
 252
 253   /* iterators */
 254
 255   iterator
 256     begin()BOOST_NOEXCEPT{return make_iterator(leftmost());}
 257   const_iterator
 258     begin()const BOOST_NOEXCEPT{return make_iterator(leftmost());}
 259   iterator
 260     end()BOOST_NOEXCEPT{return make_iterator(header());}
 261   const_iterator
 262     end()const BOOST_NOEXCEPT{return make_iterator(header());}
 263   reverse_iterator
 264     rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
 265   const_reverse_iterator
 266     rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
 267   reverse_iterator
 268     rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
 269   const_reverse_iterator
 270     rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
 271   const_iterator
 272     cbegin()const BOOST_NOEXCEPT{return begin();}
 273   const_iterator
 274     cend()const BOOST_NOEXCEPT{return end();}
 275   const_reverse_iterator
 276     crbegin()const BOOST_NOEXCEPT{return rbegin();}
 277   const_reverse_iterator
 278     crend()const BOOST_NOEXCEPT{return rend();}
 279
 280   iterator iterator_to(const value_type& x)
 281   {
 282     return make_iterator(
 283       node_from_value<index_node_type>(boost::addressof(x)));
 284   }
 285
 286   const_iterator iterator_to(const value_type& x)const
 287   {
 288     return make_iterator(
 289       node_from_value<index_node_type>(boost::addressof(x)));
 290   }
 291
 292   /* capacity */
 293
 294   bool      empty()const BOOST_NOEXCEPT{return this->final_empty_();}
 295   size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
 296   size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
 297
 298   /* modifiers */
 299
 300   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
 301     emplace_return_type,emplace,emplace_impl)
 302
 303   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
 304     iterator,emplace_hint,emplace_hint_impl,iterator,position)
 305
 306   std::pair<iterator,bool> insert(const value_type& x)
 307   {
 308     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 309     std::pair<final_node_type*,bool> p=this->final_insert_(x);
 310     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 311   }
 312
 313   std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
 314   {
 315     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 316     std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
 317     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 318   }
 319
 320   iterator insert(iterator position,const value_type& x)
 321   {
 322     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 323     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 324     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 325     std::pair<final_node_type*,bool> p=this->final_insert_(
 326       x,static_cast<final_node_type*>(position.get_node()));
 327     return make_iterator(p.first);
 328   }
 329
 330   iterator insert(iterator position,BOOST_RV_REF(value_type) x)
 331   {
 332     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 333     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 334     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 335     std::pair<final_node_type*,bool> p=this->final_insert_rv_(
 336       x,static_cast<final_node_type*>(position.get_node()));
 337     return make_iterator(p.first);
 338   }
 339
 340   template<typename InputIterator>
 341   void insert(InputIterator first,InputIterator last)
 342   {
 343     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 344     index_node_type* hint=header(); /* end() */
 345     for(;first!=last;++first){
 346       hint=this->final_insert_ref_(
 347         *first,static_cast<final_node_type*>(hint)).first;
 348       index_node_type::increment(hint);
 349     }
 350   }
 351
 352 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 353   void insert(std::initializer_list<value_type> list)
 354   {
 355     insert(list.begin(),list.end());
 356   }
 357 #endif
 358
 359   insert_return_type insert(BOOST_RV_REF(node_type) nh)
 360   {
 361     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
 362     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 363     std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh);
 364     return insert_return_type(make_iterator(p.first),p.second,boost::move(nh));
 365   }
 366
 367   iterator insert(const_iterator position,BOOST_RV_REF(node_type) nh)
 368   {
 369     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 370     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 371     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
 372     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 373     std::pair<final_node_type*,bool> p=this->final_insert_nh_(
 374       nh,static_cast<final_node_type*>(position.get_node()));
 375     return make_iterator(p.first);
 376   }
 377
 378   node_type extract(const_iterator position)
 379   {
 380     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 381     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 382     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 383     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 384     return this->final_extract_(
 385       static_cast<final_node_type*>(position.get_node()));
 386   }
 387
 388   node_type extract(key_param_type x)
 389   {
 390     iterator position=lower_bound(x);
 391     if(position==end()||comp_(x,key(*position)))return node_type();
 392     else return extract(position);
 393   }
 394
 395   iterator erase(iterator position)
 396   {
 397     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 398     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 399     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 400     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 401     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
 402     return position;
 403   }
 404
 405   size_type erase(key_param_type x)
 406   {
 407     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 408     std::pair<iterator,iterator> p=equal_range(x);
 409     size_type s=0;
 410     while(p.first!=p.second){
 411       p.first=erase(p.first);
 412       ++s;
 413     }
 414     return s;
 415   }
 416
 417   iterator erase(iterator first,iterator last)
 418   {
 419     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 420     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 421     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 422     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 423     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 424     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 425     while(first!=last){
 426       first=erase(first);
 427     }
 428     return first;
 429   }
 430
 431   bool replace(iterator position,const value_type& x)
 432   {
 433     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 434     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 435     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 436     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 437     return this->final_replace_(
 438       x,static_cast<final_node_type*>(position.get_node()));
 439   }
 440
 441   bool replace(iterator position,BOOST_RV_REF(value_type) x)
 442   {
 443     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 444     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 445     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 446     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 447     return this->final_replace_rv_(
 448       x,static_cast<final_node_type*>(position.get_node()));
 449   }
 450
 451   template<typename Modifier>
 452   bool modify(iterator position,Modifier mod)
 453   {
 454     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 455     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 456     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 457     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 458
 459 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 460     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 461      * this is not added. Left it for all compilers as it does no
 462      * harm.
 463      */
 464
 465     position.detach();
 466 #endif
 467
 468     return this->final_modify_(
 469       mod,static_cast<final_node_type*>(position.get_node()));
 470   }
 471
 472   template<typename Modifier,typename Rollback>
 473   bool modify(iterator position,Modifier mod,Rollback back_)
 474   {
 475     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 476     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 477     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 478     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 479
 480 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 481     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 482      * this is not added. Left it for all compilers as it does no
 483      * harm.
 484      */
 485
 486     position.detach();
 487 #endif
 488
 489     return this->final_modify_(
 490       mod,back_,static_cast<final_node_type*>(position.get_node()));
 491   }
 492
 493   template<typename Modifier>
 494   bool modify_key(iterator position,Modifier mod)
 495   {
 496     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 497     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 498     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 499     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 500     return modify(
 501       position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
 502   }
 503
 504   template<typename Modifier,typename Rollback>
 505   bool modify_key(iterator position,Modifier mod,Rollback back_)
 506   {
 507     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 508     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 509     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 510     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 511     return modify(
 512       position,
 513       modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
 514       modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
 515   }
 516
 517   void swap(
 518     ordered_index<
 519       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
 520   {
 521     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 522     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x);
 523     this->final_swap_(x.final());
 524   }
 525
 526   void clear()BOOST_NOEXCEPT
 527   {
 528     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
 529     this->final_clear_();
 530   }
 531
 532   /* observers */
 533
 534   key_from_value key_extractor()const{return key;}
 535   key_compare    key_comp()const{return comp_;}
 536   value_compare  value_comp()const{return value_compare(key,comp_);}
 537
 538   /* set operations */
 539
 540   /* Internally, these ops rely on const_iterator being the same
 541    * type as iterator.
 542    */
 543
 544   template<typename CompatibleKey>
 545   iterator find(const CompatibleKey& x)const
 546   {
 547     return make_iterator(ordered_index_find(root(),header(),key,x,comp_));
 548   }
 549
 550   template<typename CompatibleKey,typename CompatibleCompare>
 551   iterator find(
 552     const CompatibleKey& x,const CompatibleCompare& comp)const
 553   {
 554     return make_iterator(ordered_index_find(root(),header(),key,x,comp));
 555   }
 556
 557   template<typename CompatibleKey>
 558   size_type count(const CompatibleKey& x)const
 559   {
 560     return count(x,comp_);
 561   }
 562
 563   template<typename CompatibleKey,typename CompatibleCompare>
 564   size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
 565   {
 566     std::pair<iterator,iterator> p=equal_range(x,comp);
 567     size_type n=static_cast<size_type>(std::distance(p.first,p.second));
 568     return n;
 569   }
 570
 571   template<typename CompatibleKey>
 572   iterator lower_bound(const CompatibleKey& x)const
 573   {
 574     return make_iterator(
 575       ordered_index_lower_bound(root(),header(),key,x,comp_));
 576   }
 577
 578   template<typename CompatibleKey,typename CompatibleCompare>
 579   iterator lower_bound(
 580     const CompatibleKey& x,const CompatibleCompare& comp)const
 581   {
 582     return make_iterator(
 583       ordered_index_lower_bound(root(),header(),key,x,comp));
 584   }
 585
 586   template<typename CompatibleKey>
 587   iterator upper_bound(const CompatibleKey& x)const
 588   {
 589     return make_iterator(
 590       ordered_index_upper_bound(root(),header(),key,x,comp_));
 591   }
 592
 593   template<typename CompatibleKey,typename CompatibleCompare>
 594   iterator upper_bound(
 595     const CompatibleKey& x,const CompatibleCompare& comp)const
 596   {
 597     return make_iterator(
 598       ordered_index_upper_bound(root(),header(),key,x,comp));
 599   }
 600
 601   template<typename CompatibleKey>
 602   std::pair<iterator,iterator> equal_range(
 603     const CompatibleKey& x)const
 604   {
 605     std::pair<index_node_type*,index_node_type*> p=
 606       ordered_index_equal_range(root(),header(),key,x,comp_);
 607     return std::pair<iterator,iterator>(
 608       make_iterator(p.first),make_iterator(p.second));
 609   }
 610
 611   template<typename CompatibleKey,typename CompatibleCompare>
 612   std::pair<iterator,iterator> equal_range(
 613     const CompatibleKey& x,const CompatibleCompare& comp)const
 614   {
 615     std::pair<index_node_type*,index_node_type*> p=
 616       ordered_index_equal_range(root(),header(),key,x,comp);
 617     return std::pair<iterator,iterator>(
 618       make_iterator(p.first),make_iterator(p.second));
 619   }
 620
 621   /* range */
 622
 623   template<typename LowerBounder,typename UpperBounder>
 624   std::pair<iterator,iterator>
 625   range(LowerBounder lower,UpperBounder upper)const
 626   {
 627     typedef typename mpl::if_<
 628       is_same<LowerBounder,unbounded_type>,
 629       BOOST_DEDUCED_TYPENAME mpl::if_<
 630         is_same<UpperBounder,unbounded_type>,
 631         both_unbounded_tag,
 632         lower_unbounded_tag
 633       >::type,
 634       BOOST_DEDUCED_TYPENAME mpl::if_<
 635         is_same<UpperBounder,unbounded_type>,
 636         upper_unbounded_tag,
 637         none_unbounded_tag
 638       >::type
 639     >::type dispatch;
 640
 641     return range(lower,upper,dispatch());
 642   }
 643
 644 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 645   ordered_index_impl(const ctor_args_list& args_list,const allocator_type& al):
 646     super(args_list.get_tail(),al),
 647     key(tuples::get<0>(args_list.get_head())),
 648     comp_(tuples::get<1>(args_list.get_head()))
 649   {
 650     empty_initialize();
 651   }
 652
 653   ordered_index_impl(
 654     const ordered_index_impl<
 655       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x):
 656     super(x),
 657
 658 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 659     safe_super(),
 660 #endif
 661
 662     key(x.key),
 663     comp_(x.comp_)
 664   {
 665     /* Copy ctor just takes the key and compare objects from x. The rest is
 666      * done in a subsequent call to copy_().
 667      */
 668   }
 669
 670   ordered_index_impl(
 671      const ordered_index_impl<
 672        KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
 673      do_not_copy_elements_tag):
 674     super(x,do_not_copy_elements_tag()),
 675
 676 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 677     safe_super(),
 678 #endif
 679
 680     key(x.key),
 681     comp_(x.comp_)
 682   {
 683     empty_initialize();
 684   }
 685
 686   ~ordered_index_impl()
 687   {
 688     /* the container is guaranteed to be empty by now */
 689   }
 690
 691 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 692   iterator       make_iterator(index_node_type* node)
 693     {return iterator(node,this);}
 694   const_iterator make_iterator(index_node_type* node)const
 695     {return const_iterator(node,const_cast<ordered_index_impl*>(this));}
 696 #else
 697   iterator       make_iterator(index_node_type* node){return iterator(node);}
 698   const_iterator make_iterator(index_node_type* node)const
 699                    {return const_iterator(node);}
 700 #endif
 701
 702   void copy_(
 703     const ordered_index_impl<
 704       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
 705     const copy_map_type& map)
 706   {
 707     if(!x.root()){
 708       empty_initialize();
 709     }
 710     else{
 711       header()->color()=x.header()->color();
 712       AugmentPolicy::copy(x.header()->impl(),header()->impl());
 713
 714       index_node_type* root_cpy=map.find(
 715         static_cast<final_node_type*>(x.root()));
 716       header()->parent()=root_cpy->impl();
 717
 718       index_node_type* leftmost_cpy=map.find(
 719         static_cast<final_node_type*>(x.leftmost()));
 720       header()->left()=leftmost_cpy->impl();
 721
 722       index_node_type* rightmost_cpy=map.find(
 723         static_cast<final_node_type*>(x.rightmost()));
 724       header()->right()=rightmost_cpy->impl();
 725
 726       typedef typename copy_map_type::const_iterator copy_map_iterator;
 727       for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){
 728         index_node_type* org=it->first;
 729         index_node_type* cpy=it->second;
 730
 731         cpy->color()=org->color();
 732         AugmentPolicy::copy(org->impl(),cpy->impl());
 733
 734         node_impl_pointer parent_org=org->parent();
 735         if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0);
 736         else{
 737           index_node_type* parent_cpy=map.find(
 738             static_cast<final_node_type*>(
 739               index_node_type::from_impl(parent_org)));
 740           cpy->parent()=parent_cpy->impl();
 741           if(parent_org->left()==org->impl()){
 742             parent_cpy->left()=cpy->impl();
 743           }
 744           else if(parent_org->right()==org->impl()){
 745             /* header() does not satisfy this nor the previous check */
 746             parent_cpy->right()=cpy->impl();
 747           }
 748         }
 749
 750         if(org->left()==node_impl_pointer(0))
 751           cpy->left()=node_impl_pointer(0);
 752         if(org->right()==node_impl_pointer(0))
 753           cpy->right()=node_impl_pointer(0);
 754       }
 755     }
 756
 757     super::copy_(x,map);
 758   }
 759
 760   template<typename Variant>
 761   final_node_type* insert_(
 762     value_param_type v,final_node_type*& x,Variant variant)
 763   {
 764     link_info inf;
 765     if(!link_point(key(v),inf,Category())){
 766       return static_cast<final_node_type*>(
 767         index_node_type::from_impl(inf.pos));
 768     }
 769
 770     final_node_type* res=super::insert_(v,x,variant);
 771     if(res==x){
 772       node_impl_type::link(
 773         static_cast<index_node_type*>(x)->impl(),
 774         inf.side,inf.pos,header()->impl());
 775     }
 776     return res;
 777   }
 778
 779   template<typename Variant>
 780   final_node_type* insert_(
 781     value_param_type v,index_node_type* position,
 782     final_node_type*& x,Variant variant)
 783   {
 784     link_info inf;
 785     if(!hinted_link_point(key(v),position,inf,Category())){
 786       return static_cast<final_node_type*>(
 787         index_node_type::from_impl(inf.pos));
 788     }
 789
 790     final_node_type* res=super::insert_(v,position,x,variant);
 791     if(res==x){
 792       node_impl_type::link(
 793         static_cast<index_node_type*>(x)->impl(),
 794         inf.side,inf.pos,header()->impl());
 795     }
 796     return res;
 797   }
 798
 799   void extract_(index_node_type* x)
 800   {
 801     node_impl_type::rebalance_for_extract(
 802       x->impl(),header()->parent(),header()->left(),header()->right());
 803     super::extract_(x);
 804
 805 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 806     detach_iterators(x);
 807 #endif
 808   }
 809
 810   void delete_all_nodes_()
 811   {
 812     delete_all_nodes(root());
 813   }
 814
 815   void clear_()
 816   {
 817     super::clear_();
 818     empty_initialize();
 819
 820 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 821     safe_super::detach_dereferenceable_iterators();
 822 #endif
 823   }
 824
 825   template<typename BoolConstant>
 826   void swap_(
 827     ordered_index_impl<
 828       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
 829     BoolConstant swap_allocators)
 830   {
 831     adl_swap(key,x.key);
 832     adl_swap(comp_,x.comp_);
 833
 834 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 835     safe_super::swap(x);
 836 #endif
 837
 838     super::swap_(x,swap_allocators);
 839   }
 840
 841   void swap_elements_(
 842     ordered_index_impl<
 843       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
 844   {
 845 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 846     safe_super::swap(x);
 847 #endif
 848
 849     super::swap_elements_(x);
 850   }
 851
 852   template<typename Variant>
 853   bool replace_(value_param_type v,index_node_type* x,Variant variant)
 854   {
 855     if(in_place(v,x,Category())){
 856       return super::replace_(v,x,variant);
 857     }
 858
 859     index_node_type* next=x;
 860     index_node_type::increment(next);
 861
 862     node_impl_type::rebalance_for_extract(
 863       x->impl(),header()->parent(),header()->left(),header()->right());
 864
 865     BOOST_TRY{
 866       link_info inf;
 867       if(link_point(key(v),inf,Category())&&super::replace_(v,x,variant)){
 868         node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
 869         return true;
 870       }
 871       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
 872       return false;
 873     }
 874     BOOST_CATCH(...){
 875       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
 876       BOOST_RETHROW;
 877     }
 878     BOOST_CATCH_END
 879   }
 880
 881   bool modify_(index_node_type* x)
 882   {
 883     bool b;
 884     BOOST_TRY{
 885       b=in_place(x->value(),x,Category());
 886     }
 887     BOOST_CATCH(...){
 888       extract_(x);
 889       BOOST_RETHROW;
 890     }
 891     BOOST_CATCH_END
 892     if(!b){
 893       node_impl_type::rebalance_for_extract(
 894         x->impl(),header()->parent(),header()->left(),header()->right());
 895       BOOST_TRY{
 896         link_info inf;
 897         if(!link_point(key(x->value()),inf,Category())){
 898           super::extract_(x);
 899
 900 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 901           detach_iterators(x);
 902 #endif
 903           return false;
 904         }
 905         node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
 906       }
 907       BOOST_CATCH(...){
 908         super::extract_(x);
 909
 910 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 911         detach_iterators(x);
 912 #endif
 913
 914         BOOST_RETHROW;
 915       }
 916       BOOST_CATCH_END
 917     }
 918
 919     BOOST_TRY{
 920       if(!super::modify_(x)){
 921         node_impl_type::rebalance_for_extract(
 922           x->impl(),header()->parent(),header()->left(),header()->right());
 923
 924 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 925         detach_iterators(x);
 926 #endif
 927
 928         return false;
 929       }
 930       else return true;
 931     }
 932     BOOST_CATCH(...){
 933       node_impl_type::rebalance_for_extract(
 934         x->impl(),header()->parent(),header()->left(),header()->right());
 935
 936 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 937       detach_iterators(x);
 938 #endif
 939
 940       BOOST_RETHROW;
 941     }
 942     BOOST_CATCH_END
 943   }
 944
 945   bool modify_rollback_(index_node_type* x)
 946   {
 947     if(in_place(x->value(),x,Category())){
 948       return super::modify_rollback_(x);
 949     }
 950
 951     index_node_type* next=x;
 952     index_node_type::increment(next);
 953
 954     node_impl_type::rebalance_for_extract(
 955       x->impl(),header()->parent(),header()->left(),header()->right());
 956
 957     BOOST_TRY{
 958       link_info inf;
 959       if(link_point(key(x->value()),inf,Category())&&
 960          super::modify_rollback_(x)){
 961         node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
 962         return true;
 963       }
 964       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
 965       return false;
 966     }
 967     BOOST_CATCH(...){
 968       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
 969       BOOST_RETHROW;
 970     }
 971     BOOST_CATCH_END
 972   }
 973
 974   bool check_rollback_(index_node_type* x)const
 975   {
 976     return in_place(x->value(),x,Category())&&super::check_rollback_(x);
 977   }
 978
 979 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 980   /* serialization */
 981
 982   template<typename Archive>
 983   void save_(
 984     Archive& ar,const unsigned int version,const index_saver_type& sm)const
 985   {
 986     save_(ar,version,sm,Category());
 987   }
 988
 989   template<typename Archive>
 990   void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
 991   {
 992     load_(ar,version,lm,Category());
 993   }
 994 #endif
 995
 996 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 997   /* invariant stuff */
 998
 999   bool invariant_()const
1000   {
1001     if(size()==0||begin()==end()){
1002       if(size()!=0||begin()!=end()||
1003          header()->left()!=header()->impl()||
1004          header()->right()!=header()->impl())return false;
1005     }
1006     else{
1007       if((size_type)std::distance(begin(),end())!=size())return false;
1008
1009       std::size_t len=node_impl_type::black_count(
1010         leftmost()->impl(),root()->impl());
1011       for(const_iterator it=begin(),it_end=end();it!=it_end;++it){
1012         index_node_type* x=it.get_node();
1013         index_node_type* left_x=index_node_type::from_impl(x->left());
1014         index_node_type* right_x=index_node_type::from_impl(x->right());
1015
1016         if(x->color()==red){
1017           if((left_x&&left_x->color()==red)||
1018              (right_x&&right_x->color()==red))return false;
1019         }
1020         if(left_x&&comp_(key(x->value()),key(left_x->value())))return false;
1021         if(right_x&&comp_(key(right_x->value()),key(x->value())))return false;
1022         if(!left_x&&!right_x&&
1023            node_impl_type::black_count(x->impl(),root()->impl())!=len)
1024           return false;
1025         if(!AugmentPolicy::invariant(x->impl()))return false;
1026       }
1027
1028       if(leftmost()->impl()!=node_impl_type::minimum(root()->impl()))
1029         return false;
1030       if(rightmost()->impl()!=node_impl_type::maximum(root()->impl()))
1031         return false;
1032     }
1033
1034     return super::invariant_();
1035   }
1036
1037
1038   /* This forwarding function eases things for the boost::mem_fn construct
1039    * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
1040    * final_check_invariant is already an inherited member function of
1041    * ordered_index_impl.
1042    */
1043   void check_invariant_()const{this->final_check_invariant_();}
1044 #endif
1045
1046 protected: /* for the benefit of AugmentPolicy::augmented_interface */
1047   index_node_type* header()const
1048     {return this->final_header();}
1049   index_node_type* root()const
1050     {return index_node_type::from_impl(header()->parent());}
1051   index_node_type* leftmost()const
1052     {return index_node_type::from_impl(header()->left());}
1053   index_node_type* rightmost()const
1054     {return index_node_type::from_impl(header()->right());}
1055
1056 private:
1057   void empty_initialize()
1058   {
1059     header()->color()=red;
1060     /* used to distinguish header() from root, in iterator.operator++ */
1061
1062     header()->parent()=node_impl_pointer(0);
1063     header()->left()=header()->impl();
1064     header()->right()=header()->impl();
1065   }
1066
1067   struct link_info
1068   {
1069     /* coverity[uninit_ctor]: suppress warning */
1070     link_info():side(to_left){}
1071
1072     ordered_index_side side;
1073     node_impl_pointer  pos;
1074   };
1075
1076   bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
1077   {
1078     index_node_type* y=header();
1079     index_node_type* x=root();
1080     bool c=true;
1081     while(x){
1082       y=x;
1083       c=comp_(k,key(x->value()));
1084       x=index_node_type::from_impl(c?x->left():x->right());
1085     }
1086     index_node_type* yy=y;
1087     if(c){
1088       if(yy==leftmost()){
1089         inf.side=to_left;
1090         inf.pos=y->impl();
1091         return true;
1092       }
1093       else index_node_type::decrement(yy);
1094     }
1095
1096     if(comp_(key(yy->value()),k)){
1097       inf.side=c?to_left:to_right;
1098       inf.pos=y->impl();
1099       return true;
1100     }
1101     else{
1102       inf.pos=yy->impl();
1103       return false;
1104     }
1105   }
1106
1107   bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1108   {
1109     index_node_type* y=header();
1110     index_node_type* x=root();
1111     bool c=true;
1112     while (x){
1113      y=x;
1114      c=comp_(k,key(x->value()));
1115      x=index_node_type::from_impl(c?x->left():x->right());
1116     }
1117     inf.side=c?to_left:to_right;
1118     inf.pos=y->impl();
1119     return true;
1120   }
1121
1122   bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1123   {
1124     index_node_type* y=header();
1125     index_node_type* x=root();
1126     bool c=false;
1127     while (x){
1128      y=x;
1129      c=comp_(key(x->value()),k);
1130      x=index_node_type::from_impl(c?x->right():x->left());
1131     }
1132     inf.side=c?to_right:to_left;
1133     inf.pos=y->impl();
1134     return true;
1135   }
1136
1137   bool hinted_link_point(
1138     key_param_type k,index_node_type* position,
1139     link_info& inf,ordered_unique_tag)
1140   {
1141     if(position->impl()==header()->left()){
1142       if(size()>0&&comp_(k,key(position->value()))){
1143         inf.side=to_left;
1144         inf.pos=position->impl();
1145         return true;
1146       }
1147       else return link_point(k,inf,ordered_unique_tag());
1148     }
1149     else if(position==header()){
1150       if(comp_(key(rightmost()->value()),k)){
1151         inf.side=to_right;
1152         inf.pos=rightmost()->impl();
1153         return true;
1154       }
1155       else return link_point(k,inf,ordered_unique_tag());
1156     }
1157     else{
1158       index_node_type* before=position;
1159       index_node_type::decrement(before);
1160       if(comp_(key(before->value()),k)&&comp_(k,key(position->value()))){
1161         if(before->right()==node_impl_pointer(0)){
1162           inf.side=to_right;
1163           inf.pos=before->impl();
1164           return true;
1165         }
1166         else{
1167           inf.side=to_left;
1168           inf.pos=position->impl();
1169           return true;
1170         }
1171       }
1172       else return link_point(k,inf,ordered_unique_tag());
1173     }
1174   }
1175
1176   bool hinted_link_point(
1177     key_param_type k,index_node_type* position,
1178     link_info& inf,ordered_non_unique_tag)
1179   {
1180     if(position->impl()==header()->left()){
1181       if(size()>0&&!comp_(key(position->value()),k)){
1182         inf.side=to_left;
1183         inf.pos=position->impl();
1184         return true;
1185       }
1186       else return lower_link_point(k,inf,ordered_non_unique_tag());
1187     }
1188     else if(position==header()){
1189       if(!comp_(k,key(rightmost()->value()))){
1190         inf.side=to_right;
1191         inf.pos=rightmost()->impl();
1192         return true;
1193       }
1194       else return link_point(k,inf,ordered_non_unique_tag());
1195     }
1196     else{
1197       index_node_type* before=position;
1198       index_node_type::decrement(before);
1199       if(!comp_(k,key(before->value()))){
1200         if(!comp_(key(position->value()),k)){
1201           if(before->right()==node_impl_pointer(0)){
1202             inf.side=to_right;
1203             inf.pos=before->impl();
1204             return true;
1205           }
1206           else{
1207             inf.side=to_left;
1208             inf.pos=position->impl();
1209             return true;
1210           }
1211         }
1212         else return lower_link_point(k,inf,ordered_non_unique_tag());
1213       }
1214       else return link_point(k,inf,ordered_non_unique_tag());
1215     }
1216   }
1217
1218   void delete_all_nodes(index_node_type* x)
1219   {
1220     if(!x)return;
1221
1222     delete_all_nodes(index_node_type::from_impl(x->left()));
1223     delete_all_nodes(index_node_type::from_impl(x->right()));
1224     this->final_delete_node_(static_cast<final_node_type*>(x));
1225   }
1226
1227   bool in_place(value_param_type v,index_node_type* x,ordered_unique_tag)const
1228   {
1229     index_node_type* y;
1230     if(x!=leftmost()){
1231       y=x;
1232       index_node_type::decrement(y);
1233       if(!comp_(key(y->value()),key(v)))return false;
1234     }
1235
1236     y=x;
1237     index_node_type::increment(y);
1238     return y==header()||comp_(key(v),key(y->value()));
1239   }
1240
1241   bool in_place(
1242     value_param_type v,index_node_type* x,ordered_non_unique_tag)const
1243   {
1244     index_node_type* y;
1245     if(x!=leftmost()){
1246       y=x;
1247       index_node_type::decrement(y);
1248       if(comp_(key(v),key(y->value())))return false;
1249     }
1250
1251     y=x;
1252     index_node_type::increment(y);
1253     return y==header()||!comp_(key(y->value()),key(v));
1254   }
1255
1256 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1257   void detach_iterators(index_node_type* x)
1258   {
1259     iterator it=make_iterator(x);
1260     safe_mode::detach_equivalent_iterators(it);
1261   }
1262 #endif
1263
1264   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1265   std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1266   {
1267     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1268     std::pair<final_node_type*,bool>p=
1269       this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1270     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1271   }
1272
1273   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1274   iterator emplace_hint_impl(
1275     iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1276   {
1277     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1278     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1279     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1280     std::pair<final_node_type*,bool>p=
1281       this->final_emplace_hint_(
1282         static_cast<final_node_type*>(position.get_node()),
1283         BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1284     return make_iterator(p.first);
1285   }
1286
1287   template<typename LowerBounder,typename UpperBounder>
1288   std::pair<iterator,iterator>
1289   range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
1290   {
1291     index_node_type* y=header();
1292     index_node_type* z=root();
1293
1294     while(z){
1295       if(!lower(key(z->value()))){
1296         z=index_node_type::from_impl(z->right());
1297       }
1298       else if(!upper(key(z->value()))){
1299         y=z;
1300         z=index_node_type::from_impl(z->left());
1301       }
1302       else{
1303         return std::pair<iterator,iterator>(
1304           make_iterator(
1305             lower_range(index_node_type::from_impl(z->left()),z,lower)),
1306           make_iterator(
1307             upper_range(index_node_type::from_impl(z->right()),y,upper)));
1308       }
1309     }
1310
1311     return std::pair<iterator,iterator>(make_iterator(y),make_iterator(y));
1312   }
1313
1314   template<typename LowerBounder,typename UpperBounder>
1315   std::pair<iterator,iterator>
1316   range(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
1317   {
1318     return std::pair<iterator,iterator>(
1319       begin(),
1320       make_iterator(upper_range(root(),header(),upper)));
1321   }
1322
1323   template<typename LowerBounder,typename UpperBounder>
1324   std::pair<iterator,iterator>
1325   range(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
1326   {
1327     return std::pair<iterator,iterator>(
1328       make_iterator(lower_range(root(),header(),lower)),
1329       end());
1330   }
1331
1332   template<typename LowerBounder,typename UpperBounder>
1333   std::pair<iterator,iterator>
1334   range(LowerBounder,UpperBounder,both_unbounded_tag)const
1335   {
1336     return std::pair<iterator,iterator>(begin(),end());
1337   }
1338
1339   template<typename LowerBounder>
1340   index_node_type * lower_range(
1341     index_node_type* top,index_node_type* y,LowerBounder lower)const
1342   {
1343     while(top){
1344       if(lower(key(top->value()))){
1345         y=top;
1346         top=index_node_type::from_impl(top->left());
1347       }
1348       else top=index_node_type::from_impl(top->right());
1349     }
1350
1351     return y;
1352   }
1353
1354   template<typename UpperBounder>
1355   index_node_type * upper_range(
1356     index_node_type* top,index_node_type* y,UpperBounder upper)const
1357   {
1358     while(top){
1359       if(!upper(key(top->value()))){
1360         y=top;
1361         top=index_node_type::from_impl(top->left());
1362       }
1363       else top=index_node_type::from_impl(top->right());
1364     }
1365
1366     return y;
1367   }
1368
1369 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1370   template<typename Archive>
1371   void save_(
1372     Archive& ar,const unsigned int version,const index_saver_type& sm,
1373     ordered_unique_tag)const
1374   {
1375     super::save_(ar,version,sm);
1376   }
1377
1378   template<typename Archive>
1379   void load_(
1380     Archive& ar,const unsigned int version,const index_loader_type& lm,
1381     ordered_unique_tag)
1382   {
1383     super::load_(ar,version,lm);
1384   }
1385
1386   template<typename Archive>
1387   void save_(
1388     Archive& ar,const unsigned int version,const index_saver_type& sm,
1389     ordered_non_unique_tag)const
1390   {
1391     typedef duplicates_iterator<index_node_type,value_compare> dup_iterator;
1392
1393     sm.save(
1394       dup_iterator(begin().get_node(),end().get_node(),value_comp()),
1395       dup_iterator(end().get_node(),value_comp()),
1396       ar,version);
1397     super::save_(ar,version,sm);
1398   }
1399
1400   template<typename Archive>
1401   void load_(
1402     Archive& ar,const unsigned int version,const index_loader_type& lm,
1403     ordered_non_unique_tag)
1404   {
1405     lm.load(
1406       ::boost::bind(
1407         &ordered_index_impl::rearranger,this,
1408         ::boost::arg<1>(),::boost::arg<2>()),
1409       ar,version);
1410     super::load_(ar,version,lm);
1411   }
1412
1413   void rearranger(index_node_type* position,index_node_type *x)
1414   {
1415     if(!position||comp_(key(position->value()),key(x->value()))){
1416       position=lower_bound(key(x->value())).get_node();
1417     }
1418     else if(comp_(key(x->value()),key(position->value()))){
1419       /* inconsistent rearrangement */
1420       throw_exception(
1421         archive::archive_exception(
1422           archive::archive_exception::other_exception));
1423     }
1424     else index_node_type::increment(position);
1425
1426     if(position!=x){
1427       node_impl_type::rebalance_for_extract(
1428         x->impl(),header()->parent(),header()->left(),header()->right());
1429       node_impl_type::restore(
1430         x->impl(),position->impl(),header()->impl());
1431     }
1432   }
1433 #endif /* serialization */
1434
1435 protected: /* for the benefit of AugmentPolicy::augmented_interface */
1436   key_from_value key;
1437   key_compare    comp_;
1438
1439 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1440     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1441 #pragma parse_mfunc_templ reset
1442 #endif
1443 };
1444
1445 template<
1446   typename KeyFromValue,typename Compare,
1447   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1448 >
1449 class ordered_index:
1450   public AugmentPolicy::template augmented_interface<
1451     ordered_index_impl<
1452       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy
1453     >
1454   >::type
1455 {
1456   typedef typename AugmentPolicy::template
1457     augmented_interface<
1458       ordered_index_impl<
1459         KeyFromValue,Compare,
1460         SuperMeta,TagList,Category,AugmentPolicy
1461       >
1462     >::type                                       super;
1463 public:
1464   typedef typename super::ctor_args_list          ctor_args_list;
1465   typedef typename super::allocator_type          allocator_type;
1466   typedef typename super::iterator                iterator;
1467
1468   /* construct/copy/destroy
1469    * Default and copy ctors are in the protected section as indices are
1470    * not supposed to be created on their own. No range ctor either.
1471    */
1472
1473   ordered_index& operator=(const ordered_index& x)
1474   {
1475     this->final()=x.final();
1476     return *this;
1477   }
1478
1479 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1480   ordered_index& operator=(
1481     std::initializer_list<BOOST_DEDUCED_TYPENAME super::value_type> list)
1482   {
1483     this->final()=list;
1484     return *this;
1485   }
1486 #endif
1487
1488 protected:
1489   ordered_index(
1490     const ctor_args_list& args_list,const allocator_type& al):
1491     super(args_list,al){}
1492
1493   ordered_index(const ordered_index& x):super(x){}
1494
1495   ordered_index(const ordered_index& x,do_not_copy_elements_tag):
1496     super(x,do_not_copy_elements_tag()){}
1497 };
1498
1499 /* comparison */
1500
1501 template<
1502   typename KeyFromValue1,typename Compare1,
1503   typename SuperMeta1,typename TagList1,typename Category1,
1504   typename AugmentPolicy1,
1505   typename KeyFromValue2,typename Compare2,
1506   typename SuperMeta2,typename TagList2,typename Category2,
1507   typename AugmentPolicy2
1508 >
1509 bool operator==(
1510   const ordered_index<
1511     KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1512   const ordered_index<
1513     KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1514 {
1515   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1516 }
1517
1518 template<
1519   typename KeyFromValue1,typename Compare1,
1520   typename SuperMeta1,typename TagList1,typename Category1,
1521   typename AugmentPolicy1,
1522   typename KeyFromValue2,typename Compare2,
1523   typename SuperMeta2,typename TagList2,typename Category2,
1524   typename AugmentPolicy2
1525 >
1526 bool operator<(
1527   const ordered_index<
1528     KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1529   const ordered_index<
1530     KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1531 {
1532   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1533 }
1534
1535 template<
1536   typename KeyFromValue1,typename Compare1,
1537   typename SuperMeta1,typename TagList1,typename Category1,
1538   typename AugmentPolicy1,
1539   typename KeyFromValue2,typename Compare2,
1540   typename SuperMeta2,typename TagList2,typename Category2,
1541   typename AugmentPolicy2
1542 >
1543 bool operator!=(
1544   const ordered_index<
1545     KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1546   const ordered_index<
1547     KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1548 {
1549   return !(x==y);
1550 }
1551
1552 template<
1553   typename KeyFromValue1,typename Compare1,
1554   typename SuperMeta1,typename TagList1,typename Category1,
1555   typename AugmentPolicy1,
1556   typename KeyFromValue2,typename Compare2,
1557   typename SuperMeta2,typename TagList2,typename Category2,
1558   typename AugmentPolicy2
1559 >
1560 bool operator>(
1561   const ordered_index<
1562     KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1563   const ordered_index<
1564     KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1565 {
1566   return y<x;
1567 }
1568
1569 template<
1570   typename KeyFromValue1,typename Compare1,
1571   typename SuperMeta1,typename TagList1,typename Category1,
1572   typename AugmentPolicy1,
1573   typename KeyFromValue2,typename Compare2,
1574   typename SuperMeta2,typename TagList2,typename Category2,
1575   typename AugmentPolicy2
1576 >
1577 bool operator>=(
1578   const ordered_index<
1579     KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1580   const ordered_index<
1581     KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1582 {
1583   return !(x<y);
1584 }
1585
1586 template<
1587   typename KeyFromValue1,typename Compare1,
1588   typename SuperMeta1,typename TagList1,typename Category1,
1589   typename AugmentPolicy1,
1590   typename KeyFromValue2,typename Compare2,
1591   typename SuperMeta2,typename TagList2,typename Category2,
1592   typename AugmentPolicy2
1593 >
1594 bool operator<=(
1595   const ordered_index<
1596     KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1597   const ordered_index<
1598     KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1599 {
1600   return !(x>y);
1601 }
1602
1603 /*  specialized algorithms */
1604
1605 template<
1606   typename KeyFromValue,typename Compare,
1607   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1608 >
1609 void swap(
1610   ordered_index<
1611     KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
1612   ordered_index<
1613     KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& y)
1614 {
1615   x.swap(y);
1616 }
1617
1618 } /* namespace multi_index::detail */
1619
1620 } /* namespace multi_index */
1621
1622 } /* namespace boost */
1623
1624 /* Boost.Foreach compatibility */
1625
1626 template<
1627   typename KeyFromValue,typename Compare,
1628   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1629 >
1630 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1631   boost::multi_index::detail::ordered_index<
1632     KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>*&,
1633   boost_foreach_argument_dependent_lookup_hack)
1634 {
1635   return 0;
1636 }
1637
1638 #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
1639 #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF
1640
1641 #endif