CODEWITHSUNDEEP
c++11forward-list
user3599681
user3599681

Reputation:

before_begin implementation of forward_list

How is the before_begin method implemented in the context of a std::forward_list?

I have tried something like this:

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));
}

What I understood is that the before_begin method shall be used when calling insert_after emplace_after etc. Thus I made the method return an iterator to a new node that points to m_pHead and has a default value for the template type _Tp. However, I am unsure about two things:

1) As I am using templates, how can I get the default value? Is _Tp() a legal expression in order to get the default value for the specific type (with both primitive and user-defined types)?

2) As this method returns an iterator before m_pHead, if I call one of the insert_after overloaded methods with before_begin as the first argument, wouldn't I end up having the data inserted in the list, but without having the m_pHead updated?

My implementation of (one of the four overloads of) insert_after is as follows:

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;
}

Thank you very much for taking your time. :)

EDIT: According to the code in the link from T.C.'s answer, the before_begin should be implemented like this:

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

However, this is how my begin is implemented:

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

I don't really get how the before_begin implementation above should work (either that, or my insert_after is not written correctly).

EDIT 2: From what I understand so far, the before_begin should return the m_pHead and the begin should return m_pHead->m_pNext.. That doesn't really make much sense, as begin should implicitly refer to m_pHead, but it is a workaround I guess.

Upvotes: 0

Views: 1000

Answers (1)

T.C.
T.C.

Reputation: 137310

The basic idea is this:

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
};

The head node is embedded in the forward_list itself, and is just a node_base, which just contains just a pointer to the next node. All other nodes are actually node<T>s, which derive from node_base and stores a value of type T. The iterator stores a node_base *, and casts it to a node<T> * when dereferenced. before_begin() points to head; begin() points to head.next, which is actually the first node to contain a value.

Upvotes: 4

Related Questions