folly/folly/detail/Iterators.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <cstddef>
#include <iterator>
#include <type_traits>

/*
 * This contains stripped-down workalikes of some Boost classes:
 *
 *   iterator_adaptor
 *   iterator_facade
 *
 * Rationale: the boost headers providing those classes are surprisingly large.
 * The bloat comes from the headers themselves, but more so, their transitive
 * includes.
 *
 * These implementations are simple and minimal.  They may be missing features
 * provided by the Boost classes mentioned above.  Also at this time they only
 * support forward-iterators.  They provide just enough for the few uses within
 * Folly libs; more features will be slapped in here if and when they're needed.
 *
 * These classes may possibly add features as well.  Care is taken not to
 * change functionality where it's expected to be the same (e.g. `dereference`
 * will do the same thing).
 *
 * These are currently only intended for use within Folly, hence their living
 * under detail.  Use outside Folly is not recommended.
 *
 * To see how to use these classes, find the instances where this is used within
 * Folly libs.  Common use cases can also be found in `IteratorsTest.cpp`.
 */

namespace folly {
namespace detail {

/**
 * Currently this only supports forward and bidirectional iteration.  The
 * derived class must must have definitions for these methods:
 *
 *   void increment();
 *   void decrement(); // optional, to be used with bidirectional
 *   reference dereference() const;
 *   bool equal([appropriate iterator type] const& rhs) const;
 *
 * These names are consistent with those used by the Boost iterator
 * facade / adaptor classes to ease migration classes in this file.
 *
 * Template parameters:
 * D: the deriving class (CRTP)
 * V: value type
 * Tag: the iterator category, one of:
 *   std::forward_iterator_tag
 *   std::bidirectional_iterator_tag
 */
template <class D, class V, class Tag>
class IteratorFacade { … };

/**
 * Wrap one iterator while providing an interator interface with e.g. a
 * different value_type.
 *
 * Template parameters:
 * D: the deriving class (CRTP)
 * I: the wrapper iterator type
 * V: value type
 */
template <class D, class I, class V, class Tag>
class IteratorAdaptor : public IteratorFacade<D, V, Tag> { … };

} // namespace detail
} // namespace folly