11.13. Реализация итератора с шагом
11.13. Реализация итератора с шагом
Проблема
Имеются смежные числовые ряды и требуется обеспечить доступ к каждому n-му элементу.
Решение
В примере 11.24 представлен заголовочный файл, реализующий класс итератора с шагом.
Пример 11.24. stride_iter.hpp
#ifndef STRIDE_ITER_HPP
#define STRIDE_ITER_HPP
#include <iterator>
#include <cassert>
template<class Iter_T>
class stride_iter {
public:
// открытые имена, вводимые typedef
typedef typename std::iterator_traits<Iter_T>::value_type value_type;
typedef typename std::iterator_traits<Iter_T>::reference reference;
typedef typename std::iterator_traits<Iter_T>::difference_type
difference_type;
typedef typename std::iterator_traits<Iter_T>::pointer pointer;
typedef std::random_access_iterator_tag iterator_category;
typedef stride_iter self;
// конструкторы
stride_iter() : m(NULL), step(0) {};
stride_iter(const self& x) : m(x.m), step(x.step) {}
stride_iter(Iter_T x, difference_type n) : m(x), step(n) {}
// операторы
self& operator++() { m += step; return *this; }
self operator++(int) { self tmp = *this; m += step; return tmp; }
self& operator+=(difference_type x) { m += x * step; return *this; }
self& operator--() { m -= step; return *this; }
self operator--(int) { self tmp = *this; m -= step; return trap; }
self& operator--(difference type x) { m -= x + step; return *this; }
reference operator[](difference_type n) { return m[n * step]; }
reference operator*() { return *m; }
// дружественные операторы
friend bool operator==(const self& x, const self& y) {
assert(x.step == y.step);
return x.m == y.m;
}
friend bool operator!=(const self& x, const self& y) {
assert(x.step == y.step);
return x.m != y.m;
}
friend bool operator<(const self& x, const self& y) {
assert(x.step == y.step);
return x.m < y.m;
}
friend difference type operator-(const self& x, const self& y) {
assert(x.step == y.step);
return (x.m - y.m) / x.step;
}
friend self operator+(const self& x, difference_type y) {
assert(x.step == y.step);
return x += y * x.step;
}
friend self operator+(difference_type x, const self& y) {
assert(x.step == y.step);
return y += x * x.step;
}
private:
Iter_T m;
difference_type step;
};
#endif
Пример 11.25 показывает, как можно использовать итератор stride_iter из примера 11.24 для получения доступа к каждому второму элементу последовательности.
Пример 11.25. Применение итератора stride_iter
#include "stride_iter.hpp"
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
int main() {
int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
stride_iter<int*> first(a, 2);
stride_iter<int*> last(a + 8, 2);
copy(first, last, ostream_iterator<int>(cout, " "));
}
Программа примера 11.25 выдает следующий результат.
0
2
4
6
Обсуждение
Итераторы с шагом часто используются при работе с матрицами. Они обеспечивают простой и эффективный способ реализации матриц в виде набора числовых рядов. Представленная в примере 11.24 реализация итератора с шагом выполнена в виде оболочки другого итератора, который передается как параметр шаблона.
Я хотел сделать итератор с шагом совместимым с STL, поэтому пришлось выбрать подходящий тип стандартного итератора и удовлетворить его требования. Представленный в примере 11.24 итератор с шагом сделан по образцу итератора с произвольным доступом.
В примере 11.26 я отдельно привел реализацию итератора с шагом (названную kstride_iter), когда размер шага известен на этапе компиляции. Поскольку размер шага передается как параметр шаблона, компилятор может оптимизировать программный код итератора более эффективно, и размер итератора уменьшается.
Пример 11.26. kstride_iter.hpp
#ifndef KSTRIDE_ITER_HPP
#define KSTRIDE_ITER_HPP
#include <iterator>
template<class Iter_T, int Step_N>
class kstride_iter {
public:
// открытые имена, вводимые typedef
typedef typename std::iterator_traits<Iter_T>::value_type value_type;
typedef typename std::iterator_traits<Iter_T>::reference reference;
typedef typename std::iterator_traits<Iter_T>::difference_type
difference_type;
typedef typename std::iterator_traits<Iter_T>::pointer pointer;
typedef std::random_access_iterator_tag iterator_category;
typedef kstride_iter self;
// конструкторы
kstride_iter() : m(NULL) {} kstride_iter(const self& x) : m(x.m) {}
explicit kstride_iter(Iter_T x) : m(x) {}
// операторы
self& operator++() { m += Step_N; return *this; }
self operator++(int) { self tmp = *this; m += Step_N; return tmp; }
self& operator+=(difference_type x) { m += x * Step_N; return *this; }
self& operator--() { m -= Step_N; return *this; }
self operator--(int) { self tmp = *this; m -= Step_N; return tmp; }
self& operator--(difference_type x) { m -= x * Step_N; return *this; }
reference operator[](difference_type n) { return m[n * Step_N]; }
reference operator*() { return *m; }
// дружественные операторы
friend bool operator==(self x, self y) { return x.m == y.m; }
friend bool operator!=(self x, self y) { return x.m != y.m; }
friend bool operator<(self x, self y) { return x.m < y.m; }
friend difference_type operator-(self x, self y) {
return (x.m - y.m) / Step_N;
}
friend self operator+(self x, difference_type y) { return x += y * Step_N; }
friend self operator+(difference_type x, self y) { return y += x * Step_N; }
private:
Iter_T m;
};
#endif
Пример 11.27 показывает, как можно использовать итератор kstride_iter.
Пример 11.27. Применение итератора kstride_iter
#include "kstride_iter.hpp"
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
int main() {
int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
kstride_iter<int*, 2> first(a);
kstride_iter<int*, 2> last(a + 8);
copy(first, last, ostream_iterator<int>(cout, " "));
}