1.. Distributed under the Boost 2.. Software License, Version 1.0. (See accompanying 3.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 4 5+++++++++++++++++++++++++++++ 6 Iterator Facade and Adaptor 7+++++++++++++++++++++++++++++ 8 9:Author: David Abrahams, Jeremy Siek, Thomas Witt 10:Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com 11:organization: `Boost Consulting`_, Indiana University `Open Systems 12 Lab`_, `Zephyr Associates, Inc.`_ 13:date: $Date$ 14 15:Number: This is a revised version of N1530_\ =03-0113, which was 16 accepted for Technical Report 1 by the C++ standard 17 committee's library working group. 18 19.. Version 1.9 of this ReStructuredText document corresponds to 20 n1530_, the paper accepted by the LWG. 21 22.. _n1530: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1530.html 23 24:copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. 25 26.. _`Boost Consulting`: http://www.boost-consulting.com 27.. _`Open Systems Lab`: http://www.osl.iu.edu 28.. _`Zephyr Associates, Inc.`: http://www.styleadvisor.com 29 30:abstract: We propose a set of class templates that help programmers 31 build standard-conforming iterators, both from scratch and 32 by adapting other iterators. 33 34.. contents:: Table of Contents 35 36============ 37 Motivation 38============ 39 40Iterators play an important role in modern C++ programming. The 41iterator is the central abstraction of the algorithms of the Standard 42Library, allowing algorithms to be re-used in in a wide variety of 43contexts. The C++ Standard Library contains a wide variety of useful 44iterators. Every one of the standard containers comes with constant 45and mutable iterators [#mutable]_, and also reverse versions of those 46same iterators which traverse the container in the opposite direction. 47The Standard also supplies ``istream_iterator`` and 48``ostream_iterator`` for reading from and writing to streams, 49``insert_iterator``, ``front_insert_iterator`` and 50``back_insert_iterator`` for inserting elements into containers, and 51``raw_storage_iterator`` for initializing raw memory [7]. 52 53Despite the many iterators supplied by the Standard Library, obvious 54and useful iterators are missing, and creating new iterator types is 55still a common task for C++ programmers. The literature documents 56several of these, for example line_iterator [3] and Constant_iterator 57[9]. The iterator abstraction is so powerful that we expect 58programmers will always need to invent new iterator types. 59 60Although it is easy to create iterators that *almost* conform to the 61standard, the iterator requirements contain subtleties which can make 62creating an iterator which *actually* conforms quite difficult. 63Further, the iterator interface is rich, containing many operators 64that are technically redundant and tedious to implement. To automate 65the repetitive work of constructing iterators, we propose 66``iterator_facade``, an iterator base class template which provides 67the rich interface of standard iterators and delegates its 68implementation to member functions of the derived class. In addition 69to reducing the amount of code necessary to create an iterator, the 70``iterator_facade`` also provides compile-time error detection. 71Iterator implementation mistakes that often go unnoticed are turned 72into compile-time errors because the derived class implementation must 73match the expectations of the ``iterator_facade``. 74 75A common pattern of iterator construction is the adaptation of one 76iterator to form a new one. The functionality of an iterator is 77composed of four orthogonal aspects: traversal, indirection, equality 78comparison and distance measurement. Adapting an old iterator to 79create a new one often saves work because one can reuse one aspect of 80functionality while redefining the other. For example, the Standard 81provides ``reverse_iterator``, which adapts any Bidirectional Iterator 82by inverting its direction of traversal. As with plain iterators, 83iterator adaptors defined outside the Standard have become commonplace 84in the literature: 85 86* Checked iter[13] adds bounds-checking to an existing iterator. 87 88* The iterators of the View Template Library[14], which adapts 89 containers, are themselves adaptors over the underlying iterators. 90 91* Smart iterators [5] adapt an iterator's dereferencing behavior by 92 applying a function object to the object being referenced and 93 returning the result. 94 95* Custom iterators [4], in which a variety of adaptor types are enumerated. 96 97* Compound iterators [1], which access a slice out of a container of containers. 98 99* Several iterator adaptors from the MTL [12]. The MTL contains a 100 strided iterator, where each call to ``operator++()`` moves the 101 iterator ahead by some constant factor, and a scaled iterator, which 102 multiplies the dereferenced value by some constant. 103 104.. [#concept] We use the term concept to mean a set of requirements 105 that a type must satisfy to be used with a particular template 106 parameter. 107 108.. [#mutable] The term mutable iterator refers to iterators over objects that 109 can be changed by assigning to the dereferenced iterator, while 110 constant iterator refers to iterators over objects that cannot be 111 modified. 112 113To fulfill the need for constructing adaptors, we propose the 114``iterator_adaptor`` class template. Instantiations of 115``iterator_adaptor`` serve as a base classes for new iterators, 116providing the default behavior of forwarding all operations to the 117underlying iterator. The user can selectively replace these features 118in the derived iterator class. This proposal also includes a number 119of more specialized adaptors, such as the ``transform_iterator`` that 120applies some user-specified function during the dereference of the 121iterator. 122 123======================== 124 Impact on the Standard 125======================== 126 127This proposal is purely an addition to the C++ standard library. 128However, note that this proposal relies on the proposal for New 129Iterator Concepts. 130 131======== 132 Design 133======== 134 135Iterator Concepts 136================= 137 138This proposal is formulated in terms of the new ``iterator concepts`` 139as proposed in n1550_, since user-defined and especially adapted 140iterators suffer from the well known categorization problems that are 141inherent to the current iterator categories. 142 143.. _n1550: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm 144 145This proposal does not strictly depend on proposal n1550_, as there 146is a direct mapping between new and old categories. This proposal 147could be reformulated using this mapping if n1550_ was not accepted. 148 149Interoperability 150================ 151 152The question of iterator interoperability is poorly addressed in the 153current standard. There are currently two defect reports that are 154concerned with interoperability issues. 155 156Issue 179_ concerns the fact that mutable container iterator types 157are only required to be convertible to the corresponding constant 158iterator types, but objects of these types are not required to 159interoperate in comparison or subtraction expressions. This situation 160is tedious in practice and out of line with the way built in types 161work. This proposal implements the proposed resolution to issue 162179_, as most standard library implementations do nowadays. In other 163words, if an iterator type A has an implicit or user defined 164conversion to an iterator type B, the iterator types are interoperable 165and the usual set of operators are available. 166 167Issue 280_ concerns the current lack of interoperability between 168reverse iterator types. The proposed new reverse_iterator template 169fixes the issues raised in 280. It provides the desired 170interoperability without introducing unwanted overloads. 171 172.. _179: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#179 173.. _280: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#280 174 175 176Iterator Facade 177=============== 178 179.. include:: iterator_facade_body.rst 180 181Iterator Adaptor 182================ 183 184.. include:: iterator_adaptor_body.rst 185 186Specialized Adaptors 187==================== 188 189This proposal also contains several examples of specialized adaptors 190which were easily implemented using ``iterator_adaptor``: 191 192* ``indirect_iterator``, which iterates over iterators, pointers, 193 or smart pointers and applies an extra level of dereferencing. 194 195* A new ``reverse_iterator``, which inverts the direction of a Base 196 iterator's motion, while allowing adapted constant and mutable 197 iterators to interact in the expected ways (unlike those in most 198 implementations of C++98). 199 200* ``transform_iterator``, which applies a user-defined function object 201 to the underlying values when dereferenced. 202 203* ``filter_iterator``, which provides a view of an iterator range in 204 which some elements of the underlying range are skipped. 205 206.. _counting: 207 208* ``counting_iterator``, which adapts any incrementable type 209 (e.g. integers, iterators) so that incrementing/decrementing the 210 adapted iterator and dereferencing it produces successive values of 211 the Base type. 212 213* ``function_output_iterator``, which makes it easier to create custom 214 output iterators. 215 216Based on examples in the Boost library, users have generated many new 217adaptors, among them a permutation adaptor which applies some 218permutation to a random access iterator, and a strided adaptor, which 219adapts a random access iterator by multiplying its unit of motion by a 220constant factor. In addition, the Boost Graph Library (BGL) uses 221iterator adaptors to adapt other graph libraries, such as LEDA [10] 222and Stanford GraphBase [8], to the BGL interface (which requires C++ 223Standard compliant iterators). 224 225=============== 226 Proposed Text 227=============== 228 229 230Header ``<iterator_helper>`` synopsis [lib.iterator.helper.synopsis] 231======================================================================= 232 233 234:: 235 236 struct use_default; 237 238 struct iterator_core_access { /* implementation detail */ }; 239 240 template < 241 class Derived 242 , class Value 243 , class CategoryOrTraversal 244 , class Reference = Value& 245 , class Difference = ptrdiff_t 246 > 247 class iterator_facade; 248 249 template < 250 class Derived 251 , class Base 252 , class Value = use_default 253 , class CategoryOrTraversal = use_default 254 , class Reference = use_default 255 , class Difference = use_default 256 > 257 class iterator_adaptor; 258 259 template < 260 class Iterator 261 , class Value = use_default 262 , class CategoryOrTraversal = use_default 263 , class Reference = use_default 264 , class Difference = use_default 265 > 266 class indirect_iterator; 267 268 template <class Dereferenceable> 269 struct pointee; 270 271 template <class Dereferenceable> 272 struct indirect_reference; 273 274 template <class Iterator> 275 class reverse_iterator; 276 277 template < 278 class UnaryFunction 279 , class Iterator 280 , class Reference = use_default 281 , class Value = use_default 282 > 283 class transform_iterator; 284 285 template <class Predicate, class Iterator> 286 class filter_iterator; 287 288 template < 289 class Incrementable 290 , class CategoryOrTraversal = use_default 291 , class Difference = use_default 292 > 293 class counting_iterator; 294 295 template <class UnaryFunction> 296 class function_output_iterator; 297 298 299 300Iterator facade [lib.iterator.facade] 301===================================== 302 303.. include:: iterator_facade_abstract.rst 304 305Class template ``iterator_facade`` 306---------------------------------- 307 308.. include:: iterator_facade_ref.rst 309 310Iterator adaptor [lib.iterator.adaptor] 311======================================= 312 313.. include:: iterator_adaptor_abstract.rst 314 315Class template ``iterator_adaptor`` 316----------------------------------- 317 318.. include:: iterator_adaptor_ref.rst 319 320 321Specialized adaptors [lib.iterator.special.adaptors] 322==================================================== 323 324 325The ``enable_if_convertible<X,Y>::type`` expression used in 326this section is for exposition purposes. The converting constructors 327for specialized adaptors should be only be in an overload set provided 328that an object of type ``X`` is implicitly convertible to an object of 329type ``Y``. 330The signatures involving ``enable_if_convertible`` should behave 331*as-if* ``enable_if_convertible`` were defined to be:: 332 333 template <bool> enable_if_convertible_impl 334 {}; 335 336 template <> enable_if_convertible_impl<true> 337 { struct type; }; 338 339 template<typename From, typename To> 340 struct enable_if_convertible 341 : enable_if_convertible_impl<is_convertible<From,To>::value> 342 {}; 343 344If an expression other than the default argument is used to supply 345the value of a function parameter whose type is written in terms 346of ``enable_if_convertible``, the program is ill-formed, no 347diagnostic required. 348 349[*Note:* The ``enable_if_convertible`` approach uses SFINAE to 350take the constructor out of the overload set when the types are not 351implicitly convertible. 352] 353 354 355Indirect iterator 356----------------- 357 358.. include:: indirect_iterator_abstract.rst 359 360Class template ``pointee`` 361.................................... 362 363.. include:: pointee_ref.rst 364 365Class template ``indirect_reference`` 366..................................... 367 368.. include:: indirect_reference_ref.rst 369 370Class template ``indirect_iterator`` 371.................................... 372 373.. include:: indirect_iterator_ref.rst 374 375Reverse iterator 376---------------- 377 378.. include:: reverse_iterator_abstract.rst 379 380Class template ``reverse_iterator`` 381................................... 382 383.. include:: reverse_iterator_ref.rst 384 385 386Transform iterator 387------------------ 388 389.. include:: transform_iterator_abstract.rst 390 391Class template ``transform_iterator`` 392..................................... 393 394.. include:: transform_iterator_ref.rst 395 396 397Filter iterator 398--------------- 399 400.. include:: filter_iterator_abstract.rst 401 402 403Class template ``filter_iterator`` 404.................................. 405 406.. include:: filter_iterator_ref.rst 407 408 409Counting iterator 410----------------- 411 412.. include:: counting_iterator_abstract.rst 413 414Class template ``counting_iterator`` 415.................................... 416 417.. include:: counting_iterator_ref.rst 418 419 420Function output iterator 421------------------------ 422 423.. include:: func_output_iter_abstract.rst 424 425Class template ``function_output_iterator`` 426........................................... 427 428.. include:: func_output_iter_ref.rst 429 430 431 432 433.. LocalWords: Abrahams Siek Witt istream ostream iter MTL strided interoperate 434 LocalWords: CRTP metafunctions inlining lvalue JGS incrementable BGL LEDA cv 435 LocalWords: GraphBase struct ptrdiff UnaryFunction const int typename bool pp 436 LocalWords: lhs rhs SFINAE markup iff tmp OtherDerived OtherIterator DWA foo 437 LocalWords: dereferenceable subobject AdaptableUnaryFunction impl pre ifdef'd 438 LocalWords: OtherIncrementable Coplien 439