ceph/src/boost/boost/container/detail/iterators.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2013.
   4 // (C) Copyright Gennaro Prota 2003 - 2004.
   5 //
   6 // Distributed under the Boost Software License, Version 1.0.
   7 // (See accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10 // See http://www.boost.org/libs/container for documentation.
  11 //
  12 //////////////////////////////////////////////////////////////////////////////
  13
  14 #ifndef BOOST_CONTAINER_DETAIL_ITERATORS_HPP
  15 #define BOOST_CONTAINER_DETAIL_ITERATORS_HPP
  16
  17 #ifndef BOOST_CONFIG_HPP
  18 #  include <boost/config.hpp>
  19 #endif
  20
  21 #if defined(BOOST_HAS_PRAGMA_ONCE)
  22 #  pragma once
  23 #endif
  24
  25 #include <boost/container/detail/config_begin.hpp>
  26 #include <boost/container/detail/workaround.hpp>
  27 #include <boost/container/allocator_traits.hpp>
  28 #include <boost/container/detail/type_traits.hpp>
  29 #include <boost/container/detail/value_init.hpp>
  30 #include <boost/static_assert.hpp>
  31 #include <boost/move/utility_core.hpp>
  32 #include <boost/intrusive/detail/reverse_iterator.hpp>
  33
  34 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  35 #include <boost/move/detail/fwd_macros.hpp>
  36 #else
  37 #include <boost/container/detail/variadic_templates_tools.hpp>
  38 #endif
  39 #include <boost/container/detail/iterator.hpp>
  40
  41 namespace boost {
  42 namespace container {
  43
  44 template <class T>
  45 class constant_iterator
  46   : public ::boost::container::iterator
  47       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
  48 {
  49    typedef  constant_iterator<T> this_type;
  50
  51    public:
  52    BOOST_CONTAINER_FORCEINLINE explicit constant_iterator(const T &ref, std::size_t range_size)
  53       :  m_ptr(&ref), m_num(range_size){}
  54
  55    //Constructors
  56    BOOST_CONTAINER_FORCEINLINE constant_iterator()
  57       :  m_ptr(0), m_num(0){}
  58
  59    BOOST_CONTAINER_FORCEINLINE constant_iterator& operator++()
  60    { increment();   return *this;   }
  61
  62    BOOST_CONTAINER_FORCEINLINE constant_iterator operator++(int)
  63    {
  64       constant_iterator result (*this);
  65       increment();
  66       return result;
  67    }
  68
  69    BOOST_CONTAINER_FORCEINLINE constant_iterator& operator--()
  70    { decrement();   return *this;   }
  71
  72    BOOST_CONTAINER_FORCEINLINE constant_iterator operator--(int)
  73    {
  74       constant_iterator result (*this);
  75       decrement();
  76       return result;
  77    }
  78
  79    BOOST_CONTAINER_FORCEINLINE friend bool operator== (const constant_iterator& i, const constant_iterator& i2)
  80    { return i.equal(i2); }
  81
  82    BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const constant_iterator& i, const constant_iterator& i2)
  83    { return !(i == i2); }
  84
  85    BOOST_CONTAINER_FORCEINLINE friend bool operator< (const constant_iterator& i, const constant_iterator& i2)
  86    { return i.less(i2); }
  87
  88    BOOST_CONTAINER_FORCEINLINE friend bool operator> (const constant_iterator& i, const constant_iterator& i2)
  89    { return i2 < i; }
  90
  91    BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const constant_iterator& i, const constant_iterator& i2)
  92    { return !(i > i2); }
  93
  94    BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const constant_iterator& i, const constant_iterator& i2)
  95    { return !(i < i2); }
  96
  97    BOOST_CONTAINER_FORCEINLINE friend std::ptrdiff_t operator- (const constant_iterator& i, const constant_iterator& i2)
  98    { return i2.distance_to(i); }
  99
 100    //Arithmetic signed
 101    BOOST_CONTAINER_FORCEINLINE constant_iterator& operator+=(std::ptrdiff_t off)
 102    {  this->advance(off); return *this;   }
 103
 104    BOOST_CONTAINER_FORCEINLINE constant_iterator operator+(std::ptrdiff_t off) const
 105    {
 106       constant_iterator other(*this);
 107       other.advance(off);
 108       return other;
 109    }
 110
 111    BOOST_CONTAINER_FORCEINLINE friend constant_iterator operator+(std::ptrdiff_t off, const constant_iterator& right)
 112    {  return right + off; }
 113
 114    BOOST_CONTAINER_FORCEINLINE constant_iterator& operator-=(std::ptrdiff_t off)
 115    {  this->advance(-off); return *this;   }
 116
 117    BOOST_CONTAINER_FORCEINLINE constant_iterator operator-(std::ptrdiff_t off) const
 118    {  return *this + (-off);  }
 119
 120    BOOST_CONTAINER_FORCEINLINE const T& operator[] (std::ptrdiff_t ) const
 121    { return dereference(); }
 122
 123    BOOST_CONTAINER_FORCEINLINE const T& operator*() const
 124    { return dereference(); }
 125
 126    BOOST_CONTAINER_FORCEINLINE const T* operator->() const
 127    { return &(dereference()); }
 128
 129    //Arithmetic unsigned
 130    BOOST_CONTAINER_FORCEINLINE constant_iterator& operator+=(std::size_t off)
 131    {  return *this += std::ptrdiff_t(off);  }
 132
 133    BOOST_CONTAINER_FORCEINLINE constant_iterator operator+(std::size_t off) const
 134    {  return *this + std::ptrdiff_t(off);  }
 135
 136    BOOST_CONTAINER_FORCEINLINE friend constant_iterator operator+(std::size_t off, const constant_iterator& right)
 137    {  return std::ptrdiff_t(off) + right;  }
 138
 139    BOOST_CONTAINER_FORCEINLINE constant_iterator& operator-=(std::size_t off)
 140    {  return *this -= std::ptrdiff_t(off);  }
 141
 142    BOOST_CONTAINER_FORCEINLINE constant_iterator operator-(std::size_t off) const
 143    {  return *this - std::ptrdiff_t(off);  }
 144
 145    BOOST_CONTAINER_FORCEINLINE const T& operator[] (std::size_t off) const
 146    { return (*this)[std::ptrdiff_t(off)]; }
 147
 148    private:
 149    const T *   m_ptr;
 150    std::size_t m_num;
 151
 152    BOOST_CONTAINER_FORCEINLINE void increment()
 153    { --m_num; }
 154
 155    BOOST_CONTAINER_FORCEINLINE void decrement()
 156    { ++m_num; }
 157
 158    BOOST_CONTAINER_FORCEINLINE bool equal(const this_type &other) const
 159    {  return m_num == other.m_num;   }
 160
 161    BOOST_CONTAINER_FORCEINLINE bool less(const this_type &other) const
 162    {  return other.m_num < m_num;   }
 163
 164    BOOST_CONTAINER_FORCEINLINE const T & dereference() const
 165    { return *m_ptr; }
 166
 167    BOOST_CONTAINER_FORCEINLINE void advance(std::ptrdiff_t n)
 168    {  m_num = std::size_t(std::ptrdiff_t(m_num) - n); }
 169
 170    BOOST_CONTAINER_FORCEINLINE std::ptrdiff_t distance_to(const this_type &other)const
 171    {  return std::ptrdiff_t(m_num - other.m_num);   }
 172 };
 173
 174 template <class T>
 175 class value_init_construct_iterator
 176   : public ::boost::container::iterator
 177       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
 178 {
 179    typedef  value_init_construct_iterator<T> this_type;
 180
 181    public:
 182    BOOST_CONTAINER_FORCEINLINE explicit value_init_construct_iterator(std::size_t range_size)
 183       :  m_num(range_size){}
 184
 185    //Constructors
 186    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator()
 187       :  m_num(0){}
 188
 189    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator& operator++()
 190    { increment();   return *this;   }
 191
 192    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator operator++(int)
 193    {
 194       value_init_construct_iterator result (*this);
 195       increment();
 196       return result;
 197    }
 198
 199    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator& operator--()
 200    { decrement();   return *this;   }
 201
 202    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator operator--(int)
 203    {
 204       value_init_construct_iterator result (*this);
 205       decrement();
 206       return result;
 207    }
 208
 209    BOOST_CONTAINER_FORCEINLINE friend bool operator== (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 210    { return i.equal(i2); }
 211
 212    BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 213    { return !(i == i2); }
 214
 215    BOOST_CONTAINER_FORCEINLINE friend bool operator< (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 216    { return i.less(i2); }
 217
 218    BOOST_CONTAINER_FORCEINLINE friend bool operator> (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 219    { return i2 < i; }
 220
 221    BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 222    { return !(i > i2); }
 223
 224    BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 225    { return !(i < i2); }
 226
 227    BOOST_CONTAINER_FORCEINLINE friend std::ptrdiff_t operator- (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 228    { return i2.distance_to(i); }
 229
 230    //Arithmetic
 231    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator& operator+=(std::ptrdiff_t off)
 232    {  this->advance(off); return *this;   }
 233
 234    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator operator+(std::ptrdiff_t off) const
 235    {
 236       value_init_construct_iterator other(*this);
 237       other.advance(off);
 238       return other;
 239    }
 240
 241    BOOST_CONTAINER_FORCEINLINE friend value_init_construct_iterator operator+(std::ptrdiff_t off, const value_init_construct_iterator& right)
 242    {  return right + off; }
 243
 244    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator& operator-=(std::ptrdiff_t off)
 245    {  this->advance(-off); return *this;   }
 246
 247    BOOST_CONTAINER_FORCEINLINE value_init_construct_iterator operator-(std::ptrdiff_t off) const
 248    {  return *this + (-off);  }
 249
 250    //This pseudo-iterator's dereference operations have no sense since value is not
 251    //constructed until ::boost::container::construct_in_place is called.
 252    //So comment them to catch bad uses
 253    //const T& operator*() const;
 254    //const T& operator[](difference_type) const;
 255    //const T* operator->() const;
 256
 257    private:
 258    std::size_t  m_num;
 259
 260    BOOST_CONTAINER_FORCEINLINE void increment()
 261    { --m_num; }
 262
 263    BOOST_CONTAINER_FORCEINLINE void decrement()
 264    { ++m_num; }
 265
 266    BOOST_CONTAINER_FORCEINLINE bool equal(const this_type &other) const
 267    {  return m_num == other.m_num;   }
 268
 269    BOOST_CONTAINER_FORCEINLINE bool less(const this_type &other) const
 270    {  return other.m_num < m_num;   }
 271
 272    BOOST_CONTAINER_FORCEINLINE const T & dereference() const
 273    {
 274       static T dummy;
 275       return dummy;
 276    }
 277
 278    BOOST_CONTAINER_FORCEINLINE void advance(std::ptrdiff_t n)
 279    {  m_num = std::size_t(std::ptrdiff_t(m_num) - n); }
 280
 281    BOOST_CONTAINER_FORCEINLINE std::ptrdiff_t distance_to(const this_type &other)const
 282    {  return std::ptrdiff_t(m_num - other.m_num);   }
 283 };
 284
 285 template <class T>
 286 class default_init_construct_iterator
 287   : public ::boost::container::iterator
 288       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
 289 {
 290    typedef  default_init_construct_iterator<T> this_type;
 291
 292    public:
 293    BOOST_CONTAINER_FORCEINLINE explicit default_init_construct_iterator(std::size_t range_size)
 294       :  m_num(range_size){}
 295
 296    //Constructors
 297    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator()
 298       :  m_num(0){}
 299
 300    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator& operator++()
 301    { increment();   return *this;   }
 302
 303    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator operator++(int)
 304    {
 305       default_init_construct_iterator result (*this);
 306       increment();
 307       return result;
 308    }
 309
 310    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator& operator--()
 311    { decrement();   return *this;   }
 312
 313    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator operator--(int)
 314    {
 315       default_init_construct_iterator result (*this);
 316       decrement();
 317       return result;
 318    }
 319
 320    BOOST_CONTAINER_FORCEINLINE friend bool operator== (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 321    { return i.equal(i2); }
 322
 323    BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 324    { return !(i == i2); }
 325
 326    BOOST_CONTAINER_FORCEINLINE friend bool operator< (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 327    { return i.less(i2); }
 328
 329    BOOST_CONTAINER_FORCEINLINE friend bool operator> (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 330    { return i2 < i; }
 331
 332    BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 333    { return !(i > i2); }
 334
 335    BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 336    { return !(i < i2); }
 337
 338    BOOST_CONTAINER_FORCEINLINE friend std::ptrdiff_t operator- (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
 339    { return i2.distance_to(i); }
 340
 341    //Arithmetic
 342    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator& operator+=(std::ptrdiff_t off)
 343    {  this->advance(off); return *this;   }
 344
 345    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator operator+(std::ptrdiff_t off) const
 346    {
 347       default_init_construct_iterator other(*this);
 348       other.advance(off);
 349       return other;
 350    }
 351
 352    BOOST_CONTAINER_FORCEINLINE friend default_init_construct_iterator operator+(std::ptrdiff_t off, const default_init_construct_iterator& right)
 353    {  return right + off; }
 354
 355    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator& operator-=(std::ptrdiff_t off)
 356    {  this->advance(-off); return *this;   }
 357
 358    BOOST_CONTAINER_FORCEINLINE default_init_construct_iterator operator-(std::ptrdiff_t off) const
 359    {  return *this + (-off);  }
 360
 361    //This pseudo-iterator's dereference operations have no sense since value is not
 362    //constructed until ::boost::container::construct_in_place is called.
 363    //So comment them to catch bad uses
 364    //const T& operator*() const;
 365    //const T& operator[](difference_type) const;
 366    //const T* operator->() const;
 367
 368    private:
 369    std::size_t  m_num;
 370
 371    BOOST_CONTAINER_FORCEINLINE void increment()
 372    { --m_num; }
 373
 374    BOOST_CONTAINER_FORCEINLINE void decrement()
 375    { ++m_num; }
 376
 377    BOOST_CONTAINER_FORCEINLINE bool equal(const this_type &other) const
 378    {  return m_num == other.m_num;   }
 379
 380    BOOST_CONTAINER_FORCEINLINE bool less(const this_type &other) const
 381    {  return other.m_num < m_num;   }
 382
 383    BOOST_CONTAINER_FORCEINLINE const T & dereference() const
 384    {
 385       static T dummy;
 386       return dummy;
 387    }
 388
 389    BOOST_CONTAINER_FORCEINLINE void advance(std::ptrdiff_t n)
 390    {  m_num = std::size_t(std::ptrdiff_t(m_num) - n); }
 391
 392    BOOST_CONTAINER_FORCEINLINE std::ptrdiff_t distance_to(const this_type &other) const
 393    {  return std::ptrdiff_t(m_num - other.m_num);   }
 394 };
 395
 396
 397 template <class T>
 398 class repeat_iterator
 399   : public ::boost::container::iterator
 400       <std::random_access_iterator_tag, T, std::ptrdiff_t, T*, T&>
 401 {
 402    typedef repeat_iterator<T> this_type;
 403    public:
 404    BOOST_CONTAINER_FORCEINLINE explicit repeat_iterator(T &ref, std::size_t range_size)
 405       :  m_ptr(&ref), m_num(range_size){}
 406
 407    //Constructors
 408    BOOST_CONTAINER_FORCEINLINE repeat_iterator()
 409       :  m_ptr(0), m_num(0){}
 410
 411    BOOST_CONTAINER_FORCEINLINE this_type& operator++()
 412    { increment();   return *this;   }
 413
 414    BOOST_CONTAINER_FORCEINLINE this_type operator++(int)
 415    {
 416       this_type result (*this);
 417       increment();
 418       return result;
 419    }
 420
 421    BOOST_CONTAINER_FORCEINLINE this_type& operator--()
 422    { increment();   return *this;   }
 423
 424    BOOST_CONTAINER_FORCEINLINE this_type operator--(int)
 425    {
 426       this_type result (*this);
 427       increment();
 428       return result;
 429    }
 430
 431    BOOST_CONTAINER_FORCEINLINE friend bool operator== (const this_type& i, const this_type& i2)
 432    { return i.equal(i2); }
 433
 434    BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const this_type& i, const this_type& i2)
 435    { return !(i == i2); }
 436
 437    BOOST_CONTAINER_FORCEINLINE friend bool operator< (const this_type& i, const this_type& i2)
 438    { return i.less(i2); }
 439
 440    BOOST_CONTAINER_FORCEINLINE friend bool operator> (const this_type& i, const this_type& i2)
 441    { return i2 < i; }
 442
 443    BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const this_type& i, const this_type& i2)
 444    { return !(i > i2); }
 445
 446    BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const this_type& i, const this_type& i2)
 447    { return !(i < i2); }
 448
 449    BOOST_CONTAINER_FORCEINLINE friend std::ptrdiff_t operator- (const this_type& i, const this_type& i2)
 450    { return i2.distance_to(i); }
 451
 452    //Arithmetic
 453    BOOST_CONTAINER_FORCEINLINE this_type& operator+=(std::ptrdiff_t off)
 454    {  this->advance(off); return *this;   }
 455
 456    BOOST_CONTAINER_FORCEINLINE this_type operator+(std::ptrdiff_t off) const
 457    {
 458       this_type other(*this);
 459       other.advance(off);
 460       return other;
 461    }
 462
 463    BOOST_CONTAINER_FORCEINLINE friend this_type operator+(std::ptrdiff_t off, const this_type& right)
 464    {  return right + off; }
 465
 466    BOOST_CONTAINER_FORCEINLINE this_type& operator-=(std::ptrdiff_t off)
 467    {  this->advance(-off); return *this;   }
 468
 469    BOOST_CONTAINER_FORCEINLINE this_type operator-(std::ptrdiff_t off) const
 470    {  return *this + (-off);  }
 471
 472    BOOST_CONTAINER_FORCEINLINE T& operator*() const
 473    { return dereference(); }
 474
 475    BOOST_CONTAINER_FORCEINLINE T& operator[] (std::ptrdiff_t ) const
 476    { return dereference(); }
 477
 478    BOOST_CONTAINER_FORCEINLINE T *operator->() const
 479    { return &(dereference()); }
 480
 481    private:
 482    T *         m_ptr;
 483    std::size_t m_num;
 484
 485    BOOST_CONTAINER_FORCEINLINE void increment()
 486    { --m_num; }
 487
 488    BOOST_CONTAINER_FORCEINLINE void decrement()
 489    { ++m_num; }
 490
 491    BOOST_CONTAINER_FORCEINLINE bool equal(const this_type &other) const
 492    {  return m_num == other.m_num;   }
 493
 494    BOOST_CONTAINER_FORCEINLINE bool less(const this_type &other) const
 495    {  return other.m_num < m_num;   }
 496
 497    BOOST_CONTAINER_FORCEINLINE T & dereference() const
 498    { return *m_ptr; }
 499
 500    BOOST_CONTAINER_FORCEINLINE void advance(std::ptrdiff_t n)
 501    {  m_num = std::size_t(std::ptrdiff_t(m_num - n)); }
 502
 503    BOOST_CONTAINER_FORCEINLINE std::ptrdiff_t distance_to(const this_type &other)const
 504    {  return std::ptrdiff_t(m_num - other.m_num);   }
 505 };
 506
 507 template <class T, class EmplaceFunctor>
 508 class emplace_iterator
 509   : public ::boost::container::iterator
 510       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
 511 {
 512    typedef emplace_iterator this_type;
 513
 514    public:
 515    typedef std::ptrdiff_t difference_type;
 516    BOOST_CONTAINER_FORCEINLINE explicit emplace_iterator(EmplaceFunctor&e)
 517       :  m_num(1), m_pe(&e){}
 518
 519    BOOST_CONTAINER_FORCEINLINE emplace_iterator()
 520       :  m_num(0), m_pe(0){}
 521
 522    BOOST_CONTAINER_FORCEINLINE this_type& operator++()
 523    { increment();   return *this;   }
 524
 525    BOOST_CONTAINER_FORCEINLINE this_type operator++(int)
 526    {
 527       this_type result (*this);
 528       increment();
 529       return result;
 530    }
 531
 532    BOOST_CONTAINER_FORCEINLINE this_type& operator--()
 533    { decrement();   return *this;   }
 534
 535    BOOST_CONTAINER_FORCEINLINE this_type operator--(int)
 536    {
 537       this_type result (*this);
 538       decrement();
 539       return result;
 540    }
 541
 542    BOOST_CONTAINER_FORCEINLINE friend bool operator== (const this_type& i, const this_type& i2)
 543    { return i.equal(i2); }
 544
 545    BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const this_type& i, const this_type& i2)
 546    { return !(i == i2); }
 547
 548    BOOST_CONTAINER_FORCEINLINE friend bool operator< (const this_type& i, const this_type& i2)
 549    { return i.less(i2); }
 550
 551    BOOST_CONTAINER_FORCEINLINE friend bool operator> (const this_type& i, const this_type& i2)
 552    { return i2 < i; }
 553
 554    BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const this_type& i, const this_type& i2)
 555    { return !(i > i2); }
 556
 557    BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const this_type& i, const this_type& i2)
 558    { return !(i < i2); }
 559
 560    BOOST_CONTAINER_FORCEINLINE friend difference_type operator- (const this_type& i, const this_type& i2)
 561    { return i2.distance_to(i); }
 562
 563    //Arithmetic
 564    BOOST_CONTAINER_FORCEINLINE this_type& operator+=(difference_type off)
 565    {  this->advance(off); return *this;   }
 566
 567    BOOST_CONTAINER_FORCEINLINE this_type operator+(difference_type off) const
 568    {
 569       this_type other(*this);
 570       other.advance(off);
 571       return other;
 572    }
 573
 574    BOOST_CONTAINER_FORCEINLINE friend this_type operator+(difference_type off, const this_type& right)
 575    {  return right + off; }
 576
 577    BOOST_CONTAINER_FORCEINLINE this_type& operator-=(difference_type off)
 578    {  this->advance(-off); return *this;   }
 579
 580    BOOST_CONTAINER_FORCEINLINE this_type operator-(difference_type off) const
 581    {  return *this + (-off);  }
 582
 583    private:
 584    //This pseudo-iterator's dereference operations have no sense since value is not
 585    //constructed until ::boost::container::construct_in_place is called.
 586    //So comment them to catch bad uses
 587    const T& operator*() const;
 588    const T& operator[](difference_type) const;
 589    const T* operator->() const;
 590
 591    public:
 592    template<class Allocator>
 593    BOOST_CONTAINER_FORCEINLINE void construct_in_place(Allocator &a, T* ptr)
 594    {  (*m_pe)(a, ptr);  }
 595
 596    template<class DestIt>
 597    BOOST_CONTAINER_FORCEINLINE void assign_in_place(DestIt dest)
 598    {  (*m_pe)(dest);  }
 599
 600    private:
 601    std::size_t m_num;
 602    EmplaceFunctor *            m_pe;
 603
 604    BOOST_CONTAINER_FORCEINLINE void increment()
 605    { --m_num; }
 606
 607    BOOST_CONTAINER_FORCEINLINE void decrement()
 608    { ++m_num; }
 609
 610    BOOST_CONTAINER_FORCEINLINE bool equal(const this_type &other) const
 611    {  return m_num == other.m_num;   }
 612
 613    BOOST_CONTAINER_FORCEINLINE bool less(const this_type &other) const
 614    {  return other.m_num < m_num;   }
 615
 616    BOOST_CONTAINER_FORCEINLINE const T & dereference() const
 617    {
 618       static T dummy;
 619       return dummy;
 620    }
 621
 622    BOOST_CONTAINER_FORCEINLINE void advance(difference_type n)
 623    {  m_num -= n; }
 624
 625    BOOST_CONTAINER_FORCEINLINE difference_type distance_to(const this_type &other)const
 626    {  return difference_type(m_num - other.m_num);   }
 627 };
 628
 629 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 630
 631 template<class ...Args>
 632 struct emplace_functor
 633 {
 634    typedef typename dtl::build_number_seq<sizeof...(Args)>::type index_tuple_t;
 635
 636    BOOST_CONTAINER_FORCEINLINE emplace_functor(BOOST_FWD_REF(Args)... args)
 637       : args_(args...)
 638    {}
 639
 640    template<class Allocator, class T>
 641    BOOST_CONTAINER_FORCEINLINE void operator()(Allocator &a, T *ptr)
 642    {  emplace_functor::inplace_impl(a, ptr, index_tuple_t());  }
 643
 644    template<class DestIt>
 645    BOOST_CONTAINER_FORCEINLINE void operator()(DestIt dest)
 646    {  emplace_functor::inplace_impl(dest, index_tuple_t());  }
 647
 648    private:
 649    template<class Allocator, class T, std::size_t ...IdxPack>
 650    BOOST_CONTAINER_FORCEINLINE void inplace_impl(Allocator &a, T* ptr, const dtl::index_tuple<IdxPack...>&)
 651    {
 652       allocator_traits<Allocator>::construct
 653          (a, ptr, ::boost::forward<Args>(dtl::get<IdxPack>(args_))...);
 654    }
 655
 656    template<class DestIt, std::size_t ...IdxPack>
 657    BOOST_CONTAINER_FORCEINLINE void inplace_impl(DestIt dest, const dtl::index_tuple<IdxPack...>&)
 658    {
 659       typedef typename boost::container::iterator_traits<DestIt>::value_type value_type;
 660       value_type && tmp= value_type(::boost::forward<Args>(dtl::get<IdxPack>(args_))...);
 661       *dest = ::boost::move(tmp);
 662    }
 663
 664    dtl::tuple<Args&...> args_;
 665 };
 666
 667 template<class ...Args>
 668 struct emplace_functor_type
 669 {
 670    typedef emplace_functor<Args...> type;
 671 };
 672
 673 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 674
 675 //Partial specializations cannot match argument list for primary template, so add an extra argument
 676 template <BOOST_MOVE_CLASSDFLT9, class Dummy = void>
 677 struct emplace_functor_type;
 678
 679 #define BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE(N) \
 680 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
 681 struct emplace_functor##N\
 682 {\
 683    BOOST_CONTAINER_FORCEINLINE explicit emplace_functor##N( BOOST_MOVE_UREF##N )\
 684       BOOST_MOVE_COLON##N BOOST_MOVE_FWD_INIT##N{}\
 685    \
 686    template<class Allocator, class T>\
 687    BOOST_CONTAINER_FORCEINLINE void operator()(Allocator &a, T *ptr)\
 688    {  allocator_traits<Allocator>::construct(a, ptr BOOST_MOVE_I##N BOOST_MOVE_MFWD##N);  }\
 689    \
 690    template<class DestIt>\
 691    BOOST_CONTAINER_FORCEINLINE void operator()(DestIt dest)\
 692    {\
 693       typedef typename boost::container::iterator_traits<DestIt>::value_type value_type;\
 694       BOOST_MOVE_IF(N, value_type tmp(BOOST_MOVE_MFWD##N), dtl::value_init<value_type> tmp) ;\
 695       *dest = ::boost::move(const_cast<value_type &>(BOOST_MOVE_IF(N, tmp, tmp.get())));\
 696    }\
 697    \
 698    BOOST_MOVE_MREF##N\
 699 };\
 700 \
 701 template <BOOST_MOVE_CLASS##N>\
 702 struct emplace_functor_type<BOOST_MOVE_TARG##N>\
 703 {\
 704    typedef emplace_functor##N BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N type;\
 705 };\
 706 //
 707
 708 BOOST_MOVE_ITERATE_0TO9(BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE)
 709
 710 #undef BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE
 711
 712 #endif
 713
 714 namespace dtl {
 715
 716 template<class T>
 717 struct has_iterator_category
 718 {
 719    struct two { char _[2]; };
 720
 721    template <typename X>
 722    static char test(int, typename X::iterator_category*);
 723
 724    template <typename X>
 725    static two test(int, ...);
 726
 727    static const bool value = (1 == sizeof(test<T>(0, 0)));
 728 };
 729
 730
 731 template<class T, bool = has_iterator_category<T>::value >
 732 struct is_input_iterator
 733 {
 734    static const bool value = is_same<typename T::iterator_category, std::input_iterator_tag>::value;
 735 };
 736
 737 template<class T>
 738 struct is_input_iterator<T, false>
 739 {
 740    static const bool value = false;
 741 };
 742
 743 template<class T>
 744 struct is_not_input_iterator
 745 {
 746    static const bool value = !is_input_iterator<T>::value;
 747 };
 748
 749 template<class T, bool = has_iterator_category<T>::value >
 750 struct is_forward_iterator
 751 {
 752    static const bool value = is_same<typename T::iterator_category, std::forward_iterator_tag>::value;
 753 };
 754
 755 template<class T>
 756 struct is_forward_iterator<T, false>
 757 {
 758    static const bool value = false;
 759 };
 760
 761 template<class T, bool = has_iterator_category<T>::value >
 762 struct is_bidirectional_iterator
 763 {
 764    static const bool value = is_same<typename T::iterator_category, std::bidirectional_iterator_tag>::value;
 765 };
 766
 767 template<class T>
 768 struct is_bidirectional_iterator<T, false>
 769 {
 770    static const bool value = false;
 771 };
 772
 773 template<class IINodeType>
 774 struct iiterator_node_value_type {
 775   typedef typename IINodeType::value_type type;
 776 };
 777
 778 template<class IIterator>
 779 struct iiterator_types
 780 {
 781    typedef typename IIterator::value_type                            it_value_type;
 782    typedef typename iiterator_node_value_type<it_value_type>::type   value_type;
 783    typedef typename boost::container::iterator_traits<IIterator>::pointer         it_pointer;
 784    typedef typename boost::container::iterator_traits<IIterator>::difference_type difference_type;
 785    typedef typename ::boost::intrusive::pointer_traits<it_pointer>::
 786       template rebind_pointer<value_type>::type                      pointer;
 787    typedef typename ::boost::intrusive::pointer_traits<it_pointer>::
 788       template rebind_pointer<const value_type>::type                const_pointer;
 789    typedef typename ::boost::intrusive::
 790       pointer_traits<pointer>::reference                             reference;
 791    typedef typename ::boost::intrusive::
 792       pointer_traits<const_pointer>::reference                       const_reference;
 793    typedef typename IIterator::iterator_category                     iterator_category;
 794 };
 795
 796 template<class IIterator, bool IsConst>
 797 struct iterator_types
 798 {
 799    typedef typename ::boost::container::iterator
 800       < typename iiterator_types<IIterator>::iterator_category
 801       , typename iiterator_types<IIterator>::value_type
 802       , typename iiterator_types<IIterator>::difference_type
 803       , typename iiterator_types<IIterator>::const_pointer
 804       , typename iiterator_types<IIterator>::const_reference> type;
 805 };
 806
 807 template<class IIterator>
 808 struct iterator_types<IIterator, false>
 809 {
 810    typedef typename ::boost::container::iterator
 811       < typename iiterator_types<IIterator>::iterator_category
 812       , typename iiterator_types<IIterator>::value_type
 813       , typename iiterator_types<IIterator>::difference_type
 814       , typename iiterator_types<IIterator>::pointer
 815       , typename iiterator_types<IIterator>::reference> type;
 816 };
 817
 818 template<class IIterator, bool IsConst>
 819 class iterator_from_iiterator
 820 {
 821    typedef typename iterator_types<IIterator, IsConst>::type   types_t;
 822    class nat
 823    {
 824       public:
 825       IIterator get() const
 826       {  return IIterator(); }
 827    };
 828    typedef typename dtl::if_c< IsConst
 829                              , iterator_from_iiterator<IIterator, false>
 830                              , nat>::type                      nonconst_iterator;
 831
 832    public:
 833    typedef typename types_t::pointer             pointer;
 834    typedef typename types_t::reference           reference;
 835    typedef typename types_t::difference_type     difference_type;
 836    typedef typename types_t::iterator_category   iterator_category;
 837    typedef typename types_t::value_type          value_type;
 838
 839    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator()
 840       : m_iit()
 841    {}
 842
 843    BOOST_CONTAINER_FORCEINLINE explicit iterator_from_iiterator(IIterator iit) BOOST_NOEXCEPT_OR_NOTHROW
 844       : m_iit(iit)
 845    {}
 846
 847    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator(const iterator_from_iiterator& other) BOOST_NOEXCEPT_OR_NOTHROW
 848       :  m_iit(other.get())
 849    {}
 850
 851    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator(const nonconst_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
 852       :  m_iit(other.get())
 853    {}
 854
 855    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator& operator=(const iterator_from_iiterator& other) BOOST_NOEXCEPT_OR_NOTHROW
 856    {  m_iit = other.get(); return *this;  }
 857
 858    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
 859    {  ++this->m_iit;   return *this;  }
 860
 861    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
 862    {
 863       iterator_from_iiterator result (*this);
 864       ++this->m_iit;
 865       return result;
 866    }
 867
 868    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
 869    {
 870       //If the iterator_from_iiterator is not a bidirectional iterator, operator-- should not exist
 871       BOOST_STATIC_ASSERT((is_bidirectional_iterator<iterator_from_iiterator>::value));
 872       --this->m_iit;   return *this;
 873    }
 874
 875    BOOST_CONTAINER_FORCEINLINE iterator_from_iiterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
 876    {
 877       iterator_from_iiterator result (*this);
 878       --this->m_iit;
 879       return result;
 880    }
 881
 882    BOOST_CONTAINER_FORCEINLINE friend bool operator== (const iterator_from_iiterator& l, const iterator_from_iiterator& r) BOOST_NOEXCEPT_OR_NOTHROW
 883    {  return l.m_iit == r.m_iit;   }
 884
 885    BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const iterator_from_iiterator& l, const iterator_from_iiterator& r) BOOST_NOEXCEPT_OR_NOTHROW
 886    {  return !(l == r); }
 887
 888    BOOST_CONTAINER_FORCEINLINE reference operator*()  const BOOST_NOEXCEPT_OR_NOTHROW
 889    {  return this->m_iit->get_data();  }
 890
 891    BOOST_CONTAINER_FORCEINLINE pointer   operator->() const BOOST_NOEXCEPT_OR_NOTHROW
 892    {  return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*());  }
 893
 894    BOOST_CONTAINER_FORCEINLINE const IIterator &get() const BOOST_NOEXCEPT_OR_NOTHROW
 895    {  return this->m_iit;   }
 896
 897    private:
 898    IIterator m_iit;
 899 };
 900
 901 }  //namespace dtl {
 902
 903 using ::boost::intrusive::reverse_iterator;
 904
 905 }  //namespace container {
 906 }  //namespace boost {
 907
 908 #include <boost/container/detail/config_end.hpp>
 909
 910 #endif   //#ifndef BOOST_CONTAINER_DETAIL_ITERATORS_HPP