使用 unique_ptr 实现的列表的迭代器

Question

我正在创建一个使用 unique_ptr 的数据结构。我现在想在此数据结构上定义不同的迭代器，但是我的数据结构的节点是数据本身的一部分。因此，我希望迭代器 return 实际节点，而不仅仅是其中包含的值。

这是我到目前为止得到的（简化得多的示例）：

#include <algorithm>
#include <iostream>
#include <memory>

using namespace std;

template <typename T> struct node {
  node(T val) : val(val), next(nullptr) {}
  node(T val, unique_ptr<node<T>> &n) : val(val), next(move(n)) {}
  T val;
  unique_ptr<node<T>> next;

  template <bool Const = true> struct iter {
    using reference =
        typename std::conditional<Const, const node<T> *, node<T> *>::type;
    iter() : nptr(nullptr) {}
    iter(node<T> *n) : nptr(n) {}

    reference operator*() { return nptr; }

    iter &operator++() {
      nptr = nptr->next.get();
      return *this;
    }

    friend bool operator==(const iter &lhs, const iter &rhs) {
      return lhs.nptr == rhs.nptr;
    }

    friend bool operator!=(const iter &lhs, const iter &rhs) {
      return lhs.nptr != rhs.nptr;
    }
    node<T> *nptr;
  };

  iter<> begin() const { return iter<>(this); }
  iter<> end() const { return iter<>(); }

  iter<false> begin() { return iter<false>(this); }
  iter<false> end() { return iter<false>(); }
};

template <typename T> void pretty_print(const unique_ptr<node<T>> &l) {
  auto it = l->begin();
  while (it != l->end()) {
    auto elem = *it;
    cout << elem->val << endl;
    ++it;
  }
}

int main() {
  auto a = make_unique<node<int>>(4);
  auto b = make_unique<node<int>>(3, a);
  auto c = make_unique<node<int>>(2, b);
  auto d = make_unique<node<int>>(1, c);

  for (auto *elem : *d) {
    elem->val = elem->val - 1;
  }

  pretty_print(d);

  return 0;
}

以这种方式公开指向数据结构元素的原始指针是否被认为是不好的做法？这在更复杂的示例中是否有效，尤其是在 const-正确性方面？

Answer 1

这主要是个人意见，但我认为这是个坏主意。 unique_ptrs 应该是唯一的；罕见的例外情况应该是，如果您需要将原始指针传递给其他未正确模板化的函数（并且您知道事实上它不会保留指针）。

否则，您处于合理使用的情况，例如使用迭代器初始化为 std::vector<node<int>*>，违反了 unique_ptr 中的假设。通常，您希望 API 的行为可预测，开发人员的头痛有限，而您的提议增加了 "You can iterate it as long as you don't store anything to anything with a lifetime beyond my custom structure's lifetime".

的头痛

更好的选择是：

Return 对您的实际 unique_ptr 的引用（这样人们就可以在不违反唯一性契约的情况下使用它们；如果不应该改变它们，请将它们设为 const );他们必须获得所有权或显式使用 "borrowed" 非托管指针，风险自负以存储结果，但迭代可以正常工作，并且他们不会意外违反唯一性保证
在内部存储 shared_ptrs，并在迭代期间分发新的 shared_ptrs，因此所有权会自动共享，只要保留一个共享指针，生命周期就会延长

重要的是，这两个选项都不允许有人意外 "do the wrong thing"。调用者可以做坏事，但他们必须亲自明确绕过智能指针保护机制才能这样做，这是他们的责任。

当然，第三个选项是：

Return 对指向的值的引用，而不是指针；如果存储值，则应复制构造

用户可能会弄错最后一个（通过长期存储引用，获取它的地址以获得违反唯一性保证的新指针等），但它遵循现有的C++ 约定（正如 Ryan 在评论中指出的那样）适用于像 std::vector 这样的容器，所以这不是一个新问题； C++ 开发人员通常知道不要对从迭代中获取的引用做可怕的事情。 它可以说是最好的选择，因为它很好地映射到标准模式，使开发人员更容易适应现有的心智模型。

Answer 2

我会在你的迭代器中使用引用而不是指针

using reference =
    typename std::conditional<Const, const node<T>&, node<T>&>::type;

因此您的迭代器只需取消引用一次。（不过我会为会员保留指针）。

(public) 接口中的指针引起了对所有权的怀疑。

使用语法为：

for (auto& elem : *d) {
  elem.val = elem.val - 1;
}

或

while (it != l->end()) {
   const auto& elem = *it;
   std::cout << elem.val << std::endl;
   ++it;
}

您的迭代器确实在其相应节点被释放时失效，这是常见的情况。

使用 unique_ptr 实现的列表的迭代器

Iterator for a list implemented using unique_ptr

c++

iterator

unique-ptr

data-structures

c++11