c++ - Boost iterator_facade 取消引用

Question

我正在尝试使用 boost 迭代器外观来为存储 data_t 类型元素的排序 vector 的类实现迭代器。目前我在取消引用它时遇到了麻烦。我只需要遍历和搜索的迭代器，迭代器不需要改变Range对象的任何内部状态。

这是 range.hpp:

#include <algorithm>
#include <vector>
#include <sstream>
#include <stdexcept>
#include <functional>

#include <boost/iterator/iterator_facade.hpp>

struct testRangeImpl{
    typedef unsigned int data_t;

    struct RangeOrdering : public std::binary_function< data_t const &, data_t const &, bool >{
        bool operator()(data_t const& a, data_t const& b){
            return a < b;
        }
    };
};


template<
    typename ImplT 
>
class SortedRange: public boost::iterator_facade< 
                    SortedRange< ImplT >,  //this type because of the CRTP
                    typename ImplT::data_t, //The type of the data
                    boost::bidirectional_traversal_tag //iterators can be incremented and decremented
                >{
    public:
        /*! this type */
        typedef SortedRange< ImplT > type;

        /*! The type of the implementation policy */
        typedef ImplT impl_t; 

        /*! The internal representation of an element */
        typedef typename impl_t::data_t data_t;

        /*! The internal representation of a range */
        typedef std::vector< data_t > range_t;

        /*! A member variabe to keep track of if the range has been sorted */
        bool m_sorted;

        /*! The actual range itself in its internal representation */
        range_t m_range;

        /*! The actual range itself in its internal representation */
        size_t m_range_size;

        /*! An exception indicating an invalid range */
        struct InvalidRangeException{};

        /*! Current element for iterator */
        size_t m_current_combo;

        enum class PositionClass {
            NOT_END,
            END,
            REND
        };

        explicit SortedRange( )
            : m_sorted(false), m_range(), m_range_size(0), m_current_combo(0) , m_posclass(PositionClass::END){
        }

        explicit SortedRange(std::vector < data_t > const& rg, size_t const& current_combo, PositionClass const& p )
            : m_sorted(false), m_range(rg), m_range_size(rg.size()), m_current_combo(current_combo) , m_posclass(p){
            if(rg.empty()){
                throw InvalidRangeException();
            }
            std::sort(m_range.begin(),m_range.end(),typename ImplT::RangeOrdering());
            m_sorted = true;
            //initialise();
        }

    protected:
        explicit SortedRange(std::vector < data_t > const& rg)
            : m_sorted(false), m_range(rg), m_range_size(rg.size()), m_current_combo(0) , m_posclass(PositionClass::NOT_END){
            if(rg.empty()){
                throw InvalidRangeException();
            }
            std::sort(m_range.begin(),m_range.end(),typename ImplT::RangeOrdering());
            m_sorted = true;
            //initialise();
        }   

        /*! Implementation policy object */
        impl_t m_impl;

        /*! construct a range with a specific internal state */
        explicit SortedRange(std::vector < data_t > const& rg, size_t const& current_combo)
            : m_sorted(false), m_range(rg), m_range_size(rg.size()), m_current_combo(current_combo) , m_posclass(PositionClass::NOT_END){
            if(rg.empty()){
                throw InvalidRangeException();
            }
            std::sort(m_range.begin(),m_range.end(),typename ImplT::RangeOrdering());
            m_sorted = true;
            //initialise();
        }
    public:

        size_t size(){
            m_range_size = m_range.size();
            return m_range_size;
        }

        /* Return first data */
        type begin() const {
            return type(m_range, 0);
        }

        type end() const {
            return type(m_range, m_current_combo, PositionClass::END);
        }

        type rend() const {
            return type(m_range, m_current_combo, PositionClass::REND);
        }

        /* Return last data */
        type rbegin() const {
            return type(m_range, m_range_size -1 );
        }

    private:
        friend class boost::iterator_core_access;

        /*! Position class */
        PositionClass m_posclass;

        /*! set up the initial state */
        void initialise() {
            std::sort(m_range.begin(),m_range.end());
            m_sorted == true;
        }

        /*! the first element */
        data_t first() const {
            return m_range[0];
        }

        /*! the last element */
        data_t last() const {
            return m_range[m_range_size - 1];
        }


        /*! return the current element */
        const data_t& dereference() const  {
            if(m_posclass == PositionClass::NOT_END) {
                return m_range[m_current_combo];
            }else {
                throw std::out_of_range("Attempt to dereference past the valid range");
            }
        }

        /*! get the next combination */
        void increment() {
            if(m_posclass != PositionClass::NOT_END)
                throw std::out_of_range("Cannot increment past the valid range");

            if(m_current_combo == m_range_size ) {
                //current combination is the last
                m_posclass = PositionClass::END;
            }
            m_current_combo++;
        }

        /*! get the previous combination */
        void decrement() {
            if(m_posclass != PositionClass::NOT_END)
                throw std::out_of_range("Cannot decrement past the valid range");

            if(m_current_combo == 0) {
                //current combination is the first
                m_posclass = PositionClass::REND;
            }
            m_current_combo--;  
        }

        /*! check for equality between two iterators. */
        bool equal(type const& other) const {
           if(m_posclass == PositionClass::NOT_END && 
           other.m_posclass == PositionClass::NOT_END) {

               return 
                   m_current_combo == other.m_current_combo &&
                   m_range == other.m_range;
           }
           else {
                return m_posclass == other.m_posclass && m_range == other.m_range;
           }
        }
};

struct Range : public SortedRange< testRangeImpl>{
    /*! An exception we throw if someone tries to construct an invalid range */
    struct InvalidRangeException : public SortedRange< testRangeImpl >::InvalidRangeException {};

    /*! Construct a range from a vector of unsigned ints */
    explicit Range(std::vector<unsigned int> const& r) : SortedRange<testRangeImpl>(r)
    {
        if(r.empty()){
            throw InvalidRangeException();
        }
    }
};

这是 main.cpp:

#include <vector>
#include <iostream>
#include "range.hpp"
int main(void){
    std::vector<unsigned int> rg  = { 2 , 5 , 1 , 3 , 4 };
    Range test(rg);
    for(auto elem: test){
        std::cout << elem << " " ;
    }
    return 0;
}

编译报错:

/usr/include/boost/iterator/iterator_facade.hpp: In static member function ‘static typename Facade::reference boost::iterator_core_access::dereference(const Facade&) [with Facade = SortedRange<testRangeImpl>, typename Facade::reference = unsigned int&]’:
/usr/include/boost/iterator/iterator_facade.hpp:643:67:   instantiated from ‘boost::iterator_facade<I, V, TC, R, D>::reference boost::iterator_facade<I, V, TC, R, D>::operator*() const [with Derived = SortedRange<testRangeImpl>, Value = unsigned int, CategoryOrTraversal = boost::bidirectional_traversal_tag, Reference = unsigned int&, Difference = long int, boost::iterator_facade<I, V, TC, R, D>::reference = unsigned int&]’
main.cpp:9:17:   instantiated from here
/usr/include/boost/iterator/iterator_facade.hpp:517:32: error: invalid initialisation of reference of type ‘boost::iterator_facade<SortedRange<testRangeImpl>, unsigned int, boost::bidirectional_traversal_tag, unsigned int&, long int>::reference {aka unsigned int&}’ from expression of type ‘const data_t {aka const unsigned int}’

如何使它成为可用的迭代器类型？

Answer 1

您正在尝试获取对常量值的非常量引用。出于某种原因，您决定 dereference 返回一个 const 引用，而不是遵循外观引用类型。解决这个问题，它应该会起作用。