11

为了乐趣和利润™，我正在用 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 签名的擦除函数——它需要一个iteratorto 数据来擦除（并返回一个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从迭代器的构造函数中删除“承诺”的许多焦虑。
  2. const关于迭代器及其node指针的正确语义/约定是什么？ 从来没有人向我解释过这一点，我在网上找不到任何教程或文章。这可能是更重要的问题，但它确实需要大量的计划和适当的实施。我想它可以通过实现 1 来规避，但这是事情的原理！
4

3 回答 3

2

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，你可以修改它的任何你喜欢的部分，而迭代器只是给你一个开始修改的位置。

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

于 2013-10-22T20:54:37.467 回答
1

非const方法trie希望修改 aconst_iterator指向的内容（它指向的内容应该在 的this实例中trie）应该const_cast根据需要进行修改。您知道这是一个安全且已定义的强制转换，因为如果有人设法调用了constthis 的非实例trie，那么它trie本身的这个实例就不是const.*

或者，您可以做相反的事情并将非const指针保持在trie内const_iterator，这将需要const_caston 构造。出于同样的原因，这是安全的，如上所述。这些const_iterator方法将只提供const访问权限，因此用户不能改变trie迭代器指向的部分。如果 aconst_iterator需要在非const trie方法中进行突变，那没关系，因为它trie一定不是const一开始就存在的。*

这里 ing安全的前提是，只要不改变该对象const_cast，就可以安全地持有和使用指向对象的非const指针。const并且可以安全地放弃const指向最初未声明为的指针的特性const。

*是的，非const trie方法的调用者可能const_cast以未定义的方式进行了编辑；但在那种情况下，导致未定义行为的负担在他们头上，而不是tries。

于 2013-10-22T21:02:35.877 回答
0
  1. 的构造函数应该iterator是公开的吗？

至少是复制构造函数，是的。看看这张图表，它描述了每种类型的迭代器应该具有的特征：

http://www.cplusplus.com/reference/iterator/

所有迭代器类型都应该是可复制构造、可复制赋值和可破坏的，这意味着它们需要公共复制构造函数。一些迭代器，例如RandomAccessIterator也应该是默认可构造的，因此默认构造函数也应该是公共的。

  1. const关于迭代器及其node指针的正确语义/约定是什么？

如果你想要一个，erase那么你实际上并没有一个const_iterator，你有一个常规的iterator。两者之间的区别在于，如果你有一个const trie对象，那么你只能从中得到一个const_iterator，因为你不能以任何方式修改它。

您可以在 STL 容器中注意到这一点。他们往往同时拥有：

iterator begin();
const_iterator begin() const;

通常发生的是你实现了一个const_iteratorthen：

class iterator : public const_iterator {...};

它实现了一个或两个非常量函数。这可能只erase适合您，因为您operator*将保持不变。

于 2013-10-22T20:49:41.013 回答