5

私は次のクラスを持っています:

#include <unordered_map>
#include <memory>


class Node {
public:
    typedef std::unique_ptr<Node> ptr_type;
    typedef std::unordered_map<char, ptr_type> map_type;

    typedef /**???**/ const_iterator;

    const_iterator begin() const;
    const_iterator end() const;

private:
    map_type _children;
};

ご覧のとおり、このクラスのユーザーが要素_childrenを変更せずに繰り返し処理できる方法が必要です。pair<char, const Node&>の代わりに型の要素を指すイテレータを作成したいのはそのためですpair<char, ptr_type>。

基本イテレータ クラスの作成は、目の前のタスクには少し複雑すぎるようです。transform_iterator私はブーストイテレータを見てきましたが、それが進むべき道かもしれないと思いますが、それを機能させる方法をまだ見つけていません。

で定義されているイテレータのさまざまな例の例をどこで見つけることができるか知っている人はいますboost-iteratorsか? ドキュメントには各タイプの例が 1 つしかなく、常に私のニーズに合うとは限りません (私はこのライブラリを初めて使用するため、明らかな何かを見落としている可能性があります)。

更新：これが私の使用の試みですboost::transform_iterator

class Node {
public:
    typedef std::unique_ptr<Node> ptr_type;
    typedef std::unordered_map<char, ptr_type> map_type;


    struct Transformer {
        std::pair<char, const Node&> operator()(const std::pair<char, ptr_type> &p) const {
            return std::pair<char, const Node&>(p.first, *p.second);
        }
    };

    typedef boost::transform_iterator<Transformer, map_type::const_iterator, std::pair<char, const Node&>&, std::pair<char, const Node&>> const_iterator;

    const_iterator begin() const {
        return boost::make_transform_iterator<Transformer, map_type::const_iterator>(_children.begin(), Transformer());
    }
    const_iterator end() const {
        return boost::make_transform_iterator<Transformer, map_type::const_iterator>(_children.end(), Transformer());
    }

private:
    map_type _children;
};

残念ながらコンパイルされず、次のエラーが発生します。

error: no type named ‘type’ in ‘boost::mpl::eval_if<boost::is_same<boost::iterators::use_default, boost::iterators::use_default>, boost::result_of<const Node::Transformer(const std::pair<const char, std::unique_ptr<Node> >&)>, boost::mpl::identity<boost::iterators::use_default> >::f_ {aka struct boost::result_of<const Node::Transformer(const std::pair<const char, std::unique_ptr<Node> >&)>}’
     typedef typename f_::type type;
4

2 に答える 2

4

ブースト イテレータの使用が必須でない場合は、独自のイテレータを記述できます。ForwardIteratorを満たすものを投稿しています。簡単に BidirectionalIterator に展開できます (ただし、少し面倒かもしれません)。

投稿する前に、残念ながら私はあなたの要件を満たすことができませんでした (boost-iterator の使用は別として)。後者はコピーを禁止するため、std::pair<char, const Node*>代わりに使用されます。std::pair<char, const Node&>たぶん、これがあなたのboost::transform_iterator例をコンパイルできなかった理由です（私はよくわかりません;私はboost-iteratorにあまり慣れていません）。

とにかく、ここに code.cpp (125 行) があります。mainテスト用の機能が含まれています：

#include <unordered_map>
#include <memory>

class Node;

template <class Map>
class MyIterator {
public:
    // iterator member typedefs
    using iterator_category = std::forward_iterator_tag;
    using value_type = std::pair<char, const Node*>;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;

    // typedef for underlying iterator
    using underlying_iterator = typename Map::const_iterator;

    // constructors
    // takes an underlying iterator
    explicit MyIterator(underlying_iterator it) : _it(std::move(it)) {}
    // default constructor; required by ForwardIterator
    MyIterator() = default;

    // dereference; required by InputIterator
    reference operator*() {
        update();
        return _p;
    }

    // dereference; required by InputIterator
    pointer operator->() {
        update();
        return &_p;
    }

    // increment; required by Iterator
    MyIterator<Map>& operator++() {
        ++_it;
        return *this;
    }

    // increment; required by InputIterator
    MyIterator<Map> operator++(int) {
        auto mit = *this;
        ++*this;
        return mit;
    }

    // comparison; required by EqualityComparable
    bool operator==(const MyIterator<Map>& mit) const {
        return _it == mit._it;
    }

    // comparison; required by InputIterator
    bool operator!=(const MyIterator<Map>& mit) const {
        return !(*this == mit);
    }

private:
    // this method must be called at dereference-time but not
    // traverse-time in order to prevent UB at a wrong time.
    void update() {
        _p = value_type{_it->first, &*(_it->second)};
    }

    // the underlying iterator that tracks the map
    underlying_iterator _it;
    // the pair of the desired type. without it, e.g. operator-> doesn't
    // work; it has to return a pointer, and the pointed must not be a
    // temporary object.
    value_type _p;
};

class Node {
public:
    typedef std::unique_ptr<Node> ptr_type;
    typedef std::unordered_map<char, ptr_type> map_type;

    typedef MyIterator<map_type> const_iterator;

    const_iterator begin() const {
        return const_iterator{_children.begin()};
    }
    const_iterator end() const {
        return const_iterator{_children.end()};
    }

private:
    map_type _children;

// additional members for testing purposes.
public:
    Node(std::string name) : _name(std::move(name)) {}
    Node(std::string name, map_type&& children) :
        _children(std::move(children)), _name(std::move(name)) {}
    std::string const& name() const {
        return _name;
    }
private:
    std::string _name;
};

#include <iostream>

// test program; construct a simple tree and print children.
int main() {
    typedef std::unique_ptr<Node> ptr_type;
    typedef std::unordered_map<char, ptr_type> map_type;

    ptr_type leaf1(new Node("leaf1"));
    ptr_type leaf2(new Node("leaf2"));
    ptr_type leaf3(new Node("leaf3"));
    map_type branch;
    branch.emplace('1', std::move(leaf1));
    branch.emplace('2', std::move(leaf2));
    branch.emplace('3', std::move(leaf3));
    Node parent("parent", std::move(branch));

    for (auto it = parent.begin(); it != parent.end(); ++it) {
        std::cout << it->first << ' ' << it->second->name() << '\n';
    }

    return 0;
};

コンパイル コマンド:

g++ -std=c++11 -g -O2 -Wall code.cpp

私の出力：

3 leaf3
2 leaf2
1 leaf1

MyIteratorはテンプレート クラスとして記述されているため、std::unordered_mapたとえば に変更するstd::map場合は、変更する必要はありませんMyIterator;)

複雑なのは、 が;operator*への参照を返さなければならないことです。これは、どこかに (一時的ではない) オブジェクトがstd::pair存在する必要があることを意味します。存在しない場合、その参照はダングリング参照になります。についても同じです(「参照」を「ポインター」に置き換えます)。std::pairoperator->

ここでMyIterator::_pは、std::pairを参照します。これは更新時にコピー割り当てされますが、これはstd::pair<char, const Node&>(参照を含むペア) 禁止されています。

の代替std::pair<char, const Node&>はstd::pair<char, const Node*>またはstd::pair<char, std::reference_wrapper<const Node>>です。代替を使用it->second->name()するit->second.get().name()場合は、に置き換えます。std::reference_wrapper

于 2016-08-19T16:58:52.030 に答える