楽しみと利益のために、C++ で trie クラスを作成しています (C++11 標準を使用)。
私trie<T>にはイテレータがありますtrie<T>::iterator。(トライの を変更することはできないため、これらはすべて実際には機能的 には です。) イテレータのクラス宣言は、部分的に次のようになります。const_iteratorvalue_type
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;
// ...
};
nodeポインターが宣言されていることに注意してくださいconst。これは、(私の考えでは) イテレータがそれが指すノードを変更してはならないためです。それは単なるイテレータです。
ここで、メインtrie<T>クラスの別の場所に、共通の STL シグネチャを持つ消去関数があります。iterator消去するには to データを使用します (iterator次のオブジェクトに to を返します)。
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;
// ...
}
nodeポインターが読み取り専用であるため、コンパイラーは文句を言います! 関数はerase、イテレータが指すトライを変更するべきではありませんが、イテレータが指すトライを変更する必要があります。
だから、私は2つの質問があります：
iteratorのコンストラクターは公開する必要がありますか?trie<T>には必要なbegin()andend()メンバーがいて、もちろんtrie<T>::iteratorandtrie<T>は相互の友人ですが、慣習が何であるかはわかりません。constそれらを非公開にすることで、イテレーターのコンストラクターから「約束」を削除することについて私が抱えている多くの不安が解決されます。constここでのイテレータとそのnodeポインタに関する正しいセマンティクス/規則は何ですか? 誰もこれについて私に説明したことはありませんし、Web 上でチュートリアルや記事を見つけることもできません。これはおそらくより重要な質問ですが、十分な計画と適切な実装が必要です。1を実装するだけで回避できると思いますが、それが原則です！