Реализация оператора/итератора инкремента

Я пытаюсь выяснить здесь пару вещей:

  1. Как написать оператор приращения для класса узлов, у которого есть указатель на следующий узел?
  2. Как реализовать итераторы для класса, как показано ниже?

    #include <iostream>
    #include <vector>
    using namespace std;
    
    template <typename T>
    class Node {
    public:
        Node(int i=0):val(i) {}
        Node*& operator++(int i=0) {return next;};
    
        T val;
        Node *next;
    };
    
    //================================================
    int main() {
    
        Node<int> *head, *tmp1, *tmp2;
    
        tmp1 = new Node<int>(0); 
        head = tmp1;
    
        for (int i=1; i<10; ++i) {
    
            tmp2 = new Node<int>(i);
            tmp1->next = tmp2;
            tmp1 = tmp2;
        }
    
        while (head != NULL) {
    
            cout << head->val << " '";
            head = head->operator++(0);    //How do I make it work with ++head;?
        }
    }
    

Это не лучший пример для демонстрации перегрузки операторов или итераторов.


person blueskin    schedule 01.12.2010    source источник
comment
Вы не можете. head - это указатель, а оператор ++ встроен/определен для указателей. Если бы голова была объектом или ссылкой на объект, вы могли бы это сделать.   -  person Martin York    schedule 02.12.2010
comment
Хм, хорошо. Знаете ли вы какие-либо ссылки на реализацию итераторов? Спасибо   -  person blueskin    schedule 02.12.2010
comment
Вы можете посмотреть ответы на этот вопрос: stackoverflow.com/questions/3582608/   -  person Fred Larson    schedule 02.12.2010
comment
@Фред; поскольку вы предложили получить итераторы STL, я смотрел пример на cplusplus.com/reference/ стандартный/итератор/итератор. Итак, если я хочу читать и писать, должен ли я просто использовать random_access_iterator_tag? или посоветуете другие?   -  person blueskin    schedule 02.12.2010
comment
Я бы рекомендовал начать с boost::iterator_facade, что помогает обеспечить некоторую инфраструктуру, которая нужна правильным итераторам. У него даже есть учебник, который идет вместе с ним.   -  person ephemient    schedule 02.12.2010
comment
@blueskin: чтобы быть итератором с произвольным доступом, ваш итератор должен реализовать operator+(int) и operator-(int), а также operator++() и operator--(). Я думаю, что здесь для односвязного списка у вас будет прямой итератор.   -  person Fred Larson    schedule 02.12.2010
comment
@ephemient: хм ... это хорошее место, чтобы начать понимать лучший дизайн итератора, но для моего приложения я рассматриваю просто использование C ++ и STL. Спасибо, эфемиент   -  person blueskin    schedule 02.12.2010
comment
@Fred: именно это я и искал .. Я также смотрел qlist.h, чтобы понять, как они отделяют интерфейс от реализации. Спасибо, Фред.   -  person blueskin    schedule 02.12.2010


Ответы (1)


Вы не реализуете operator++ для класса Node; вы реализуете его для итератора. Класс итератора должен быть отдельным классом.

И, пожалуйста, не портите свой шаблон предположениями (поскольку val — это T, ваш конструктор должен принимать T, а не int). Кроме того, не игнорируйте параметр int оператора ++ вот так: это фиктивный элемент, используемый для отличия реализации до инкремента от реализации после инкремента.

template <typename T>
struct Node {
    T val;
    Node *next;

    Node(const T& t = T()) : val(t) {}
};

template <typename T>
struct node_iter {
    Node<T>* current;
    node_iter(Node<T>* current): current(current) {}

    const node_iter& operator++() { current = current->next; return *this; }
    node_iter operator++(int) {
        node_iter result = *this; ++(*this); return result;
    }
    T& operator*() { return current->val; }
};

int main() {
    // We make an array of nodes, and link them together - no point in
    // dynamic allocation for such a simple example.
    Node<int> nodes[10];
    for (int i = 0; i < 10; ++i) {
        nodes[i] = Node<int>(i);
        nodes[i].next = (i == 9) ? nodes + i + 1 : 0;
    }

    // we supply a pointer to the first element of the array
    node_iter<int> test(nodes);
    // and then iterate:
    while (test.current) {
        cout << *test++ << " ";
    }
    // Exercise: try linking the nodes in reverse order. Therefore, we create 
    // 'test' with a pointer to the last element of the array, rather than 
    // the first. However, we will not need to change the while loop, because
    // of how the operator overload works.

    // Exercise: try writing that last while loop as a for loop. Do not use
    // any information about the number of nodes.
}

До обеспечения надлежащей инкапсуляции данных, управления памятью и т. д. еще очень далеко. Создать правильный класс связанного списка нелегко. Вот почему стандартная библиотека предоставляет один. Не изобретайте велосипед.

person Karl Knechtel    schedule 02.12.2010
comment
Я это понял после публикации. На самом деле я пытался понять, как реализовать итераторы, это плохой пример, который я привел. Я думаю, что QList лучше реализован, чем список STL. Попробую реализовать что-то подобное. Спасибо, Карл. - person blueskin; 02.12.2010
comment
en.literateprograms.org/Singly_linked_list_%28C_Plus_Plus%29 более полезен - person blueskin; 02.12.2010
comment
Почему оператор ++() возвращает константную ссылку, а оператор ++(int) возвращает значение? - person Alexander Duchene; 14.03.2013
comment
@AlexanderDuchene Я точно не знаю, но я думаю, это потому, что при постинкременте вы должны вернуть значение, которое существовало до инкремента, тогда как преинкремент возвращает константную ссылку на итератор, потому что он используется исключительно для продвижения итератор. Обратите внимание, что постинкремент также использует преинкремент для продвижения итератора. - person Dennis; 29.07.2013