// ------------------------------------------------------------------------ // // SPDX-License-Identifier: LGPL-2.1-or-later // Copyright (C) 2014 - 2025 by the deal.II authors // // This file is part of the deal.II library. // // Part of the source code is dual licensed under Apache-2.0 WITH // LLVM-exception OR LGPL-2.1-or-later. Detailed license information // governing the source code and code contributions can be found in // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. // // ------------------------------------------------------------------------ #ifndef dealii_iterator_range_h #define dealii_iterator_range_h #include #include #include #include DEAL_II_NAMESPACE_OPEN // Forward declaration #ifndef DOXYGEN template class IteratorOverIterators; #endif /** * A class that is used to denote a collection of iterators that can be * expressed in terms of a range of iterators characterized by a begin and an * end iterator. As is common in C++, these ranges are specified as half open * intervals defined by a begin iterator and a one-past-the-end iterator. * * The purpose of this class is so that classes such as Triangulation and * DoFHandler can return ranges of cell iterators using an object of the * current type from functions such as * Triangulation::cell_iterators() and that such an * object can then be used in a range-based for loop as supported by C++11, * see also * @ref CPP11 "C++11 standard". * * For example, such a loop could look like this if the goal is to set the * user flag on every active cell: * @code * Triangulation triangulation; * ... * for (auto &cell : triangulation.active_cell_iterators()) * cell->set_user_flag(); * @endcode * In other words, the cell objects are iterators, and the range * object returned by Triangulation::active_cell_iterators() and similar * functions are conceptually thought of as collections of iterators. * * Of course, the class may also be used to denote other iterator ranges using * different kinds of iterators into other containers. * * *

Class design: Motivation

* * Informally, the way the C++11 standard describes range-based * for loops works as follows: A range-based for loop of the * form * @code * Container c; * for (auto v : c) * statement; * @endcode * where c is a container or collection, is equivalent to the * following loop: * @code * Container c; * for (auto tmp=c.begin(); tmp!=c.end(); ++tmp) * { * auto v = *tmp; * statement; * } * @endcode * (The precise definition can be found here: * https://en.cppreference.com/w/cpp/language/range-for .) * In other words, the compiler introduces a temporary variable that * iterates over the elements of the container or collection, and the * original variable v that appeared in the range-based for loop * represents the dereferenced state of these iterators -- namely, * the elements of the collection. * * In the context of loops over cells, we typically want to retain the fact * that the loop variable is an iterator, not a value. This is because in * deal.II, we never actually use the dereferenced state of a cell * iterator: conceptually, it would represent a cell, and technically it is * implemented by classes such as CellAccessor and DoFCellAccessor, but these * classes are never used explicitly. Consequently, what we would like is that * a call such as Triangulation::active_cell_iterators() returns an object * that represents a collection of iterators of the kind {begin, * begin+1, ..., end-1}. This is conveniently expressed as the half * open interval [begin,end). The loop variable in the * range-based for loop would then take on each of these iterators in turn. * * *

Class design: Implementation

* * To represent the desired semantics as outlined above, this class stores a * half-open range of iterators [b,e) of the given template type. * Secondly, the class needs to provide begin() and end() functions in such a * way that if you dereference the result of IteratorRange::begin(), * you get the b iterator. Furthermore, you must be able to * increment the object returned by IteratorRange::begin() so that * *(std::next(begin())) == b+1. In other words, * IteratorRange::begin() must return an iterator that when dereferenced returns * an iterator of the template type Iterator: It is an iterator * over iterators in the same sense as if you had a pointer into an array of * pointers. * * This is implemented in the form of the IteratorRange::IteratorOverIterators * class. * * @ingroup CPP11 */ template class IteratorRange { public: /** * Typedef for the iterator type that iterates over other iterators. */ using IteratorOverIterators = dealii::IteratorOverIterators; /** * Typedef for the iterator type represent by this class. */ using iterator = Iterator; /** * Default constructor. Create a range represented by two default * constructed iterators. This range is likely (depending on the type of the * iterators) empty. */ IteratorRange(); /** * Constructor. Constructs a range given the begin and end iterators. * * @param[in] begin An iterator pointing to the first element of the range * @param[in] end An iterator pointing past the last element represented * by this range. */ IteratorRange(const iterator begin, const iterator end); /** * Return the iterator pointing to the first element of this range. */ IteratorOverIterators begin(); /** * Return the iterator pointing to the first element of this range. */ IteratorOverIterators begin() const; /** * Return the iterator pointing to the element past the last element of this * range. */ IteratorOverIterators end() const; /** * Return the iterator pointing to the element past the last element of this * range. */ IteratorOverIterators end(); private: /** * Iterators characterizing the begin and end of the range. */ const IteratorOverIterators it_begin; const IteratorOverIterators it_end; }; /** * A class that implements the semantics of iterators over iterators as * discussed in the design sections of the IteratorRange class. */ template class IteratorOverIterators { public: /** * Typedef the elements of the collection to give them a name that is more * distinct. */ using BaseIterator = Iterator; /** * Constructor. Initialize this iterator-over-iterator in such a way that * it points to the given argument. * * @param iterator An iterator to which this object is supposed to point. */ explicit IteratorOverIterators(const BaseIterator &iterator); /** * Dereferencing operator. * @return The iterator within the collection currently pointed to. */ const BaseIterator & operator*() const; /** * Dereferencing operator. * @return The iterator within the collection currently pointed to. */ const BaseIterator * operator->() const; /** * Prefix increment operator. Move the current iterator to the next * element of the collection and return the new value. */ IteratorOverIterators & operator++(); /** * Postfix increment operator. Move the current iterator to the next * element of the collection, but return the previous value of the * iterator. */ IteratorOverIterators operator++(int); /** * Comparison operator * @param i_o_i Another iterator over iterators. * @return Returns whether the current iterator points to a different * object than the iterator represented by the argument. */ bool operator!=(const IteratorOverIterators &i_o_i) const; /** * Implicit conversion operator. * * @warning When you call this conversion operator (i.e., you convert this * iterator-over-iterators to the iterator we are currently pointing to), * you obtain a `const` reference to this underlying iterator. The only * thing you can really do with this result is dereferencing itself: it * presumably points to something useful, but since you don't know where * the pointed to object lives, you shouldn't increment or decrement the * iterator you get from this operator. As a consequence, the returned * iterator is marked as `const`, as this should prevent you from doing * anything other than dereference it. */ operator const BaseIterator &() const; /** * Mark the class as forward iterator and declare some alias which are * standard for iterators and are used by algorithms to enquire about the * specifics of the iterators they work on. */ using iterator_category = std::forward_iterator_tag; using value_type = Iterator; using difference_type = typename Iterator::difference_type; using pointer = Iterator *; using reference = Iterator &; private: /** * The object this iterator currently points to. */ BaseIterator element_of_iterator_collection; }; /** * Create an object of type IteratorRange given the beginning and * end iterator. */ template IteratorRange make_iterator_range(const BaseIterator &begin, const std_cxx20::type_identity_t &end) { IteratorRange ir(begin, end); return ir; } // ------------------- template member functions template inline IteratorOverIterators::IteratorOverIterators( const BaseIterator &iterator) : element_of_iterator_collection(iterator) {} template inline const typename IteratorOverIterators::BaseIterator & IteratorOverIterators::operator*() const { return element_of_iterator_collection; } template inline const typename IteratorOverIterators::BaseIterator * IteratorOverIterators::operator->() const { return &element_of_iterator_collection; } template inline IteratorOverIterators & IteratorOverIterators::operator++() { ++element_of_iterator_collection; return *this; } template inline IteratorOverIterators IteratorOverIterators::operator++(int) { const IteratorOverIterators old_value = *this; ++element_of_iterator_collection; return *old_value; } template inline bool IteratorOverIterators::operator!=( const IteratorOverIterators &i_o_i) const { return element_of_iterator_collection != i_o_i.element_of_iterator_collection; } template inline IteratorOverIterators::operator const BaseIterator &() const { return element_of_iterator_collection; } template inline IteratorRange::IteratorRange() : it_begin() , it_end() {} template inline IteratorRange::IteratorRange(const iterator b, const iterator e) : it_begin(b) , it_end(e) {} template inline typename IteratorRange::IteratorOverIterators IteratorRange::begin() { return it_begin; } template inline typename IteratorRange::IteratorOverIterators IteratorRange::begin() const { return it_begin; } template inline typename IteratorRange::IteratorOverIterators IteratorRange::end() { return it_end; } template inline typename IteratorRange::IteratorOverIterators IteratorRange::end() const { return it_end; } DEAL_II_NAMESPACE_CLOSE #endif