c++ - C++ 中的常量正确性语义

Question

为了乐趣和利润™，我正在用 C++(使用 C++11 标准)编写一个 trie 类。

我的 trie<T>有一个迭代器，trie<T>::iterator . (它们实际上都是功能性 const_iterator s，因为您不能修改 trie 的 value_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到要删除的数据(并将 iterator 返回给下一个对象)。

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函数绝对应该修改迭代器指向的 trie，即使迭代器不应该修改。

所以，我有两个问题:

1. 应该iterator的构造函数是公开的吗？ trie<T>有必要的begin()和 end()成员，当然还有trie<T>::iterator和 trie<T>是共同的 friend ，但我不知道惯例是什么。将它们设为私有(private)可以解决很多我对删除 const 的焦虑。来自迭代器构造函数的“ promise ”。
2. 哪些是正确的const关于迭代器及其 node 的语义/约定pointer here? 从来没有人向我解释过这个，我在网上也找不到任何教程或文章。这可能是更重要的问题，但它确实需要大量的规划和适当的实现。我想它可以通过实现 1 来规避，但这是事情的原则!

Answer 1

1) 所有迭代器都必须是可复制构造的。您的迭代器是双向的，因此也需要默认构造( http://en.cppreference.com/w/cpp/concept/ForwardIterator )，尽管我不知道为什么。所以默认构造函数需要公开，但你可以用 const trie<T>* 做你喜欢的事。一。我认为它应该是私有(private)的，因为此类的目的是为用户提供一个遍历 trie 的迭代器，因此它的公共(public)接口(interface)应该只是适当类别的迭代器的接口(interface)。不需要任何额外的公共(public)构造函数。

2) erase是非常量函数。您可以有效传递给它的唯一迭代器是引用调用该函数的同一个 trie 的迭代器，这意味着(我认为，虽然我不太确定我是否遵循了您的设计)父级的整个层次结构是非常量对象。所以我怀疑这是你可以const_cast<trie<T>*>(it.parents.top().node)的情况之一. iterator 不允许使用它来修改 trie，这就是为什么你希望它保存一个指向常量的指针。但是当你持有一个指向 trie 的非常量指针时，即 this , 你可以随意修改它的任何部分，迭代器只是给你一个开始修改的位置。

您可以在此处绘制一些更通用的 const-safety 原则。 container::erase(const_iterator) 中的一种可能情况功能是const container*你从迭代器得到的等于this .在这种情况下 const_cast肯定是安全和合法的(也是不必要的，因为你可以只使用 this ，但这与它是否常量正确无关)。在您的容器中，它(通常)不等于 this , 它指向几个 trie 之一一起构成分层容器的对象 this是其一部分。好消息是，整个容器在逻辑上是常量的，或者在逻辑上是非常量的，因此 const_cast就好像它们都是一个物体一样安全合法。但是要证明正确性有点困难，因为您必须确保在您的设计中整个分层容器确实如我所假设的那样共享非常量。