before_begin 实施 forward_list

Question

before_begin 方法如何在 std::forward_list 的上下文中实现？

我试过这样的事情：

template <class _Tp>
typename forward_list<_Tp>::iterator forward_list<_Tp>::before_begin() NOEXCEPT {
  return forward_list_iterator<_Tp>(new forward_list_node<_Tp>(_Tp(), m_pHead));
}

template <class _Tp>
typename forward_list<_Tp>::const_iterator forward_list<_Tp>::before_begin() const NOEXCEPT {
  return forward_list_const_iterator<_Tp>(new forward_list_node<_Tp>(_Tp(), m_pHead));
}

我理解的是调用insert_afteremplace_after等时应该使用before_begin方法，所以我把方法return变成了iterator到指向 m_pHead 并具有模板类型 _Tp 的默认值的新节点。但是，我不确定两件事：

1) 我在使用模板时，如何获取默认值？ _Tp() 是为了获取特定类型（原始类型和用户定义类型）的默认值的合法表达式吗？

2) 由于此方法 return 是 m_pHead 之前的 iterator，如果我使用 before_begin 调用 insert_after 重载方法之一第一个参数，我不会最终将数据插入列表，但没有更新 m_pHead 吗？

我对insert_after（的四个重载之一）的实现如下：

template <class _Tp>
void forward_list<_Tp>::insert_after(const_iterator _position, const _Tp& _value) {
  forward_list_node<_Tp>* _node = new forward_list_node<_Tp>(_value, _position.m_pNode->m_pNext);
  _position.m_pNode->m_pNext = _node;
}

非常感谢您抽出宝贵时间。 :)

编辑：根据T.C中link中的代码。的答案，before_begin应该像这样实现：

iterator before_begin() { return iterator(&head); }

但是，我的 begin 是这样实现的：

template <class _Tp>
typename forward_list<_Tp>::iterator forward_list<_Tp>::begin() NOEXCEPT {
  return forward_list_iterator<_Tp>(m_pHead);
}

我真的不明白上面的 before_begin 实现应该如何工作（或者我的 insert_after 写得不正确）。

编辑 2：据我所知，before_begin 应该 return m_pHead 和 begin 应该 return m_pHead->m_pNext.. 这并没有多大意义，因为 begin 应该隐含地引用 m_pHead，但我想这是一种解决方法。

Answer 1

基本思路是这样的：

struct node_base {
    node_base * next;
};

template<class T>
struct node : node_base {
    T value;
};

template<class T>
struct forward_list_iter {
    forward_list_iter(node_base *pn) : pnode(pn) { }
    T& operator*() const { return static_cast<node<T>*>(pnode)->value; }
    forward_list_iter& operator++() { pnode = pnode->next; return *this; }
    // other stuff
    node_base* pnode;
};

template<class T>
struct forward_list {
    node_base head;
    forward_list_iter<T> before_begin() { 
        return forward_list_iter<T>(&head); 
    }
    forward_list_iter<T> begin() { 
        return forward_list_iter<T>(head.next); 
    }
    // other stuff
};

head 节点嵌入在 forward_list 本身中，只是一个 node_base，它只包含一个指向下一个节点的指针。所有其他节点实际上都是 node<T>s，它派生自 node_base 并存储类型 T 的值。迭代器存储 node_base *，并在取消引用时将其转换为 node<T> *。 before_begin() 指向 head； begin()指向head.next，实际上是第一个包含值的节点。

before_begin 实施 forward_list

before_begin implementation of forward_list

c++11

forward-list