Дэк на с++ с использованием итераторов

[Команданте Роха]

Господа сообщники, я прошу вашей помощи.
Необходимо реализовать очередь, а затем превратить ее в дэк, использовать при этом итераторы. Есть начальный код, который необходимо дописать. Я не понимаю ни принципов работы с итераторами, ни применения их к дэку, реализовать тоже толком ничего не могу.
Листание форумов и лекций пользы не принесло.
Подскажите, что делать, с чего начинать?

@темы: Вопрос, C++

Comments

[Скептичный циник]

[captain_mode]С чтения статей по итераторам, односвязным и двусвязным спискам?[/captain_mode]
А что конкретно не понятно или не получается?

Если надо самому изобрести двусвязный список, то можно создать объект, в котором будут методы: инициализировать, добавить в начало, добавить в конец, взять с начала, взять с конца, проверить на наличие, разрушить. А по элементам этого списка ходить с помощью итераторов, а не индексированием массивов.
Если я правильно понял задачу, конечно.

[Команданте Роха]

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

[Скептичный циник]

Сначала создай список. Для простоты возьмём односвязный. Тем более, что сделать двусвязный из него феерически просто.
Для этого можно создать некоторый узел Node, а затем цеплять их друг к другу:

#include <iostream>
#define TYPE int
using namespace std;

class Node
{
    public:
        TYPE    data;
        Node*   next;
};

Тогда для создания списка придётся делать вот такое безобразие:

int main(void)
{
    Node* node = new Node;
    node->data = 42;

    node->next = new Node;
    node->next->data = 777;

    node->next->next = new Node;
    node->next->next->data = 100500;

    return 0;
}

Не очень-то удобно. Можно добавить метод void Node::insert(TYPE data);, который будет добавлять элементы сам, а код будет прозрачен и чист. Для удобства можно ещё добавить конструктор Node::Node();, который уберёт кашу из памяти.
Дек это очередь. Очередь – это самостоятельный объект из узлов, которые в ней находятся. Посему создадим класс Queue, который будет иметь методы для работы с односвязным списком, а так же методы для дека.

В конечном итоге, выглядеть они могут приблизительно так:

#include <iostream>
#define TYPE int
using namespace std;

/**
 * Узел очереди
 *
 * @param   data    Данные узла
 * @param   next    Указатель на следующий узел
 */
class Node
{
    public:
        TYPE    data;
        Node*   next;

        Node();
        void insert(TYPE);
};

/**
 * Очередь
 *
 * @param   head    Первый узел
 * @param   tail    Последний узел
 * @param   size    Размер очереди
 */
class Queue
{
    public:
        Node* head;
        Node* tail;
        int   size;

        Queue();
        ~Queue();
        void pushHead(TYPE);
        void pushTail(TYPE);
        void popHead();
        void popTail();
};

Использовать можно примерно так:

int main(void)
{

    Queue deq;
    Node* node;

    deq.pushTail(3);       // [3]
    deq.pushTail(2);       // [3, 2]
    deq.pushTail(1);       // [3, 2, 1]
    deq.pushHead(42);      // [42, 3, 2, 1]
    deq.pushHead(100500);  // [100500, 42, 3, 2, 1]

    // Начнём с начала списка
    node = deq.head;        // 100500

    // Немного побегаем по нему
    node = node->next;      // 42
    node = node->next;      // 3
    cout << node->data << endl;

    return 0;
}

Итераторы нужны для инкапсуляции. Из неё вытекают следующие бонусы:
– при обращении к элементу коллекции совершенно не нужно знать что из себя эта коллекция представляет (массив, вектор, список, дерево, набор и т.д.) – мы всё-равно можем использовать единый интерфейс для работы с ними.
– можно добавить дополнительный функционал, например, метод для проверки все элементы обошли или ещё есть необработанные, или после прохода элемента совершать над ним какие-нибудь действия.
– итераторы позволяют гибко обрабатывать попытки выйти за границы коллекции.

Итератор – отдельный объект. К чему его применять – для кода, который его использует – не важно, реализация работы с коллекцией описана внутри итератора. В самом простом случае, он должен содержать методы для перехода в начало/конец, для доступа к значению и для проверки на пустоту элемента (чтобы знать когда конец):

/**
 * Итератор по очереди
 */
class Iter {
    public:
        Node*   node;
        Queue*  deq;

        Iter(Node*, Queue*);
        void begin();
        void next();
        TYPE get();
        bool empty();
};

Использовать всё вместе с итератором можно примерно вот так:

int main(void)
{
    Queue deq;

    // Добавим немного узлов в нашу очередь и что-нибудь удалим
    deq.pushTail(3);               // [3]
    deq.pushTail(2);               // [3, 2]
    deq.pushTail(1);               // [3, 2, 1]
    deq.pushHead(42);              // [42, 3, 2, 1]
    deq.popTail();                 // [42, 3, 2]
    deq.pushHead(100500);          // [100500, 42, 3, 2]

    // Создадим итератор
    Iter iter(deq.head, &deq);      // 100500

    // Немного побегаем по очереди
    iter.next();                    // 42

    // Вставим что-нибудь
    iter.node->insert(777);         // [100500, 42, 777, 3, 2]

    // Ещё побегаем
    iter.next();                    // 777

    // Попробуем выйти за границы
    iter.next();                    // 3
    cout << iter.get() << endl;
    iter.next();                    // 2
    cout << iter.get() << endl;
    iter.next();                    // Ooops...?
    cout << iter.get() << endl;

    // Выведем всю текущую очередь
    cout << "Enjoy your deq: ";
    for (iter.begin(); !iter.empty(); iter.next()) {
        cout << iter.get() << ", ";
    }
    cout << endl;

    return 0;
}

Ещё было бы хорошо работать с добавлением/удалением элементов, передавая итератор по ссылке, а не напрямую как в примере выше: Queue::Insert(Iter&, TYPE) и Queue:elete(Iter&); ... но мне уже лень писать (:

Общая схема очередей на односвязных списках примерно такова.
Тебе же нужно реализовать все описанные методы классов так, чтобы этот код корректно отработал (:

ps: следует заметить, что это задание, скорее всего, нужно в обучающих целях чтобы было понимание общих алгоритмов работы. На практике свой велосипед лучше не изобретать и использовать std::deque и std::iterator.

[Команданте Роха]

А можно поподробнее, как реализовать, например, сравнение итераторов? Что с чем сравнивают?

[Скептичный циник]

Сравнение какого типа итераторов? Реализовывать это нет необходимости в любом случае:
1. Одного типа можно сравнивать так же, как указатели – если указывают на один и тот же адрес, значит, то, на что они указывают – равно между собой.
2. Разных типов – не нужно сравнивать. Если это стало необходимо, значит, где-то проблема с логикой, а не с итераторами. В стандартах этого тоже нет до c++11 точно (насчёт последнего не уверен, не следил).

Вот общий пример того, как выглядит код обхода любой итерируемой коллекции из STL, если нужно сравнение в условии цикла:

Foo bar; // bar – любая итерируемая коллекция типа Foo из STL
for (FooIter it = bar.begin(), it != it.end(); ++it) {
    cout << *it << endl;
}

Посмотрите на формулировки методов begin(), end() и работу с коллекцией smth – код (в данном случае цикл), работающий с ней, не знает в каком типе хранятся данные и ему это не нужно. В качестве коллекции может быть любой итерируемый тип данных (array, list, stack, queue, deque, set, map, vector и т.д.), а код для его обхода будет один и тот же.

ps: чтобы обойтись без перегрузки операторов и сделать код более читабельным, я в комменте выше использовал next() вместо ++ и get() вместо разыменовывания, но это одно и то же и суть не меняется.