Transform итератора на unordered_map с типом значения указателя на итератор на одной карте с Const ссылочного типа значения

Question

У меня есть следующий класс:

#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; 
}; 

Как вы можете видеть, я хочу способ Fo пользователя этого класса для перебора элементов из _children без возможности их изменения. Вот почему я хочу создать итератор, который указывает на элементы типа pair<char, const Node&> вместо pair<char, ptr_type>.

Создание базового класса итератора кажется слишком сложным для задачи. Я взглянул на повышение итератора, я думаю, что transform_iterator может быть путем, но я еще не нашел, как заставить его работать.

В то время как я нахожусь в этом, кто-нибудь знает, где я могу найти примеры различных примеров итераторов, определенных в boost-iterators? В документе есть только один пример для каждого типа, и они не всегда соответствуют моим потребностям (я новичок в этой библиотеке, возможно, я пропустил что-то очевидное).

UPDATE: Вот моя попытка с помощью 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; 

Answer 1

Я думаю, что это может быть причиной boost::indirect_iterator существует , Адаптирование примера из документации на повышающем (тривиальный) map<char, char *>:

#include <iostream> 
#include <map> 
#include <boost/iterator/indirect_iterator.hpp> 


int main() { 
    char characters[] = "abcdefg"; 
    size_t ncharacters = sizeof characters - 1; 
    char *charptr[ncharacters]; 

    for (size_t i = 0; i < ncharacters; ++i) { 
     charptr[i] = &characters[i]; 
    } 

    std::map <char, char *> map1; 
    for (size_t i = 0; i < ncharacters; ++i) { 
     map1[characters[i]] = charptr[i]; /* Trivial, just to demonstrate */ 
    } 

    boost::indirect_iterator<char * const*, char const> const_indirect_first(charptr), 
                 const_indirect_last(charptr + ncharacters); 

    std::copy(const_indirect_first, const_indirect_last, std::ostream_iterator<char>(std::cout, " ")); 
    std::cout << std::endl; 

    return 0; 
} 

Answer 2

Если использование повышающего-итератор не является обязательным, вы можете написать свой собственный итератор. Я отправляю один, который удовлетворяет ForwardIterator. Вы можете развернуть его в BidirectionalIterator тривиально (может быть, бит утомительный, однако).

Прежде чем отправлять его, я боюсь, что не смогу выполнить ваши требования (помимо использования ускорителя-итератора); std::pair<char, const Node*> используется вместо std::pair<char, const Node&>, поскольку последний запрещает копирование. Может быть, это и помешало вам составить ваш пример boost::transform_iterator (я не уверен, я не так хорошо знаком с итератором).

В любом случае, вот код.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; это означает, что там где-то должен существовать объект(), в противном случае ссылка становится оборванной ссылкой.То же самое для operator-> (заменить «ссылка» на «указатель»).

Здесь 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.