If using boost-iterator is optional, you can write your own iterator. I am sending a message that satisfies ForwardIterator . You can deploy it to the BidirectionalIterator trivially (this can be a bit tedious, however).
Before sending it, I am afraid that I will not be able to fulfill your requirements (in addition to using boost-iterator); std::pair<char, const Node*> used instead of std::pair<char, const Node&> , because the latter prohibits copying. Perhaps this prevents you from compiling your boost::transform_iterator example (I'm not sure, I'm not so familiar with the boost iterator).
Anyway, here is code.cpp (125 lines). main for testing included:
#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, eg 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; };
compilation command:
g++ -std=c++11 -g -O2 -Wall code.cpp
my conclusion:
3 leaf3 2 leaf2 1 leaf1
MyIterator written as a template class, so if you want to change std::unordered_map to, for example, std::map , you do not need to change MyIterator ;)
What complicates this is that operator* must return a link to std::pair ; this means that somewhere the < non-temporary ) std::pair object must exist, otherwise the link will become a dangling link. The same goes for operator-> (replace "link" with "pointer").
Here MyIterator::_p is std::pair , the link to which is made. This is assigned to copies during updates that std::pair<char, const Node&> (a pair containing a link) prohibits.
Alternatives to std::pair<char, const Node&> : std::pair<char, const Node*> or std::pair<char, std::reference_wrapper<const Node>> . Replace it->second->name() with it->second.get().name() if you decide to use the alternative std::reference_wrapper .