For fun and profit™, I'm writing a trie class in C++ (using the C++11 standard.) My trie<T> has an iterator, trie<T>::iterator. (They're all actually functionally const_iterators, because you cannot modify a trie's value_type.) The iterator's class declaration looks partially like this: template<typename T> class trie<T>::iterator : public std::iterator<std::bidirectional_iterator_tag, T> { friend class trie<T>; struct state { state(const trie<T>* const node, const typename std::vector<std::pair<typename T::value_type, std::unique_ptr<trie<T>>>>::const_iterator& node_map_it ) : node{node}, node_map_it{node_map_it} {} // This pointer is to const data: const trie<T>* node; typename std::vector<std::pair<typename T::value_type, std::unique_ptr<trie<T>>>>::const_iterator node_map_it; }; public: typedef const T value_type; iterator() =default; iterator(const trie<T>* node) { parents.emplace(node, node->children.cbegin()); // ... } // ... private: std::stack<state> parents; // ... }; Notice that the node pointer is declared const. This is because (in my mind) the iterator should not be modifying the node that it points to; it is just an iterator. Now, elsewhere in my main trie<T> class, I have an erase function that has a common STL signature--it takes an iterator to data to erase (and returns an iterator to the next object). template<typename T> typename trie<T>::iterator trie<T>::erase(const_iterator it) { // ... // Cannot modify a const object! it.parents.top().node->is_leaf = false; // ... } The compiler complains because the node pointer is read-only! The erase function definitely should modify the trie that the iterator points to, even though the iterator shouldn't. So, I have two questions: Should iterator's constructors be public? trie<T> has the necessary begin() and end() members, and of course trie<T>::iterator and trie<T> are mutual friends, but I don't know what the convention is. Making them private would solve a lot of the angst I'm having about removing the const "promise" from the iterator's constructor. What are the correct const semantics/conventions regarding the iterator and its node pointer here? Nobody has ever explained this to me, and I can't find any tutorials or articles on the Web. This is probably the more important question, but it does require a good deal of planning and proper implementation. I suppose it could be circumvented by just implementing 1, but it's the principle of the thing!