Trans einen Iterator auf einem unordered_map mit Zeigerwert Typ Iterator auf der gleichen Karte mit konst Referenzwert Typ

Question

ich die folgende Klasse haben:

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

Wie Sie sehen können, ich fo ein Benutzer eine Art und Weise wollen dieser Klasse, um über Elemente von _children zu iterieren, ohne sie modifizieren zu können. Deshalb möchte ich einen Iterator erstellen, der auf Elemente vom Typ pair<char, const Node&> anstelle von pair<char, ptr_type> zeigt.

Das Erstellen einer Basis-Iterator-Klasse scheint für die vorliegende Aufgabe etwas zu kompliziert zu sein. Ich habe einen Blick auf Boost-Iterator geworfen, ich denke, transform_iterator ist vielleicht der Weg zu gehen, aber ich habe noch nicht gefunden, wie es funktioniert.

Während ich dabei bin, weiß jemand, wo ich Beispiele für die verschiedenen Beispiele von Iteratoren in boost-iterators definiert finden kann? Es gibt nur ein Beispiel im Dokument für jeden Typ, und sie passen nicht immer zu meinen Bedürfnissen (ich bin neu in dieser Bibliothek, ich habe vielleicht etwas Offensichtliches übersehen).

UPDATE: Hier ist mein Versuch 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; 
}; 

bei Verwendung Es ist leider nicht kompilieren, und gibt den folgenden Fehler:

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

ich denke, das ist der Grund sein könnte boost::indirect_iterator existiert . Die Anpassung eines Beispiels aus der Boost-Dokumentation auf einem (triviale) 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

Wenn die Verwendung von boost-Iterator nicht zwingend notwendig ist, können Sie Ihre eigene Iterator schreiben kann. Ich poste eine, die ForwardIterator erfüllt. Sie können es auf BidirektionalIterator trivial erweitern (es kann jedoch ein bisschen langwierig sein).

Vor dem Posten, ich fürchte, ich konnte Ihre Anforderung nicht erfüllen (abgesehen von der Verwendung von Boost-Iterator); std::pair<char, const Node*> wird anstelle von std::pair<char, const Node&> verwendet, da letzteres das Kopieren verhindert. Vielleicht hat dich das daran gehindert, dein boost::transform_iterator Beispiel zu kompilieren (ich bin mir nicht sicher; ich kenne boost-iterator nicht so gut).

Wie auch immer, hier ist die code.cpp (125 Zeilen lang). main Funktion zum Testen enthalten:

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

Kompilation Befehl:

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

meine Ausgabe:

3 leaf3 
2 leaf2 
1 leaf1 

MyIterator wird als Template-Klasse geschrieben, so dass, wenn Sie std::unordered_map ändern möchten z.B. std::map, brauchen Sie nicht MyIterator zu ändern;)

Was die Dinge kompliziert ist, dass die operator* einen Verweis auf ein std::pair zurückkehren müssen; es bedeutet, dass irgendwo ein (nicht-temporäres) Objekt von std::pair existieren muss, sonst wird diese Referenz zu einer dangling Referenz.Gleiches für die operator-> (ersetzen Sie "Referenz" durch "Zeiger").

Hier ist MyIterator::_p der std::pair, dessen Referenz genommen wird. Dies wird bei Aktualisierungen, die std::pair<char, const Node&> (Paar, das eine Referenz enthält) verbietet, kopiert.

Alternativen zu std::pair<char, const Node&> sind std::pair<char, const Node*> oder std::pair<char, std::reference_wrapper<const Node>>. Ersetzen Sie it->second->name() durch it->second.get().name(), wenn Sie std::reference_wrapper Alternative verwenden möchten.