Iterators for custom datastructure

Question

Getting along with iterators and containers, I stumbled onto a little experiment which I was trying to implement. However, I got stuck pretty early.

The idea was to create a linked list, which contains of two different types of entries, namely out and in items. All the items are linked together, while items of the same kind contain references to each other as well.

Next up, I want to be able to loop the data-structure by means of iterators, in three different ways:

1. Any, in which the entire data-structure is traversed.
2. In, in which solely the in items are traversed.
3. Out, in which solely the out items are traversed.

So when calling for any of the types listed above, only a begin() and end() iterator are passed to the requester.

I've got a set up for the following data structure, I'm able to loop it in the ways mentioned above, though I can't set up the iterators.

template <class T>
struct dual_node {
    /*
     * Constructors
     */
    dual_node(T data): data(data) {};

    /*
     * Operators
     */
    bool operator ==(const dual_node<T> &rhs) const {
        return this->data == rhs.data;
    }

    /*
     * Members
     */
    T data;
    dual_node *type_next = nullptr;
    dual_node *type_prev = nullptr;
};

The wrapping class:

using namespace std;

template <class T>
class DualLinkedList {
public:
    /*
     * Mutators
     */
    template <class Direction>
    void push_front(T element){
        elements.push_front(dual_node<T>(element));
        Direction::template set_ptr<T>(elements.front(), &last_in, &last_out);
    }

    void remove(T element){
        auto it = find(elements.begin(), elements.end(), element);

        // Element found
        if(it != elements.end()){
            // If it has a previous
            if(it->type_prev) {
                it->type_prev->type_next = it->type_next;
            }else{
                // No previous, so last_in or last_out should match.
                if(*last_in == *it){
                    last_in = it->type_next;
                }

                if(*last_out == *it){
                    last_out = it->type_next;
                }
            }

            // Remove from forward_list
            elements.remove(*it);
        }


    }
//private:
    forward_list<dual_node<T>> elements;
    dual_node<T> *last_in;
    dual_node<T> *last_out;
};

Direction classes:

struct in {
        static edge_list& get_list(pair<edge_list, edge_list> &a) {
            return a.first;
        }
        // conceptual
        static pair<iterator, iterator> get_it_pair(dual_node<T>** last_in){
            // Return iterator starting at last_in, following type_next pointers
        }

        template <class T>
        static void set_ptr(dual_node<T> &element, dual_node<T>** last_in, dual_node<T>** last_out){
            // If last incoming exists.
            if(*last_in) {
                (**last_in).type_prev = &element;
            }
            element.type_next = *last_in;
            *last_in = &element;
        }
    };

    struct out {
        static edge_list& get_list(pair<edge_list, edge_list> &a) {
            return a.second;
        }

        // conceptual
        static pair<iterator, iterator> get_it_pair(dual_node<T>** last_out){
            // Return iterator starting at last_out, following type_next ptrs
        }

        template <class T>
        static void set_ptr(dual_node<T> &element, dual_node<T>** last_in, dual_node<T>** last_out) {
            // If last outgoing exists.
            if(*last_out) {
                (**last_out).type_prev = &element;
            }
            element.type_next = *last_out;
            *last_out = &element;
        }
    };

    struct any {
        // conceptual
        static pair<iterator, iterator> get_it_pair(dual_node<T>** last_out){
            // Returning iterator starting at last out following forward_list
        }
    };

Answer 1

I'm not too terribly familiar with iterators, but have you tried browsing through some of these tutorials?

https://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html

How to correctly implement custom iterators and const_iterators?

Creating my own Iterators