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