container/detail/iterators.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2013.
0004 // (C) Copyright Gennaro Prota 2003 - 2004.
0005 //
0006 // Distributed under the Boost Software License, Version 1.0.
0007 // (See accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //
0010 // See http://www.boost.org/libs/container for documentation.
0011 //
0012 //////////////////////////////////////////////////////////////////////////////
0013
0014 #ifndef BOOST_CONTAINER_DETAIL_ITERATORS_HPP
0015 #define BOOST_CONTAINER_DETAIL_ITERATORS_HPP
0016
0017 #ifndef BOOST_CONFIG_HPP
0018 #  include <boost/config.hpp>
0019 #endif
0020
0021 #if defined(BOOST_HAS_PRAGMA_ONCE)
0022 #  pragma once
0023 #endif
0024
0025 #include <boost/container/detail/config_begin.hpp>
0026 #include <boost/container/detail/workaround.hpp>
0027 #include <boost/container/allocator_traits.hpp>
0028 #include <boost/container/detail/type_traits.hpp>
0029 #include <boost/container/detail/value_init.hpp>
0030 #include <boost/move/utility_core.hpp>
0031 #include <boost/intrusive/detail/reverse_iterator.hpp>
0032
0033 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0034 #include <boost/move/detail/fwd_macros.hpp>
0035 #else
0036 #include <boost/container/detail/variadic_templates_tools.hpp>
0037 #endif
0038 #include <boost/container/detail/iterator.hpp>
0039
0040 namespace boost {
0041 namespace container {
0042
0043 template <class T>
0044 class constant_iterator
0045   : public ::boost::container::iterator
0046       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
0047 {
0048    typedef  constant_iterator<T> this_type;
0049
0050    public:
0051    inline explicit constant_iterator(const T &ref, std::size_t range_size)
0052       :  m_ptr(&ref), m_num(range_size){}
0053
0054    //Constructors
0055    inline constant_iterator()
0056       :  m_ptr(0), m_num(0){}
0057
0058    inline constant_iterator& operator++()
0059    { increment();   return *this;   }
0060
0061    inline constant_iterator operator++(int)
0062    {
0063       constant_iterator result (*this);
0064       increment();
0065       return result;
0066    }
0067
0068    inline constant_iterator& operator--()
0069    { decrement();   return *this;   }
0070
0071    inline constant_iterator operator--(int)
0072    {
0073       constant_iterator result (*this);
0074       decrement();
0075       return result;
0076    }
0077
0078    inline friend bool operator== (const constant_iterator& i, const constant_iterator& i2)
0079    { return i.equal(i2); }
0080
0081    inline friend bool operator!= (const constant_iterator& i, const constant_iterator& i2)
0082    { return !(i == i2); }
0083
0084    inline friend bool operator< (const constant_iterator& i, const constant_iterator& i2)
0085    { return i.less(i2); }
0086
0087    inline friend bool operator> (const constant_iterator& i, const constant_iterator& i2)
0088    { return i2 < i; }
0089
0090    inline friend bool operator<= (const constant_iterator& i, const constant_iterator& i2)
0091    { return !(i > i2); }
0092
0093    inline friend bool operator>= (const constant_iterator& i, const constant_iterator& i2)
0094    { return !(i < i2); }
0095
0096    inline friend std::ptrdiff_t operator- (const constant_iterator& i, const constant_iterator& i2)
0097    { return i2.distance_to(i); }
0098
0099    //Arithmetic signed
0100    inline constant_iterator& operator+=(std::ptrdiff_t off)
0101    {  this->advance(off); return *this;   }
0102
0103    inline constant_iterator operator+(std::ptrdiff_t off) const
0104    {
0105       constant_iterator other(*this);
0106       other.advance(off);
0107       return other;
0108    }
0109
0110    inline friend constant_iterator operator+(std::ptrdiff_t off, const constant_iterator& right)
0111    {  return right + off; }
0112
0113    inline constant_iterator& operator-=(std::ptrdiff_t off)
0114    {  this->advance(-off); return *this;   }
0115
0116    inline constant_iterator operator-(std::ptrdiff_t off) const
0117    {  return *this + (-off);  }
0118
0119    inline const T& operator[] (std::ptrdiff_t ) const
0120    { return dereference(); }
0121
0122    inline const T& operator*() const
0123    { return dereference(); }
0124
0125    inline const T* operator->() const
0126    { return &(dereference()); }
0127
0128    //Arithmetic unsigned
0129    inline constant_iterator& operator+=(std::size_t off)
0130    {  return *this += std::ptrdiff_t(off);  }
0131
0132    inline constant_iterator operator+(std::size_t off) const
0133    {  return *this + std::ptrdiff_t(off);  }
0134
0135    inline friend constant_iterator operator+(std::size_t off, const constant_iterator& right)
0136    {  return std::ptrdiff_t(off) + right;  }
0137
0138    inline constant_iterator& operator-=(std::size_t off)
0139    {  return *this -= std::ptrdiff_t(off);  }
0140
0141    inline constant_iterator operator-(std::size_t off) const
0142    {  return *this - std::ptrdiff_t(off);  }
0143
0144    inline const T& operator[] (std::size_t off) const
0145    { return (*this)[std::ptrdiff_t(off)]; }
0146
0147    private:
0148    const T *   m_ptr;
0149    std::size_t m_num;
0150
0151    inline void increment()
0152    { --m_num; }
0153
0154    inline void decrement()
0155    { ++m_num; }
0156
0157    inline bool equal(const this_type &other) const
0158    {  return m_num == other.m_num;   }
0159
0160    inline bool less(const this_type &other) const
0161    {  return other.m_num < m_num;   }
0162
0163    inline const T & dereference() const
0164    { return *m_ptr; }
0165
0166    inline void advance(std::ptrdiff_t n)
0167    {  m_num = std::size_t(std::ptrdiff_t(m_num) - n); }
0168
0169    inline std::ptrdiff_t distance_to(const this_type &other)const
0170    {  return std::ptrdiff_t(m_num - other.m_num);   }
0171 };
0172
0173 template <class T>
0174 class value_init_construct_iterator
0175   : public ::boost::container::iterator
0176       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
0177 {
0178    typedef  value_init_construct_iterator<T> this_type;
0179
0180    public:
0181    inline explicit value_init_construct_iterator(std::size_t range_size)
0182       :  m_num(range_size){}
0183
0184    //Constructors
0185    inline value_init_construct_iterator()
0186       :  m_num(0){}
0187
0188    inline value_init_construct_iterator& operator++()
0189    { increment();   return *this;   }
0190
0191    inline value_init_construct_iterator operator++(int)
0192    {
0193       value_init_construct_iterator result (*this);
0194       increment();
0195       return result;
0196    }
0197
0198    inline value_init_construct_iterator& operator--()
0199    { decrement();   return *this;   }
0200
0201    inline value_init_construct_iterator operator--(int)
0202    {
0203       value_init_construct_iterator result (*this);
0204       decrement();
0205       return result;
0206    }
0207
0208    inline friend bool operator== (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0209    { return i.equal(i2); }
0210
0211    inline friend bool operator!= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0212    { return !(i == i2); }
0213
0214    inline friend bool operator< (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0215    { return i.less(i2); }
0216
0217    inline friend bool operator> (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0218    { return i2 < i; }
0219
0220    inline friend bool operator<= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0221    { return !(i > i2); }
0222
0223    inline friend bool operator>= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0224    { return !(i < i2); }
0225
0226    inline friend std::ptrdiff_t operator- (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
0227    { return i2.distance_to(i); }
0228
0229    //Arithmetic
0230    inline value_init_construct_iterator& operator+=(std::ptrdiff_t off)
0231    {  this->advance(off); return *this;   }
0232
0233    inline value_init_construct_iterator operator+(std::ptrdiff_t off) const
0234    {
0235       value_init_construct_iterator other(*this);
0236       other.advance(off);
0237       return other;
0238    }
0239
0240    inline friend value_init_construct_iterator operator+(std::ptrdiff_t off, const value_init_construct_iterator& right)
0241    {  return right + off; }
0242
0243    inline value_init_construct_iterator& operator-=(std::ptrdiff_t off)
0244    {  this->advance(-off); return *this;   }
0245
0246    inline value_init_construct_iterator operator-(std::ptrdiff_t off) const
0247    {  return *this + (-off);  }
0248
0249    //This pseudo-iterator's dereference operations have no sense since value is not
0250    //constructed until ::boost::container::construct_in_place is called.
0251    //So comment them to catch bad uses
0252    //const T& operator*() const;
0253    //const T& operator[](difference_type) const;
0254    //const T* operator->() const;
0255
0256    private:
0257    std::size_t  m_num;
0258
0259    inline void increment()
0260    { --m_num; }
0261
0262    inline void decrement()
0263    { ++m_num; }
0264
0265    inline bool equal(const this_type &other) const
0266    {  return m_num == other.m_num;   }
0267
0268    inline bool less(const this_type &other) const
0269    {  return other.m_num < m_num;   }
0270
0271    inline const T & dereference() const
0272    {
0273       static T dummy;
0274       return dummy;
0275    }
0276
0277    inline void advance(std::ptrdiff_t n)
0278    {  m_num = std::size_t(std::ptrdiff_t(m_num) - n); }
0279
0280    inline std::ptrdiff_t distance_to(const this_type &other)const
0281    {  return std::ptrdiff_t(m_num - other.m_num);   }
0282 };
0283
0284 template <class T>
0285 class default_init_construct_iterator
0286   : public ::boost::container::iterator
0287       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
0288 {
0289    typedef  default_init_construct_iterator<T> this_type;
0290
0291    public:
0292    inline explicit default_init_construct_iterator(std::size_t range_size)
0293       :  m_num(range_size){}
0294
0295    //Constructors
0296    inline default_init_construct_iterator()
0297       :  m_num(0){}
0298
0299    inline default_init_construct_iterator& operator++()
0300    { increment();   return *this;   }
0301
0302    inline default_init_construct_iterator operator++(int)
0303    {
0304       default_init_construct_iterator result (*this);
0305       increment();
0306       return result;
0307    }
0308
0309    inline default_init_construct_iterator& operator--()
0310    { decrement();   return *this;   }
0311
0312    inline default_init_construct_iterator operator--(int)
0313    {
0314       default_init_construct_iterator result (*this);
0315       decrement();
0316       return result;
0317    }
0318
0319    inline friend bool operator== (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0320    { return i.equal(i2); }
0321
0322    inline friend bool operator!= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0323    { return !(i == i2); }
0324
0325    inline friend bool operator< (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0326    { return i.less(i2); }
0327
0328    inline friend bool operator> (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0329    { return i2 < i; }
0330
0331    inline friend bool operator<= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0332    { return !(i > i2); }
0333
0334    inline friend bool operator>= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0335    { return !(i < i2); }
0336
0337    inline friend std::ptrdiff_t operator- (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
0338    { return i2.distance_to(i); }
0339
0340    //Arithmetic
0341    inline default_init_construct_iterator& operator+=(std::ptrdiff_t off)
0342    {  this->advance(off); return *this;   }
0343
0344    inline default_init_construct_iterator operator+(std::ptrdiff_t off) const
0345    {
0346       default_init_construct_iterator other(*this);
0347       other.advance(off);
0348       return other;
0349    }
0350
0351    inline friend default_init_construct_iterator operator+(std::ptrdiff_t off, const default_init_construct_iterator& right)
0352    {  return right + off; }
0353
0354    inline default_init_construct_iterator& operator-=(std::ptrdiff_t off)
0355    {  this->advance(-off); return *this;   }
0356
0357    inline default_init_construct_iterator operator-(std::ptrdiff_t off) const
0358    {  return *this + (-off);  }
0359
0360    //This pseudo-iterator's dereference operations have no sense since value is not
0361    //constructed until ::boost::container::construct_in_place is called.
0362    //So comment them to catch bad uses
0363    //const T& operator*() const;
0364    //const T& operator[](difference_type) const;
0365    //const T* operator->() const;
0366
0367    private:
0368    std::size_t  m_num;
0369
0370    inline void increment()
0371    { --m_num; }
0372
0373    inline void decrement()
0374    { ++m_num; }
0375
0376    inline bool equal(const this_type &other) const
0377    {  return m_num == other.m_num;   }
0378
0379    inline bool less(const this_type &other) const
0380    {  return other.m_num < m_num;   }
0381
0382    inline const T & dereference() const
0383    {
0384       static T dummy;
0385       return dummy;
0386    }
0387
0388    inline void advance(std::ptrdiff_t n)
0389    {  m_num = std::size_t(std::ptrdiff_t(m_num) - n); }
0390
0391    inline std::ptrdiff_t distance_to(const this_type &other) const
0392    {  return std::ptrdiff_t(m_num - other.m_num);   }
0393 };
0394
0395
0396 template <class T>
0397 class repeat_iterator
0398   : public ::boost::container::iterator
0399       <std::random_access_iterator_tag, T, std::ptrdiff_t, T*, T&>
0400 {
0401    typedef repeat_iterator<T> this_type;
0402    public:
0403    inline explicit repeat_iterator(T &ref, std::size_t range_size)
0404       :  m_ptr(&ref), m_num(range_size){}
0405
0406    //Constructors
0407    inline repeat_iterator()
0408       :  m_ptr(0), m_num(0){}
0409
0410    inline this_type& operator++()
0411    { increment();   return *this;   }
0412
0413    inline this_type operator++(int)
0414    {
0415       this_type result (*this);
0416       increment();
0417       return result;
0418    }
0419
0420    inline this_type& operator--()
0421    { increment();   return *this;   }
0422
0423    inline this_type operator--(int)
0424    {
0425       this_type result (*this);
0426       increment();
0427       return result;
0428    }
0429
0430    inline friend bool operator== (const this_type& i, const this_type& i2)
0431    { return i.equal(i2); }
0432
0433    inline friend bool operator!= (const this_type& i, const this_type& i2)
0434    { return !(i == i2); }
0435
0436    inline friend bool operator< (const this_type& i, const this_type& i2)
0437    { return i.less(i2); }
0438
0439    inline friend bool operator> (const this_type& i, const this_type& i2)
0440    { return i2 < i; }
0441
0442    inline friend bool operator<= (const this_type& i, const this_type& i2)
0443    { return !(i > i2); }
0444
0445    inline friend bool operator>= (const this_type& i, const this_type& i2)
0446    { return !(i < i2); }
0447
0448    inline friend std::ptrdiff_t operator- (const this_type& i, const this_type& i2)
0449    { return i2.distance_to(i); }
0450
0451    //Arithmetic
0452    inline this_type& operator+=(std::ptrdiff_t off)
0453    {  this->advance(off); return *this;   }
0454
0455    inline this_type operator+(std::ptrdiff_t off) const
0456    {
0457       this_type other(*this);
0458       other.advance(off);
0459       return other;
0460    }
0461
0462    inline friend this_type operator+(std::ptrdiff_t off, const this_type& right)
0463    {  return right + off; }
0464
0465    inline this_type& operator-=(std::ptrdiff_t off)
0466    {  this->advance(-off); return *this;   }
0467
0468    inline this_type operator-(std::ptrdiff_t off) const
0469    {  return *this + (-off);  }
0470
0471    inline T& operator*() const
0472    { return dereference(); }
0473
0474    inline T& operator[] (std::ptrdiff_t ) const
0475    { return dereference(); }
0476
0477    inline T *operator->() const
0478    { return &(dereference()); }
0479
0480    private:
0481    T *         m_ptr;
0482    std::size_t m_num;
0483
0484    inline void increment()
0485    { --m_num; }
0486
0487    inline void decrement()
0488    { ++m_num; }
0489
0490    inline bool equal(const this_type &other) const
0491    {  return m_num == other.m_num;   }
0492
0493    inline bool less(const this_type &other) const
0494    {  return other.m_num < m_num;   }
0495
0496    inline T & dereference() const
0497    { return *m_ptr; }
0498
0499    inline void advance(std::ptrdiff_t n)
0500    {  m_num = std::size_t(std::ptrdiff_t(m_num - n)); }
0501
0502    inline std::ptrdiff_t distance_to(const this_type &other)const
0503    {  return std::ptrdiff_t(m_num - other.m_num);   }
0504 };
0505
0506 template <class T, class EmplaceFunctor>
0507 class emplace_iterator
0508   : public ::boost::container::iterator
0509       <std::random_access_iterator_tag, T, std::ptrdiff_t, const T*, const T &>
0510 {
0511    typedef emplace_iterator this_type;
0512
0513    public:
0514    typedef std::ptrdiff_t difference_type;
0515    inline explicit emplace_iterator(EmplaceFunctor&e)
0516       :  m_num(1), m_pe(&e){}
0517
0518    inline emplace_iterator()
0519       :  m_num(0), m_pe(0){}
0520
0521    inline this_type& operator++()
0522    { increment();   return *this;   }
0523
0524    inline this_type operator++(int)
0525    {
0526       this_type result (*this);
0527       increment();
0528       return result;
0529    }
0530
0531    inline this_type& operator--()
0532    { decrement();   return *this;   }
0533
0534    inline this_type operator--(int)
0535    {
0536       this_type result (*this);
0537       decrement();
0538       return result;
0539    }
0540
0541    inline friend bool operator== (const this_type& i, const this_type& i2)
0542    { return i.equal(i2); }
0543
0544    inline friend bool operator!= (const this_type& i, const this_type& i2)
0545    { return !(i == i2); }
0546
0547    inline friend bool operator< (const this_type& i, const this_type& i2)
0548    { return i.less(i2); }
0549
0550    inline friend bool operator> (const this_type& i, const this_type& i2)
0551    { return i2 < i; }
0552
0553    inline friend bool operator<= (const this_type& i, const this_type& i2)
0554    { return !(i > i2); }
0555
0556    inline friend bool operator>= (const this_type& i, const this_type& i2)
0557    { return !(i < i2); }
0558
0559    inline friend difference_type operator- (const this_type& i, const this_type& i2)
0560    { return i2.distance_to(i); }
0561
0562    //Arithmetic
0563    inline this_type& operator+=(difference_type off)
0564    {  this->advance(off); return *this;   }
0565
0566    inline this_type operator+(difference_type off) const
0567    {
0568       this_type other(*this);
0569       other.advance(off);
0570       return other;
0571    }
0572
0573    inline friend this_type operator+(difference_type off, const this_type& right)
0574    {  return right + off; }
0575
0576    inline this_type& operator-=(difference_type off)
0577    {  this->advance(-off); return *this;   }
0578
0579    inline this_type operator-(difference_type off) const
0580    {  return *this + (-off);  }
0581
0582    private:
0583    //This pseudo-iterator's dereference operations have no sense since value is not
0584    //constructed until ::boost::container::construct_in_place is called.
0585    //So comment them to catch bad uses
0586    const T& operator*() const;
0587    const T& operator[](difference_type) const;
0588    const T* operator->() const;
0589
0590    public:
0591    template<class Allocator>
0592    inline void construct_in_place(Allocator &a, T* ptr)
0593    {  (*m_pe)(a, ptr);  }
0594
0595    template<class DestIt>
0596    inline void assign_in_place(DestIt dest)
0597    {  (*m_pe)(dest);  }
0598
0599    private:
0600    std::size_t m_num;
0601    EmplaceFunctor *            m_pe;
0602
0603    inline void increment()
0604    { --m_num; }
0605
0606    inline void decrement()
0607    { ++m_num; }
0608
0609    inline bool equal(const this_type &other) const
0610    {  return m_num == other.m_num;   }
0611
0612    inline bool less(const this_type &other) const
0613    {  return other.m_num < m_num;   }
0614
0615    inline const T & dereference() const
0616    {
0617       static T dummy;
0618       return dummy;
0619    }
0620
0621    inline void advance(difference_type n)
0622    {  m_num -= n; }
0623
0624    inline difference_type distance_to(const this_type &other)const
0625    {  return difference_type(m_num - other.m_num);   }
0626 };
0627
0628 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0629
0630 template<class ...Args>
0631 struct emplace_functor
0632 {
0633    typedef typename dtl::build_number_seq<sizeof...(Args)>::type index_tuple_t;
0634
0635    inline emplace_functor(BOOST_FWD_REF(Args)... args)
0636       : args_(args...)
0637    {}
0638
0639    template<class Allocator, class T>
0640    inline void operator()(Allocator &a, T *ptr)
0641    {  emplace_functor::inplace_impl(a, ptr, index_tuple_t());  }
0642
0643    template<class DestIt>
0644    inline void operator()(DestIt dest)
0645    {  emplace_functor::inplace_impl(dest, index_tuple_t());  }
0646
0647    private:
0648    template<class Allocator, class T, std::size_t ...IdxPack>
0649    inline void inplace_impl(Allocator &a, T* ptr, const dtl::index_tuple<IdxPack...>&)
0650    {
0651       allocator_traits<Allocator>::construct
0652          (a, ptr, ::boost::forward<Args>(dtl::get<IdxPack>(args_))...);
0653    }
0654
0655    template<class DestIt, std::size_t ...IdxPack>
0656    inline void inplace_impl(DestIt dest, const dtl::index_tuple<IdxPack...>&)
0657    {
0658       typedef typename boost::container::iterator_traits<DestIt>::value_type value_type;
0659       value_type && tmp= value_type(::boost::forward<Args>(dtl::get<IdxPack>(args_))...);
0660       *dest = ::boost::move(tmp);
0661    }
0662
0663    dtl::tuple<Args&...> args_;
0664 };
0665
0666 template<class ...Args>
0667 struct emplace_functor_type
0668 {
0669    typedef emplace_functor<Args...> type;
0670 };
0671
0672 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0673
0674 //Partial specializations cannot match argument list for primary template, so add an extra argument
0675 template <BOOST_MOVE_CLASSDFLT9, class Dummy = void>
0676 struct emplace_functor_type;
0677
0678 #define BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE(N) \
0679 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0680 struct emplace_functor##N\
0681 {\
0682    inline explicit emplace_functor##N( BOOST_MOVE_UREF##N )\
0683       BOOST_MOVE_COLON##N BOOST_MOVE_FWD_INIT##N{}\
0684    \
0685    template<class Allocator, class T>\
0686    inline void operator()(Allocator &a, T *ptr)\
0687    {  allocator_traits<Allocator>::construct(a, ptr BOOST_MOVE_I##N BOOST_MOVE_MFWD##N);  }\
0688    \
0689    template<class DestIt>\
0690    inline void operator()(DestIt dest)\
0691    {\
0692       typedef typename boost::container::iterator_traits<DestIt>::value_type value_type;\
0693       BOOST_MOVE_IF(N, value_type tmp(BOOST_MOVE_MFWD##N), dtl::value_init<value_type> tmp) ;\
0694       *dest = ::boost::move(const_cast<value_type &>(BOOST_MOVE_IF(N, tmp, tmp.get())));\
0695    }\
0696    \
0697    BOOST_MOVE_MREF##N\
0698 };\
0699 \
0700 template <BOOST_MOVE_CLASS##N>\
0701 struct emplace_functor_type<BOOST_MOVE_TARG##N>\
0702 {\
0703    typedef emplace_functor##N BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N type;\
0704 };\
0705 //
0706
0707 BOOST_MOVE_ITERATE_0TO9(BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE)
0708
0709 #undef BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE
0710
0711 #endif
0712
0713 namespace dtl {
0714
0715 template<class T>
0716 struct has_iterator_category
0717 {
0718    struct two { char _[2]; };
0719
0720    template <typename X>
0721    static char test(int, typename X::iterator_category*);
0722
0723    template <typename X>
0724    static two test(int, ...);
0725
0726    BOOST_STATIC_CONSTEXPR bool value = (1 == sizeof(test<T>(0, 0)));
0727 };
0728
0729
0730 template<class T, bool = has_iterator_category<T>::value >
0731 struct is_input_iterator
0732 {
0733    BOOST_STATIC_CONSTEXPR bool value = is_same<typename T::iterator_category, std::input_iterator_tag>::value;
0734 };
0735
0736 template<class T>
0737 struct is_input_iterator<T, false>
0738 {
0739    BOOST_STATIC_CONSTEXPR bool value = false;
0740 };
0741
0742 template<class T>
0743 struct is_not_input_iterator
0744 {
0745    BOOST_STATIC_CONSTEXPR bool value = !is_input_iterator<T>::value;
0746 };
0747
0748 template<class T, bool = has_iterator_category<T>::value >
0749 struct is_forward_iterator
0750 {
0751    BOOST_STATIC_CONSTEXPR bool value = is_same<typename T::iterator_category, std::forward_iterator_tag>::value;
0752 };
0753
0754 template<class T>
0755 struct is_forward_iterator<T, false>
0756 {
0757    BOOST_STATIC_CONSTEXPR bool value = false;
0758 };
0759
0760 template<class T, bool = has_iterator_category<T>::value >
0761 struct is_bidirectional_iterator
0762 {
0763    BOOST_STATIC_CONSTEXPR bool value = is_same<typename T::iterator_category, std::bidirectional_iterator_tag>::value;
0764 };
0765
0766 template<class T>
0767 struct is_bidirectional_iterator<T, false>
0768 {
0769    BOOST_STATIC_CONSTEXPR bool value = false;
0770 };
0771
0772 template<class IINodeType>
0773 struct iiterator_node_value_type {
0774   typedef typename IINodeType::value_type type;
0775 };
0776
0777 template<class IIterator>
0778 struct iiterator_types
0779 {
0780    typedef typename IIterator::value_type                            it_value_type;
0781    typedef typename iiterator_node_value_type<it_value_type>::type   value_type;
0782    typedef typename boost::container::iterator_traits<IIterator>::pointer         it_pointer;
0783    typedef typename boost::container::iterator_traits<IIterator>::difference_type difference_type;
0784    typedef typename ::boost::intrusive::pointer_traits<it_pointer>::
0785       template rebind_pointer<value_type>::type                      pointer;
0786    typedef typename ::boost::intrusive::pointer_traits<it_pointer>::
0787       template rebind_pointer<const value_type>::type                const_pointer;
0788    typedef typename ::boost::intrusive::
0789       pointer_traits<pointer>::reference                             reference;
0790    typedef typename ::boost::intrusive::
0791       pointer_traits<const_pointer>::reference                       const_reference;
0792    typedef typename IIterator::iterator_category                     iterator_category;
0793 };
0794
0795 template<class IIterator, bool IsConst>
0796 struct iterator_types
0797 {
0798    typedef typename ::boost::container::iterator
0799       < typename iiterator_types<IIterator>::iterator_category
0800       , typename iiterator_types<IIterator>::value_type
0801       , typename iiterator_types<IIterator>::difference_type
0802       , typename iiterator_types<IIterator>::const_pointer
0803       , typename iiterator_types<IIterator>::const_reference> type;
0804 };
0805
0806 template<class IIterator>
0807 struct iterator_types<IIterator, false>
0808 {
0809    typedef typename ::boost::container::iterator
0810       < typename iiterator_types<IIterator>::iterator_category
0811       , typename iiterator_types<IIterator>::value_type
0812       , typename iiterator_types<IIterator>::difference_type
0813       , typename iiterator_types<IIterator>::pointer
0814       , typename iiterator_types<IIterator>::reference> type;
0815 };
0816
0817 template<class IIterator, bool IsConst>
0818 class iterator_from_iiterator
0819 {
0820    typedef typename iterator_types<IIterator, IsConst>::type   types_t;
0821    class nat
0822    {
0823       public:
0824       IIterator get() const
0825       {  return IIterator(); }
0826    };
0827    typedef typename dtl::if_c< IsConst
0828                              , iterator_from_iiterator<IIterator, false>
0829                              , nat>::type                      nonconst_iterator;
0830
0831    public:
0832    typedef typename types_t::pointer             pointer;
0833    typedef typename types_t::reference           reference;
0834    typedef typename types_t::difference_type     difference_type;
0835    typedef typename types_t::iterator_category   iterator_category;
0836    typedef typename types_t::value_type          value_type;
0837
0838    inline iterator_from_iiterator()
0839       : m_iit()
0840    {}
0841
0842    inline explicit iterator_from_iiterator(IIterator iit) BOOST_NOEXCEPT_OR_NOTHROW
0843       : m_iit(iit)
0844    {}
0845
0846    inline iterator_from_iiterator(const iterator_from_iiterator& other) BOOST_NOEXCEPT_OR_NOTHROW
0847       :  m_iit(other.get())
0848    {}
0849
0850    inline iterator_from_iiterator(const nonconst_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
0851       :  m_iit(other.get())
0852    {}
0853
0854    inline iterator_from_iiterator& operator=(const iterator_from_iiterator& other) BOOST_NOEXCEPT_OR_NOTHROW
0855    {  m_iit = other.get(); return *this;  }
0856
0857    inline iterator_from_iiterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
0858    {  ++this->m_iit;   return *this;  }
0859
0860    inline iterator_from_iiterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
0861    {
0862       iterator_from_iiterator result (*this);
0863       ++this->m_iit;
0864       return result;
0865    }
0866
0867    inline iterator_from_iiterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
0868    {
0869       //If the iterator_from_iiterator is not a bidirectional iterator, operator-- should not exist
0870       BOOST_CONTAINER_STATIC_ASSERT((is_bidirectional_iterator<iterator_from_iiterator>::value));
0871       --this->m_iit;   return *this;
0872    }
0873
0874    inline iterator_from_iiterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
0875    {
0876       iterator_from_iiterator result (*this);
0877       --this->m_iit;
0878       return result;
0879    }
0880
0881    inline friend bool operator== (const iterator_from_iiterator& l, const iterator_from_iiterator& r) BOOST_NOEXCEPT_OR_NOTHROW
0882    {  return l.m_iit == r.m_iit;   }
0883
0884    inline friend bool operator!= (const iterator_from_iiterator& l, const iterator_from_iiterator& r) BOOST_NOEXCEPT_OR_NOTHROW
0885    {  return l.m_iit != r.m_iit;   }
0886
0887    inline reference operator*()  const BOOST_NOEXCEPT_OR_NOTHROW
0888    {  return this->m_iit->get_data();  }
0889
0890    inline pointer   operator->() const BOOST_NOEXCEPT_OR_NOTHROW
0891    {  return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*());  }
0892
0893    inline const IIterator &get() const BOOST_NOEXCEPT_OR_NOTHROW
0894    {  return this->m_iit;   }
0895
0896    private:
0897    IIterator m_iit;
0898 };
0899
0900 }  //namespace dtl {
0901
0902 using ::boost::intrusive::reverse_iterator;
0903
0904 }  //namespace container {
0905 }  //namespace boost {
0906
0907 #include <boost/container/detail/config_end.hpp>
0908
0909 #endif   //#ifndef BOOST_CONTAINER_DETAIL_ITERATORS_HPP