Roman Podoliaka's Blog

Итераторы для начинающих. Путь С++

written by Roman Podoliaka on

Предисловие

Данный пост предназначен исключительно для начинающих и не преследует цели рассказать всё об итераторах в С++. Так что если вы знаете о чём-нибудь вроде iterator_traits<>, вам не будет интересно. Тем не менее, я надеюсь, что эта информация будет полезна для людей, которые раньше не сталкивались с итераторами.

Практическая задача

Предположим перед нами стоит простая задача – написать функцию, которая находила бы в массиве целых чисел максимальное значение и возвращала его индекс. Вы могли бы сделать это примерно так:

int max_element(int arr[], int len)
{
    int max = 0;

    for (int i = 1; i < len; ++i)
    {
        if (arr[i] > arr[max])
            max = i;
    }

    return max;
}

Функция работает замечательно, но сразу видно её ограничение – она работает только с целыми значениями типа int. Для поиска максимального значения в массива из элементов типа float нам нужно написать такую же функцию, только изменив название типа. Мы знаем, что в таком случае, лучшие друзья С++-программиста – шаблоны (templates).

Универсальный вариант функции для поиска максимального элемента в массиве переменных произвольного типа выглядит так:

template<class T>
int max_element(T arr[], int len)
{
    int max = 0;

    for (int i = 1; i < len; ++i)
    {
        if (arr[i] > arr[max])
            max = i;
    }

    return max;
}

Казалось бы, чего можно ещё желать. Но что если нам будет необходимо искать максимальный элемент не во всём массиве, а в лишь в определённой его части?

Мы знаем, что массивы в С++ представляют собой линейно выделенный участок памяти, в котором по порядку расположены элементы. Более того имя массива является указателем на его первый элемент. Указатели и массивы неразрывно связаны – для доступа к элементам массива можно использовать адресную арифметику.

Интервал элементов для нашей функции можно задавать при помощи двух указателей – указателя на первый нужный элемент (begin) и указателем на элемент, следующий за последним нужным элементом (end). Почему именно полуоткрытый интервал [begin; end)? Потому что это позволит формировать условие выхода из цикла очевидным образом.

Реализация выглядит примерно так:

template<class T>
const T* max_element(const T* begin, const T* end)
{
    const T* max = begin;

    for (++begin; begin != end; ++begin)
    {
        if (*begin > * max)
            max = begin;
    }

    return max;
}

Используя этот вариант функции можно искать индекс максимального элемента во всём массиве, либо в какой-то его части:

int array[] = {1, 2, 3, 4, 5, 6};

int max = max_element(array, array + 6);
int max_of_first3 = max_element(array, array + 3);

А можно ли обобщить ещё больше?

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

Но в связном списке элементы не расположены в памяти по порядку – наша функция поиска индекса максимального элемента не может быть использована с этой структурой данных, хотя алгоритм остался прежним – необходимо последовательно пройти все элементы и сравнить их с сохранённым максимальным.

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

Давайте ещё раз взглянем на нашу функцию:

template<class T>
const T* max_element(const T* begin, const T* end)
{
    const T* max = begin;

    for (++begin; begin != end; ++begin)
    {
        if (*begin > * max)
            max = begin;
    }

    return max;
}

Какие операции для доступа к элементам мы используем?

  1. *разыменование указателя – получения значения, которое хранится по адресу указателя.
  2. !=не равно – сравнение двух указателей на неравенство (для определения конца интервала).
  3. ++инкремент – перемещение указателя на следующий элемент.

Если бы мы могли передать в функцию max_element() вместо обычного указателя какой-нибудь объект, то определив для него данные операции, можно было бы заключить в них логику доступа к элементам связного списка. Это не сложно сделать, используя механизмы перегрузки операторов и шаблонов.

Окончательный вариант функции выглядит так:

template<class Iterator>
Iterator max_element(Iterator begin, Iterator end)
{
    Iterator max = begin;

    for (++begin; begin != end; ++begin)
    {
        if (*begin > * max)
            max = begin;
    }

    return max;
}

Вместо указателя используется новый параметр шаблона - класс Iterator. Так что же такое итератор?

Итератор - это специальный объект, который позволяет получить доступ к элементам структуры данных, не раскрывая её внутренного устройства, используя определённый абстрактный интерфейс.

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

Пример своего итератора

Рассмотрим простейшую реализацию связного списка. Реализация узла списка:

#ifndef __LIST_NODE_H__
#define __LIST_NODE_H__

template<class T>
struct Node
{
    T data;
    Node<T>* next;
};

#endif /* __LIST_NODE_H__ */

Реализация класса списка:

#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__

#include "list_node.h"
#include "list_iterator.h"

template<class T>
class LinkedList
{
public:
    LinkedList();
    ~LinkedList();

    ListIterator<T> begin() const;
    ListIterator<T> end() const;

    void push_front(const T& elem);
    void push_back(const T& elem);

private:
    Node<T>* _head;
    Node<T>* _tail;
};

template<class T>
LinkedList<T>::LinkedList()
    : _head(0), _tail(0)
{ }

template<class T>
LinkedList<T>::~LinkedList()
{
    while (_head)
    {
        Node<T>* next = _head->next;
        delete _head;
        _head = next;
    }
}

template<class T>
void LinkedList<T>::push_front(const T& elem)
{
    if (!_head)
    {
        _head = new Node<T>;
        _head->data = elem;
        _head->next = 0;

        _tail = _head;
    }
    else
    {
        Node<T>* oldfirst = _head;

        _head = new Node<T>;
        _head->data = elem;
        _head->next = oldfirst;
    }
}

template<class T>
void LinkedList<T>::push_back(const T& elem)
{
    if (!_tail)
    {
        _tail = new Node<T>;
        _tail->data = elem;
        _tail->next = 0;

        _head = _tail;
    }
    else
    {
        Node<T>* oldlast = _tail;

        _tail = new Node<T>;
        _tail->data = elem;
        _tail->next = 0;

        oldlast->next = _tail;
    }
}

template<class T>
ListIterator<T> LinkedList<T>::begin() const
{
    return ListIterator<T>(_head);
}

template<class T>
ListIterator<T> LinkedList<T>::end() const
{
    return ListIterator<T>(0);
}

#endif /* __LINKED_LIST_H__ */

Реализован минимальный набор методов:

  • инициализация структуры данных, освобождение памяти - LinkedList(), ~LinkedList()
  • добавление элементов в начало и в конец списка - push_front(), push_back()
  • доступ к элементам списка - методы, возвращающие итераторы на начало и конец (как вы помните, для итераторов конец - это элемент следующий сразу за последним) - begin(), end()

При помощи 2 итераторов можно пройти по всем элементам списка между ними. Реализация итератора для списка:

#ifndef __LIST_ITERATOR_H__
#define __LIST_ITERATOR_H__

template<class T>
class ListIterator
{
public:
    ListIterator(Node<T>* node);

    const Node<T>* node() const;

    ListIterator<T>& operator++();
    const T& operator*() const;
    bool operator!=(const ListIterator<T>& it) const;

private:
    Node<T>* _currentNode;
};

template<class T>
ListIterator<T>::ListIterator(Node<T>* node)
    : _currentNode(node)
{ }

template<class T>
const Node<T>* ListIterator<T>::node() const
{
    return _currentNode;
}

template<class T>
ListIterator<T>& ListIterator<T>::operator++()
{
    _currentNode = _currentNode->next;
    return *this;
}

template<class T>
const T& ListIterator<T>::operator*() const
{
    return _currentNode->data;
}

template<class T>
bool ListIterator<T>::operator!=(const ListIterator<T>& it) const
{
    return _currentNode != it.node();
}

#endif /* __LIST_ITERATOR_H__ */

Итератор инициализируется указателем на узел связного списка. Перегруженные операторы содержат логику перемещения между узлами и получения хранимого значения.

Давайте посмотрим, как можно использовать нашу функцию для поиска максимального элемента как в связном списке так и в обычном массиве:

LinkedList<int> l;
l.push_front(1);
l.push_back(2);
l.push_back(3);
l.push_back(10);
l.push_back(4);
l.push_front(5);

int arr[] = {1, 2, 3, 10, 4, 5};

std::cout << "Max in list: "  << *max_element(l.begin(), l.end()) << " ";
std::cout << "Max in array: " << *max_element(arr, arr + 6) << " ";

Заключение

Это, конечно же, лишь малая часть того, что нужно знать об итераторах. Мы рассмотрели лишь один вид итераторов, так называемые Forward Iterators, которые позволяют получать следующие элементы, двигаясь "прямо" (используется оператор ++). Существуют и другие виды итераторов, например, Bidirectional Iterators, которые также позволяют двигаться в обратном направлении (к операторам ++, !=, * добавляется оператор --), и другие.

В С++ в качестве интерфейса итераторов используется семантика указателей, но это просто условность - мог быть выбран любой другой интерфейс. Однако такая реализация позволяет использовать обычные указатели в качеcтве итераторов.

Итераторы играют очень важную роль в STL - они позволяют отделить алгоритмы от структур данных - являются прослойкой между ними. Таким образом алгоритмы могут быть обобщены для использования над различными структурами данных.

Исходный код примеров доступен на GitHub.