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!
