C++中的const-correctness语义

Question

为了fun and profit™,我正在用C++编写一个trie类(使用C++ 11标准.)

我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>有共同的朋友,但我不知道该约定是什么.将它们设为私有可以解决我const从迭代器的构造函数中删除"promise"时遇到的许多烦恼.
2. const关于迭代器及其node指针的正确语义/约定是什么？ 没有人向我解释这个,我在网上找不到任何教程或文章.这可能是更重要的问题,但它确实需要大量的规划和正确的实施.我想只要实施1就可以规避它,但这是事情的原则!

Answer 1

1) 所有迭代器都必须是可复制构造的。您的迭代器是双向的，因此也需要默认可构造（http://en.cppreference.com/w/cpp/concept/ForwardIterator），尽管我不知道为什么。因此，默认构造函数需要是公共的，但您可以对其进行任何您喜欢的操作const trie<T>*。我认为它应该是私有的，因为此类的目的是为用户提供 trie 上的迭代器，因此它的公共接口应该只是适当类别的迭代器的接口。不需要任何额外的公共构造函数。

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

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